1/* $NetBSD: hash.c,v 1.1.1.1 2011/04/13 18:14:41 elric Exp $ */ 2 3/* 4 * Copyright (c) 1997 Kungliga Tekniska Högskolan 5 * (Royal Institute of Technology, Stockholm, Sweden). 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * 3. Neither the name of the Institute nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE 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 INSTITUTE 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 * Hash table functions 38 */ 39 40#include "gen_locl.h" 41 42__RCSID("$NetBSD: hash.c,v 1.1.1.1 2011/04/13 18:14:41 elric Exp $"); 43 44static Hashentry *_search(Hashtab * htab, /* The hash table */ 45 void *ptr); /* And key */ 46 47Hashtab * 48hashtabnew(int sz, 49 int (*cmp) (void *, void *), 50 unsigned (*hash) (void *)) 51{ 52 Hashtab *htab; 53 int i; 54 55 assert(sz > 0); 56 57 htab = (Hashtab *) malloc(sizeof(Hashtab) + (sz - 1) * sizeof(Hashentry *)); 58 if (htab == NULL) 59 return NULL; 60 61 for (i = 0; i < sz; ++i) 62 htab->tab[i] = NULL; 63 64 htab->cmp = cmp; 65 htab->hash = hash; 66 htab->sz = sz; 67 return htab; 68} 69 70/* Intern search function */ 71 72static Hashentry * 73_search(Hashtab * htab, void *ptr) 74{ 75 Hashentry *hptr; 76 77 assert(htab && ptr); 78 79 for (hptr = htab->tab[(*htab->hash) (ptr) % htab->sz]; 80 hptr; 81 hptr = hptr->next) 82 if ((*htab->cmp) (ptr, hptr->ptr) == 0) 83 break; 84 return hptr; 85} 86 87/* Search for element in hash table */ 88 89void * 90hashtabsearch(Hashtab * htab, void *ptr) 91{ 92 Hashentry *tmp; 93 94 tmp = _search(htab, ptr); 95 return tmp ? tmp->ptr : tmp; 96} 97 98/* add element to hash table */ 99/* if already there, set new value */ 100/* !NULL if succesful */ 101 102void * 103hashtabadd(Hashtab * htab, void *ptr) 104{ 105 Hashentry *h = _search(htab, ptr); 106 Hashentry **tabptr; 107 108 assert(htab && ptr); 109 110 if (h) 111 free((void *) h->ptr); 112 else { 113 h = (Hashentry *) malloc(sizeof(Hashentry)); 114 if (h == NULL) { 115 return NULL; 116 } 117 tabptr = &htab->tab[(*htab->hash) (ptr) % htab->sz]; 118 h->next = *tabptr; 119 *tabptr = h; 120 h->prev = tabptr; 121 if (h->next) 122 h->next->prev = &h->next; 123 } 124 h->ptr = ptr; 125 return h; 126} 127 128/* delete element with key key. Iff freep, free Hashentry->ptr */ 129 130int 131_hashtabdel(Hashtab * htab, void *ptr, int freep) 132{ 133 Hashentry *h; 134 135 assert(htab && ptr); 136 137 h = _search(htab, ptr); 138 if (h) { 139 if (freep) 140 free(h->ptr); 141 if ((*(h->prev) = h->next)) 142 h->next->prev = h->prev; 143 free(h); 144 return 0; 145 } else 146 return -1; 147} 148 149/* Do something for each element */ 150 151void 152hashtabforeach(Hashtab * htab, int (*func) (void *ptr, void *arg), 153 void *arg) 154{ 155 Hashentry **h, *g; 156 157 assert(htab); 158 159 for (h = htab->tab; h < &htab->tab[htab->sz]; ++h) 160 for (g = *h; g; g = g->next) 161 if ((*func) (g->ptr, arg)) 162 return; 163} 164 165/* standard hash-functions for strings */ 166 167unsigned 168hashadd(const char *s) 169{ /* Standard hash function */ 170 unsigned i; 171 172 assert(s); 173 174 for (i = 0; *s; ++s) 175 i += *s; 176 return i; 177} 178 179unsigned 180hashcaseadd(const char *s) 181{ /* Standard hash function */ 182 unsigned i; 183 184 assert(s); 185 186 for (i = 0; *s; ++s) 187 i += toupper((unsigned char)*s); 188 return i; 189} 190 191#define TWELVE (sizeof(unsigned)) 192#define SEVENTYFIVE (6*sizeof(unsigned)) 193#define HIGH_BITS (~((unsigned)(~0) >> TWELVE)) 194 195unsigned 196hashjpw(const char *ss) 197{ /* another hash function */ 198 unsigned h = 0; 199 unsigned g; 200 const unsigned char *s = (const unsigned char *)ss; 201 202 for (; *s; ++s) { 203 h = (h << TWELVE) + *s; 204 if ((g = h & HIGH_BITS)) 205 h = (h ^ (g >> SEVENTYFIVE)) & ~HIGH_BITS; 206 } 207 return h; 208} 209