hash.c revision 256281
1/* $NetBSD: hash.c,v 1.7 2002/01/21 19:49:52 tv Exp $ */ 2 3/* 4 * Copyright (c) 1994, 1995 Jochen Pohl 5 * All Rights Reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by Jochen Pohl for 18 * The NetBSD Project. 19 * 4. The name of the author may not be used to endorse or promote products 20 * derived from this software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34#include <sys/cdefs.h> 35#if defined(__RCSID) && !defined(lint) 36__RCSID("$NetBSD: hash.c,v 1.7 2002/01/21 19:49:52 tv Exp $"); 37#endif 38__FBSDID("$FreeBSD: stable/10/usr.bin/xlint/lint2/hash.c 148723 2005-08-05 09:07:42Z stefanf $"); 39 40/* 41 * XXX Really need a generalized hash table package 42 */ 43 44#include <err.h> 45#include <limits.h> 46#include <stddef.h> 47#include <stdlib.h> 48#include <string.h> 49 50#include "lint2.h" 51 52/* pointer to hash table, initialized in inithash() */ 53static hte_t **htab; 54 55static int hash(const char *); 56 57/* 58 * Initialize hash table. 59 */ 60void 61_inithash(hte_t ***tablep) 62{ 63 64 if (tablep == NULL) 65 tablep = &htab; 66 67 *tablep = xcalloc(HSHSIZ2, sizeof (hte_t *)); 68} 69 70/* 71 * Compute hash value from a string. 72 */ 73static int 74hash(const char *s) 75{ 76 u_int v; 77 const u_char *us; 78 79 v = 0; 80 for (us = (const u_char *)s; *us != '\0'; us++) { 81 v = (v << sizeof (v)) + *us; 82 v ^= v >> (sizeof (v) * CHAR_BIT - sizeof (v)); 83 } 84 return (v % HSHSIZ2); 85} 86 87/* 88 * Look for a hash table entry. If no hash table entry for the 89 * given name exists and mknew is set, create a new one. 90 */ 91hte_t * 92_hsearch(hte_t **table, const char *s, int mknew) 93{ 94 int h; 95 hte_t *hte; 96 97 if (table == NULL) 98 table = htab; 99 100 h = hash(s); 101 for (hte = table[h]; hte != NULL; hte = hte->h_link) { 102 if (strcmp(hte->h_name, s) == 0) 103 break; 104 } 105 106 if (hte != NULL || !mknew) 107 return (hte); 108 109 /* create a new hte */ 110 hte = xmalloc(sizeof (hte_t)); 111 hte->h_name = xstrdup(s); 112 hte->h_used = 0; 113 hte->h_def = 0; 114 hte->h_static = 0; 115 hte->h_syms = NULL; 116 hte->h_lsym = &hte->h_syms; 117 hte->h_calls = NULL; 118 hte->h_lcall = &hte->h_calls; 119 hte->h_usyms = NULL; 120 hte->h_lusym = &hte->h_usyms; 121 hte->h_link = table[h]; 122 hte->h_hte = NULL; 123 table[h] = hte; 124 125 return (hte); 126} 127 128/* 129 * Call function f for each name in the hash table. 130 */ 131void 132_forall(hte_t **table, void (*f)(hte_t *)) 133{ 134 int i; 135 hte_t *hte; 136 137 if (table == NULL) 138 table = htab; 139 140 for (i = 0; i < HSHSIZ2; i++) { 141 for (hte = table[i]; hte != NULL; hte = hte->h_link) 142 (*f)(hte); 143 } 144} 145 146/* 147 * Free all contents of the hash table that this module allocated. 148 */ 149void 150_destroyhash(hte_t **table) 151{ 152 int i; 153 hte_t *hte, *nexthte; 154 155 if (table == NULL) 156 err(1, "_destroyhash called on main hash table"); 157 158 for (i = 0; i < HSHSIZ2; i++) { 159 for (hte = table[i]; hte != NULL; hte = nexthte) { 160 free((void *)hte->h_name); 161 nexthte = hte->h_link; 162 free(hte); 163 } 164 } 165 free(table); 166} 167