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