Utilities/cmtar/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 <@LISTHASH_PREFIX@/config.h>
  16 #include <@LISTHASH_PREFIX@/compat.h>
  17
  18 #include <@LISTHASH_PREFIX@/@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