hash.c revision 12099
1/* $NetBSD: hash.c,v 1.2 1995/07/03 21:24:47 cgd 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#ifndef lint 35static char rcsid[] = "$NetBSD: hash.c,v 1.2 1995/07/03 21:24:47 cgd Exp $"; 36#endif 37 38#include <stddef.h> 39#include <string.h> 40#include <limits.h> 41 42#include "lint2.h" 43 44/* pointer to hash table, initialized in inithash() */ 45static hte_t **htab; 46 47static int hash __P((const char *)); 48 49/* 50 * Initialize hash table. 51 */ 52void 53inithash() 54{ 55 htab = xcalloc(HSHSIZ2, sizeof (hte_t *)); 56} 57 58/* 59 * Compute hash value from a string. 60 */ 61static int 62hash(s) 63 const char *s; 64{ 65 u_int v; 66 const u_char *us; 67 68 v = 0; 69 for (us = (const u_char *)s; *us != '\0'; us++) { 70 v = (v << sizeof (v)) + *us; 71 v ^= v >> (sizeof (v) * CHAR_BIT - sizeof (v)); 72 } 73 return (v % HSHSIZ2); 74} 75 76/* 77 * Look for a hash table entry. If no hash table entry for the 78 * given name exists and mknew is set, create a new one. 79 */ 80hte_t * 81hsearch(s, mknew) 82 const char *s; 83 int mknew; 84{ 85 int h; 86 hte_t *hte; 87 88 h = hash(s); 89 for (hte = htab[h]; hte != NULL; hte = hte->h_link) { 90 if (strcmp(hte->h_name, s) == 0) 91 break; 92 } 93 94 if (hte != NULL || !mknew) 95 return (hte); 96 97 /* create a new hte */ 98 hte = xalloc(sizeof (hte_t)); 99 hte->h_name = xstrdup(s); 100 hte->h_lsym = &hte->h_syms; 101 hte->h_lcall = &hte->h_calls; 102 hte->h_lusym = &hte->h_usyms; 103 hte->h_link = htab[h]; 104 htab[h] = hte; 105 106 return (hte); 107} 108 109/* 110 * Call function f for each name in the hash table. 111 */ 112void 113forall(f) 114 void (*f) __P((hte_t *)); 115{ 116 int i; 117 hte_t *hte; 118 119 for (i = 0; i < HSHSIZ2; i++) { 120 for (hte = htab[i]; hte != NULL; hte = hte->h_link) 121 (*f)(hte); 122 } 123} 124