cde/programs/dtinfo/DtMmdb/dti_cc/cc_hdict.C

   1 // $TOG: cc_hdict.C /main/5 1998/04/17 11:45:00 mgreess $
   2
   3 #include "dti_cc/cc_exceptions.h"
   4
   5 #if !defined(__osf__)
   6 template <class K, class V> CC_Boolean kv_pair<K, V>::f_needRemove = FALSE;
   7 #endif
   8
   9 template <class K, class V>
  10 kv_pair<K, V>::~kv_pair()
  11 {
  12    if ( f_needRemove == TRUE ) {
  13       delete f_key;
  14       delete f_value;
  15    }
  16 }
  17
  18 #ifdef DEBUG
  19 template <class K, class V>
  20 ostream& kv_pair<K, V>::print(ostream& out)
  21 {
  22    return out << *f_key << " " << *f_value << "\n";
  23 }
  24 #endif
  25
  26 template <class K, class V>
  27 unsigned int kv_pair<K, V>::operator==(const kv_pair<K, V>& kv)
  28 {
  29    if ( f_key ==  0 || kv.f_key == 0 )
  30       throw(ccStringException("kv_pair::operator==(): null pointer(s)."));
  31
  32    return ( *f_key == (*kv.f_key) ) ? 1 : 0;
  33 }
  34
  35 ///////////////////////////////////
  36 //
  37 ///////////////////////////////////
  38
  39 template <class K, class V>
  40 hashTable<K,V>::hashTable(const hashTable<K, V>& h) :
  41   f_hash_func_ptr(h.f_hash_func_ptr), f_buckets(h.f_buckets),
  42   f_items(h.f_items)
  43 {
  44    cerr << "Warning: hashTable(const hashTable&) called" << endl;
  45    exit(-1);
  46 }
  47
  48 template <class K, class V>
  49 hashTable<K,V>::hashTable(unsigned (*f)(const K&), size_t init_bucket_num) :
  50   f_hash_func_ptr(f), f_buckets(init_bucket_num),
  51   f_items(0)
  52 {
  53 }
  54
  55 template <class K, class V>
  56 hashTable<K,V>::~hashTable()
  57 {
  58    CC_TPtrSlist<kv_pair<K, V> > * b = 0;
  59    kv_pair<K, V>  * r = 0;
  60
  61    for (size_t i=0; i<f_buckets.length(); i++ ) {
  62
  63       b  = f_buckets[i];
  64
  65       if ( b ) {
  66          while ( (r = b -> removeFirst()) )
  67             delete r;
  68
  69          delete b;
  70       }
  71    }
  72 }
  73
  74 template <class K, class V>
  75 void hashTable<K,V>::clearAndDestroy()
  76 {
  77    kv_pair<K, V>::f_needRemove = TRUE;
  78
  79    CC_TPtrSlist<kv_pair<K, V> >* b = 0;
  80
  81    for (size_t i=0; i<f_buckets.length(); i++ ) {
  82
  83      b = f_buckets[i];
  84      if ( b ) {
  85         b -> clearAndDestroy();
  86         delete b;
  87         f_buckets[i] = 0;
  88      }
  89    }
  90
  91    f_items = 0;
  92
  93    kv_pair<K, V>::f_needRemove = FALSE;
  94 }
  95
  96 template <class K, class V>
  97 CC_Boolean hashTable<K,V>::contains(const K* k) const
  98 {
  99    if ( findValue(k) )
 100      return TRUE;
 101    else
 102      return FALSE;
 103
 104 }
 105
 106 template <class K, class V>
 107 kv_pair<K, V>* hashTable<K,V>::_find(const K* k) const
 108 {
 109    size_t i = (*f_hash_func_ptr)(*k) % f_buckets.length();
 110
 111    CC_TPtrSlist<kv_pair<K, V> >* b = f_buckets[i];
 112
 113    if ( b == 0 )
 114      return 0;
 115
 116    kv_pair<K, V> key((K*)k);
 117
 118    return b -> find(&key);
 119 }
 120
 121 template <class K, class V>
 122 V* hashTable<K,V>::findValue(const K* k) const
 123 {
 124    kv_pair<K, V>* p = _find(k);
 125    if ( p )
 126      return p -> f_value;
 127    else
 128      return 0;
 129 }
 130
 131 template <class K, class V>
 132 K* hashTable<K,V>::findKeyAndValue(const K* k, V*& v) const
 133 {
 134    kv_pair<K, V>* p = _find(k);
 135    if ( p ) {
 136      v = p -> f_value;
 137      return p -> f_key;
 138    } else
 139      return 0;
 140 }
 141
 142 template <class K, class V>
 143 void hashTable<K,V>::insertKeyAndValue(K* k, V* v)
 144 {
 145    size_t i = (*f_hash_func_ptr)(*k) % f_buckets.length();
 146
 147    CC_TPtrSlist<kv_pair<K, V> >* b = f_buckets[i];
 148
 149    if ( b == 0 ) {
 150      f_buckets[i] = new CC_TPtrSlist<kv_pair<K, V> >;
 151    }
 152
 153    kv_pair<K, V>* p = new kv_pair<K, V>(k, v);
 154    f_buckets[i] -> insert(p);
 155
 156    f_items ++;
 157 }
 158
 159 template <class K, class V>
 160 K* hashTable<K,V>::remove(const K* k)
 161 {
 162    size_t i = (*f_hash_func_ptr)(*k) % f_buckets.length();
 163
 164    CC_TPtrSlist<kv_pair<K, V> >* b = f_buckets[i];
 165
 166    if ( b == 0 )
 167       return 0;
 168
 169    kv_pair<K, V> key((K*)k, 0);
 170    kv_pair<K, V>* result = b -> remove(&key);
 171
 172    if ( result == 0 )
 173      return 0;
 174
 175    K* kr = result -> f_key;
 176
 177    delete result;
 178
 179    f_items --;
 180
 181    return kr;
 182 }
 183
 184 #ifdef DEBUG
 185 template <class K, class V>
 186 ostream& hashTable<K,V>::print(ostream& out)
 187 {
 188    CC_TPtrSlist<kv_pair<K, V> >* b = 0;
 189
 190    for (int i=0; i<f_buckets.length(); i++ ) {
 191
 192      b = f_buckets[i];
 193      if ( b ) {
 194         cerr << "bucket num = " << i << "\n";
 195
 196         CC_TPtrSlistIterator<kv_pair<K, V> > next(*b);
 197
 198         while (++next) {
 199            out << ' ' << *next.key() ;
 200         }
 201      }
 202    }
 203
 204    return out;
 205 }
 206 #endif
 207
 208 ////////////////////////////////////////
 209 template <class K, class V>
 210 hashTableIterator<K,V>::hashTableIterator(hashTable<K, V>& b) :
 211    f_bucket_num(0), f_pos(0), f_rec(0), f_hashTable(b)
 212 {
 213 }
 214
 215 template <class K, class V>
 216 hashTableIterator<K,V>::~hashTableIterator()
 217 {
 218 }
 219
 220 template <class K, class V>
 221 CC_Boolean hashTableIterator<K,V>::_findNonEmptyBucket()
 222 {
 223    CC_TPtrSlist<kv_pair<K, V> >* b = 0;
 224
 225    for (; f_bucket_num<f_hashTable.f_buckets.length(); f_bucket_num++ ) {
 226       if ( (b=f_hashTable.f_buckets[f_bucket_num]) && b->entries() > 0 ) {
 227          f_pos = 0;
 228          return TRUE;
 229       }
 230    }
 231
 232    return FALSE;
 233 }
 234
 235 template <class K, class V>
 236 CC_Boolean hashTableIterator<K,V>::operator++()
 237 {
 238    if ( f_rec == 0 ) { // first call to this op.
 239        if (  _findNonEmptyBucket() == FALSE )
 240          return FALSE;
 241
 242    } else {
 243        if (  _findNextRecord() == FALSE ) {
 244           f_bucket_num++;
 245           if (  _findNonEmptyBucket() == FALSE )
 246              return FALSE;
 247        }
 248    }
 249
 250 //fprintf(stderr, "in operator++: f_bucket_num= %d, f_pos = %d\n",
 251 //f_bucket_num, f_pos);
 252
 253    f_rec = f_hashTable.f_buckets[f_bucket_num] -> at(f_pos);
 254    return TRUE;
 255 }
 256
 257 template <class K, class V>
 258 CC_Boolean hashTableIterator<K,V>::_findNextRecord()
 259 {
 260    f_pos++;
 261
 262 //fprintf(stderr, "f_bucket_num= %d, f_pos = %d, entries() = %d\n", f_bucket_num, f_pos, f_hashTable.f_buckets[f_bucket_num] -> entries() );
 263
 264    if ( f_hashTable.f_buckets[f_bucket_num] -> entries() <= f_pos )
 265       return FALSE;
 266    else
 267       return TRUE;
 268 }
 269
 270 template <class K, class V>
 271 K* hashTableIterator<K,V>::key()
 272 {
 273    return f_rec -> f_key;
 274 }
 275
 276 template <class K, class V>
 277 V* hashTableIterator<K,V>::value() const
 278 {
 279    return f_rec -> f_value;
 280 }
 281