lib/asn1/hash.c

   1 /*
   2  * Copyright (c) 1997 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 /*
  35  * Hash table functions
  36  */
  37
  38 #include "gen_locl.h"
  39
  40 RCSID("$Id$");
  41
  42 static Hashentry *_search(Hashtab * htab,       /* The hash table */
  43                           void *ptr);   /* And key */
  44
  45 Hashtab *
  46 hashtabnew(int sz,
  47            int (*cmp) (void *, void *),
  48            unsigned (*hash) (void *))
  49 {
  50     Hashtab *htab;
  51     int i;
  52
  53     assert(sz > 0);
  54
  55     htab = (Hashtab *) malloc(sizeof(Hashtab) + (sz - 1) * sizeof(Hashentry *));
  56     if (htab == NULL)
  57         return NULL;
  58
  59     for (i = 0; i < sz; ++i)
  60         htab->tab[i] = NULL;
  61
  62     htab->cmp = cmp;
  63     htab->hash = hash;
  64     htab->sz = sz;
  65     return htab;
  66 }
  67
  68 /* Intern search function */
  69
  70 static Hashentry *
  71 _search(Hashtab * htab, void *ptr)
  72 {
  73     Hashentry *hptr;
  74
  75     assert(htab && ptr);
  76
  77     for (hptr = htab->tab[(*htab->hash) (ptr) % htab->sz];
  78          hptr;
  79          hptr = hptr->next)
  80         if ((*htab->cmp) (ptr, hptr->ptr) == 0)
  81             break;
  82     return hptr;
  83 }
  84
  85 /* Search for element in hash table */
  86
  87 void *
  88 hashtabsearch(Hashtab * htab, void *ptr)
  89 {
  90     Hashentry *tmp;
  91
  92     tmp = _search(htab, ptr);
  93     return tmp ? tmp->ptr : tmp;
  94 }
  95
  96 /* add element to hash table */
  97 /* if already there, set new value */
  98 /* !NULL if succesful */
  99
 100 void *
 101 hashtabadd(Hashtab * htab, void *ptr)
 102 {
 103     Hashentry *h = _search(htab, ptr);
 104     Hashentry **tabptr;
 105
 106     assert(htab && ptr);
 107
 108     if (h)
 109         free((void *) h->ptr);
 110     else {
 111         h = (Hashentry *) malloc(sizeof(Hashentry));
 112         if (h == NULL) {
 113             return NULL;
 114         }
 115         tabptr = &htab->tab[(*htab->hash) (ptr) % htab->sz];
 116         h->next = *tabptr;
 117         *tabptr = h;
 118         h->prev = tabptr;
 119         if (h->next)
 120             h->next->prev = &h->next;
 121     }
 122     h->ptr = ptr;
 123     return h;
 124 }
 125
 126 /* delete element with key key. Iff freep, free Hashentry->ptr */
 127
 128 int
 129 _hashtabdel(Hashtab * htab, void *ptr, int freep)
 130 {
 131     Hashentry *h;
 132
 133     assert(htab && ptr);
 134
 135     h = _search(htab, ptr);
 136     if (h) {
 137         if (freep)
 138             free(h->ptr);
 139         if ((*(h->prev) = h->next))
 140             h->next->prev = h->prev;
 141         free(h);
 142         return 0;
 143     } else
 144         return -1;
 145 }
 146
 147 /* Do something for each element */
 148
 149 void
 150 hashtabforeach(Hashtab * htab, int (*func) (void *ptr, void *arg),
 151                void *arg)
 152 {
 153     Hashentry **h, *g;
 154
 155     assert(htab);
 156
 157     for (h = htab->tab; h < &htab->tab[htab->sz]; ++h)
 158         for (g = *h; g; g = g->next)
 159             if ((*func) (g->ptr, arg))
 160                 return;
 161 }
 162
 163 /* standard hash-functions for strings */
 164
 165 unsigned
 166 hashadd(const char *s)
 167 {                               /* Standard hash function */
 168     unsigned i;
 169
 170     assert(s);
 171
 172     for (i = 0; *s; ++s)
 173         i += *s;
 174     return i;
 175 }
 176
 177 unsigned
 178 hashcaseadd(const char *s)
 179 {                               /* Standard hash function */
 180     unsigned i;
 181
 182     assert(s);
 183
 184     for (i = 0; *s; ++s)
 185         i += toupper((unsigned char)*s);
 186     return i;
 187 }
 188
 189 #define TWELVE (sizeof(unsigned))
 190 #define SEVENTYFIVE (6*sizeof(unsigned))
 191 #define HIGH_BITS (~((unsigned)(~0) >> TWELVE))
 192
 193 unsigned
 194 hashjpw(const char *ss)
 195 {                               /* another hash function */
 196     unsigned h = 0;
 197     unsigned g;
 198     const unsigned char *s = (const unsigned char *)ss;
 199
 200     for (; *s; ++s) {
 201         h = (h << TWELVE) + *s;
 202         if ((g = h & HIGH_BITS))
 203             h = (h ^ (g >> SEVENTYFIVE)) & ~HIGH_BITS;
 204     }
 205     return h;
 206 }