zdd/lib/SAPPOROBDD/src/BDD+/BDDHASH.cc

   1 /****************************************
   2  * BDD+ Manipulator (SAPPORO-1.21)      *
   3  * (Hash table methods)                 *
   4  * (C) Shin-ichi MINATO (Feb. 18, 2009) *
   5  ****************************************/
   6
   7 #include "BDD.h"
   8
   9 BDD_Hash::BDD_Hash()
  10 {
  11   _hashSize = 16;
  12   _wheel = new BDD_Entry[_hashSize];
  13   _amount = 0;
  14 }
  15
  16 BDD_Hash::~BDD_Hash() { delete[] _wheel; }
  17
  18 void BDD_Hash::Clear()
  19 {
  20   if(_hashSize != 0) delete[] _wheel;
  21   _hashSize = 16;
  22   _wheel = new BDD_Entry[_hashSize];
  23   _amount = 0;
  24 }
  25
  26 BDD_Hash::BDD_Entry* BDD_Hash::GetEntry(BDD key)
  27 {
  28   bddword id = key.GetID();
  29   bddword hash = (id+(id>>10)+(id>>20)) & (_hashSize - 1);
  30   bddword i = hash;
  31   while(_wheel[i]._key != -1)
  32   {
  33     if(key == _wheel[i]._key) return & _wheel[i];
  34     i++;
  35     i &= (_hashSize -1);
  36   }
  37   i = hash;
  38   while(_wheel[i]._key != -1)
  39   {
  40     if(_wheel[i]._ptr == 0) break;
  41     i++;
  42     i &= (_hashSize -1);
  43   }
  44   return & _wheel[i];
  45 }
  46
  47 void BDD_Hash::Enlarge()
  48 {
  49   bddword oldSize = _hashSize;
  50   BDD_Entry* oldWheel = _wheel;
  51
  52   _hashSize <<= 2;
  53   _wheel = new BDD_Entry[_hashSize];
  54   if(_wheel == 0)
  55   {
  56     cerr << "<ERROR> BDD_Hash::Enlarge(): Memory overflow (";
  57     cerr << _hashSize << ")\n";
  58     exit(1);
  59   }
  60   _amount = 0;
  61   for(bddword i=0; i<oldSize; i++)
  62     if(oldWheel[i]._ptr != 0)
  63       if(oldWheel[i]._key != -1)
  64         Enter(oldWheel[i]._key, oldWheel[i]._ptr);
  65   delete[] oldWheel;
  66 }
  67
  68 void BDD_Hash::Enter(BDD key, void* ptr)
  69 // ptr = 0 means deleting.
  70 {
  71   BDD_Entry* ent = GetEntry(key);
  72   if(ent -> _key == -1) _amount++;
  73   else if(ent -> _ptr == 0) _amount++;
  74   if(ptr == 0) _amount--;
  75   ent -> _key = key;
  76   ent -> _ptr = ptr;
  77   if(_amount >= (_hashSize>>1)) Enlarge();
  78 }
  79
  80 void* BDD_Hash::Refer(BDD key)
  81 // returns 0 if not found.
  82 {
  83   BDD_Entry* ent = GetEntry(key);
  84   if(ent -> _key == -1) return 0;
  85   return ent -> _ptr;
  86 }
  87
  88 bddword BDD_Hash::Amount() { return _amount; }
  89