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 38148723Sstefanf__FBSDID("$FreeBSD$"); 3912099Sjoerg 4091586Smarkm/* 4191586Smarkm * XXX Really need a generalized hash table package 4291586Smarkm */ 4391586Smarkm 44148723Sstefanf#include <err.h> 4591586Smarkm#include <limits.h> 4612099Sjoerg#include <stddef.h> 4791586Smarkm#include <stdlib.h> 4812099Sjoerg#include <string.h> 4912099Sjoerg 5012099Sjoerg#include "lint2.h" 5112099Sjoerg 5212099Sjoerg/* pointer to hash table, initialized in inithash() */ 5312099Sjoergstatic hte_t **htab; 5412099Sjoerg 5591586Smarkmstatic int hash(const char *); 5612099Sjoerg 5712099Sjoerg/* 5812099Sjoerg * Initialize hash table. 5912099Sjoerg */ 6012099Sjoergvoid 6191586Smarkm_inithash(hte_t ***tablep) 6212099Sjoerg{ 6391586Smarkm 6491586Smarkm if (tablep == NULL) 6591586Smarkm tablep = &htab; 6691586Smarkm 6791586Smarkm *tablep = xcalloc(HSHSIZ2, sizeof (hte_t *)); 6812099Sjoerg} 6912099Sjoerg 7012099Sjoerg/* 7112099Sjoerg * Compute hash value from a string. 7212099Sjoerg */ 7312099Sjoergstatic int 7491586Smarkmhash(const char *s) 7512099Sjoerg{ 7612099Sjoerg u_int v; 7712099Sjoerg const u_char *us; 7812099Sjoerg 7912099Sjoerg v = 0; 8012099Sjoerg for (us = (const u_char *)s; *us != '\0'; us++) { 8112099Sjoerg v = (v << sizeof (v)) + *us; 8212099Sjoerg v ^= v >> (sizeof (v) * CHAR_BIT - sizeof (v)); 8312099Sjoerg } 8412099Sjoerg return (v % HSHSIZ2); 8512099Sjoerg} 8612099Sjoerg 8712099Sjoerg/* 8812099Sjoerg * Look for a hash table entry. If no hash table entry for the 8912099Sjoerg * given name exists and mknew is set, create a new one. 9012099Sjoerg */ 9112099Sjoerghte_t * 9291586Smarkm_hsearch(hte_t **table, const char *s, int mknew) 9312099Sjoerg{ 9412099Sjoerg int h; 9512099Sjoerg hte_t *hte; 9612099Sjoerg 9791586Smarkm if (table == NULL) 9891586Smarkm table = htab; 9991586Smarkm 10012099Sjoerg h = hash(s); 10191586Smarkm for (hte = table[h]; hte != NULL; hte = hte->h_link) { 10212099Sjoerg if (strcmp(hte->h_name, s) == 0) 10312099Sjoerg break; 10412099Sjoerg } 10512099Sjoerg 10612099Sjoerg if (hte != NULL || !mknew) 10712099Sjoerg return (hte); 10812099Sjoerg 10912099Sjoerg /* create a new hte */ 11091586Smarkm hte = xmalloc(sizeof (hte_t)); 11112099Sjoerg hte->h_name = xstrdup(s); 11291586Smarkm hte->h_used = 0; 11391586Smarkm hte->h_def = 0; 11491586Smarkm hte->h_static = 0; 11591586Smarkm hte->h_syms = NULL; 11612099Sjoerg hte->h_lsym = &hte->h_syms; 11791586Smarkm hte->h_calls = NULL; 11812099Sjoerg hte->h_lcall = &hte->h_calls; 11991586Smarkm hte->h_usyms = NULL; 12012099Sjoerg hte->h_lusym = &hte->h_usyms; 12191586Smarkm hte->h_link = table[h]; 12291586Smarkm hte->h_hte = NULL; 12391586Smarkm table[h] = hte; 12412099Sjoerg 12512099Sjoerg return (hte); 12612099Sjoerg} 12712099Sjoerg 12812099Sjoerg/* 12912099Sjoerg * Call function f for each name in the hash table. 13012099Sjoerg */ 13112099Sjoergvoid 13291586Smarkm_forall(hte_t **table, void (*f)(hte_t *)) 13312099Sjoerg{ 13412099Sjoerg int i; 13512099Sjoerg hte_t *hte; 13612099Sjoerg 13791586Smarkm if (table == NULL) 13891586Smarkm table = htab; 13991586Smarkm 14012099Sjoerg for (i = 0; i < HSHSIZ2; i++) { 14191586Smarkm for (hte = table[i]; hte != NULL; hte = hte->h_link) 14212099Sjoerg (*f)(hte); 14312099Sjoerg } 14412099Sjoerg} 14591586Smarkm 14691586Smarkm/* 14791586Smarkm * Free all contents of the hash table that this module allocated. 14891586Smarkm */ 14991586Smarkmvoid 15091586Smarkm_destroyhash(hte_t **table) 15191586Smarkm{ 15291586Smarkm int i; 15391586Smarkm hte_t *hte, *nexthte; 15491586Smarkm 15591586Smarkm if (table == NULL) 15691586Smarkm err(1, "_destroyhash called on main hash table"); 15791586Smarkm 15891586Smarkm for (i = 0; i < HSHSIZ2; i++) { 15991586Smarkm for (hte = table[i]; hte != NULL; hte = nexthte) { 16091586Smarkm free((void *)hte->h_name); 16191586Smarkm nexthte = hte->h_link; 16291586Smarkm free(hte); 16391586Smarkm } 16491586Smarkm } 16591586Smarkm free(table); 16691586Smarkm} 167