1 /*
2 * Copyright (c) 1993-2001 by Sun Microsystems, Inc.
3 * All rights reserved.
4 */
5
6 /*
7 * Copyright 1988, 1991 by Carnegie Mellon University
8 * All Rights Reserved
9 *
10 * Permission to use, copy, modify, and distribute this software and its
11 * documentation for any purpose and without fee is hereby granted, provided
12 * that the above copyright notice appear in all copies and that both that
13 * copyright notice and this permission notice appear in supporting
14 * documentation, and that the name of Carnegie Mellon University not be used
15 * in advertising or publicity pertaining to distribution of the software
16 * without specific, written prior permission.
17 *
18 * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
19 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
20 * IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
21 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
22 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
23 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
24 * THIS SOFTWARE.
25 */
26
27 #ifndef _HASH_H
28 #define _HASH_H
29
30 #pragma ident "%Z%%M% %I% %E% SMI"
31
32 /*
33 * Generalized hash table ADT
34 *
35 * Provides multiple, dynamically-allocated, variable-sized hash tables on
36 * various data and keys.
37 *
38 * This package attempts to follow some of the coding conventions suggested
39 * by Bob Sidebotham and the AFS Clean Code Committee.
40 */
41
42 /*
43 * The user must supply the following:
44 *
45 * 1. A comparison function which is declared as:
46 *
47 * int compare(data1, data2)
48 * hash_datum *data1, *data2;
49 *
50 * This function must compare the desired fields of data1 and
51 * data2 and return B_TRUE (1) if the data should be considered
52 * equivalent (i.e. have the same key value) or B_FALSE (0)
53 * otherwise. This function is called through a pointer passed to
54 * the various hashtable functions (thus pointers to different
55 * functions may be passed to effect different tests on different
56 * hash tables).
57 *
58 * Internally, all the functions of this package always call the
59 * compare function with the "key" parameter as the first parameter,
60 * and a full data element as the second parameter. Thus, the key
61 * and element arguments to functions such as hash_Lookup() may
62 * actually be of different types and the programmer may provide a
63 * compare function which compares the two different object types
64 * as desired.
65 *
66 * Example:
67 *
68 * int compare(key, element)
69 * char *key;
70 * struct some_complex_structure *element;
71 * {
72 * return !strcmp(key, element->name);
73 * }
74 *
75 * key = "John C. Doe"
76 * element = &some_complex_structure
77 * hash_Lookup(table, hashptr, hashlen, compare, key, free_rec, B_TRUE);
78 *
79 * 2. A hash function yielding an unsigned integer value to be used
80 * as the hashcode (index into the hashtable). Thus, the user
81 * may hash on whatever data is desired and may use several
82 * different hash functions for various different hash tables.
83 * The actual hash table index will be the passed hashcode modulo
84 * the hash table size.
85 *
86 * A generalized hash function, hash_HashFunction(), is included
87 * with this package to make things a little easier. It is not
88 * guarenteed to use the best hash algorithm in existence. . . .
89 *
90 * 3. An ability to garbage collect data has been added. Timed garbage
91 * collection of hash members is provided to relieve the interface and worker
92 * threads of explicit data structure management. Expired data structures
93 * are pruned during hash insertion and deletion, or by explicit calls
94 * to Delete and Reap functions.
95 */
96
97 #ifdef __cplusplus
98 extern "C" {
99 #endif
100
101 /*
102 * Various hash table definitions
103 */
104
105 /*
106 * Define "hash_datum" as a universal data type
107 */
108 typedef void hash_datum;
109 typedef void *hash_handle;
110
111 typedef struct hash_memberstruct hash_member;
112 typedef struct hash_bucketstruct hash_bucket;
113 typedef struct hash_tblstruct hash_tbl;
114 typedef struct hash_tblstruct_hdr hash_tblhdr;
115
116 struct hash_memberstruct {
117 hash_member *next; /* hash next pointer */
118 hash_datum *data; /* hash data */
119 time_t h_time; /* hash dynamic free time */
120 int h_count; /* hash reference count */
121 mutex_t h_mtx; /* hash mutex */
122 };
123
124 struct hash_tblstruct;
125 struct hash_bucketstruct {
126 hash_member *next;
127 struct hash_tblstruct *table;
128 rwlock_t rwlock;
129 };
130
131 struct hash_tblstruct_hdr {
132 unsigned size;
133 unsigned bucketnum;
134 hash_member *member;
135 };
136
137 struct hash_tblstruct {
138 unsigned size;
139 unsigned bucketnum;
140 hash_member *member; /* Used for linear dump */
141 boolean_t (*dfree_data)(); /* Used for dynamic free */
142 boolean_t dfree_lck; /* Use for dynamic free locking */
143 time_t dfree_time; /* Unused time to dynamically free */
144 hash_bucket *table; /* Dynamically Extend */
145 hash_bucket data[1];
146 };
147
148 extern unsigned hash_Size(unsigned int);
149 extern hash_tbl *hash_Init(unsigned, boolean_t (*)(), time_t, boolean_t);
150 extern void hash_Reset(hash_tbl *, boolean_t (*)());
151 extern void *hash_Insert(hash_tbl *, void *, unsigned, int (*)(),
152 hash_datum *, hash_datum *);
153 extern hash_datum *hash_Lookup(hash_tbl *, void *, unsigned, int (*)(),
154 hash_datum *, boolean_t);
155 extern boolean_t hash_Delete(hash_tbl *, void *, unsigned, int (*)(),
156 hash_datum *, boolean_t (*)());
157 extern void hash_Reap(hash_tbl *, boolean_t (*)());
158 extern void hash_Age(void *);
159 extern void hash_Dtime(void *, time_t);
160 extern int hash_Refcount(void *);
161 extern int hash_Htime(void *);
162 extern void hash_Rele(void *, boolean_t);
163
164 #ifdef __cplusplus
165 }
166 #endif
167
168 #endif /* _HASH_H */