hash.c revision 12099
112099Sjoerg/* $NetBSD: hash.c,v 1.2 1995/07/03 21:24:47 cgd 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 3412099Sjoerg#ifndef lint 3512099Sjoergstatic char rcsid[] = "$NetBSD: hash.c,v 1.2 1995/07/03 21:24:47 cgd Exp $"; 3612099Sjoerg#endif 3712099Sjoerg 3812099Sjoerg#include <stddef.h> 3912099Sjoerg#include <string.h> 4012099Sjoerg#include <limits.h> 4112099Sjoerg 4212099Sjoerg#include "lint2.h" 4312099Sjoerg 4412099Sjoerg/* pointer to hash table, initialized in inithash() */ 4512099Sjoergstatic hte_t **htab; 4612099Sjoerg 4712099Sjoergstatic int hash __P((const char *)); 4812099Sjoerg 4912099Sjoerg/* 5012099Sjoerg * Initialize hash table. 5112099Sjoerg */ 5212099Sjoergvoid 5312099Sjoerginithash() 5412099Sjoerg{ 5512099Sjoerg htab = xcalloc(HSHSIZ2, sizeof (hte_t *)); 5612099Sjoerg} 5712099Sjoerg 5812099Sjoerg/* 5912099Sjoerg * Compute hash value from a string. 6012099Sjoerg */ 6112099Sjoergstatic int 6212099Sjoerghash(s) 6312099Sjoerg const char *s; 6412099Sjoerg{ 6512099Sjoerg u_int v; 6612099Sjoerg const u_char *us; 6712099Sjoerg 6812099Sjoerg v = 0; 6912099Sjoerg for (us = (const u_char *)s; *us != '\0'; us++) { 7012099Sjoerg v = (v << sizeof (v)) + *us; 7112099Sjoerg v ^= v >> (sizeof (v) * CHAR_BIT - sizeof (v)); 7212099Sjoerg } 7312099Sjoerg return (v % HSHSIZ2); 7412099Sjoerg} 7512099Sjoerg 7612099Sjoerg/* 7712099Sjoerg * Look for a hash table entry. If no hash table entry for the 7812099Sjoerg * given name exists and mknew is set, create a new one. 7912099Sjoerg */ 8012099Sjoerghte_t * 8112099Sjoerghsearch(s, mknew) 8212099Sjoerg const char *s; 8312099Sjoerg int mknew; 8412099Sjoerg{ 8512099Sjoerg int h; 8612099Sjoerg hte_t *hte; 8712099Sjoerg 8812099Sjoerg h = hash(s); 8912099Sjoerg for (hte = htab[h]; hte != NULL; hte = hte->h_link) { 9012099Sjoerg if (strcmp(hte->h_name, s) == 0) 9112099Sjoerg break; 9212099Sjoerg } 9312099Sjoerg 9412099Sjoerg if (hte != NULL || !mknew) 9512099Sjoerg return (hte); 9612099Sjoerg 9712099Sjoerg /* create a new hte */ 9812099Sjoerg hte = xalloc(sizeof (hte_t)); 9912099Sjoerg hte->h_name = xstrdup(s); 10012099Sjoerg hte->h_lsym = &hte->h_syms; 10112099Sjoerg hte->h_lcall = &hte->h_calls; 10212099Sjoerg hte->h_lusym = &hte->h_usyms; 10312099Sjoerg hte->h_link = htab[h]; 10412099Sjoerg htab[h] = hte; 10512099Sjoerg 10612099Sjoerg return (hte); 10712099Sjoerg} 10812099Sjoerg 10912099Sjoerg/* 11012099Sjoerg * Call function f for each name in the hash table. 11112099Sjoerg */ 11212099Sjoergvoid 11312099Sjoergforall(f) 11412099Sjoerg void (*f) __P((hte_t *)); 11512099Sjoerg{ 11612099Sjoerg int i; 11712099Sjoerg hte_t *hte; 11812099Sjoerg 11912099Sjoerg for (i = 0; i < HSHSIZ2; i++) { 12012099Sjoerg for (hte = htab[i]; hte != NULL; hte = hte->h_link) 12112099Sjoerg (*f)(hte); 12212099Sjoerg } 12312099Sjoerg} 124