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 17016 2006-04-07 22:16:00Z lha $"); 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 } 207