Home | History | Annotate | Line # | Download | only in lint2
hash.c revision 1.1 
      1 /*
      2  * Copyright (c) 1994, 1995 Jochen Pohl
      3  * All Rights Reserved.
      4  *
      5  * Redistribution and use in source and binary forms, with or without
      6  * modification, are permitted provided that the following conditions
      7  * are met:
      8  * 1. Redistributions of source code must retain the above copyright
      9  *    notice, this list of conditions and the following disclaimer.
     10  * 2. Redistributions in binary form must reproduce the above copyright
     11  *    notice, this list of conditions and the following disclaimer in the
     12  *    documentation and/or other materials provided with the distribution.
     13  * 3. All advertising materials mentioning features or use of this software
     14  *    must display the following acknowledgement:
     15  *      This product includes software developed by Jochen Pohl for
     16  *	The NetBSD Project.
     17  * 4. The name of the author may not be used to endorse or promote products
     18  *    derived from this software without specific prior written permission.
     19  *
     20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     21  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     22  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     23  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     25  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     29  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     30  *
     31  *	$Id: hash.c,v 1.1 1995/07/03 20:56:38 cgd Exp $
     32  */
     33 
     34 #ifndef lint
     35 static char rcsid[] = "$Id: hash.c,v 1.1 1995/07/03 20:56:38 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() */
     45 static	hte_t	**htab;
     46 
     47 static	int	hash __P((const char *));
     48 
     49 /*
     50  * Initialize hash table.
     51  */
     52 void
     53 inithash()
     54 {
     55 	htab = xcalloc(HSHSIZ2, sizeof (hte_t *));
     56 }
     57 
     58 /*
     59  * Compute hash value from a string.
     60  */
     61 static int
     62 hash(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  */
     80 hte_t *
     81 hsearch(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  */
    112 void
    113 forall(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