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