Home | History | Annotate | Line # | Download | only in common
hash.h revision 1.2 
      1 /*	$NetBSD: hash.h,v 1.2 1998/01/09 08:09:10 perry Exp $	*/
      2 
      3 #ifndef	HASH_H
      4 #define HASH_H
      5 /* hash.h */
      6 /************************************************************************
      7           Copyright 1988, 1991 by Carnegie Mellon University
      8 
      9                           All Rights Reserved
     10 
     11 Permission to use, copy, modify, and distribute this software and its
     12 documentation for any purpose and without fee is hereby granted, provided
     13 that the above copyright notice appear in all copies and that both that
     14 copyright notice and this permission notice appear in supporting
     15 documentation, and that the name of Carnegie Mellon University not be used
     16 in advertising or publicity pertaining to distribution of the software
     17 without specific, written prior permission.
     18 
     19 CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
     20 SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
     21 IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
     22 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
     23 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
     24 ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
     25 SOFTWARE.
     26 ************************************************************************/
     27 
     28 /*
     29  * Generalized hash table ADT
     30  *
     31  * Provides multiple, dynamically-allocated, variable-sized hash tables on
     32  * various data and keys.
     33  *
     34  * This package attempts to follow some of the coding conventions suggested
     35  * by Bob Sidebotham and the AFS Clean Code Committee.
     36  */
     37 
     38 
     39 /*
     40  * The user must supply the following:
     41  *
     42  *	1.  A comparison function which is declared as:
     43  *
     44  *		int compare(data1, data2)
     45  *		hash_datum *data1, *data2;
     46  *
     47  *	    This function must compare the desired fields of data1 and
     48  *	    data2 and return TRUE (1) if the data should be considered
     49  *	    equivalent (i.e. have the same key value) or FALSE (0)
     50  *	    otherwise.  This function is called through a pointer passed to
     51  *	    the various hashtable functions (thus pointers to different
     52  *	    functions may be passed to effect different tests on different
     53  *	    hash tables).
     54  *
     55  *	    Internally, all the functions of this package always call the
     56  *	    compare function with the "key" parameter as the first parameter,
     57  *	    and a full data element as the second parameter.  Thus, the key
     58  *	    and element arguments to functions such as hash_Lookup() may
     59  *	    actually be of different types and the programmer may provide a
     60  *	    compare function which compares the two different object types
     61  *	    as desired.
     62  *
     63  *	    Example:
     64  *
     65  *		int compare(key, element)
     66  *		char *key;
     67  *		struct some_complex_structure *element;
     68  *		{
     69  *		    return !strcmp(key, element->name);
     70  *		}
     71  *
     72  *		key = "John C. Doe"
     73  *		element = &some_complex_structure
     74  *		hash_Lookup(table, hashcode, compare, key);
     75  *
     76  *	2.  A hash function yielding an unsigned integer value to be used
     77  *	    as the hashcode (index into the hashtable).  Thus, the user
     78  *	    may hash on whatever data is desired and may use several
     79  *	    different hash functions for various different hash tables.
     80  *	    The actual hash table index will be the passed hashcode modulo
     81  *	    the hash table size.
     82  *
     83  *	    A generalized hash function, hash_HashFunction(), is included
     84  *	    with this package to make things a little easier.  It is not
     85  *	    guarenteed to use the best hash algorithm in existence. . . .
     86  */
     87 
     88 
     89 
     91 /*
     92  * Various hash table definitions
     93  */
     94 
     95 
     96 /*
     97  * Define "hash_datum" as a universal data type
     98  */
     99 #ifdef __STDC__
    100 typedef void hash_datum;
    101 #else
    102 typedef char hash_datum;
    103 #endif
    104 
    105 typedef struct hash_memberstruct  hash_member;
    106 typedef struct hash_tblstruct     hash_tbl;
    107 typedef struct hash_tblstruct_hdr hash_tblhdr;
    108 
    109 struct hash_memberstruct {
    110     hash_member *next;
    111     hash_datum  *data;
    112 };
    113 
    114 struct hash_tblstruct_hdr {
    115     unsigned	size, bucketnum;
    116     hash_member *member;
    117 };
    118 
    119 struct hash_tblstruct {
    120     unsigned	size, bucketnum;
    121     hash_member *member;		/* Used for linear dump */
    122     hash_member	*table[1];		/* Dynamically extended */
    123 };
    124 
    125 /* ANSI function prototypes or empty arg list? */
    126 #ifdef	__STDC__
    127 #define P(args) args
    128 #else
    129 #define P(args) ()
    130 #endif
    131 
    132 typedef int (*hash_cmpfp) P((hash_datum *, hash_datum *));
    133 typedef void (*hash_freefp) P((hash_datum *));
    134 
    135 extern hash_tbl	  *hash_Init P((u_int tablesize));
    136 
    137 extern void	   hash_Reset P((hash_tbl *tbl, hash_freefp));
    138 
    139 extern unsigned	   hash_HashFunction P((u_char *str, u_int len));
    140 
    141 extern int	   hash_Exists P((hash_tbl *, u_int code,
    142 				  hash_cmpfp, hash_datum *key));
    143 
    144 extern int	   hash_Insert P((hash_tbl *, u_int code,
    145 				  hash_cmpfp, hash_datum *key,
    146 				  hash_datum *element));
    147 
    148 extern int	   hash_Delete P((hash_tbl *, u_int code,
    149 				  hash_cmpfp, hash_datum *key,
    150 				  hash_freefp));
    151 
    152 extern hash_datum *hash_Lookup P((hash_tbl *, u_int code,
    153 				  hash_cmpfp, hash_datum *key));
    154 
    155 extern hash_datum *hash_FirstEntry P((hash_tbl *));
    156 
    157 extern hash_datum *hash_NextEntry P((hash_tbl *));
    158 
    159 #undef P
    160 
    161 #endif	/* HASH_H */
    162