no-stddef-in-kernel-20021009
[openafs.git] / src / util / afs_lhash.h
1 /*
2  * Copyright 2000, International Business Machines Corporation and others.
3  * All Rights Reserved.
4  * 
5  * This software has been released under the terms of the IBM Public
6  * License.  For details, see the LICENSE file in the top-level source
7  * directory or online at http://www.openafs.org/dl/license10.html
8  */
9
10 /*
11  * An afs_lhash is a linear hash table.  It is intended for use where
12  * the number of elements in the hash table is not known in advance.
13  * It grows as required in order to keep the average hash chain length
14  * within certain bounds, which keeps average lookup times small.
15  * Growth is efficient and does not require rehashing of all the
16  * elements in the table at once.
17  *
18  * The caller is responsible for doing any required locking.
19  *
20  * For more information on the algorithm, see
21  *
22  *      Dynamic Hash Tables
23  *      Per-Åke Larson (Per-Ake Larson)
24  *      Communications of the ACM
25  *      Vol. 31, No. 4 (April 1988), Pages 446-457
26  */
27
28 #ifndef AFS_LHASH_H
29 #define AFS_LHASH_H
30
31 #ifndef KERNEL
32 #include <stddef.h>
33 #endif
34
35 /*
36  * The user is responsible for generating the key values corresponding
37  * to the data in the hash table.  The key values should be distributed
38  * over some interval [0,M], where M is sufficiently large, say
39  * M > 2**20 (1048576).
40  */
41
42 typedef struct afs_lhash afs_lhash;
43
44 struct afs_lhash_stat {
45     size_t      min_chain_length;
46     size_t      max_chain_length;
47     size_t      buckets;
48     size_t      records;
49
50     size_t      search_calls;   /* cumulative afs_lhash_search() call count */
51     size_t      search_tests;   /* cumulative afs_lhash_search() comparison count */
52     size_t      remove_calls;   /* cumulative afs_lhash_remove() call count */
53     size_t      remove_tests;   /* cumulative afs_lhash_remove() comparison count */
54 };
55
56 /*
57  * afs_lhash_create() allocates a new hash table.
58  *
59  * equal() -- compares table elements for equality
60  *
61  * allocate() -- allocates memory
62  *
63  * deallocate() -- frees memory acquired via allocate()
64  *
65  * afs_lhash_create() returns a pointer to the new hash table, or 0 on
66  * error.
67  */
68
69 afs_lhash *
70 afs_lhash_create
71 ( int (*equal)(const void *a, const void *b)
72         /* returns true if the elements pointed to by
73            a and b are the same, false otherwise */
74 , void *(*allocate)(size_t n)
75 , void (*deallocate)(void *p, size_t n)
76 );
77
78 /*
79  * afs_lhash_destroy() destroys the given hash table.
80  *
81  * Note that the caller is responsible for freeing the table elements if
82  * required.
83  */
84
85 void
86 afs_lhash_destroy
87 ( afs_lhash *lh
88 );
89
90 /*
91  * afs_lhash_iter() calls the given function for each element of the
92  * given hash table.
93  *
94  * The function called with the key and data pointer for each element of
95  * the hash table.  It is also given the hash table index value, in case
96  * the function wants to compute how many elements are in each bucket.
97  */
98
99 void
100 afs_lhash_iter
101 ( afs_lhash *lh
102 , void(*f)(size_t index, unsigned key, void *data)
103 );
104
105 /*
106  * afs_lhash_search() searches the given hash table for the given key
107  * and element.
108  *
109  * The element may be incomplete; it is compared to elements in the hash
110  * table using the hash table's equal() function.
111  *
112  * If the element is found, it is moved to the front of its hash chain
113  * list to try to make future lookups faster.
114  *
115  * afs_lhash_search() returns a pointer to the desired data element if
116  * found, 0 otherwise.
117  */
118
119 void *
120 afs_lhash_search
121 ( afs_lhash *lh
122 , unsigned key
123 , const void *data
124 );
125
126 /*
127  * afs_lhash_rosearch() searches the given hash table for the given key
128  * and element.
129  *
130  * The element may be incomplete; it is compared to elements in the hash
131  * table using the hash table's equal() function.
132  *
133  * The hash table is not modified.
134  *
135  * afs_lhash_rosearch() returns a pointer to the desired data element if
136  * found, 0 otherwise.
137  */
138
139 void *
140 afs_lhash_rosearch
141 ( const afs_lhash *lh
142 , unsigned key
143 , const void *data
144 );
145
146 /*
147  * afs_lhash_remove() removes an item matching the given key and data
148  * from the hash table.
149  *
150  * afs_lhash_remove() returns a pointer to the item removed on success,
151  * 0 otherwise.
152  */
153
154 void *
155 afs_lhash_remove
156 ( afs_lhash *lh
157 , unsigned key
158 , const void *data
159 );
160
161 /*
162  * afs_lhash_enter() enters the given data element into the given hash
163  * table using the given key.
164  *
165  * It is not an error to enter the same [key, data] twice, so the
166  * caller should check for duplicates if that is important.
167  *
168  * afs_lhash_enter() returns 0 on success, nonzero otherwise.
169  */
170
171 int
172 afs_lhash_enter
173 ( afs_lhash *lh
174 , unsigned key
175 , void *data
176 );
177
178 /*
179  * afs_lhash_stat() writes certain statistics about the given hash table
180  * into the given afs_lhash_stat structure.
181  *
182  * afs_lhash_stat() returns 0 on success, nonzero otherwise.
183  */
184
185 int
186 afs_lhash_stat
187 ( afs_lhash *lh
188 , struct afs_lhash_stat *sb
189 );
190
191 #endif /* AFS_LHASH_H */