1/*	$NetBSD: hash.h,v 1.3 2002/07/14 00:26:17 wiz 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
11Permission to use, copy, modify, and distribute this software and its
12documentation for any purpose and without fee is hereby granted, provided
13that the above copyright notice appear in all copies and that both that
14copyright notice and this permission notice appear in supporting
15documentation, and that the name of Carnegie Mellon University not be used
16in advertising or publicity pertaining to distribution of the software
17without specific, written prior permission.
18
19CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
20SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
21IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
22DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
23PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
24ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
25SOFTWARE.
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 *	    guaranteed to use the best hash algorithm in existence. . . .
86 */
87
88
89
90/*
91 * Various hash table definitions
92 */
93
94
95/*
96 * Define "hash_datum" as a universal data type
97 */
98typedef void hash_datum;
99
100typedef struct hash_memberstruct  hash_member;
101typedef struct hash_tblstruct     hash_tbl;
102typedef struct hash_tblstruct_hdr hash_tblhdr;
103
104struct hash_memberstruct {
105    hash_member *next;
106    hash_datum  *data;
107};
108
109struct hash_tblstruct_hdr {
110    unsigned	size, bucketnum;
111    hash_member *member;
112};
113
114struct hash_tblstruct {
115    unsigned	size, bucketnum;
116    hash_member *member;		/* Used for linear dump */
117    hash_member	*table[1];		/* Dynamically extended */
118};
119
120typedef int (*hash_cmpfp)(hash_datum *, hash_datum *);
121typedef void (*hash_freefp)(hash_datum *);
122
123extern hash_tbl	  *hash_Init(u_int tablesize);
124
125extern void	   hash_Reset(hash_tbl *tbl, hash_freefp);
126
127extern unsigned	   hash_HashFunction(u_char *str, u_int len);
128
129extern int	   hash_Exists(hash_tbl *, u_int code,
130			       hash_cmpfp, hash_datum *key);
131
132extern int	   hash_Insert(hash_tbl *, u_int code, hash_cmpfp,
133			       hash_datum *key, hash_datum *element);
134
135extern int	   hash_Delete(hash_tbl *, u_int code,
136			       hash_cmpfp, hash_datum *key,
137			       hash_freefp);
138
139extern hash_datum *hash_Lookup(hash_tbl *, u_int code,
140			       hash_cmpfp, hash_datum *key);
141
142extern hash_datum *hash_FirstEntry(hash_tbl *);
143
144extern hash_datum *hash_NextEntry(hash_tbl *);
145
146#endif	/* HASH_H */
147