1 #include "integer-pool.hpp"
8 const unsigned special_level
= 21;
9 uint64_t level_base
[] = {
30 164703072086692425ULL,
31 1317624576693539401ULL,
32 3623467585907233353ULL, //Special: Fits 2^64 bits.
34 uint64_t level_size
[] = {
54 144115188075855872ULL,
55 1152921504606846976ULL,
56 2305843009213693952ULL, //Special: 2^64 bits.
59 const unsigned levels
= 22;
60 unsigned level_from_size(uint64_t size
)
62 for(unsigned i
= 0; i
< levels
; i
++) {
63 if(size
<= level_base
[i
+ 1]) return i
;
68 uint64_t get_levelsize(unsigned n
)
70 static uint64_t table
[levels
];
71 static bool init
= false;
74 for(unsigned i
= 0; i
< levels
; i
++) {
83 unsigned lsbz(uint8_t b
)
85 return ((b
& 1) ? ((b
& 2) ? ((b
& 4) ? ((b
& 8) ? ((b
& 16) ? ((b
& 32) ? ((b
& 64) ?
86 ((b
& 128) ? 8 : 7) : 6) : 5) : 4) : 3) : 2) : 1) : 0);
90 integer_pool::integer_pool() throw()
96 uint64_t integer_pool::operator()() throw(std::bad_alloc
)
98 //If the first byte is 0xFF, we got to expand the array.
100 unsigned level
= level_from_size(_bits
.size()); //If bits.size() == 0, this correctly returns 0.
101 assert(level
< special_level
);
102 std::vector
<uint8_t> newbits
;
103 newbits
.resize(level_base
[level
+ 2]);
104 memset(&newbits
[0], 0, level_base
[level
+ 2]);
105 for(unsigned i
= 0; i
<= level
; i
++)
106 memcpy(&newbits
[level_base
[i
+ 1]], &bits
[level_base
[i
]], level_size
[i
]);
108 std::swap(_bits
, newbits
);
112 unsigned level
= level_from_size(_bits
.size()); //If bits.size() == 0, this correctly returns 0.
113 uint64_t pathbits
= 0;
114 for(unsigned i
= 0; i
< level
; i
++) {
115 uint64_t byte
= level_base
[i
] + pathbits
;
116 assert(bits
[byte
] < 255);
117 unsigned lsb
= lsbz(bits
[byte
]);
118 pathbits
= 8 * pathbits
+ lsb
;
121 //Check if there are free integers in pool.
122 if(pathbits
> 0x1FFFFFFFFFFFFFFFULL
) throw std::bad_alloc();
124 //Reserve it, and propagate fullness downward if needed.
125 uint64_t byte
= level_base
[level
] + pathbits
;
126 assert(bits
[byte
] < 255);
127 unsigned lsb
= lsbz(bits
[byte
]);
128 pathbits
= 8 * pathbits
+ lsb
;
129 uint64_t bit
= pathbits
;
131 for(unsigned i
= level
; i
<= level
; i
--) {
133 byte
= level_base
[i
] + (pathbits
>> 3);
134 bits
[byte
] |= (1 << (pathbits
& 7));
135 carry
= (bits
[byte
] == 255);
143 void integer_pool::operator()(uint64_t num
) throw()
145 unsigned level
= level_from_size(_bits
.size()); //If bits.size() == 0, this correctly returns 0.
146 for(unsigned i
= level
; i
<= level
; i
--) {
147 uint64_t byte
= level_base
[i
] + (num
>> 3);
148 bits
[byte
] &= ~(1 << (num
& 7));