4 /************************************************************************
5 Copyright 1988, 1991 by Carnegie Mellon University
9 Permission to use, copy, modify, and distribute this software and its
10 documentation for any purpose and without fee is hereby granted, provided
11 that the above copyright notice appear in all copies and that both that
12 copyright notice and this permission notice appear in supporting
13 documentation, and that the name of Carnegie Mellon University not be used
14 in advertising or publicity pertaining to distribution of the software
15 without specific, written prior permission.
17 CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
18 SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
19 IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
20 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
21 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
22 ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
24 ************************************************************************/
27 * Generalized hash table ADT
30 * Provides multiple, dynamically-allocated, variable-sized hash tables on
31 * various data and keys.
33 * This package attempts to follow some of the coding conventions suggested
34 * by Bob Sidebotham and the AFS Clean Code Committee.
39 * The user must supply the following:
41 * 1. A comparison function which is declared as:
43 * int compare(data1, data2)
44 * hash_datum *data1, *data2;
46 * This function must compare the desired fields of data1 and
47 * data2 and return TRUE (1) if the data should be considered
48 * equivalent (i.e. have the same key value) or FALSE (0)
49 * otherwise. This function is called through a pointer passed to
50 * the various hashtable functions (thus pointers to different
51 * functions may be passed to effect different tests on different
54 * Internally, all the functions of this package always call the
55 * compare function with the "key" parameter as the first parameter,
56 * and a full data element as the second parameter. Thus, the key
57 * and element arguments to functions such as hash_Lookup() may
58 * actually be of different types and the programmer may provide a
59 * compare function which compares the two different object types
64 * int compare(key, element)
66 * struct some_complex_structure *element;
68 * return !strcmp(key, element->name);
72 * element = &some_complex_structure
73 * hash_Lookup(table, hashcode, compare, key);
75 * 2. A hash function yielding an unsigned integer value to be used
76 * as the hashcode (index into the hashtable). Thus, the user
77 * may hash on whatever data is desired and may use several
78 * different hash functions for various different hash tables.
79 * The actual hash table index will be the passed hashcode modulo
80 * the hash table size.
82 * A generalized hash function, hash_HashFunction(), is included
83 * with this package to make things a little easier. It is not
84 * guaranteed to use the best hash algorithm in existence. . . .
90 * Various hash table definitions
95 * Define "hash_datum" as a universal data type
97 typedef void hash_datum;
99 typedef struct hash_memberstruct hash_member;
100 typedef struct hash_tblstruct hash_tbl;
101 typedef struct hash_tblstruct_hdr hash_tblhdr;
103 struct hash_memberstruct {
108 struct hash_tblstruct_hdr {
109 unsigned size, bucketnum;
113 struct hash_tblstruct {
114 unsigned size, bucketnum;
115 hash_member *member; /* Used for linear dump */
116 hash_member *table[1]; /* Dynamically extended */
119 /* ANSI function prototypes or empty arg list? */
121 typedef int (*hash_cmpfp)(hash_datum *, hash_datum *);
122 typedef void (*hash_freefp)(hash_datum *);
124 extern hash_tbl *hash_Init(u_int tablesize);
126 extern void hash_Reset(hash_tbl *tbl, hash_freefp);
128 extern unsigned hash_HashFunction(u_char *str, u_int len);
130 extern int hash_Exists(hash_tbl *, u_int code,
131 hash_cmpfp, hash_datum *key);
133 extern int hash_Insert(hash_tbl *, u_int code,
134 hash_cmpfp, hash_datum *key,
135 hash_datum *element);
137 extern int hash_Delete(hash_tbl *, u_int code,
138 hash_cmpfp, hash_datum *key,
141 extern hash_datum *hash_Lookup(hash_tbl *, u_int code,
142 hash_cmpfp, hash_datum *key);
144 extern hash_datum *hash_FirstEntry(hash_tbl *);
146 extern hash_datum *hash_NextEntry(hash_tbl *);