wxPython/wxSWIG/SWIG/hash.cxx

   1 /*******************************************************************************
   2  * Simplified Wrapper and Interface Generator  (SWIG)
   3  *
   4  * Author : David Beazley
   5  *
   6  * Department of Computer Science
   7  * University of Chicago
   8  * 1100 E 58th Street
   9  * Chicago, IL  60637
  10  * beazley@cs.uchicago.edu
  11  *
  12  * Please read the file LICENSE for the copyright and terms by which SWIG
  13  * can be used and distributed.
  14  *******************************************************************************/
  15
  16 #include "internal.h"
  17
  18 /*******************************************************************************
  19  * $Header$
  20  *
  21  * File : hash.cxx
  22  *
  23  * A very simple Hash table class.  Could probably make it more elegant with
  24  * templates, but templates are pure evil...
  25  *******************************************************************************/
  26
  27 #define INIT_SIZE   119
  28
  29 // -----------------------------------------------------------------------------
  30 // Hash::Hash()
  31 //
  32 // Constructor.  Creates a new hash table.
  33 //
  34 // Inputs : None
  35 //
  36 // Output : New Hash object.
  37 //
  38 // Side Effects : None
  39 // -----------------------------------------------------------------------------
  40
  41 Hash::Hash() {
  42   int i;
  43   hashsize = INIT_SIZE;
  44   hashtable = new Node *[hashsize];
  45   for (i = 0; i < hashsize; i++) {
  46     hashtable[i] = 0;
  47   }
  48   index = -1;
  49   current = 0;
  50 }
  51
  52 // -----------------------------------------------------------------------------
  53 // Hash::~Hash()
  54 //
  55 // Destructor.
  56 //
  57 // Inputs : None
  58 //
  59 // Output : None
  60 //
  61 // Side Effects : Total destruction.
  62 // -----------------------------------------------------------------------------
  63
  64 Hash::~Hash() {
  65   int   i;
  66   Node *n,*next;
  67
  68   for (i = 0; i < hashsize; i++) {
  69     if (hashtable[i]) {
  70       n = hashtable[i];
  71       while (n) {
  72         next = n->next;
  73         delete n;
  74         n = next;
  75       }
  76     }
  77   }
  78   delete [] hashtable;
  79 }
  80
  81 // -----------------------------------------------------------------------------
  82 // int Hash::h1(const char *key)
  83 //
  84 // Hashing function.
  85 //
  86 // Inputs : ASCII character string.
  87 //
  88 // Output : Hash table index.
  89 //
  90 // Side Effects : None
  91 // -----------------------------------------------------------------------------
  92
  93 int Hash::h1(const char *key) {
  94   int h = 0;
  95   const char *c;
  96
  97   c = key;
  98   while (*c) {
  99     h = (128*h + *c) % hashsize;
 100     c++;
 101   }
 102   return h;
 103 }
 104
 105 // -----------------------------------------------------------------------------
 106 // int Hash::add(const char *k, void *obj)
 107 //
 108 // Adds a new object to the hash table.
 109 //
 110 // Inputs :
 111 //          k     = Hash key
 112 //          obj   = Pointer to an object
 113 //
 114 // Output : 0 on success, -1 if item is already in hash table.
 115 //
 116 // Side Effects :
 117 //          Makes a new hash table entry.
 118 // -----------------------------------------------------------------------------
 119
 120 int Hash::add(const char *k, void *obj) {
 121
 122   int  hv;
 123   Node *n,*prev;
 124
 125   hv = h1(k);                                  // Get hash value
 126   n = hashtable[hv];
 127   prev = n;
 128   while (n) {
 129     if (strcmp(n->key,k) == 0) return -1;      // Already in hash table
 130     prev = n;
 131     n = n->next;
 132   }
 133
 134   // Safe to add this to the table
 135
 136   n = new Node(k,obj,0);
 137   if (prev) prev->next = n;
 138   else hashtable[hv] = n;
 139   return 0;
 140 }
 141
 142 // -----------------------------------------------------------------------------
 143 // int Hash::add(const char *k, void *obj, void (*d)(void *))
 144 //
 145 // Adds a new object to the hash table.  Allows additional specification of
 146 // a callback function for object deletion.
 147 //
 148 // Inputs :
 149 //          k       = Hash key
 150 //          obj     = Object pointer
 151 //          d       = Deletion function
 152 //
 153 // Output : 0 on success, -1 if item is already in hash table.
 154 //
 155 // Side Effects :
 156 //          Adds an entry to the hash table
 157 // -----------------------------------------------------------------------------
 158
 159 int Hash::add(const char *k, void *obj, void (*d)(void *)) {
 160
 161   int  hv;
 162   Node *n,*prev;
 163
 164   hv = h1(k);                                  // Get hash value
 165   n = hashtable[hv];
 166   prev = n;
 167   while (n) {
 168     if (strcmp(n->key,k) == 0) return -1;      // Already in hash table
 169     prev = n;
 170     n = n->next;
 171   }
 172
 173   // Safe to add this to the table
 174
 175   n = new Node(k,obj,d);
 176   if (prev) prev->next = n;
 177   else hashtable[hv] = n;
 178   return 0;
 179 }
 180
 181 // -----------------------------------------------------------------------------
 182 // void *Hash::lookup(const char *k)
 183 //
 184 // Looks up a value in the hash table.  Returns a pointer to the object if found.
 185 //
 186 // Inputs : k   = key value
 187 //
 188 // Output : Pointer to object or NULL if not found.
 189 //
 190 // Side Effects : None
 191 // -----------------------------------------------------------------------------
 192
 193 void *Hash::lookup(const char *k) {
 194   int hv;
 195   Node *n;
 196
 197   hv = h1(k);                                // Get hash value
 198   n = hashtable[hv];
 199
 200   while (n) {
 201     if (strcmp(n->key,k) == 0) return n->object;
 202     n = n->next;
 203   }
 204
 205   return 0;
 206 }
 207
 208 // -----------------------------------------------------------------------------
 209 // void Hash::remove(const char *k)
 210 //
 211 // Removes an item from the hash table.  Does nothing if item isn't in the
 212 // hash table to begin with.
 213 //
 214 // Inputs : k = Key value
 215 //
 216 // Output : None
 217 //
 218 // Side Effects : Deletes item from hash table.
 219 // -----------------------------------------------------------------------------
 220
 221 void Hash::remove(const char *k) {
 222
 223   int  hv;
 224   Node *n,*prev;
 225
 226   hv = h1(k);                                  // Get hash value
 227   n = hashtable[hv];
 228   prev = 0;
 229   while (n) {
 230     if (strcmp(n->key,k) == 0) {
 231       // Found it, kill the thing
 232       if (prev) {
 233         prev->next = n->next;
 234       } else {
 235         hashtable[hv] = n->next;
 236       }
 237       delete n;
 238       return;
 239     }
 240     prev = n;
 241     n = n->next;
 242   }
 243 }
 244
 245 // -----------------------------------------------------------------------------
 246 // void *Hash::first()
 247 //
 248 // Gets the first item from the hash table or NULL if empty.
 249 //
 250 // Inputs : None
 251 //
 252 // Output : First object in hash table or NULL if hash table is empty.
 253 //
 254 // Side Effects : Resets an internal iterator variable on the hash table.
 255 // -----------------------------------------------------------------------------
 256
 257 void *Hash::first() {
 258   index = 0;
 259   current = 0;
 260
 261   while (!hashtable[index] && (index < hashsize))
 262     index++;
 263
 264   if (index >= hashsize) return 0;
 265   current = hashtable[index];
 266   return current->object;
 267 }
 268
 269
 270 // -----------------------------------------------------------------------------
 271 // char *Hash::firstkey()
 272 //
 273 // Gets the first key from the hash table or NULL if empty.
 274 //
 275 // Inputs : None
 276 //
 277 // Output : First key in hash table or NULL if hash table is empty.
 278 //
 279 // Side Effects : Resets an internal iterator variable on the hash table.
 280 // -----------------------------------------------------------------------------
 281
 282 char *Hash::firstkey() {
 283   index = 0;
 284   current = 0;
 285
 286   while ((index < hashsize) && (!hashtable[index]))
 287     index++;
 288
 289   if (index >= hashsize) return 0;
 290   current = hashtable[index];
 291   return current->key;
 292 }
 293
 294 // -----------------------------------------------------------------------------
 295 // void *Hash::next()
 296 //
 297 // Returns the next item in the hash table or NULL if there are no more entries.
 298 // A call to first() should generally be made before using this function.
 299 //
 300 // Inputs : None
 301 //
 302 // Output : Pointer to next object or NULL if there are no more objects.
 303 //
 304 // Side Effects : Updates an iterator variable private to the hash table.
 305 // -----------------------------------------------------------------------------
 306
 307 void *Hash::next() {
 308   if (index < 0) return first();
 309
 310   // Try to move to the next entry
 311
 312   current = current->next;
 313
 314   if (current) {
 315     return current->object;
 316   } else {
 317     index++;
 318     while ((index < hashsize) && (!hashtable[index]))
 319       index++;
 320     if (index >= hashsize) return 0;
 321     current = hashtable[index];
 322     return current->object;
 323   }
 324 }
 325
 326
 327 // -----------------------------------------------------------------------------
 328 // char *Hash::nextkey()
 329 //
 330 // Returns the next key in the hash table or NULL if there are no more entries.
 331 // A call to firstkey() should generally be made before using this function.
 332 //
 333 // Inputs : None
 334 //
 335 // Output : Pointer to next key or NULL if there are no more objects.
 336 //
 337 // Side Effects : Updates an iterator variable private to the hash table.
 338 // -----------------------------------------------------------------------------
 339
 340 char *Hash::nextkey() {
 341   if (index < 0) return firstkey();
 342
 343   // Try to move to the next entry
 344
 345   current = current->next;
 346
 347   if (current) {
 348     return current->key;
 349   } else {
 350     index++;
 351     while (!hashtable[index] && (index < hashsize))
 352       index++;
 353     if (index >= hashsize) return 0;
 354     current = hashtable[index];
 355     return current->key;
 356   }
 357 }
 358
 359