src/chash.c

   1
   2 /*
   3  * libEtPan! -- a mail stuff library
   4  *
   5  * chash - Implements generic hash tables.
   6  *
   7  * Copyright (c) 1999-2000, Gaël Roualland <gael.roualland@iname.com>
   8  * interface changes - 2002 - DINH Viet Hoa
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the libEtPan! project nor the names of its
  20  *    contributors may be used to endorse or promote products derived
  21  *    from this software without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 #include <stdlib.h>
  37 #include <string.h>
  38
  39 #include "chash.h"
  40
  41 /* This defines the maximum (average) number of entries per bucket.
  42    The hash is resized everytime inserting an entry makes the
  43    average go over that value. */
  44 #define CHASH_MAXDEPTH    3
  45
  46 static inline unsigned int chash_func(const char * key, int len) {
  47   register unsigned int c = 0, t;
  48   register const char * k = key;
  49
  50   while (len--) {
  51     c += (c << 4) + *k++;
  52     if ((t = c & 0xF0000000)) {
  53       c ^= t >> 24;
  54       c ^= t;
  55     }
  56   }
  57   return c;
  58 }
  59
  60 static inline char * chash_dup(const char * data, int len)
  61 {
  62   char * r;
  63
  64   r = (char *) malloc(len * sizeof(char));
  65   if (!r)
  66     return NULL;
  67   memcpy(r, data, len * sizeof(char));
  68   return r;
  69 }
  70
  71 chash * chash_new(int size, int flags)
  72 {
  73   chash * h;
  74
  75   h = (chash *) malloc(sizeof(chash));
  76   if (h == NULL)
  77     return NULL;
  78
  79   h->count = 0;
  80   h->cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
  81   if (h->cells == NULL) {
  82     free(h);
  83     return NULL;
  84   }
  85   h->size = size;
  86   h->copykey = flags & CHASH_COPYKEY;
  87   h->copyvalue = flags & CHASH_COPYVALUE;
  88
  89   return h;
  90 }
  91
  92 int chash_get(chash * hash,
  93               chashdatum * key, chashdatum * result)
  94 {
  95   unsigned int func;
  96   chashiter * iter;
  97
  98   func = chash_func(key->data, key->len);
  99
 100   /* look for the key in existing cells */
 101   iter = hash->cells[func % hash->size];
 102   while (iter) {
 103     if (iter->key.len == key->len && iter->func == func
 104         && !memcmp(iter->key.data, key->data, key->len)) {
 105       * result = iter->value; /* found */
 106
 107       return 0;
 108     }
 109     iter = iter->next;
 110   }
 111
 112   return -1;
 113 }
 114
 115 int chash_set(chash * hash,
 116               chashdatum * key,
 117               chashdatum * value,
 118               chashdatum * oldvalue)
 119 {
 120   unsigned int func, indx;
 121   chashiter * iter, * cell;
 122   int r;
 123
 124   if (hash->count > hash->size * CHASH_MAXDEPTH) {
 125     r = chash_resize(hash, (hash->count / CHASH_MAXDEPTH) * 2 + 1);
 126     if (r < 0)
 127       goto err;
 128   }
 129
 130   func = chash_func(key->data, key->len);
 131   indx = func % hash->size;
 132
 133   /* look for the key in existing cells */
 134   iter = hash->cells[indx];
 135   while (iter) {
 136     if (iter->key.len == key->len && iter->func == func
 137         && !memcmp(iter->key.data, key->data, key->len)) {
 138       /* found, replacing entry */
 139       if (hash->copyvalue) {
 140         char * data;
 141
 142         data = chash_dup(value->data, value->len);
 143         if (data == NULL)
 144           goto err;
 145
 146         free(iter->value.data);
 147         iter->value.data = data;
 148         iter->value.len = value->len;
 149       } else {
 150         if (oldvalue != NULL) {
 151           oldvalue->data = iter->value.data;
 152           oldvalue->len = iter->value.len;
 153         }
 154         iter->value.data = value->data;
 155         iter->value.len = value->len;
 156       }
 157       if (!hash->copykey)
 158         iter->key.data = key->data;
 159
 160       if (oldvalue != NULL) {
 161         oldvalue->data = value->data;
 162         oldvalue->len = value->len;
 163       }
 164
 165       return 0;
 166     }
 167     iter = iter->next;
 168   }
 169
 170   if (oldvalue != NULL) {
 171     oldvalue->data = NULL;
 172     oldvalue->len = 0;
 173   }
 174
 175   /* not found, adding entry */
 176   cell = (struct chashcell *) malloc(sizeof(struct chashcell));
 177   if (cell == NULL)
 178     goto err;
 179
 180   if (hash->copykey) {
 181     cell->key.data = chash_dup(key->data, key->len);
 182     if (cell->key.data == NULL)
 183       goto free;
 184   }
 185   else
 186     cell->key.data = key->data;
 187
 188   cell->key.len = key->len;
 189   if (hash->copyvalue) {
 190     cell->value.data = chash_dup(value->data, value->len);
 191     if (cell->value.data == NULL)
 192       goto free_key_data;
 193   }
 194   else
 195     cell->value.data = value->data;
 196
 197   cell->value.len = value->len;
 198   cell->func = func;
 199   cell->next = hash->cells[indx];
 200   hash->cells[indx] = cell;
 201   hash->count++;
 202
 203   return 0;
 204
 205  free_key_data:
 206   if (hash->copykey)
 207     free(cell->key.data);
 208  free:
 209   free(cell);
 210  err:
 211   return -1;
 212 }
 213
 214 int chash_delete(chash * hash, chashdatum * key, chashdatum * oldvalue)
 215 {
 216   /*  chashdatum result = { NULL, TRUE }; */
 217   unsigned int func, indx;
 218   chashiter * iter, * old;
 219
 220   /*
 221   if (!keylen)
 222     keylen = strlen(key) + 1;
 223   */
 224
 225   func = chash_func(key->data, key->len);
 226   indx = func % hash->size;
 227
 228   /* look for the key in existing cells */
 229   old = NULL;
 230   iter = hash->cells[indx];
 231   while (iter) {
 232     if (iter->key.len == key->len && iter->func == func
 233         && !memcmp(iter->key.data, key->data, key->len)) {
 234       /* found, deleting */
 235       if (old)
 236         old->next = iter->next;
 237       else
 238         hash->cells[indx] = iter->next;
 239       if (hash->copykey)
 240         free(iter->key.data);
 241       if (hash->copyvalue)
 242         free(iter->value.data);
 243       else {
 244         if (oldvalue != NULL) {
 245           oldvalue->data = iter->value.data;
 246           oldvalue->len = iter->value.len;
 247         }
 248       }
 249       free(iter);
 250       hash->count--;
 251       return 0;
 252     }
 253     old = iter;
 254     iter = iter->next;
 255   }
 256
 257   return -1; /* not found */
 258 }
 259
 260 void chash_free(chash * hash) {
 261   int indx;
 262   chashiter * iter, * next;
 263
 264   /* browse the hash table */
 265   for(indx = 0; indx < hash->size; indx++) {
 266     iter = hash->cells[indx];
 267     while (iter) {
 268       next = iter->next;
 269       if (hash->copykey)
 270         free(iter->key.data);
 271       if (hash->copyvalue)
 272         free(iter->value.data);
 273       free(iter);
 274       iter = next;
 275     }
 276   }
 277   free(hash->cells);
 278   free(hash);
 279 }
 280
 281 void chash_clear(chash * hash) {
 282   int indx;
 283   chashiter * iter, * next;
 284
 285   /* browse the hash table */
 286   for(indx = 0; indx < hash->size; indx++) {
 287     iter = hash->cells[indx];
 288     while (iter) {
 289       next = iter->next;
 290       if (hash->copykey)
 291         free(iter->key.data);
 292       if (hash->copyvalue)
 293         free(iter->value.data);
 294       free(iter);
 295       iter = next;
 296     }
 297   }
 298   memset(hash->cells, 0, hash->size * sizeof(* hash->cells));
 299   hash->count = 0;
 300 }
 301
 302 chashiter * chash_begin(chash * hash) {
 303   chashiter * iter;
 304   int indx = 0;
 305
 306   iter = hash->cells[0];
 307   while(!iter) {
 308     indx++;
 309     if (indx >= hash->size)
 310       return NULL;
 311     iter = hash->cells[indx];
 312   }
 313   return iter;
 314 }
 315
 316 chashiter * chash_next(chash * hash, chashiter * iter) {
 317   int indx;
 318
 319   if (!iter)
 320     return NULL;
 321
 322   indx = iter->func % hash->size;
 323   iter = iter->next;
 324
 325   while(!iter) {
 326     indx++;
 327     if (indx >= hash->size)
 328       return NULL;
 329     iter = hash->cells[indx];
 330   }
 331   return iter;
 332 }
 333
 334 int chash_resize(chash * hash, int size)
 335 {
 336   struct chashcell ** cells;
 337   int indx, nindx;
 338   chashiter * iter, * next;
 339
 340   if (hash->size == size)
 341     return 0;
 342
 343   cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
 344   if (!cells)
 345     return -1;
 346
 347   /* browse initial hash and copy items in second hash */
 348   for(indx = 0; indx < hash->size; indx++) {
 349     iter = hash->cells[indx];
 350     while (iter) {
 351       next = iter->next;
 352       nindx = iter->func % size;
 353       iter->next = cells[nindx];
 354       cells[nindx] = iter;
 355       iter = next;
 356     }
 357   }
 358   free(hash->cells);
 359   hash->size = size;
 360   hash->cells = cells;
 361
 362   return 0;
 363 }
 364
 365 #ifdef NO_MACROS
 366 int chash_count(chash * hash) {
 367   return hash->count;
 368 }
 369
 370 int chash_size(chash * hash) {
 371   return hash->size;
 372 }
 373
 374 void chash_value(chashiter * iter, chashdatum * result) {
 375   * result = iter->value;
 376 }
 377
 378 void chash_key(chashiter * iter, chashdatum * result) {
 379   * result = iter->key;
 380 }
 381 #endif