src/plugins/mailmbox/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 /*
  37  * $Id$
  38  */
  39
  40 #include "config.h"
  41
  42 #include <stdlib.h>
  43 #include <string.h>
  44
  45 #include "chash.h"
  46
  47 /* This defines the maximum (average) number of entries per bucket.
  48    The hash is resized everytime inserting an entry makes the
  49    average go over that value. */
  50 #define CHASH_MAXDEPTH    3
  51
  52 static inline unsigned int chash_func(const char * key, unsigned int len) {
  53 #if 0
  54   register unsigned int c = 0, t;
  55   register const char * k = key;
  56
  57   while (len--) {
  58     c += (c << 4) + *k++;
  59     if ((t = c & 0xF0000000)) {
  60       c ^= t >> 24;
  61       c ^= t;
  62     }
  63   }
  64   return c;
  65 #endif
  66   register unsigned int c = 5381;
  67   register const char * k = key;
  68
  69   while (len--) {
  70     c = ((c << 5) + c) + *k++;
  71   }
  72
  73   return c;
  74 }
  75
  76 static inline char * chash_dup(const void * data, unsigned int len)
  77 {
  78   void * r;
  79
  80   r = (char *) malloc(len);
  81   if (!r)
  82     return NULL;
  83   memcpy(r, data, len);
  84   return r;
  85 }
  86
  87 chash * chash_new(unsigned int size, int flags)
  88 {
  89   chash * h;
  90
  91   h = (chash *) malloc(sizeof(chash));
  92   if (h == NULL)
  93     return NULL;
  94
  95   h->count = 0;
  96   h->cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
  97   if (h->cells == NULL) {
  98     free(h);
  99     return NULL;
 100   }
 101   h->size = size;
 102   h->copykey = flags & CHASH_COPYKEY;
 103   h->copyvalue = flags & CHASH_COPYVALUE;
 104
 105   return h;
 106 }
 107
 108 int chash_get(chash * hash,
 109               chashdatum * key, chashdatum * result)
 110 {
 111   unsigned int func;
 112   chashiter * iter;
 113
 114   func = chash_func(key->data, key->len);
 115
 116   /* look for the key in existing cells */
 117   iter = hash->cells[func % hash->size];
 118   while (iter) {
 119     if (iter->key.len == key->len && iter->func == func
 120         && !memcmp(iter->key.data, key->data, key->len)) {
 121       * result = iter->value; /* found */
 122
 123       return 0;
 124     }
 125     iter = iter->next;
 126   }
 127
 128   return -1;
 129 }
 130
 131 int chash_set(chash * hash,
 132               chashdatum * key,
 133               chashdatum * value,
 134               chashdatum * oldvalue)
 135 {
 136   unsigned int func, indx;
 137   chashiter * iter, * cell;
 138   int r;
 139
 140   if (hash->count > hash->size * CHASH_MAXDEPTH) {
 141     r = chash_resize(hash, (hash->count / CHASH_MAXDEPTH) * 2 + 1);
 142     if (r < 0)
 143       goto err;
 144   }
 145
 146   func = chash_func(key->data, key->len);
 147   indx = func % hash->size;
 148
 149   /* look for the key in existing cells */
 150   iter = hash->cells[indx];
 151   while (iter) {
 152     if (iter->key.len == key->len && iter->func == func
 153         && !memcmp(iter->key.data, key->data, key->len)) {
 154       /* found, replacing entry */
 155       if (hash->copyvalue) {
 156         char * data;
 157
 158         data = chash_dup(value->data, value->len);
 159         if (data == NULL)
 160           goto err;
 161
 162         free(iter->value.data);
 163         iter->value.data = data;
 164         iter->value.len = value->len;
 165       } else {
 166         if (oldvalue != NULL) {
 167           oldvalue->data = iter->value.data;
 168           oldvalue->len = iter->value.len;
 169         }
 170         iter->value.data = value->data;
 171         iter->value.len = value->len;
 172       }
 173       if (!hash->copykey)
 174         iter->key.data = key->data;
 175
 176       if (oldvalue != NULL) {
 177         oldvalue->data = value->data;
 178         oldvalue->len = value->len;
 179       }
 180
 181       return 0;
 182     }
 183     iter = iter->next;
 184   }
 185
 186   if (oldvalue != NULL) {
 187     oldvalue->data = NULL;
 188     oldvalue->len = 0;
 189   }
 190
 191   /* not found, adding entry */
 192   cell = (struct chashcell *) malloc(sizeof(struct chashcell));
 193   if (cell == NULL)
 194     goto err;
 195
 196   if (hash->copykey) {
 197     cell->key.data = chash_dup(key->data, key->len);
 198     if (cell->key.data == NULL)
 199       goto free;
 200   }
 201   else
 202     cell->key.data = key->data;
 203
 204   cell->key.len = key->len;
 205   if (hash->copyvalue) {
 206     cell->value.data = chash_dup(value->data, value->len);
 207     if (cell->value.data == NULL)
 208       goto free_key_data;
 209   }
 210   else
 211     cell->value.data = value->data;
 212
 213   cell->value.len = value->len;
 214   cell->func = func;
 215   cell->next = hash->cells[indx];
 216   hash->cells[indx] = cell;
 217   hash->count++;
 218
 219   return 0;
 220
 221  free_key_data:
 222   if (hash->copykey)
 223     free(cell->key.data);
 224  free:
 225   free(cell);
 226  err:
 227   return -1;
 228 }
 229
 230 int chash_delete(chash * hash, chashdatum * key, chashdatum * oldvalue)
 231 {
 232   /*  chashdatum result = { NULL, TRUE }; */
 233   unsigned int func, indx;
 234   chashiter * iter, * old;
 235
 236   /*
 237   if (!keylen)
 238     keylen = strlen(key) + 1;
 239   */
 240
 241   func = chash_func(key->data, key->len);
 242   indx = func % hash->size;
 243
 244   /* look for the key in existing cells */
 245   old = NULL;
 246   iter = hash->cells[indx];
 247   while (iter) {
 248     if (iter->key.len == key->len && iter->func == func
 249         && !memcmp(iter->key.data, key->data, key->len)) {
 250       /* found, deleting */
 251       if (old)
 252         old->next = iter->next;
 253       else
 254         hash->cells[indx] = iter->next;
 255       if (hash->copykey)
 256         free(iter->key.data);
 257       if (hash->copyvalue)
 258         free(iter->value.data);
 259       else {
 260         if (oldvalue != NULL) {
 261           oldvalue->data = iter->value.data;
 262           oldvalue->len = iter->value.len;
 263         }
 264       }
 265       free(iter);
 266       hash->count--;
 267       return 0;
 268     }
 269     old = iter;
 270     iter = iter->next;
 271   }
 272
 273   return -1; /* not found */
 274 }
 275
 276 void chash_free(chash * hash) {
 277   unsigned int indx;
 278   chashiter * iter, * next;
 279
 280   /* browse the hash table */
 281   for(indx = 0; indx < hash->size; indx++) {
 282     iter = hash->cells[indx];
 283     while (iter) {
 284       next = iter->next;
 285       if (hash->copykey)
 286         free(iter->key.data);
 287       if (hash->copyvalue)
 288         free(iter->value.data);
 289       free(iter);
 290       iter = next;
 291     }
 292   }
 293   free(hash->cells);
 294   free(hash);
 295 }
 296
 297 void chash_clear(chash * hash) {
 298   unsigned int indx;
 299   chashiter * iter, * next;
 300
 301   /* browse the hash table */
 302   for(indx = 0; indx < hash->size; indx++) {
 303     iter = hash->cells[indx];
 304     while (iter) {
 305       next = iter->next;
 306       if (hash->copykey)
 307         free(iter->key.data);
 308       if (hash->copyvalue)
 309         free(iter->value.data);
 310       free(iter);
 311       iter = next;
 312     }
 313   }
 314   memset(hash->cells, 0, hash->size * sizeof(* hash->cells));
 315   hash->count = 0;
 316 }
 317
 318 chashiter * chash_begin(chash * hash) {
 319   chashiter * iter;
 320   unsigned int indx = 0;
 321
 322   iter = hash->cells[0];
 323   while(!iter) {
 324     indx++;
 325     if (indx >= hash->size)
 326       return NULL;
 327     iter = hash->cells[indx];
 328   }
 329   return iter;
 330 }
 331
 332 chashiter * chash_next(chash * hash, chashiter * iter) {
 333   unsigned int indx;
 334
 335   if (!iter)
 336     return NULL;
 337
 338   indx = iter->func % hash->size;
 339   iter = iter->next;
 340
 341   while(!iter) {
 342     indx++;
 343     if (indx >= hash->size)
 344       return NULL;
 345     iter = hash->cells[indx];
 346   }
 347   return iter;
 348 }
 349
 350 int chash_resize(chash * hash, unsigned int size)
 351 {
 352   struct chashcell ** cells;
 353   unsigned int indx, nindx;
 354   chashiter * iter, * next;
 355
 356   if (hash->size == size)
 357     return 0;
 358
 359   cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
 360   if (!cells)
 361     return -1;
 362
 363   /* browse initial hash and copy items in second hash */
 364   for(indx = 0; indx < hash->size; indx++) {
 365     iter = hash->cells[indx];
 366     while (iter) {
 367       next = iter->next;
 368       nindx = iter->func % size;
 369       iter->next = cells[nindx];
 370       cells[nindx] = iter;
 371       iter = next;
 372     }
 373   }
 374   free(hash->cells);
 375   hash->size = size;
 376   hash->cells = cells;
 377
 378   return 0;
 379 }
 380
 381 #ifdef NO_MACROS
 382 int chash_count(chash * hash) {
 383   return hash->count;
 384 }
 385
 386 int chash_size(chash * hash) {
 387   return hash->size;
 388 }
 389
 390 void chash_value(chashiter * iter, chashdatum * result) {
 391   * result = iter->value;
 392 }
 393
 394 void chash_key(chashiter * iter, chashdatum * result) {
 395   * result = iter->key;
 396 }
 397 #endif