external/ibm-public/postfix/dist/src/util/htable.c

   1 /*      $NetBSD$        */
   2
   3 /*++
   4 /* NAME
   5 /*      htable 3
   6 /* SUMMARY
   7 /*      hash table manager
   8 /* SYNOPSIS
   9 /*      #include <htable.h>
  10 /*
  11 /*      typedef struct {
  12 /* .in +4
  13 /*              char    *key;
  14 /*              char    *value;
  15 /*              /* private fields... */
  16 /* .in -4
  17 /*      } HTABLE_INFO;
  18 /*
  19 /*      HTABLE  *htable_create(size)
  20 /*      int     size;
  21 /*
  22 /*      HTABLE_INFO *htable_enter(table, key, value)
  23 /*      HTABLE  *table;
  24 /*      const char *key;
  25 /*      char    *value;
  26 /*
  27 /*      char    *htable_find(table, key)
  28 /*      HTABLE  *table;
  29 /*      const char *key;
  30 /*
  31 /*      HTABLE_INFO *htable_locate(table, key)
  32 /*      HTABLE  *table;
  33 /*      const char *key;
  34 /*
  35 /*      void    htable_delete(table, key, free_fn)
  36 /*      HTABLE  *table;
  37 /*      const char *key;
  38 /*      void    (*free_fn)(char *);
  39 /*
  40 /*      void    htable_free(table, free_fn)
  41 /*      HTABLE  *table;
  42 /*      void    (*free_fn)(char *);
  43 /*
  44 /*      void    htable_walk(table, action, ptr)
  45 /*      HTABLE  *table;
  46 /*      void    (*action)(HTABLE_INFO *, char *ptr);
  47 /*      char    *ptr;
  48 /*
  49 /*      HTABLE_INFO **htable_list(table)
  50 /*      HTABLE  *table;
  51 /* DESCRIPTION
  52 /*      This module maintains one or more hash tables. Each table entry
  53 /*      consists of a unique string-valued lookup key and a generic
  54 /*      character-pointer value.
  55 /*      The tables are automatically resized when they fill up. When the
  56 /*      values to be remembered are not character pointers, proper casts
  57 /*      should be used or the code will not be portable.
  58 /*
  59 /*      htable_create() creates a table of the specified size and returns a
  60 /*      pointer to the result. The lookup keys are saved with mystrdup().
  61 /*      htable_enter() stores a (key, value) pair into the specified table
  62 /*      and returns a pointer to the resulting entry. The code does not
  63 /*      check if an entry with that key already exists: use htable_locate()
  64 /*      for updating an existing entry.
  65 /*
  66 /*      htable_find() returns the value that was stored under the given key,
  67 /*      or a null pointer if it was not found. In order to distinguish
  68 /*      a null value from a non-existent value, use htable_locate().
  69 /*
  70 /*      htable_locate() returns a pointer to the entry that was stored
  71 /*      for the given key, or a null pointer if it was not found.
  72 /*
  73 /*      htable_delete() removes one entry that was stored under the given key.
  74 /*      If the free_fn argument is not a null pointer, the corresponding
  75 /*      function is called with as argument the non-zero value stored under
  76 /*      the key.
  77 /*
  78 /*      htable_free() destroys a hash table, including contents. If the free_fn
  79 /*      argument is not a null pointer, the corresponding function is called
  80 /*      for each table entry, with as argument the non-zero value stored
  81 /*      with the entry.
  82 /*
  83 /*      htable_walk() invokes the action function for each table entry, with
  84 /*      a pointer to the entry as its argument. The ptr argument is passed
  85 /*      on to the action function.
  86 /*
  87 /*      htable_list() returns a null-terminated list of pointers to
  88 /*      all elements in the named table. The list should be passed to
  89 /*      myfree().
  90 /* RESTRICTIONS
  91 /*      A callback function should not modify the hash table that is
  92 /*      specified to its caller.
  93 /* DIAGNOSTICS
  94 /*      The following conditions are reported and cause the program to
  95 /*      terminate immediately: memory allocation failure; an attempt
  96 /*      to delete a non-existent entry.
  97 /* SEE ALSO
  98 /*      mymalloc(3) memory management wrapper
  99 /* LICENSE
 100 /* .ad
 101 /* .fi
 102 /*      The Secure Mailer license must be distributed with this software.
 103 /* AUTHOR(S)
 104 /*      Wietse Venema
 105 /*      IBM T.J. Watson Research
 106 /*      P.O. Box 704
 107 /*      Yorktown Heights, NY 10598, USA
 108 /*--*/
 109
 110 /* C library */
 111
 112 #include <sys_defs.h>
 113 #include <string.h>
 114
 115 /* Local stuff */
 116
 117 #include "mymalloc.h"
 118 #include "msg.h"
 119 #include "htable.h"
 120
 121 /* htable_hash - hash a string */
 122
 123 static unsigned htable_hash(const char *s, unsigned size)
 124 {
 125     unsigned long h = 0;
 126     unsigned long g;
 127
 128     /*
 129      * From the "Dragon" book by Aho, Sethi and Ullman.
 130      */
 131
 132     while (*s) {
 133         h = (h << 4U) + *s++;
 134         if ((g = (h & 0xf0000000)) != 0) {
 135             h ^= (g >> 24U);
 136             h ^= g;
 137         }
 138     }
 139     return (h % size);
 140 }
 141
 142 /* htable_link - insert element into table */
 143
 144 #define htable_link(table, element) { \
 145      HTABLE_INFO **_h = table->data + htable_hash(element->key, table->size);\
 146     element->prev = 0; \
 147     if ((element->next = *_h) != 0) \
 148         (*_h)->prev = element; \
 149     *_h = element; \
 150     table->used++; \
 151 }
 152
 153 /* htable_size - allocate and initialize hash table */
 154
 155 static void htable_size(HTABLE *table, unsigned size)
 156 {
 157     HTABLE_INFO **h;
 158
 159     size |= 1;
 160
 161     table->data = h = (HTABLE_INFO **) mymalloc(size * sizeof(HTABLE_INFO *));
 162     table->size = size;
 163     table->used = 0;
 164
 165     while (size-- > 0)
 166         *h++ = 0;
 167 }
 168
 169 /* htable_create - create initial hash table */
 170
 171 HTABLE *htable_create(int size)
 172 {
 173     HTABLE *table;
 174
 175     table = (HTABLE *) mymalloc(sizeof(HTABLE));
 176     htable_size(table, size < 13 ? 13 : size);
 177     return (table);
 178 }
 179
 180 /* htable_grow - extend existing table */
 181
 182 static void htable_grow(HTABLE *table)
 183 {
 184     HTABLE_INFO *ht;
 185     HTABLE_INFO *next;
 186     unsigned old_size = table->size;
 187     HTABLE_INFO **h = table->data;
 188     HTABLE_INFO **old_entries = h;
 189
 190     htable_size(table, 2 * old_size);
 191
 192     while (old_size-- > 0) {
 193         for (ht = *h++; ht; ht = next) {
 194             next = ht->next;
 195             htable_link(table, ht);
 196         }
 197     }
 198     myfree((char *) old_entries);
 199 }
 200
 201 /* htable_enter - enter (key, value) pair */
 202
 203 HTABLE_INFO *htable_enter(HTABLE *table, const char *key, char *value)
 204 {
 205     HTABLE_INFO *ht;
 206
 207     if (table->used >= table->size)
 208         htable_grow(table);
 209     ht = (HTABLE_INFO *) mymalloc(sizeof(HTABLE_INFO));
 210     ht->key = mystrdup(key);
 211     ht->value = value;
 212     htable_link(table, ht);
 213     return (ht);
 214 }
 215
 216 /* htable_find - lookup value */
 217
 218 char   *htable_find(HTABLE *table, const char *key)
 219 {
 220     HTABLE_INFO *ht;
 221
 222 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
 223
 224     if (table)
 225         for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next)
 226             if (STREQ(key, ht->key))
 227                 return (ht->value);
 228     return (0);
 229 }
 230
 231 /* htable_locate - lookup entry */
 232
 233 HTABLE_INFO *htable_locate(HTABLE *table, const char *key)
 234 {
 235     HTABLE_INFO *ht;
 236
 237 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
 238
 239     if (table)
 240         for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next)
 241             if (STREQ(key, ht->key))
 242                 return (ht);
 243     return (0);
 244 }
 245
 246 /* htable_delete - delete one entry */
 247
 248 void    htable_delete(HTABLE *table, const char *key, void (*free_fn) (char *))
 249 {
 250     if (table) {
 251         HTABLE_INFO *ht;
 252         HTABLE_INFO **h = table->data + htable_hash(key, table->size);
 253
 254 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
 255
 256         for (ht = *h; ht; ht = ht->next) {
 257             if (STREQ(key, ht->key)) {
 258                 if (ht->next)
 259                     ht->next->prev = ht->prev;
 260                 if (ht->prev)
 261                     ht->prev->next = ht->next;
 262                 else
 263                     *h = ht->next;
 264                 table->used--;
 265                 myfree(ht->key);
 266                 if (free_fn && ht->value)
 267                     (*free_fn) (ht->value);
 268                 myfree((char *) ht);
 269                 return;
 270             }
 271         }
 272         msg_panic("htable_delete: unknown_key: \"%s\"", key);
 273     }
 274 }
 275
 276 /* htable_free - destroy hash table */
 277
 278 void    htable_free(HTABLE *table, void (*free_fn) (char *))
 279 {
 280     if (table) {
 281         unsigned i = table->size;
 282         HTABLE_INFO *ht;
 283         HTABLE_INFO *next;
 284         HTABLE_INFO **h = table->data;
 285
 286         while (i-- > 0) {
 287             for (ht = *h++; ht; ht = next) {
 288                 next = ht->next;
 289                 myfree(ht->key);
 290                 if (free_fn && ht->value)
 291                     (*free_fn) (ht->value);
 292                 myfree((char *) ht);
 293             }
 294         }
 295         myfree((char *) table->data);
 296         table->data = 0;
 297         myfree((char *) table);
 298     }
 299 }
 300
 301 /* htable_walk - iterate over hash table */
 302
 303 void    htable_walk(HTABLE *table, void (*action) (HTABLE_INFO *, char *),
 304                             char *ptr) {
 305     if (table) {
 306         unsigned i = table->size;
 307         HTABLE_INFO **h = table->data;
 308         HTABLE_INFO *ht;
 309
 310         while (i-- > 0)
 311             for (ht = *h++; ht; ht = ht->next)
 312                 (*action) (ht, ptr);
 313     }
 314 }
 315
 316 /* htable_list - list all table members */
 317
 318 HTABLE_INFO **htable_list(HTABLE *table)
 319 {
 320     HTABLE_INFO **list;
 321     HTABLE_INFO *member;
 322     int     count = 0;
 323     int     i;
 324
 325     if (table != 0) {
 326         list = (HTABLE_INFO **) mymalloc(sizeof(*list) * (table->used + 1));
 327         for (i = 0; i < table->size; i++)
 328             for (member = table->data[i]; member != 0; member = member->next)
 329                 list[count++] = member;
 330     } else {
 331         list = (HTABLE_INFO **) mymalloc(sizeof(*list));
 332     }
 333     list[count] = 0;
 334     return (list);
 335 }
 336
 337 #ifdef TEST
 338 #include <vstring_vstream.h>
 339 #include <myrand.h>
 340
 341 int main(int unused_argc, char **unused_argv)
 342 {
 343     VSTRING *buf = vstring_alloc(10);
 344     int     count = 0;
 345     HTABLE *hash;
 346     HTABLE_INFO **ht_info;
 347     HTABLE_INFO **ht;
 348     HTABLE_INFO *info;
 349     int     i;
 350     int     r;
 351
 352     /*
 353      * Load a large number of strings and delete them in a random order.
 354      */
 355     hash = htable_create(10);
 356     while (vstring_get(buf, VSTREAM_IN) != VSTREAM_EOF)
 357         htable_enter(hash, vstring_str(buf), CAST_INT_TO_CHAR_PTR(count++));
 358     ht_info = htable_list(hash);
 359     for (i = 0; i < hash->used; i++) {
 360         r = myrand() % hash->used;
 361         info = ht_info[i];
 362         ht_info[i] = ht_info[r];
 363         ht_info[r] = info;
 364     }
 365     for (ht = ht_info; *ht; ht++)
 366         htable_delete(hash, ht[0]->key, (void (*) (char *)) 0);
 367     if (hash->used > 0)
 368         msg_panic("%d entries not deleted", hash->used);
 369     myfree((char *) ht_info);
 370     htable_free(hash, (void (*) (char *)) 0);
 371     vstring_free(buf);
 372     return (0);
 373 }
 374
 375 #endif