uspecial.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // uspecial.h
   7 //
   8 // Template specializations for uSTL classes.
   9 //
  10
  11 #ifndef USPECIAL_H_947ADYOU0ARE3YOU2REALLY8ARE44CE0
  12 #define USPECIAL_H_947ADYOU0ARE3YOU2REALLY8ARE44CE0
  13
  14 #include "uvector.h"
  15 #include "ustring.h"
  16 #include "uset.h"
  17 #include "umultiset.h"
  18 #include "ubitset.h"
  19 #include "ulaalgo.h"
  20 #include "uctralgo.h"
  21 #include "ufunction.h"
  22 #include "uctrstrm.h"
  23 #include "sistream.h"
  24 #include <ctype.h>
  25
  26 namespace ustl {
  27
  28 //----------------------------------------------------------------------
  29 // Alogrithm specializations not in use by the library code.
  30 //----------------------------------------------------------------------
  31
  32 template <> inline void swap (cmemlink& a, cmemlink& b)                 { a.swap (b); }
  33 template <> inline void swap (memlink& a, memlink& b)                   { a.swap (b); }
  34 template <> inline void swap (memblock& a, memblock& b)                 { a.swap (b); }
  35 template <> inline void swap (string& a, string& b)                     { a.swap (b); }
  36 #define TEMPLATE_SWAP_PSPEC(type, template_decl)        \
  37 template_decl inline void swap (type& a, type& b) { a.swap (b); }
  38 TEMPLATE_SWAP_PSPEC (TEMPLATE_TYPE1 (vector,T),         TEMPLATE_DECL1 (T))
  39 TEMPLATE_SWAP_PSPEC (TEMPLATE_TYPE1 (set,T),            TEMPLATE_DECL1 (T))
  40 TEMPLATE_SWAP_PSPEC (TEMPLATE_TYPE1 (multiset,T),       TEMPLATE_DECL1 (T))
  41 TEMPLATE_SWAP_PSPEC (TEMPLATE_TYPE2 (tuple,N,T),        TEMPLATE_FULL_DECL2 (size_t,N,typename,T))
  42
  43 //----------------------------------------------------------------------
  44 // Streamable definitions. Not used in the library and require streams.
  45 //----------------------------------------------------------------------
  46
  47 //----{ pair }----------------------------------------------------------
  48
  49 /// \brief Reads pair \p p from stream \p is.
  50 template <typename T1, typename T2>
  51 istream& operator>> (istream& is, pair<T1,T2>& p)
  52 {
  53     is >> p.first;
  54     is.align (alignof(p.second));
  55     is >> p.second;
  56     is.align (alignof(p.first));
  57     return (is);
  58 }
  59
  60 /// Writes pair \p p to stream \p os.
  61 template <typename T1, typename T2>
  62 ostream& operator<< (ostream& os, const pair<T1,T2>& p)
  63 {
  64     os << p.first;
  65     os.align (alignof(p.second));
  66     os << p.second;
  67     os.align (alignof(p.first));
  68     return (os);
  69 }
  70
  71 /// Writes pair \p p to stream \p os.
  72 template <typename T1, typename T2>
  73 ostringstream& operator<< (ostringstream& os, const pair<T1,T2>& p)
  74 {
  75     os << '(' << p.first << ',' << p.second << ')';
  76     return (os);
  77 }
  78
  79 /// Returns the written size of the object.
  80 template <typename T1, typename T2>
  81 struct object_stream_size<pair<T1,T2> > {
  82     inline size_t operator()(const pair<T1,T2>& v) const
  83     {
  84         return (Align (stream_size_of(v.first), alignof(v.second)) +
  85                 Align (stream_size_of(v.second), alignof(v.first)));
  86     }
  87 };
  88
  89 /// \brief Takes a pair and returns pair.first
  90 /// This is an extension, available in uSTL and the SGI STL.
  91 template <typename Pair> struct select1st : public unary_function<Pair,typename Pair::first_type> {
  92     typedef typename Pair::first_type result_type;
  93     inline const result_type&   operator()(const Pair& a) const { return (a.first); }
  94     inline result_type&         operator()(Pair& a) const { return (a.first); }
  95 };
  96
  97 /// \brief Takes a pair and returns pair.second
  98 /// This is an extension, available in uSTL and the SGI STL.
  99 template <typename Pair> struct select2nd : public unary_function<Pair,typename Pair::second_type> {
 100     typedef typename Pair::second_type result_type;
 101     inline const result_type&   operator()(const Pair& a) const { return (a.second); }
 102     inline result_type&         operator()(Pair& a) const { return (a.second); }
 103 };
 104
 105 /// \brief Converts a const_iterator pair into an iterator pair
 106 /// Useful for converting pair ranges returned by equal_range, for instance.
 107 /// This is an extension, available in uSTL.
 108 template <typename Container>
 109 inline pair<typename Container::iterator, typename Container::iterator>
 110 unconst (const pair<typename Container::const_iterator, typename Container::const_iterator>& i, Container&)
 111 {
 112     typedef pair<typename Container::iterator, typename Container::iterator> unconst_pair_t;
 113     return (*noalias_cast<unconst_pair_t*>(&i));
 114 }
 115
 116 //----{ vector }--------------------------------------------------------
 117
 118 template <typename T>
 119 inline size_t alignof (const vector<T>&)
 120 {
 121     typedef typename vector<T>::written_size_type written_size_type;
 122     return (alignof (written_size_type()));
 123 }
 124
 125 //----{ bitset }--------------------------------------------------------
 126
 127 /// Writes bitset \p v into stream \p os.
 128 template <size_t Size>
 129 istringstream& operator>> (istringstream& is, bitset<Size>& v)
 130 {
 131     char c;
 132     for (int i = Size; --i >= 0 && (is >> c).good();)
 133         v.set (i, c == '1');
 134     return (is);
 135 }
 136
 137 //----{ tuple }---------------------------------------------------------
 138
 139 template <size_t N, typename T>
 140 inline istream& operator>> (istream& is, tuple<N,T>& v)
 141     { v.read (is); return (is); }
 142 template <size_t N, typename T>
 143 inline ostream& operator<< (ostream& os, const tuple<N,T>& v)
 144     { v.write (os); return (os); }
 145 template <size_t N, typename T>
 146 inline ostringstream& operator<< (ostringstream& os, const tuple<N,T>& v)
 147     { v.text_write (os); return (os); }
 148
 149 template <size_t N, typename T>
 150 struct numeric_limits<tuple<N,T> > {
 151     typedef numeric_limits<T> value_limits;
 152     static inline tuple<N,T> min (void) { tuple<N,T> v; fill (v, value_limits::min()); return (v); }
 153     static inline tuple<N,T> max (void) { tuple<N,T> v; fill (v, value_limits::max()); return (v); }
 154     static const bool is_signed = value_limits::is_signed;
 155     static const bool is_integer = value_limits::is_integer;
 156     static const bool is_integral = value_limits::is_integral;
 157 };
 158
 159 template <size_t N, typename T>
 160 inline size_t alignof (const tuple<N,T>&) { return (alignof (NullValue<T>())); }
 161
 162 template <typename T, typename IntT>
 163 inline ostringstream& chartype_text_write (ostringstream& os, const T& v)
 164 {
 165     os.format (_FmtPrtChr[!isprint(v)], v);
 166     return (os);
 167 }
 168
 169 template <>
 170 inline ostringstream& container_element_text_write (ostringstream& os, const uint8_t& v)
 171 { return (chartype_text_write<uint8_t, unsigned int> (os, v)); }
 172 template <>
 173 inline ostringstream& container_element_text_write (ostringstream& os, const int8_t& v)
 174 { return (chartype_text_write<int8_t, int> (os, v)); }
 175
 176 //----{ matrix }--------------------------------------------------------
 177
 178 /// Writes tuple \p v into stream \p os.
 179 template <size_t NX, size_t NY, typename T>
 180 ostringstream& operator<< (ostringstream& os, const matrix<NX,NY,T>& v)
 181 {
 182     os << '(';
 183     for (uoff_t row = 0; row < NY; ++ row) {
 184         os << '(';
 185         for (uoff_t column = 0; column < NX; ++column)
 186             os << v[row][column] << ",)"[column == NX-1];
 187     }
 188     os << ')';
 189     return (os);
 190 }
 191
 192 //----{ long4grain }----------------------------------------------------
 193
 194 #if SIZE_OF_LONG == 8 && HAVE_INT64_T
 195 // Helper class for long4grain and ptr4grain wrappers.
 196 class _long4grain {
 197 public:
 198     inline      _long4grain (uint64_t v)        : m_v (v) {}
 199 #if __x86_64__
 200     inline void read (istream& is)
 201     {
 202         assert (is.aligned(4));
 203         #ifdef WANT_STREAM_BOUNDS_CHECKING
 204             is.verify_remaining ("read", "long4grain", sizeof(m_v));
 205         #else
 206             assert (is.remaining() >= sizeof(m_v));
 207         #endif
 208         m_v = *reinterpret_cast<const uint64_t*>(is.ipos());
 209         is.skip (sizeof(m_v));
 210     }
 211     inline void write (ostream& os) const
 212     {
 213         assert (os.aligned(4));
 214         #ifdef WANT_STREAM_BOUNDS_CHECKING
 215             os.verify_remaining ("write", "long4grain", sizeof(m_v));
 216         #else
 217             assert (os.remaining() >= sizeof(m_v));
 218         #endif
 219         *reinterpret_cast<uint64_t*>(os.ipos()) = m_v;
 220         os.skip (sizeof(m_v));
 221     }
 222 #elif USTL_BYTE_ORDER == USTL_BIG_ENDIAN
 223     inline void read (istream& is)              { uint32_t vl, vh; is >> vh >> vl; m_v = (uint64_t(vh) << 32) | uint64_t(vl); }
 224     inline void write (ostream& os) const       { os << uint32_t(m_v >> 32) << uint32_t(m_v); }
 225 #else
 226     inline void read (istream& is)              { uint32_t vl, vh; is >> vl >> vh; m_v = (uint64_t(vh) << 32) | uint64_t(vl); }
 227     inline void write (ostream& os) const       { os << uint32_t(m_v) << uint32_t(m_v >> 32); }
 228 #endif
 229     inline size_t stream_size (void) const      { return (stream_size_of(m_v)); }
 230 private:
 231     uint64_t    m_v;
 232 };
 233
 234 /// Wrap long values to allow writing them on 4-grain even on 64bit platforms.
 235 inline _long4grain& long4grain (unsigned long& v)               { asm("":"+m"(v)); return (*noalias_cast<_long4grain*>(&v)); }
 236 /// Wrap long values to allow writing them on 4-grain even on 64bit platforms.
 237 inline const _long4grain long4grain (const unsigned long& v)    { return (_long4grain(v)); }
 238 /// Wrap pointer values to allow writing them on 4-grain even on 64bit platforms.
 239 template <typename T>
 240 inline _long4grain& ptr4grain (T*& p)                           { asm("":"+m"(p)); return (*noalias_cast<_long4grain*>(&p)); }
 241 /// Wrap pointer values to allow writing them on 4-grain even on 64bit platforms.
 242 template <typename T>
 243 inline const _long4grain ptr4grain (const T* const& p)          { return (_long4grain(uintptr_t(p))); }
 244 #else   // if not SIZE_OF_LONG == 8 && HAVE_INT64_T
 245 inline unsigned long& long4grain (unsigned long& v)             { return (v); }
 246 inline const unsigned long& long4grain (const unsigned long& v) { return (v); }
 247 template <typename T> inline T*& ptr4grain (T*& p)              { return (p); }
 248 template <typename T> inline const T* const& ptr4grain (const T* const& p) { return (p); }
 249 #endif  // SIZE_OF_LONG == 8
 250
 251 //----------------------------------------------------------------------
 252
 253 #ifndef DOXYGEN_SHOULD_SKIP_THIS
 254 #ifndef WITHOUT_LIBSTDCPP
 255
 256 /// \todo Need a better solution to getting the hash value.
 257 inline hashvalue_t hash_value (const string::const_pointer& v)
 258 {
 259     string::const_pointer first (v), last (v + strlen(v));
 260     hashvalue_t h = 0;
 261     // This has the bits flowing into each other from both sides of the number
 262     for (; first < last; ++ first)
 263         h = *first + ((h << 7) | (h >> BitsInType(hashvalue_t) - 7));
 264     return (h);
 265 }
 266
 267 #endif
 268 #endif
 269
 270 //----------------------------------------------------------------------
 271
 272 } // namespace ustl
 273
 274 // This is here because there really is no other place to put it.
 275 #if SIZE_OF_BOOL != SIZE_OF_CHAR
 276 // bool is a big type on some machines (like DEC Alpha), so it's written as a byte.
 277 ALIGNOF(bool, sizeof(uint8_t))
 278 CAST_STREAMABLE(bool, uint8_t)
 279 #endif
 280 #if SIZE_OF_LONG == 8 && HAVE_INT64_T
 281 ALIGNOF (_long4grain, 4)
 282 #endif
 283
 284 #endif
 285