1 /* $NetBSD: hash.c,v 1.5 1998/07/27 12:10:24 mycroft 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 #ifndef lint 36 __RCSID("$NetBSD: hash.c,v 1.5 1998/07/27 12:10:24 mycroft Exp $"); 37 #endif 38 39 /* 40 * XXX Really need a generalized hash table package 41 */ 42 43 #include <stddef.h> 44 #include <stdlib.h> 45 #include <string.h> 46 #include <limits.h> 47 #include <err.h> 48 49 #include "lint2.h" 50 51 /* pointer to hash table, initialized in inithash() */ 52 static hte_t **htab; 53 54 static int hash __P((const char *)); 55 56 /* 57 * Initialize hash table. 58 */ 59 void 60 _inithash(tablep) 61 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 */ 73 static int 74 hash(s) 75 const char *s; 76 { 77 u_int v; 78 const u_char *us; 79 80 v = 0; 81 for (us = (const u_char *)s; *us != '\0'; us++) { 82 v = (v << sizeof (v)) + *us; 83 v ^= v >> (sizeof (v) * CHAR_BIT - sizeof (v)); 84 } 85 return (v % HSHSIZ2); 86 } 87 88 /* 89 * Look for a hash table entry. If no hash table entry for the 90 * given name exists and mknew is set, create a new one. 91 */ 92 hte_t * 93 _hsearch(table, s, mknew) 94 hte_t **table; 95 const char *s; 96 int mknew; 97 { 98 int h; 99 hte_t *hte; 100 101 if (table == NULL) 102 table = htab; 103 104 h = hash(s); 105 for (hte = table[h]; hte != NULL; hte = hte->h_link) { 106 if (strcmp(hte->h_name, s) == 0) 107 break; 108 } 109 110 if (hte != NULL || !mknew) 111 return (hte); 112 113 /* create a new hte */ 114 hte = xmalloc(sizeof (hte_t)); 115 hte->h_name = xstrdup(s); 116 hte->h_used = 0; 117 hte->h_def = 0; 118 hte->h_static = 0; 119 hte->h_syms = NULL; 120 hte->h_lsym = &hte->h_syms; 121 hte->h_calls = NULL; 122 hte->h_lcall = &hte->h_calls; 123 hte->h_usyms = NULL; 124 hte->h_lusym = &hte->h_usyms; 125 hte->h_link = table[h]; 126 hte->h_hte = NULL; 127 table[h] = hte; 128 129 return (hte); 130 } 131 132 /* 133 * Call function f for each name in the hash table. 134 */ 135 void 136 _forall(table, f) 137 hte_t **table; 138 void (*f) __P((hte_t *)); 139 { 140 int i; 141 hte_t *hte; 142 143 if (table == NULL) 144 table = htab; 145 146 for (i = 0; i < HSHSIZ2; i++) { 147 for (hte = table[i]; hte != NULL; hte = hte->h_link) 148 (*f)(hte); 149 } 150 } 151 152 /* 153 * Free all contents of the hash table that this module allocated. 154 */ 155 void 156 _destroyhash(table) 157 hte_t **table; 158 { 159 int i; 160 hte_t *hte, *nexthte; 161 162 if (table == NULL) 163 err(1, "_destroyhash called on main hash table"); 164 165 for (i = 0; i < HSHSIZ2; i++) { 166 for (hte = table[i]; hte != NULL; hte = nexthte) { 167 free((void *)hte->h_name); 168 nexthte = hte->h_link; 169 free(hte); 170 } 171 } 172 free(table); 173 } 174