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         uint64_t get_levelsize(unsigned n)
  69         {
  70                 static uint64_t table[levels];
  71                 static bool init = false;
  72                 if(!init) {
  73                         uint64_t r = 1;
  74                         for(unsigned i = 0; i < levels; i++) {
  75                                 table[i] = r;
  76                                 r = 8 * r + 1;
  77                         }
  78                         init = true;
  79                 }
  80                 return table[n];
  81         }
  82
  83         unsigned lsbz(uint8_t b)
  84         {
  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);
  87         }
  88 }
  89
  90 integer_pool::integer_pool() throw()
  91 {
  92         _bits2 = 0;
  93         bits = &_bits2;
  94 }
  95
  96 uint64_t integer_pool::operator()() throw(std::bad_alloc)
  97 {
  98         //If the first byte is 0xFF, we got to expand the array.
  99         if(bits[0] == 0xFF) {
 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]);
 107                 newbits[0] = 1;
 108                 std::swap(_bits, newbits);
 109                 bits = &_bits[0];
 110         }
 111         //Find a free byte.
 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;
 119         }
 120
 121         //Check if there are free integers in pool.
 122         if(pathbits > 0x1FFFFFFFFFFFFFFFULL) throw std::bad_alloc();
 123
 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;
 130         bool carry = true;
 131         for(unsigned i = level; i <= level; i--) {
 132                 if(carry) {
 133                         byte = level_base[i] + (pathbits >> 3);
 134                         bits[byte] |= (1 << (pathbits & 7));
 135                         carry = (bits[byte] == 255);
 136                         pathbits >>= 3;
 137                 } else
 138                         break;
 139         }
 140         return bit;
 141 }
 142
 143 void integer_pool::operator()(uint64_t num) throw()
 144 {
 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));
 149                 num >>= 3;
 150         }
 151 }