cde/lib/csa/hash.c

   1 /* $XConsortium: hash.c /main/1 1996/04/21 19:23:21 drk $ */
   2 /*
   3  *  (c) Copyright 1993, 1994 Hewlett-Packard Company
   4  *  (c) Copyright 1993, 1994 International Business Machines Corp.
   5  *  (c) Copyright 1993, 1994 Novell, Inc.
   6  *  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
   7  */
   8
   9 /*
  10
  11 Synopsis:
  12
  13            #include "hash.h"
  14
  15            void * _DtCmMakeHash(int size)
  16
  17            void * _DtCmMakeIHash(int size)
  18
  19            void ** _DtCmGetHash(void * tbl, unsigned char * key)
  20
  21            void ** _DtCmFindHash(void * tbl,unsigned char * key)
  22
  23            void ** _DtCmDelHash(void * tbl, unsigned char * key)
  24
  25            int _DtCmOperateHash(void * tbl, void (*op_func)(), void * usr_arg)
  26
  27            void _DtCmDestroyHash(void * tbl, int (*des_func)(), void * usr_arg)
  28
  29
  30  Description:
  31
  32    These routines provide a general purpose hash table facility that
  33 supports multiple open hash tables.  Each entry in the table consists of a
  34 key and a data ptr.  The key is a null terminated character string, while
  35 the data ptr is opaque. Since all the entries are maintained in a doubly
  36 linked lists, deletions and operations on entire table execute very quickly.
  37 This make these routines suitable for use when the tables may be very ephemeral.
  38
  39   _DtCmMakeHash returns a pointer to the created table.  The size argument
  40 indicate the number of buckets the routine is to allocate.  This should be ~
  41 the max number of items expected in the table for maximum performance....
  42 but /2 or /3 should still be ok.  Note that for maximum efficiency the hash
  43 table size should be a prime number (a side effect of the hash alorithm).
  44
  45   _DtCmMakeIHash performs the same function as _DtCmMakeHash, except that the hash
  46 routines will use the key arguments as arbitrary integers rather than strings.
  47
  48   _DtCmGetHash searches the specified hash table tbl for an entry with the
  49 specified key.  If the entry does not exist, it is created with a NULL data
  50 ptr.  The routine returns a ptr to the area where the data ptr is (can be)
  51 stored.
  52
  53   _DtCmFindHash searchs the table for an entry with the specified key.  If the
  54 entry is found, the address of the data pointer associated with the key is
  55 returned.  If no such entry exists, the routine returns NULL.
  56
  57   _DtCmDelHash deletes the specified table entry and returns the associated data
  58 ptr.  If the entry did not exist ( or the data ptr was NULL), the routine
  59 returns NULL.
  60
  61   _DtCmOperateHash calls the routine pointed to by op_func once for each entry
  62 in tbl, with three arguments: the data ptr, the usr_arg ptr and a ptr to the
  63 key for that entry (which should NOT be altered).  This is useful for
  64 transversing a hash table quickly and operating on the entries. Note that
  65 the order of the traversal of the hash table is the reverse order of
  66 insertion.
  67
  68   _DtCmDestroyHash destroys the specified hash table after operating on it
  69 with the specified des_func function as described for _DtCmOperateHash.  All storage
  70 allocated by the hash routines is reclaimed.
  71
  72 Author:  Bart Smaalders 1/89
  73
  74
  75 */
  76 #include <EUSCompat.h>
  77 #include <stdio.h> /* grab NULL define */
  78 #include <stdlib.h>
  79 #include <string.h>
  80 #include "hash.h"
  81
  82 static int    hash_string();
  83
  84 typedef struct hash_entry {
  85   struct hash_entry
  86     * next_entry,
  87     * right_entry,
  88     * left_entry;
  89   unsigned char *               key;
  90   void          *               data;
  91 } hash_entry;
  92
  93 typedef struct hash {
  94   int           size;
  95   hash_entry ** table;
  96   hash_entry *  start;
  97   enum hash_type { String_Key = 0 , Integer_Key = 1} hash_type;
  98 } hash;
  99
 100
 101 void * _DtCmMakeHash(int size)
 102 {
 103   hash * ptr;
 104
 105   ptr        = (hash *) malloc(sizeof(*ptr));
 106   ptr->size  =   size;
 107   ptr->table = (hash_entry **) malloc( (unsigned) (sizeof(hash_entry *) * size) );
 108   (void)memset((char *) ptr->table, (char) 0, sizeof(hash_entry *)*size);
 109   ptr->start = NULL;
 110   ptr->hash_type = String_Key;
 111   return((void*)ptr);
 112 }
 113
 114 void ** _DtCmGetHash(void * t, const unsigned char * key)
 115 {
 116   hash * tbl = (hash *) t;
 117   register int bucket;
 118   register hash_entry * tmp;
 119   hash_entry * new;
 120
 121   if(tbl->hash_type == String_Key)
 122     tmp = tbl->table[bucket = hash_string(key, tbl->size)];
 123   else
 124     tmp = tbl->table[bucket = abs((long)key) % tbl->size];
 125
 126   if(tbl->hash_type == String_Key)
 127     while(tmp!=NULL)
 128       {
 129         if(strcmp((char *)tmp->key, (char *)key)==0)
 130           return(&tmp->data);
 131         tmp = tmp->next_entry;
 132       }
 133   else
 134     while(tmp!=NULL)
 135       {
 136         if(tmp->key == key)
 137           return(&tmp->data);
 138         tmp = tmp->next_entry;
 139       }
 140
 141   /*
 142     not found....
 143     insert new entry into bucket...
 144     */
 145
 146   new = (hash_entry *) malloc(sizeof(*new));
 147   new->key = (unsigned char *)((tbl->hash_type == String_Key)?(unsigned char *)strdup((char *)key):key);
 148   /*
 149     hook into chain from tbl...
 150     */
 151   new->right_entry = NULL;
 152   new->left_entry = tbl->start;
 153   tbl->start = new;
 154   /*
 155     hook into bucket chain
 156     */
 157   new->next_entry = tbl->table[bucket];
 158   tbl->table[bucket] = new;
 159   new->data = NULL;   /* so we know that it is new */
 160   return((void*)& new->data);
 161 }
 162
 163 void ** _DtCmFindHash(void * t, const unsigned char * key)
 164 {
 165   register hash * tbl = (hash *) t;
 166   register hash_entry * tmp;
 167
 168   if(tbl->hash_type == String_Key)
 169     {
 170       tmp = tbl->table[hash_string(key, tbl->size)];
 171       for(;tmp!=NULL; tmp = tmp->next_entry)
 172         if(!strcmp((char *)tmp->key, (char *)key))
 173           return((void *)&tmp->data);
 174     }
 175   else
 176     {
 177       tmp = tbl->table[abs((long)key) % tbl->size];
 178       for(;tmp!=NULL; tmp = tmp->next_entry)
 179         if(tmp->key == key)
 180           return((void *)&tmp->data);
 181     }
 182
 183   return(NULL);
 184 }
 185
 186 void _DtCmDestroyHash(void * t, int (*ptr)(), void * usr_arg)
 187 {
 188   hash * tbl = (hash *) t;
 189   register hash_entry * tmp = tbl->start, * prev;
 190
 191   while(tmp)
 192     {
 193       if(ptr)
 194         (*ptr)(tmp->data,usr_arg, tmp->key);
 195
 196       if(tbl->hash_type == String_Key)
 197         free(tmp->key);
 198       prev = tmp;
 199       tmp = tmp->left_entry;
 200       free((char *)prev);
 201     }
 202   free((char *)tbl->table);
 203   free(tbl);
 204 }
 205
 206 static int hash_string(s,modulo)
 207 register char *s;
 208 int modulo;
 209 {
 210         register unsigned result = 0;
 211         register int i=1;
 212
 213         while(*s!=0)
 214           result += (*s++ << i++);
 215
 216         return(result % modulo);
 217 }
 218