hash.c revision 91586
191586Smarkm/* $NetBSD: hash.c,v 1.7 2002/01/21 19:49:52 tv Exp $ */ 212099Sjoerg 312099Sjoerg/* 412099Sjoerg * Copyright (c) 1994, 1995 Jochen Pohl 512099Sjoerg * All Rights Reserved. 612099Sjoerg * 712099Sjoerg * Redistribution and use in source and binary forms, with or without 812099Sjoerg * modification, are permitted provided that the following conditions 912099Sjoerg * are met: 1012099Sjoerg * 1. Redistributions of source code must retain the above copyright 1112099Sjoerg * notice, this list of conditions and the following disclaimer. 1212099Sjoerg * 2. Redistributions in binary form must reproduce the above copyright 1312099Sjoerg * notice, this list of conditions and the following disclaimer in the 1412099Sjoerg * documentation and/or other materials provided with the distribution. 1512099Sjoerg * 3. All advertising materials mentioning features or use of this software 1612099Sjoerg * must display the following acknowledgement: 1712099Sjoerg * This product includes software developed by Jochen Pohl for 1812099Sjoerg * The NetBSD Project. 1912099Sjoerg * 4. The name of the author may not be used to endorse or promote products 2012099Sjoerg * derived from this software without specific prior written permission. 2112099Sjoerg * 2212099Sjoerg * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2312099Sjoerg * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2412099Sjoerg * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2512099Sjoerg * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2612099Sjoerg * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2712099Sjoerg * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2812099Sjoerg * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2912099Sjoerg * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3012099Sjoerg * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3112099Sjoerg * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3212099Sjoerg */ 3312099Sjoerg 3491586Smarkm#include <sys/cdefs.h> 3591586Smarkm#if defined(__RCSID) && !defined(lint) 3691586Smarkm__RCSID("$NetBSD: hash.c,v 1.7 2002/01/21 19:49:52 tv Exp $"); 3712099Sjoerg#endif 3812099Sjoerg 3991586Smarkm/* 4091586Smarkm * XXX Really need a generalized hash table package 4191586Smarkm */ 4291586Smarkm 4391586Smarkm#include <limits.h> 4412099Sjoerg#include <stddef.h> 4591586Smarkm#include <stdlib.h> 4612099Sjoerg#include <string.h> 4712099Sjoerg 4812099Sjoerg#include "lint2.h" 4912099Sjoerg 5012099Sjoerg/* pointer to hash table, initialized in inithash() */ 5112099Sjoergstatic hte_t **htab; 5212099Sjoerg 5391586Smarkmstatic int hash(const char *); 5412099Sjoerg 5512099Sjoerg/* 5612099Sjoerg * Initialize hash table. 5712099Sjoerg */ 5812099Sjoergvoid 5991586Smarkm_inithash(hte_t ***tablep) 6012099Sjoerg{ 6191586Smarkm 6291586Smarkm if (tablep == NULL) 6391586Smarkm tablep = &htab; 6491586Smarkm 6591586Smarkm *tablep = xcalloc(HSHSIZ2, sizeof (hte_t *)); 6612099Sjoerg} 6712099Sjoerg 6812099Sjoerg/* 6912099Sjoerg * Compute hash value from a string. 7012099Sjoerg */ 7112099Sjoergstatic int 7291586Smarkmhash(const char *s) 7312099Sjoerg{ 7412099Sjoerg u_int v; 7512099Sjoerg const u_char *us; 7612099Sjoerg 7712099Sjoerg v = 0; 7812099Sjoerg for (us = (const u_char *)s; *us != '\0'; us++) { 7912099Sjoerg v = (v << sizeof (v)) + *us; 8012099Sjoerg v ^= v >> (sizeof (v) * CHAR_BIT - sizeof (v)); 8112099Sjoerg } 8212099Sjoerg return (v % HSHSIZ2); 8312099Sjoerg} 8412099Sjoerg 8512099Sjoerg/* 8612099Sjoerg * Look for a hash table entry. If no hash table entry for the 8712099Sjoerg * given name exists and mknew is set, create a new one. 8812099Sjoerg */ 8912099Sjoerghte_t * 9091586Smarkm_hsearch(hte_t **table, const char *s, int mknew) 9112099Sjoerg{ 9212099Sjoerg int h; 9312099Sjoerg hte_t *hte; 9412099Sjoerg 9591586Smarkm if (table == NULL) 9691586Smarkm table = htab; 9791586Smarkm 9812099Sjoerg h = hash(s); 9991586Smarkm for (hte = table[h]; hte != NULL; hte = hte->h_link) { 10012099Sjoerg if (strcmp(hte->h_name, s) == 0) 10112099Sjoerg break; 10212099Sjoerg } 10312099Sjoerg 10412099Sjoerg if (hte != NULL || !mknew) 10512099Sjoerg return (hte); 10612099Sjoerg 10712099Sjoerg /* create a new hte */ 10891586Smarkm hte = xmalloc(sizeof (hte_t)); 10912099Sjoerg hte->h_name = xstrdup(s); 11091586Smarkm hte->h_used = 0; 11191586Smarkm hte->h_def = 0; 11291586Smarkm hte->h_static = 0; 11391586Smarkm hte->h_syms = NULL; 11412099Sjoerg hte->h_lsym = &hte->h_syms; 11591586Smarkm hte->h_calls = NULL; 11612099Sjoerg hte->h_lcall = &hte->h_calls; 11791586Smarkm hte->h_usyms = NULL; 11812099Sjoerg hte->h_lusym = &hte->h_usyms; 11991586Smarkm hte->h_link = table[h]; 12091586Smarkm hte->h_hte = NULL; 12191586Smarkm table[h] = hte; 12212099Sjoerg 12312099Sjoerg return (hte); 12412099Sjoerg} 12512099Sjoerg 12612099Sjoerg/* 12712099Sjoerg * Call function f for each name in the hash table. 12812099Sjoerg */ 12912099Sjoergvoid 13091586Smarkm_forall(hte_t **table, void (*f)(hte_t *)) 13112099Sjoerg{ 13212099Sjoerg int i; 13312099Sjoerg hte_t *hte; 13412099Sjoerg 13591586Smarkm if (table == NULL) 13691586Smarkm table = htab; 13791586Smarkm 13812099Sjoerg for (i = 0; i < HSHSIZ2; i++) { 13991586Smarkm for (hte = table[i]; hte != NULL; hte = hte->h_link) 14012099Sjoerg (*f)(hte); 14112099Sjoerg } 14212099Sjoerg} 14391586Smarkm 14491586Smarkm/* 14591586Smarkm * Free all contents of the hash table that this module allocated. 14691586Smarkm */ 14791586Smarkmvoid 14891586Smarkm_destroyhash(hte_t **table) 14991586Smarkm{ 15091586Smarkm int i; 15191586Smarkm hte_t *hte, *nexthte; 15291586Smarkm 15391586Smarkm if (table == NULL) 15491586Smarkm err(1, "_destroyhash called on main hash table"); 15591586Smarkm 15691586Smarkm for (i = 0; i < HSHSIZ2; i++) { 15791586Smarkm for (hte = table[i]; hte != NULL; hte = nexthte) { 15891586Smarkm free((void *)hte->h_name); 15991586Smarkm nexthte = hte->h_link; 16091586Smarkm free(hte); 16191586Smarkm } 16291586Smarkm } 16391586Smarkm free(table); 16491586Smarkm} 165