STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
uint_types.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/common/uint_types.h
3  *
4  * Class representing a 40-bit or 48-bit unsigned integer encoded in five or
5  * six bytes.
6  *
7  * Part of the STXXL. See http://stxxl.sourceforge.net
8  *
9  * Copyright (C) 2013 Timo Bingmann <[email protected]>
10  *
11  * Distributed under the Boost Software License, Version 1.0.
12  * (See accompanying file LICENSE_1_0.txt or copy at
13  * http://www.boost.org/LICENSE_1_0.txt)
14  **************************************************************************/
15 
16 #ifndef STXXL_COMMON_UINT_TYPES_HEADER
17 #define STXXL_COMMON_UINT_TYPES_HEADER
18 
19 #include <stxxl/bits/config.h>
20 #include <stxxl/bits/namespace.h>
23 
24 #include <limits>
25 #include <ostream>
26 #include <cassert>
27 
29 
30 /*!
31  * Construct an 40-bit or 48-bit unsigned integer stored in five or six bytes.
32  *
33  * The purpose of this class is to provide integers with smaller data storage
34  * footprints when more than 32-bit, but less than 64-bit indexes are
35  * needed. This is commonly the case for storing file offsets and indexes. Here
36  * smaller types currently suffice for files < 1 TiB or < 16 TiB.
37  *
38  * The class combines a 32-bit integer with a HighType (either 8-bit or 16-bit)
39  * to get a larger type. Only unsigned values are supported, which fits the
40  * general application of file offsets.
41  *
42  * Calculation in uint_pair are generally done by transforming everything to
43  * 64-bit data type, so that 64-bit register arithmetic can be used. The
44  * exception here is \b increment and \b decrement, which is done directly on
45  * the lower/higher part. Not all arithmetic operations are supported, patches
46  * welcome if you really need the operations.
47  */
48 #if STXXL_MSVC
49 #pragma pack(push, 1)
50 #endif
51 template <typename HighType>
52 class uint_pair
53 {
54 public:
55  //! lower part type, always 32-bit
56  typedef uint32 low_type;
57  //! higher part type, currently either 8-bit or 16-bit
58  typedef HighType high_type;
59 
60 private:
61  //! member containing lower significant integer value
63  //! member containing higher significant integer value
65 
66  //! return highest value storable in lower part, also used as a mask.
68  {
70  }
71 
72  //! number of bits in the lower integer part, used a bit shift value.
73  static const size_t low_bits = 8 * sizeof(low_type);
74 
75  //! return highest value storable in higher part, also used as a mask.
77  {
79  }
80 
81  //! number of bits in the higher integer part, used a bit shift value.
82  static const size_t high_bits = 8 * sizeof(high_type);
83 
84 public:
85  //! number of binary digits (bits) in uint_pair
86  static const size_t digits = low_bits + high_bits;
87 
88  //! number of bytes in uint_pair
89  static const size_t bytes = sizeof(low_type) + sizeof(high_type);
90 
91  //! empty constructor, does not even initialize to zero!
92  inline uint_pair()
93  {
94  // compile-time assertions about size of low_type
95  STXXL_STATIC_ASSERT(8 * sizeof(low_type) == 32);
96  // compile-time assertions about size of our data structure, this tests
97  // packing of structures by the compiler
101  }
102 
103  //! construct unit pair from lower and higher parts.
104  inline uint_pair(const low_type& l, const high_type& h)
105  : low(l), high(h)
106  { }
107 
108  //! copy constructor
109  inline uint_pair(const uint_pair& a)
110  : low(a.low), high(a.high)
111  { }
112 
113  //! const from a simple 32-bit unsigned integer
114  inline uint_pair(const uint32& a)
115  : low(a), high(0)
116  { }
117 
118  //! const from a simple 32-bit signed integer
119  inline uint_pair(const int32& a)
120  : low(a), high(0)
121  {
122  if (a >= 0)
123  low = a;
124  else
125  low = a, high = (high_type)high_max();
126  }
127 
128  //! construct from an uint64 (unsigned long long)
129  inline uint_pair(const uint64& a)
130  : low((low_type)(a & low_max())),
131  high((high_type)((a >> low_bits) & high_max()))
132  {
133  // check for overflow
134  assert((a >> (low_bits + high_bits)) == 0);
135  }
137  //! return the number as an uint64 (unsigned long long)
138  inline uint64 ull() const
139  {
140  return ((uint64)high) << low_bits | (uint64)low;
141  }
142 
143  //! implicit cast to an unsigned long long
144  inline operator uint64 () const
145  {
146  return ull();
147  }
148 
149  //! return the number as a uint64
150  inline uint64 u64() const
151  {
152  return ((uint64)high) << low_bits | (uint64)low;
153  }
154 
155  //! prefix increment operator (directly manipulates the integer parts)
157  {
158  if (UNLIKELY(low == low_max()))
159  ++high, low = 0;
160  else
161  ++low;
162  return *this;
163  }
164 
165  //! prefix decrement operator (directly manipulates the integer parts)
167  {
168  if (UNLIKELY(low == 0))
169  --high, low = (low_type)low_max();
170  else
171  --low;
172  return *this;
173  }
174 
175  //! addition operator (uses 64-bit arithmetic)
176  inline uint_pair& operator += (const uint_pair& b)
177  {
178  uint64 add = (uint64)low + b.low;
179  low = (low_type)(add & low_max());
180  high = (high_type)(high + b.high + ((add >> low_bits) & high_max()));
181  return *this;
182  }
184  //! equality checking operator
185  inline bool operator == (const uint_pair& b) const
186  {
187  return (low == b.low) && (high == b.high);
188  }
189 
190  //! inequality checking operator
191  inline bool operator != (const uint_pair& b) const
192  {
193  return (low != b.low) || (high != b.high);
194  }
195 
196  //! less-than comparison operator
197  inline bool operator < (const uint_pair& b) const
198  {
199  return (high < b.high) || (high == b.high && low < b.low);
200  }
201 
202  //! less-or-equal comparison operator
203  inline bool operator <= (const uint_pair& b) const
204  {
205  return (high < b.high) || (high == b.high && low <= b.low);
206  }
207 
208  //! greater comparison operator
209  inline bool operator > (const uint_pair& b) const
210  {
211  return (high > b.high) || (high == b.high && low > b.low);
212  }
213 
214  //! greater-or-equal comparison operator
215  inline bool operator >= (const uint_pair& b) const
216  {
217  return (high > b.high) || (high == b.high && low >= b.low);
218  }
219 
220  //! make a uint_pair outputtable via iostreams, using unsigned long long.
221  friend std::ostream& operator << (std::ostream& os, const uint_pair& a)
222  {
223  return os << a.ull();
224  }
225 
226  //! return an uint_pair instance containing the smallest value possible
227  static uint_pair min()
228  {
231  }
232 
233  //! return an uint_pair instance containing the largest value possible
234  static uint_pair max()
235  {
238  }
239 }
240 #if STXXL_MSVC
241 ;
242 #pragma pack(pop)
243 #else
244 __attribute__ ((packed));
245 #endif
246 
247 //! \addtogroup support
248 //! \{
249 
250 //! Construct a 40-bit unsigned integer stored in five bytes.
252 
253 //! Construct a 48-bit unsigned integer stored in six bytes.
255 
256 //! \}
257 
259 
260 namespace std {
261 
262 //! template class providing some numeric_limits fields for uint_pair types.
263 template <typename HighType>
264 class numeric_limits<stxxl::uint_pair<HighType> >
265 {
266 public:
267  //! yes we have information about uint_pair
268  static const bool is_specialized = true;
269 
270  //! return an uint_pair instance containing the smallest value possible
272  { return stxxl::uint_pair<HighType>::min(); }
273 
274  //! return an uint_pair instance containing the largest value possible
276  { return stxxl::uint_pair<HighType>::max(); }
277 
278  //! return an uint_pair instance containing the smallest value possible
280  { return min(); }
281 
282  //! unit_pair types are unsigned
283  static const bool is_signed = false;
284 
285  //! uint_pair types are integers
286  static const bool is_integer = true;
287 
288  //! unit_pair types contain exact integers
289  static const bool is_exact = true;
290 
291  //! unit_pair radix is binary
292  static const int radix = 2;
293 
294  //! number of binary digits (bits) in uint_pair
296 
297  //! epsilon is zero
299  { return stxxl::uint_pair<HighType>(0, 0); }
300 
301  //! rounding error is zero
303  { return stxxl::uint_pair<HighType>(0, 0); }
304 
305  //! no exponent
306  static const int min_exponent = 0;
307 
308  //! no exponent
309  static const int min_exponent10 = 0;
310 
311  //! no exponent
312  static const int max_exponent = 0;
313 
314  //! no exponent
315  static const int max_exponent10 = 0;
316 
317  //! no infinity
318  static const bool has_infinity = false;
319 };
320 
321 } // namespace std
322 
323 #endif // !STXXL_COMMON_UINT_TYPES_HEADER
friend std::ostream & operator<<(std::ostream &os, const uint_pair &a)
make a uint_pair outputtable via iostreams, using unsigned long long.
Definition: uint_types.h:228
static unsigned_type high_max()
return highest value storable in higher part, also used as a mask.
Definition: uint_types.h:83
static const size_t low_bits
number of bits in the lower integer part, used a bit shift value.
Definition: uint_types.h:80
HighType high_type
higher part type, currently either 8-bit or 16-bit
Definition: uint_types.h:65
uint32 low_type
lower part type, always 32-bit
Definition: uint_types.h:63
Construct an 40-bit or 48-bit unsigned integer stored in five or six bytes.
Definition: uint_types.h:52
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.h:234
unsigned long long int uint64
Definition: types.h:39
static unsigned_type high_max()
return highest value storable in higher part, also used as a mask.
Definition: uint_types.h:76
static stxxl::uint_pair< HighType > max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.h:275
uint_pair(const uint64 &a)
construct from an uint64 (unsigned long long)
Definition: uint_types.h:129
uint64 u64() const
return the number as a uint64
Definition: uint_types.h:150
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.h:234
int int32
Definition: types.h:36
uint64 ull() const
return the number as an uint64 (unsigned long long)
Definition: uint_types.h:138
low_type low
member containing lower significant integer value
Definition: uint_types.h:62
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.h:163
uint_pair(const low_type &l, const high_type &h)
construct unit pair from lower and higher parts.
Definition: uint_types.h:104
uint64 ull() const
return the number as an uint64 (unsigned long long)
Definition: uint_types.h:145
static stxxl::uint_pair< HighType > min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.h:271
uint32 low_type
lower part type, always 32-bit
Definition: uint_types.h:56
static const stxxl::uint_pair< HighType > epsilon()
epsilon is zero
Definition: uint_types.h:298
uint_pair & operator+=(const uint_pair &b)
addition operator (uses 64-bit arithmetic)
Definition: uint_types.h:183
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.h:227
unsigned int uint32
Definition: types.h:37
uint_pair< uint8 > uint40
Construct a 40-bit unsigned integer stored in five bytes.
Definition: uint_types.h:251
static unsigned_type low_max()
return highest value storable in lower part, also used as a mask.
Definition: uint_types.h:67
bool operator!=(const uint_pair &b) const
inequality checking operator
Definition: uint_types.h:198
static const stxxl::uint_pair< HighType > round_error()
rounding error is zero
Definition: uint_types.h:302
bool operator<=(const uint_pair &b) const
less-or-equal comparison operator
Definition: uint_types.h:210
static const size_t high_bits
number of bits in the higher integer part, used a bit shift value.
Definition: uint_types.h:89
bool operator>(const uint_pair &b) const
greater comparison operator
Definition: uint_types.h:216
low_type low
member containing lower significant integer value
Definition: uint_types.h:69
#define UNLIKELY(c)
Definition: utils.h:225
bool operator>=(const uint_pair &b) const
greater-or-equal comparison operator
Definition: uint_types.h:222
bool operator<(const uint_pair &b) const
less-than comparison operator
Definition: uint_types.h:204
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
uint_pair & operator--()
prefix decrement operator (directly manipulates the integer parts)
Definition: uint_types.h:173
high_type high
member containing higher significant integer value
Definition: uint_types.h:71
static uint_pair max()
return an uint_pair instance containing the largest value possible
Definition: uint_types.h:241
#define STXXL_STATIC_ASSERT(x)
Definition: utils.h:48
static stxxl::uint_pair< HighType > lowest()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.h:279
static unsigned_type low_max()
return highest value storable in lower part, also used as a mask.
Definition: uint_types.h:74
high_type high
member containing higher significant integer value
Definition: uint_types.h:64
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
static const size_t bytes
number of bytes in uint_pair
Definition: uint_types.h:96
static const size_t digits
number of binary digits (bits) in uint_pair
Definition: uint_types.h:93
uint_pair(const int32 &a)
const from a simple 32-bit signed integer
Definition: uint_types.h:119
uint_pair< uint16 > uint48
Construct a 48-bit unsigned integer stored in six bytes.
Definition: uint_types.h:254
uint_pair()
empty constructor, does not even initialize to zero!
Definition: uint_types.h:92
uint_pair()
empty constructor, does not even initialize to zero!
Definition: uint_types.h:99
HighType high_type
higher part type, currently either 8-bit or 16-bit
Definition: uint_types.h:58
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.h:192
uint_pair(const uint_pair &a)
copy constructor
Definition: uint_types.h:109
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
uint_pair(const uint32 &a)
const from a simple 32-bit unsigned integer
Definition: uint_types.h:114