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

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