src/library/integer-pool.cpp

   1 #include "integer-pool.hpp"
   2 #include <iostream>
   3 #include <cassert>
   4 #include <cstring>
   5
   6 namespace
   7 {
   8         const unsigned special_level = 21;
   9         uint64_t level_base[] = {
  10                 0ULL,
  11                 1ULL,
  12                 9ULL,
  13                 73ULL,
  14                 585ULL,
  15                 4681ULL,
  16                 37449ULL,
  17                 299593ULL,
  18                 2396745ULL,
  19                 19173961ULL,
  20                 153391689ULL,
  21                 1227133513ULL,
  22                 9817068105ULL,
  23                 78536544841ULL,
  24                 628292358729ULL,
  25                 5026338869833ULL,
  26                 40210710958665ULL,
  27                 321685687669321ULL,
  28                 2573485501354569ULL,
  29                 20587884010836553ULL,
  30                 164703072086692425ULL,
  31                 1317624576693539401ULL,
  32                 3623467585907233353ULL,         //Special: Fits 2^64 bits.
  33         };
  34         uint64_t level_size[] = {
  35                 1ULL,
  36                 8ULL,
  37                 64ULL,
  38                 512ULL,
  39                 4096ULL,
  40                 32768ULL,
  41                 262144ULL,
  42                 2097152ULL,
  43                 16777216ULL,
  44                 134217728ULL,
  45                 1073741824ULL,
  46                 8589934592ULL,
  47                 68719476736ULL,
  48                 549755813888ULL,
  49                 4398046511104ULL,
  50                 35184372088832ULL,
  51                 281474976710656ULL,
  52                 2251799813685248ULL,
  53                 18014398509481984ULL,
  54                 144115188075855872ULL,
  55                 1152921504606846976ULL,
  56                 2305843009213693952ULL,         //Special: 2^64 bits.
  57         };
  58
  59         const unsigned levels = 22;
  60         unsigned level_from_size(uint64_t size)
  61         {
  62                 for(unsigned i = 0; i < levels; i++) {
  63                         if(size <= level_base[i + 1]) return i;
  64                 }
  65                 return levels;
  66         }
  67
  68         unsigned lsbz(uint8_t b)
  69         {
  70                 return ((b & 1) ? ((b & 2) ? ((b & 4) ? ((b & 8) ? ((b & 16) ? ((b & 32) ? ((b & 64) ?
  71                         ((b & 128) ? 8 : 7) : 6) : 5) : 4) : 3) : 2) : 1) : 0);
  72         }
  73 }
  74
  75 integer_pool::integer_pool() throw()
  76 {
  77         invalid = false;
  78         _bits2 = 0;
  79         bits = &_bits2;
  80 }
  81
  82 uint64_t integer_pool::operator()() throw(std::bad_alloc)
  83 {
  84         if(invalid) throw std::bad_alloc();
  85         //If the first byte is 0xFF, we got to expand the array.
  86         if(bits[0] == 0xFF) {
  87                 unsigned level = level_from_size(_bits.size());  //If bits.size() == 0, this correctly returns 0.
  88                 assert(level < special_level);
  89                 std::vector<uint8_t> newbits;
  90                 newbits.resize(level_base[level + 2]);
  91                 memset(&newbits[0], 0, level_base[level + 2]);
  92                 for(unsigned i = 0; i <= level; i++)
  93                         memcpy(&newbits[level_base[i + 1]], &bits[level_base[i]], level_size[i]);
  94                 newbits[0] = 1;
  95                 std::swap(_bits, newbits);
  96                 bits = &_bits[0];
  97         }
  98         //Find a free byte.
  99         unsigned level = level_from_size(_bits.size());  //If bits.size() == 0, this correctly returns 0.
 100         uint64_t pathbits = 0;
 101         for(unsigned i = 0; i < level; i++) {
 102                 uint64_t byte = level_base[i] + pathbits;
 103                 assert(bits[byte] < 255);
 104                 unsigned lsb = lsbz(bits[byte]);
 105                 pathbits = 8 * pathbits + lsb;
 106         }
 107
 108         //Check if there are free integers in pool.
 109         if(pathbits > 0x1FFFFFFFFFFFFFFFULL) throw std::bad_alloc();
 110
 111         //Reserve it, and propagate fullness downward if needed.
 112         uint64_t byte = level_base[level] + pathbits;
 113         assert(bits[byte] < 255);
 114         unsigned lsb = lsbz(bits[byte]);
 115         pathbits = 8 * pathbits + lsb;
 116         uint64_t bit = pathbits;
 117         bool carry = true;
 118         for(unsigned i = level; i <= level; i--) {
 119                 if(carry) {
 120                         byte = level_base[i] + (pathbits >> 3);
 121                         bits[byte] |= (1 << (pathbits & 7));
 122                         carry = (bits[byte] == 255);
 123                         pathbits >>= 3;
 124                 } else
 125                         break;
 126         }
 127         return bit;
 128 }
 129
 130 void integer_pool::operator()(uint64_t num) throw()
 131 {
 132         if(invalid) return;
 133         unsigned level = level_from_size(_bits.size());  //If bits.size() == 0, this correctly returns 0.
 134         for(unsigned i = level; i <= level; i--) {
 135                 uint64_t byte = level_base[i] + (num >> 3);
 136                 bits[byte] &= ~(1 << (num & 7));
 137                 num >>= 3;
 138         }
 139 }
 140
 141 integer_pool::~integer_pool() throw()
 142 {
 143         invalid = true;
 144 }