listhash/hash.c.in

   1 /* @configure_input@ */
   2
   3 /*
   4 **  Copyright 1998-2002 University of Illinois Board of Trustees
   5 **  Copyright 1998-2002 Mark D. Roth
   6 **  All rights reserved.
   7 **
   8 **  @LISTHASH_PREFIX@_hash.c - hash table routines
   9 **
  10 **  Mark D. Roth <roth@uiuc.edu>
  11 **  Campus Information Technologies and Educational Services
  12 **  University of Illinois at Urbana-Champaign
  13 */
  14
  15 #include <config.h>
  16 #include <compat.h>
  17
  18 #include <@LISTHASH_PREFIX@_listhash.h>
  19
  20 #include <stdio.h>
  21 #include <errno.h>
  22
  23 #ifdef STDC_HEADERS
  24 # include <stdlib.h>
  25 #endif
  26
  27
  28 /*
  29 ** @LISTHASH_PREFIX@_hashptr_reset() - reset a hash pointer
  30 */
  31 void
  32 @LISTHASH_PREFIX@_hashptr_reset(@LISTHASH_PREFIX@_hashptr_t *hp)
  33 {
  34         @LISTHASH_PREFIX@_listptr_reset(&(hp->node));
  35         hp->bucket = -1;
  36 }
  37
  38
  39 /*
  40 ** @LISTHASH_PREFIX@_hashptr_data() - retrieve the data being pointed to
  41 */
  42 void *
  43 @LISTHASH_PREFIX@_hashptr_data(@LISTHASH_PREFIX@_hashptr_t *hp)
  44 {
  45         return @LISTHASH_PREFIX@_listptr_data(&(hp->node));
  46 }
  47
  48
  49 /*
  50 ** @LISTHASH_PREFIX@_str_hashfunc() - default hash function, optimized for
  51 **                                    7-bit strings
  52 */
  53 unsigned int
  54 @LISTHASH_PREFIX@_str_hashfunc(char *key, unsigned int num_buckets)
  55 {
  56 #if 0
  57         register unsigned result = 0;
  58         register int i;
  59
  60         if (key == NULL)
  61                 return 0;
  62
  63         for (i = 0; *key != '\0' && i < 32; i++)
  64                 result = result * 33U + *key++;
  65
  66         return (result % num_buckets);
  67 #else
  68         if (key == NULL)
  69                 return 0;
  70
  71         return (key[0] % num_buckets);
  72 #endif
  73 }
  74
  75
  76 /*
  77 ** @LISTHASH_PREFIX@_hash_nents() - return number of elements from hash
  78 */
  79 unsigned int
  80 @LISTHASH_PREFIX@_hash_nents(@LISTHASH_PREFIX@_hash_t *h)
  81 {
  82         return h->nents;
  83 }
  84
  85
  86 /*
  87 ** @LISTHASH_PREFIX@_hash_new() - create a new hash
  88 */
  89 @LISTHASH_PREFIX@_hash_t *
  90 @LISTHASH_PREFIX@_hash_new(int num, @LISTHASH_PREFIX@_hashfunc_t hashfunc)
  91 {
  92         @LISTHASH_PREFIX@_hash_t *hash;
  93
  94         hash = (@LISTHASH_PREFIX@_hash_t *)calloc(1, sizeof(@LISTHASH_PREFIX@_hash_t));
  95         if (hash == NULL)
  96                 return NULL;
  97         hash->numbuckets = num;
  98         if (hashfunc != NULL)
  99                 hash->hashfunc = hashfunc;
 100         else
 101                 hash->hashfunc = (@LISTHASH_PREFIX@_hashfunc_t)@LISTHASH_PREFIX@_str_hashfunc;
 102
 103         hash->table = (@LISTHASH_PREFIX@_list_t **)calloc(num, sizeof(@LISTHASH_PREFIX@_list_t *));
 104         if (hash->table == NULL)
 105         {
 106                 free(hash);
 107                 return NULL;
 108         }
 109
 110         return hash;
 111 }
 112
 113
 114 /*
 115 ** @LISTHASH_PREFIX@_hash_next() - get next element in hash
 116 ** returns:
 117 **      1                       data found
 118 **      0                       end of list
 119 */
 120 int
 121 @LISTHASH_PREFIX@_hash_next(@LISTHASH_PREFIX@_hash_t *h,
 122                             @LISTHASH_PREFIX@_hashptr_t *hp)
 123 {
 124 #ifdef DS_DEBUG
 125         printf("==> @LISTHASH_PREFIX@_hash_next(h=0x%lx, hp={%d,0x%lx})\n",
 126                h, hp->bucket, hp->node);
 127 #endif
 128
 129         if (hp->bucket >= 0 && hp->node != NULL &&
 130             @LISTHASH_PREFIX@_list_next(h->table[hp->bucket], &(hp->node)) != 0)
 131         {
 132 #ifdef DS_DEBUG
 133                 printf("    @LISTHASH_PREFIX@_hash_next(): found additional "
 134                        "data in current bucket (%d), returing 1\n",
 135                        hp->bucket);
 136 #endif
 137                 return 1;
 138         }
 139
 140 #ifdef DS_DEBUG
 141         printf("    @LISTHASH_PREFIX@_hash_next(): done with bucket %d\n",
 142                hp->bucket);
 143 #endif
 144
 145         for (hp->bucket++; hp->bucket < h->numbuckets; hp->bucket++)
 146         {
 147 #ifdef DS_DEBUG
 148                 printf("    @LISTHASH_PREFIX@_hash_next(): "
 149                        "checking bucket %d\n", hp->bucket);
 150 #endif
 151                 hp->node = NULL;
 152                 if (h->table[hp->bucket] != NULL &&
 153                     @LISTHASH_PREFIX@_list_next(h->table[hp->bucket],
 154                                                 &(hp->node)) != 0)
 155                 {
 156 #ifdef DS_DEBUG
 157                         printf("    @LISTHASH_PREFIX@_hash_next(): "
 158                                "found data in bucket %d, returing 1\n",
 159                                hp->bucket);
 160 #endif
 161                         return 1;
 162                 }
 163         }
 164
 165         if (hp->bucket == h->numbuckets)
 166         {
 167 #ifdef DS_DEBUG
 168                 printf("    @LISTHASH_PREFIX@_hash_next(): hash pointer "
 169                        "wrapped to 0\n");
 170 #endif
 171                 hp->bucket = -1;
 172                 hp->node = NULL;
 173         }
 174
 175 #ifdef DS_DEBUG
 176         printf("<== @LISTHASH_PREFIX@_hash_next(): no more data, "
 177                "returning 0\n");
 178 #endif
 179         return 0;
 180 }
 181
 182
 183 /*
 184 ** @LISTHASH_PREFIX@_hash_del() - delete an entry from the hash
 185 ** returns:
 186 **      0                       success
 187 **      -1 (and sets errno)     failure
 188 */
 189 int
 190 @LISTHASH_PREFIX@_hash_del(@LISTHASH_PREFIX@_hash_t *h,
 191                            @LISTHASH_PREFIX@_hashptr_t *hp)
 192 {
 193         if (hp->bucket < 0
 194             || hp->bucket >= h->numbuckets
 195             || h->table[hp->bucket] == NULL
 196             || hp->node == NULL)
 197         {
 198                 errno = EINVAL;
 199                 return -1;
 200         }
 201
 202         @LISTHASH_PREFIX@_list_del(h->table[hp->bucket], &(hp->node));
 203         h->nents--;
 204         return 0;
 205 }
 206
 207
 208 /*
 209 ** @LISTHASH_PREFIX@_hash_empty() - empty the hash
 210 */
 211 void
 212 @LISTHASH_PREFIX@_hash_empty(@LISTHASH_PREFIX@_hash_t *h, @LISTHASH_PREFIX@_freefunc_t freefunc)
 213 {
 214         int i;
 215
 216         for (i = 0; i < h->numbuckets; i++)
 217                 if (h->table[i] != NULL)
 218                         @LISTHASH_PREFIX@_list_empty(h->table[i], freefunc);
 219
 220         h->nents = 0;
 221 }
 222
 223
 224 /*
 225 ** @LISTHASH_PREFIX@_hash_free() - delete all of the nodes in the hash
 226 */
 227 void
 228 @LISTHASH_PREFIX@_hash_free(@LISTHASH_PREFIX@_hash_t *h, @LISTHASH_PREFIX@_freefunc_t freefunc)
 229 {
 230         int i;
 231
 232         for (i = 0; i < h->numbuckets; i++)
 233                 if (h->table[i] != NULL)
 234                         @LISTHASH_PREFIX@_list_free(h->table[i], freefunc);
 235
 236         free(h->table);
 237         free(h);
 238 }
 239
 240
 241 /*
 242 ** @LISTHASH_PREFIX@_hash_search() - iterative search for an element in a hash
 243 ** returns:
 244 **      1                       match found
 245 **      0                       no match
 246 */
 247 int
 248 @LISTHASH_PREFIX@_hash_search(@LISTHASH_PREFIX@_hash_t *h,
 249                               @LISTHASH_PREFIX@_hashptr_t *hp, void *data,
 250                               @LISTHASH_PREFIX@_matchfunc_t matchfunc)
 251 {
 252         while (@LISTHASH_PREFIX@_hash_next(h, hp) != 0)
 253                 if ((*matchfunc)(data, @LISTHASH_PREFIX@_listptr_data(&(hp->node))) != 0)
 254                         return 1;
 255
 256         return 0;
 257 }
 258
 259
 260 /*
 261 ** @LISTHASH_PREFIX@_hash_getkey() - hash-based search for an element in a hash
 262 ** returns:
 263 **      1                       match found
 264 **      0                       no match
 265 */
 266 int
 267 @LISTHASH_PREFIX@_hash_getkey(@LISTHASH_PREFIX@_hash_t *h,
 268                               @LISTHASH_PREFIX@_hashptr_t *hp, void *key,
 269                               @LISTHASH_PREFIX@_matchfunc_t matchfunc)
 270 {
 271 #ifdef DS_DEBUG
 272         printf("==> @LISTHASH_PREFIX@_hash_getkey(h=0x%lx, hp={%d,0x%lx}, "
 273                "key=0x%lx, matchfunc=0x%lx)\n",
 274                h, hp->bucket, hp->node, key, matchfunc);
 275 #endif
 276
 277         if (hp->bucket == -1)
 278         {
 279                 hp->bucket = (*(h->hashfunc))(key, h->numbuckets);
 280 #ifdef DS_DEBUG
 281                 printf("    @LISTHASH_PREFIX@_hash_getkey(): hp->bucket "
 282                        "set to %d\n", hp->bucket);
 283 #endif
 284         }
 285
 286         if (h->table[hp->bucket] == NULL)
 287         {
 288 #ifdef DS_DEBUG
 289                 printf("    @LISTHASH_PREFIX@_hash_getkey(): no list "
 290                        "for bucket %d, returning 0\n", hp->bucket);
 291 #endif
 292                 hp->bucket = -1;
 293                 return 0;
 294         }
 295
 296 #ifdef DS_DEBUG
 297         printf("<== @LISTHASH_PREFIX@_hash_getkey(): "
 298                "returning @LISTHASH_PREFIX@_list_search()\n");
 299 #endif
 300         return @LISTHASH_PREFIX@_list_search(h->table[hp->bucket], &(hp->node),
 301                                              key, matchfunc);
 302 }
 303
 304
 305 /*
 306 ** @LISTHASH_PREFIX@_hash_add() - add an element to the hash
 307 ** returns:
 308 **      0                       success
 309 **      -1 (and sets errno)     failure
 310 */
 311 int
 312 @LISTHASH_PREFIX@_hash_add(@LISTHASH_PREFIX@_hash_t *h, void *data)
 313 {
 314         int bucket, i;
 315
 316 #ifdef DS_DEBUG
 317         printf("==> @LISTHASH_PREFIX@_hash_add(h=0x%lx, data=0x%lx)\n",
 318                h, data);
 319 #endif
 320
 321         bucket = (*(h->hashfunc))(data, h->numbuckets);
 322 #ifdef DS_DEBUG
 323         printf("    @LISTHASH_PREFIX@_hash_add(): inserting in bucket %d\n",
 324                bucket);
 325 #endif
 326         if (h->table[bucket] == NULL)
 327         {
 328 #ifdef DS_DEBUG
 329                 printf("    @LISTHASH_PREFIX@_hash_add(): creating new list\n");
 330 #endif
 331                 h->table[bucket] = @LISTHASH_PREFIX@_list_new(LIST_QUEUE, NULL);
 332         }
 333
 334 #ifdef DS_DEBUG
 335         printf("<== @LISTHASH_PREFIX@_hash_add(): "
 336                "returning @LISTHASH_PREFIX@_list_add()\n");
 337 #endif
 338         i = @LISTHASH_PREFIX@_list_add(h->table[bucket], data);
 339         if (i == 0)
 340                 h->nents++;
 341         return i;
 342 }
 343
 344