xref: /netbsd-src/usr.sbin/bootp/common/hash.h (revision cd68fb44fb313f983f0e34147f57086645e19049)
1*cd68fb44Swiz /*	$NetBSD: hash.h,v 1.4 2003/02/02 10:24:41 wiz Exp $	*/
23fe138c1Sperry 
35e9d01f2Sgwr #ifndef	HASH_H
45e9d01f2Sgwr #define HASH_H
55e9d01f2Sgwr /* hash.h */
65e9d01f2Sgwr /************************************************************************
75e9d01f2Sgwr           Copyright 1988, 1991 by Carnegie Mellon University
85e9d01f2Sgwr 
95e9d01f2Sgwr                           All Rights Reserved
105e9d01f2Sgwr 
115e9d01f2Sgwr Permission to use, copy, modify, and distribute this software and its
125e9d01f2Sgwr documentation for any purpose and without fee is hereby granted, provided
135e9d01f2Sgwr that the above copyright notice appear in all copies and that both that
145e9d01f2Sgwr copyright notice and this permission notice appear in supporting
155e9d01f2Sgwr documentation, and that the name of Carnegie Mellon University not be used
165e9d01f2Sgwr in advertising or publicity pertaining to distribution of the software
175e9d01f2Sgwr without specific, written prior permission.
185e9d01f2Sgwr 
195e9d01f2Sgwr CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
205e9d01f2Sgwr SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
215e9d01f2Sgwr IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
225e9d01f2Sgwr DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
235e9d01f2Sgwr PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
245e9d01f2Sgwr ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
255e9d01f2Sgwr SOFTWARE.
265e9d01f2Sgwr ************************************************************************/
275e9d01f2Sgwr 
285e9d01f2Sgwr /*
295e9d01f2Sgwr  * Generalized hash table ADT
305e9d01f2Sgwr  *
315e9d01f2Sgwr  * Provides multiple, dynamically-allocated, variable-sized hash tables on
325e9d01f2Sgwr  * various data and keys.
335e9d01f2Sgwr  *
345e9d01f2Sgwr  * This package attempts to follow some of the coding conventions suggested
355e9d01f2Sgwr  * by Bob Sidebotham and the AFS Clean Code Committee.
365e9d01f2Sgwr  */
375e9d01f2Sgwr 
385e9d01f2Sgwr 
395e9d01f2Sgwr /*
405e9d01f2Sgwr  * The user must supply the following:
415e9d01f2Sgwr  *
425e9d01f2Sgwr  *	1.  A comparison function which is declared as:
435e9d01f2Sgwr  *
445e9d01f2Sgwr  *		int compare(data1, data2)
455e9d01f2Sgwr  *		hash_datum *data1, *data2;
465e9d01f2Sgwr  *
475e9d01f2Sgwr  *	    This function must compare the desired fields of data1 and
485e9d01f2Sgwr  *	    data2 and return TRUE (1) if the data should be considered
495e9d01f2Sgwr  *	    equivalent (i.e. have the same key value) or FALSE (0)
505e9d01f2Sgwr  *	    otherwise.  This function is called through a pointer passed to
515e9d01f2Sgwr  *	    the various hashtable functions (thus pointers to different
525e9d01f2Sgwr  *	    functions may be passed to effect different tests on different
535e9d01f2Sgwr  *	    hash tables).
545e9d01f2Sgwr  *
555e9d01f2Sgwr  *	    Internally, all the functions of this package always call the
565e9d01f2Sgwr  *	    compare function with the "key" parameter as the first parameter,
575e9d01f2Sgwr  *	    and a full data element as the second parameter.  Thus, the key
585e9d01f2Sgwr  *	    and element arguments to functions such as hash_Lookup() may
595e9d01f2Sgwr  *	    actually be of different types and the programmer may provide a
605e9d01f2Sgwr  *	    compare function which compares the two different object types
615e9d01f2Sgwr  *	    as desired.
625e9d01f2Sgwr  *
635e9d01f2Sgwr  *	    Example:
645e9d01f2Sgwr  *
655e9d01f2Sgwr  *		int compare(key, element)
665e9d01f2Sgwr  *		char *key;
675e9d01f2Sgwr  *		struct some_complex_structure *element;
685e9d01f2Sgwr  *		{
695e9d01f2Sgwr  *		    return !strcmp(key, element->name);
705e9d01f2Sgwr  *		}
715e9d01f2Sgwr  *
725e9d01f2Sgwr  *		key = "John C. Doe"
735e9d01f2Sgwr  *		element = &some_complex_structure
745e9d01f2Sgwr  *		hash_Lookup(table, hashcode, compare, key);
755e9d01f2Sgwr  *
765e9d01f2Sgwr  *	2.  A hash function yielding an unsigned integer value to be used
775e9d01f2Sgwr  *	    as the hashcode (index into the hashtable).  Thus, the user
785e9d01f2Sgwr  *	    may hash on whatever data is desired and may use several
795e9d01f2Sgwr  *	    different hash functions for various different hash tables.
805e9d01f2Sgwr  *	    The actual hash table index will be the passed hashcode modulo
815e9d01f2Sgwr  *	    the hash table size.
825e9d01f2Sgwr  *
835e9d01f2Sgwr  *	    A generalized hash function, hash_HashFunction(), is included
845e9d01f2Sgwr  *	    with this package to make things a little easier.  It is not
85*cd68fb44Swiz  *	    guaranteed to use the best hash algorithm in existence. . . .
865e9d01f2Sgwr  */
875e9d01f2Sgwr 
885e9d01f2Sgwr 
895e9d01f2Sgwr 
905e9d01f2Sgwr /*
915e9d01f2Sgwr  * Various hash table definitions
925e9d01f2Sgwr  */
935e9d01f2Sgwr 
945e9d01f2Sgwr 
955e9d01f2Sgwr /*
965e9d01f2Sgwr  * Define "hash_datum" as a universal data type
975e9d01f2Sgwr  */
985e9d01f2Sgwr typedef void hash_datum;
995e9d01f2Sgwr 
1005e9d01f2Sgwr typedef struct hash_memberstruct  hash_member;
1015e9d01f2Sgwr typedef struct hash_tblstruct     hash_tbl;
1025e9d01f2Sgwr typedef struct hash_tblstruct_hdr hash_tblhdr;
1035e9d01f2Sgwr 
1045e9d01f2Sgwr struct hash_memberstruct {
1055e9d01f2Sgwr     hash_member *next;
1065e9d01f2Sgwr     hash_datum  *data;
1075e9d01f2Sgwr };
1085e9d01f2Sgwr 
1095e9d01f2Sgwr struct hash_tblstruct_hdr {
1105e9d01f2Sgwr     unsigned	size, bucketnum;
1115e9d01f2Sgwr     hash_member *member;
1125e9d01f2Sgwr };
1135e9d01f2Sgwr 
1145e9d01f2Sgwr struct hash_tblstruct {
1155e9d01f2Sgwr     unsigned	size, bucketnum;
1165e9d01f2Sgwr     hash_member *member;		/* Used for linear dump */
1175e9d01f2Sgwr     hash_member	*table[1];		/* Dynamically extended */
1185e9d01f2Sgwr };
1195e9d01f2Sgwr 
120131109e4Swiz typedef int (*hash_cmpfp)(hash_datum *, hash_datum *);
121131109e4Swiz typedef void (*hash_freefp)(hash_datum *);
1225e9d01f2Sgwr 
123131109e4Swiz extern hash_tbl	  *hash_Init(u_int tablesize);
1245e9d01f2Sgwr 
125131109e4Swiz extern void	   hash_Reset(hash_tbl *tbl, hash_freefp);
1265e9d01f2Sgwr 
127131109e4Swiz extern unsigned	   hash_HashFunction(u_char *str, u_int len);
1285e9d01f2Sgwr 
129131109e4Swiz extern int	   hash_Exists(hash_tbl *, u_int code,
130131109e4Swiz 			       hash_cmpfp, hash_datum *key);
1315e9d01f2Sgwr 
132131109e4Swiz extern int	   hash_Insert(hash_tbl *, u_int code, hash_cmpfp,
133131109e4Swiz 			       hash_datum *key, hash_datum *element);
1345e9d01f2Sgwr 
135131109e4Swiz extern int	   hash_Delete(hash_tbl *, u_int code,
1365e9d01f2Sgwr 			       hash_cmpfp, hash_datum *key,
137131109e4Swiz 			       hash_freefp);
1385e9d01f2Sgwr 
139131109e4Swiz extern hash_datum *hash_Lookup(hash_tbl *, u_int code,
140131109e4Swiz 			       hash_cmpfp, hash_datum *key);
1415e9d01f2Sgwr 
142131109e4Swiz extern hash_datum *hash_FirstEntry(hash_tbl *);
1435e9d01f2Sgwr 
144131109e4Swiz extern hash_datum *hash_NextEntry(hash_tbl *);
1455e9d01f2Sgwr 
1465e9d01f2Sgwr #endif	/* HASH_H */
147