bins.h

   1 /*
   2  *  sbit.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/28/09.
   6  *  Copyright 2009 Delft Technical University. All rights reserved.
   7  *
   8  */
   9 #ifndef SERP_SBIT_H
  10 #define SERP_SBIT_H
  11 #include "bin64.h"
  12
  13 class bins64 {
  14
  15     private:
  16
  17         uint32_t    *bits;
  18         uint32_t    alloc_block;
  19
  20     protected:
  21
  22         bool        join(uint32_t half) {
  23             uint32_t cellno = bits[half]>>(half&1?16:0);
  24
  25             if (deep(left) || deep(right)) // some half is deep
  26                 return false;
  27             uint8_t b1=JOIN[cell&0xf],
  28                     b2=JOIN[(cell>>8)&0xf],
  29                     b3=JOIN[(cell>>16)&0xf],
  30                     b4=JOIN[cell>>24];
  31             if (b1==0xff || b2==0xff || b3==0xff || b4==0xff)
  32                 return false;
  33             bits[half] = b1 | (b2<<4) | (b3<<8) | (b4<<12) ;
  34             (*parentdeepcell) ^= 1<<(halfno&32);
  35             (*childdeepcell) &= 0xffff>>1; // clean the full bit
  36         }
  37
  38         bool        split(uint32_t half) {
  39             if (deep(half))
  40                 return false;
  41             uint32_t cell = alloc_cell(), left=cell<<1, right=left+1;
  42             bits[half|0xf] |= 1<<(half&0xf);
  43             bits[left] = SPLIT[bits[half]>>8];
  44             bits[right] = SPLIT[bits[half&0xff]];
  45             bits[half] = cell;
  46             return true;
  47         }
  48
  49         uint32_t    alloc_cell () {
  50             do{
  51                 for(int block=alloc_block; bits[block]&(1<<32); block+=32);
  52                 for(int off=0; bits[block+off]==0 && off<31; off++);
  53                 if (off==31)
  54                     bits[block] |= 1<<32;
  55                 if (block&(1<<31)) {
  56                     bits = realloc(bits,block*2);
  57                     memset();
  58                 }
  59             } while (off==31);
  60             alloc_block = block;
  61             return block+off;
  62         }
  63
  64     public:
  65
  66         class iterator {
  67             bins64_t    *host;
  68             uint32_t    back[32];
  69             uint32_t    half;
  70             bin64_t     top;
  71             bin64_t     focus;
  72             bin16_t     mask;
  73             public:
  74             void left();
  75             void right();
  76             void parent();
  77             bin64_t next();
  78             bool defined();
  79             uint16_t& operator* ();
  80         };
  81         friend class iterator;
  82
  83         bool get (uint64_t bin);
  84
  85         void set (uint64_t bin);
  86
  87         bin64_t find (bin64_t range, int layer);
  88
  89         // TODO: bitwise operators
  90
  91 };