cbtcommon/hash.c

   1 /*
   2  * Copyright 2001, 2002, 2003 David Mansfield and Cobite, Inc.
   3  * See COPYING file for license information
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9
  10 #include "debug.h"
  11 #include "hash.h"
  12 #include "rcsid.h"
  13
  14 RCSID("$Id: hash.c,v 1.6 2003/05/07 15:42:38 david Exp $");
  15
  16 #define HASH_CONST 37
  17
  18 static unsigned int hash_string(const char *);
  19 static struct hash_entry *scan_list(struct list_head *, const char *);
  20 static struct hash_entry *get_hash_entry(struct hash_table *tbl, const char *key);
  21
  22 struct hash_table *create_hash_table(unsigned int sz)
  23 {
  24     struct hash_table *tbl;
  25     unsigned int i;
  26
  27     tbl = (struct hash_table *)malloc(sizeof(*tbl) + sz*sizeof(struct list_head));
  28
  29     if (!tbl)
  30     {
  31         debug(DEBUG_APPERROR, "malloc for hash_table failed");
  32         return NULL;
  33     }
  34
  35     tbl->ht_size  = sz;
  36     tbl->ht_lists = (struct list_head *)(tbl + 1);
  37     tbl->iterator = 0;
  38
  39     for (i = 0; i < sz; i++)
  40         INIT_LIST_HEAD(&tbl->ht_lists[i]);
  41
  42     return tbl;
  43 }
  44
  45 void destroy_hash_table(struct hash_table *tbl, void (*delete_obj)(void *))
  46 {
  47     struct list_head  *head, *next, *tmp;
  48     struct hash_entry *entry;
  49     int i;
  50
  51     for (i = 0; i < tbl->ht_size; i++)
  52     {
  53         head = &tbl->ht_lists[i];
  54         next = head->next;
  55
  56         while (next != head)
  57         {
  58             tmp = next->next;
  59             entry = list_entry(next, struct hash_entry, he_list);
  60             if (delete_obj)
  61                 delete_obj(entry->he_obj);
  62             free(entry);
  63
  64             next = tmp;
  65         }
  66     }
  67
  68     free(tbl);
  69 }
  70
  71 /* FIXME: there is no way for the user of this to determine the difference
  72  *        between a put to a new key value and a malloc failure
  73  */
  74 void *put_hash_object(struct hash_table *tbl, const char *key, void *obj)
  75 {
  76     void * retval;
  77     put_hash_object_ex(tbl, key, obj, HT_KEYCOPY, NULL, &retval);
  78     return retval;
  79 }
  80
  81 static struct hash_entry *get_hash_entry(struct hash_table *tbl, const char *key)
  82 {
  83     struct list_head  *head;
  84     struct hash_entry *entry;
  85     unsigned int hash;
  86
  87     hash  = hash_string(key) % tbl->ht_size;
  88     head  = &tbl->ht_lists[hash];
  89     entry = scan_list(head, key);
  90
  91     return entry;
  92 }
  93
  94 void *get_hash_object(struct hash_table *tbl, const char *key)
  95 {
  96     struct hash_entry *entry = get_hash_entry(tbl, key);
  97     return (entry) ? entry->he_obj : NULL;
  98 }
  99
 100 void *remove_hash_object(struct hash_table *tbl, const char *key)
 101 {
 102     struct hash_entry *entry = get_hash_entry(tbl, key);
 103     void *retval = NULL;
 104
 105     if (entry)
 106     {
 107         list_del(&entry->he_list);
 108         retval = entry->he_obj;
 109         free(entry);
 110     }
 111
 112     return retval;
 113 }
 114
 115 static unsigned int hash_string(register const char *key)
 116 {
 117     register unsigned int hash = 0;
 118
 119     while(*key)
 120         hash = hash * HASH_CONST + *key++;
 121
 122     return hash;
 123 }
 124
 125 static struct hash_entry *scan_list(struct list_head *head, const char *key)
 126 {
 127     struct list_head  *next = head->next;
 128     struct hash_entry *entry;
 129
 130     while (next != head)
 131     {
 132         entry = list_entry(next, struct hash_entry, he_list);
 133         if (strcmp(entry->he_key, key) == 0)
 134             return entry;
 135
 136         next = next->next;
 137     }
 138
 139     return NULL;
 140 }
 141
 142 void reset_hash_iterator(struct hash_table *tbl)
 143 {
 144     tbl->iterator = 0;
 145     tbl->iterator_ptr = NULL;
 146 }
 147
 148 struct hash_entry *next_hash_entry(struct hash_table *tbl)
 149 {
 150     while( tbl->iterator < tbl->ht_size )
 151     {
 152         struct list_head *head = &tbl->ht_lists[ tbl->iterator ];
 153
 154         if( tbl->iterator_ptr == NULL )
 155             tbl->iterator_ptr = head->next;
 156
 157         if( tbl->iterator_ptr != head )
 158         {
 159             struct list_head *tmp = tbl->iterator_ptr;
 160             tbl->iterator_ptr = tbl->iterator_ptr->next;
 161             return( list_entry( tmp, struct hash_entry, he_list ) );
 162         }
 163
 164         else
 165         {
 166             tbl->iterator++;
 167             tbl->iterator_ptr = NULL;
 168         }
 169     }
 170
 171     return( NULL );
 172 }
 173
 174 int put_hash_object_ex(struct hash_table *tbl, const char *key, void *obj, int copy,
 175                        char ** oldkey, void ** oldobj)
 176 {
 177     struct list_head *head;
 178     struct hash_entry *entry;
 179     unsigned int hash;
 180     int retval = 0;
 181
 182     /* FIXME: how can get_hash_entry be changed to be usable here?
 183      * we need the value of head later if the entry is not found...
 184      */
 185     hash  = hash_string(key) % tbl->ht_size;
 186     head  = &tbl->ht_lists[hash];
 187     entry = scan_list(head, key);
 188
 189     if (entry)
 190     {
 191         if (oldkey)
 192             *oldkey = entry->he_key;
 193         if (oldobj)
 194             *oldobj = entry->he_obj;
 195
 196         /* if 'copy' is set, then we already have an exact
 197          * private copy of the key (by definition of having
 198          * found the match in scan_list) so we do nothing.
 199          * if !copy, then we can simply assign the new
 200          * key
 201          */
 202         if (!copy)
 203             entry->he_key = (char*)key; /* discard the const */
 204         entry->he_obj = obj;
 205     }
 206     else
 207     {
 208         size_t s = sizeof(*entry);
 209
 210         if (oldkey)
 211             *oldkey = NULL;
 212         if (oldobj)
 213             *oldobj = NULL;
 214
 215         if (copy)
 216             s +=  strlen(key) + 1;
 217
 218         entry = (struct hash_entry *)malloc(s);
 219
 220         if (!entry)
 221         {
 222             debug(DEBUG_APPERROR,"malloc failed put_hash_object key='%s'",key);
 223             retval = -1;
 224         }
 225         else
 226         {
 227             if (copy)
 228             {
 229                 entry->he_key = (char *)(entry + 1);
 230                 strcpy(entry->he_key, key);
 231             }
 232             else
 233             {
 234                 entry->he_key = (char*)key; /* discard the const */
 235             }
 236
 237             entry->he_obj = obj;
 238
 239             list_add(&entry->he_list, head);
 240         }
 241     }
 242
 243     return retval;
 244 }
 245
 246 void destroy_hash_table_ex(struct hash_table *tbl,
 247                            void (*delete_entry)(const void *, char *, void *),
 248                            const void * cookie)
 249 {
 250     struct list_head  *head, *next, *tmp;
 251     struct hash_entry *entry;
 252     int i;
 253
 254     for (i = 0; i < tbl->ht_size; i++)
 255     {
 256         head = &tbl->ht_lists[i];
 257         next = head->next;
 258
 259         while (next != head)
 260         {
 261             tmp = next->next;
 262             entry = list_entry(next, struct hash_entry, he_list);
 263             if (delete_entry)
 264                 delete_entry(cookie, entry->he_key, entry->he_obj);
 265             free(entry);
 266
 267             next = tmp;
 268         }
 269     }
 270
 271     free(tbl);
 272 }