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: hash.c,v 1.8 1999/12/02 17:05:02 joda Exp $"); 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 for (i = 0; i < sz; ++i) 57 htab->tab[i] = NULL; 58 59 if (htab == NULL) { 60 return NULL; 61 } else { 62 htab->cmp = cmp; 63 htab->hash = hash; 64 htab->sz = sz; 65 return htab; 66 } 67 } 68 69 /* Intern search function */ 70 71 static Hashentry * 72 _search(Hashtab * htab, void *ptr) 73 { 74 Hashentry *hptr; 75 76 assert(htab && ptr); 77 78 for (hptr = htab->tab[(*htab->hash) (ptr) % htab->sz]; 79 hptr; 80 hptr = hptr->next) 81 if ((*htab->cmp) (ptr, hptr->ptr) == 0) 82 break; 83 return hptr; 84 } 85 86 /* Search for element in hash table */ 87 88 void * 89 hashtabsearch(Hashtab * htab, void *ptr) 90 { 91 Hashentry *tmp; 92 93 tmp = _search(htab, ptr); 94 return tmp ? tmp->ptr : tmp; 95 } 96 97 /* add element to hash table */ 98 /* if already there, set new value */ 99 /* !NULL if succesful */ 100 101 void * 102 hashtabadd(Hashtab * htab, void *ptr) 103 { 104 Hashentry *h = _search(htab, ptr); 105 Hashentry **tabptr; 106 107 assert(htab && ptr); 108 109 if (h) 110 free((void *) h->ptr); 111 else { 112 h = (Hashentry *) malloc(sizeof(Hashentry)); 113 if (h == NULL) { 114 return NULL; 115 } 116 tabptr = &htab->tab[(*htab->hash) (ptr) % htab->sz]; 117 h->next = *tabptr; 118 *tabptr = h; 119 h->prev = tabptr; 120 if (h->next) 121 h->next->prev = &h->next; 122 } 123 h->ptr = ptr; 124 return h; 125 } 126 127 /* delete element with key key. Iff freep, free Hashentry->ptr */ 128 129 int 130 _hashtabdel(Hashtab * htab, void *ptr, int freep) 131 { 132 Hashentry *h; 133 134 assert(htab && ptr); 135 136 h = _search(htab, ptr); 137 if (h) { 138 if (freep) 139 free(h->ptr); 140 if ((*(h->prev) = h->next)) 141 h->next->prev = h->prev; 142 free(h); 143 return 0; 144 } else 145 return -1; 146 } 147 148 /* Do something for each element */ 149 150 void 151 hashtabforeach(Hashtab * htab, int (*func) (void *ptr, void *arg), 152 void *arg) 153 { 154 Hashentry **h, *g; 155 156 assert(htab); 157 158 for (h = htab->tab; h < &htab->tab[htab->sz]; ++h) 159 for (g = *h; g; g = g->next) 160 if ((*func) (g->ptr, arg)) 161 return; 162 } 163 164 /* standard hash-functions for strings */ 165 166 unsigned 167 hashadd(const char *s) 168 { /* Standard hash function */ 169 unsigned i; 170 171 assert(s); 172 173 for (i = 0; *s; ++s) 174 i += *s; 175 return i; 176 } 177 178 unsigned 179 hashcaseadd(const char *s) 180 { /* Standard hash function */ 181 unsigned i; 182 183 assert(s); 184 185 for (i = 0; *s; ++s) 186 i += toupper(*s); 187 return i; 188 } 189 190 #define TWELVE (sizeof(unsigned)) 191 #define SEVENTYFIVE (6*sizeof(unsigned)) 192 #define HIGH_BITS (~((unsigned)(~0) >> TWELVE)) 193 194 unsigned 195 hashjpw(const char *ss) 196 { /* another hash function */ 197 unsigned h = 0; 198 unsigned g; 199 const unsigned char *s = (const unsigned char *)ss; 200 201 for (; *s; ++s) { 202 h = (h << TWELVE) + *s; 203 if ((g = h & HIGH_BITS)) 204 h = (h ^ (g >> SEVENTYFIVE)) & ~HIGH_BITS; 205 } 206 return h; 207 } 208