cde/lib/csa/hash.c

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