LXR perl/x2p/hash.c

   1/*    hash.c
   2 *
   3 *    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1999, 2000, 2001, 2002,
   4 *    2005 by Larry Wall and others
   5 *
   6 *    You may distribute under the terms of either the GNU General Public
   7 *    License or the Artistic License, as specified in the README file.
   8 */
   9
  10#include <stdio.h>
  11#include "EXTERN.h"
  12#include "a2p.h"
  13#include "util.h"
  14
  15#ifdef NETWARE
  16char *savestr(char *str);
  17#endif
  18
  19STR *
  20hfetch(register HASH *tb, char *key)
  21{
  22    register char *s;
  23    register int i;
  24    register int hash;
  25    register HENT *entry;
  26
  27    if (!tb)
  28        return NULL;
  29    for (s=key,         i=0,    hash = 0;
  30      /* while */ *s;
  31         s++,           i++,    hash *= 5) {
  32        hash += *s * coeff[i];
  33    }
  34    entry = tb->tbl_array[hash & tb->tbl_max];
  35    for (; entry; entry = entry->hent_next) {
  36        if (entry->hent_hash != hash)           /* strings can't be equal */
  37            continue;
  38        if (strNE(entry->hent_key,key)) /* is this it? */
  39            continue;
  40        return entry->hent_val;
  41    }
  42    return NULL;
  43}
  44
  45bool
  46hstore(register HASH *tb, char *key, STR *val)
  47{
  48    register char *s;
  49    register int i;
  50    register int hash;
  51    register HENT *entry;
  52    register HENT **oentry;
  53
  54    if (!tb)
  55        return FALSE;
  56    for (s=key,         i=0,    hash = 0;
  57      /* while */ *s;
  58         s++,           i++,    hash *= 5) {
  59        hash += *s * coeff[i];
  60    }
  61
  62    oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  63    i = 1;
  64
  65    for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  66        if (entry->hent_hash != hash)           /* strings can't be equal */
  67            continue;
  68        if (strNE(entry->hent_key,key)) /* is this it? */
  69            continue;
  70        /*NOSTRICT*/
  71        safefree(entry->hent_val);
  72        entry->hent_val = val;
  73        return TRUE;
  74    }
  75    /*NOSTRICT*/
  76    entry = (HENT*) safemalloc(sizeof(HENT));
  77
  78    entry->hent_key = savestr(key);
  79    entry->hent_val = val;
  80    entry->hent_hash = hash;
  81    entry->hent_next = *oentry;
  82    *oentry = entry;
  83
  84    if (i) {                            /* initial entry? */
  85        tb->tbl_fill++;
  86        if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  87            hsplit(tb);
  88    }
  89
  90    return FALSE;
  91}
  92
  93void
  94hsplit(HASH *tb)
  95{
  96    const int oldsize = tb->tbl_max + 1;
  97    register int newsize = oldsize * 2;
  98    register int i;
  99    register HENT **a;
 100    register HENT **b;
 101    register HENT *entry;
 102    register HENT **oentry;
 103
 104    a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
 105    memset(&a[oldsize], 0, oldsize * sizeof(HENT*)); /* zero second half */
 106    tb->tbl_max = --newsize;
 107    tb->tbl_array = a;
 108
 109    for (i=0; i<oldsize; i++,a++) {
 110        if (!*a)                                /* non-existent */
 111            continue;
 112        b = a+oldsize;
 113        for (oentry = a, entry = *a; entry; entry = *oentry) {
 114            if ((entry->hent_hash & newsize) != i) {
 115                *oentry = entry->hent_next;
 116                entry->hent_next = *b;
 117                if (!*b)
 118                    tb->tbl_fill++;
 119                *b = entry;
 120                continue;
 121            }
 122            else
 123                oentry = &entry->hent_next;
 124        }
 125        if (!*a)                                /* everything moved */
 126            tb->tbl_fill--;
 127    }
 128}
 129
 130HASH *
 131hnew(void)
 132{
 133    register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
 134
 135    tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
 136    tb->tbl_fill = 0;
 137    tb->tbl_max = 7;
 138    hiterinit(tb);      /* so each() will start off right */
 139    memset(tb->tbl_array, 0, 8 * sizeof(HENT*));
 140    return tb;
 141}
 142
 143int
 144hiterinit(register HASH *tb)
 145{
 146    tb->tbl_riter = -1;
 147    tb->tbl_eiter = (HENT*)NULL;
 148    return tb->tbl_fill;
 149}
 150