b807f1059a3df9297f33d3ed170b6dbf6f4276b1
[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 #include <stddef.h>
32
33 /*
34  * The user is responsible for generating the key values corresponding
35  * to the data in the hash table.  The key values should be distributed
36  * over some interval [0,M], where M is sufficiently large, say
37  * M > 2**20 (1048576).
38  */
39
40 typedef struct afs_lhash afs_lhash;
41
42 struct afs_lhash_stat {
43     size_t      min_chain_length;
44     size_t      max_chain_length;
45     size_t      buckets;
46     size_t      records;
47
48     size_t      search_calls;   /* cumulative afs_lhash_search() call count */
49     size_t      search_tests;   /* cumulative afs_lhash_search() comparison count */
50     size_t      remove_calls;   /* cumulative afs_lhash_remove() call count */
51     size_t      remove_tests;   /* cumulative afs_lhash_remove() comparison count */
52 };
53
54 /*
55  * afs_lhash_create() allocates a new hash table.
56  *
57  * equal() -- compares table elements for equality
58  *
59  * allocate() -- allocates memory
60  *
61  * deallocate() -- frees memory acquired via allocate()
62  *
63  * afs_lhash_create() returns a pointer to the new hash table, or 0 on
64  * error.
65  */
66
67 afs_lhash *
68 afs_lhash_create
69 ( int (*equal)(const void *a, const void *b)
70         /* returns true if the elements pointed to by
71            a and b are the same, false otherwise */
72 , void *(*allocate)(size_t n)
73 , void (*deallocate)(void *p, size_t n)
74 );
75
76 /*
77  * afs_lhash_destroy() destroys the given hash table.
78  *
79  * Note that the caller is responsible for freeing the table elements if
80  * required.
81  */
82
83 void
84 afs_lhash_destroy
85 ( afs_lhash *lh
86 );
87
88 /*
89  * afs_lhash_iter() calls the given function for each element of the
90  * given hash table.
91  *
92  * The function called with the key and data pointer for each element of
93  * the hash table.  It is also given the hash table index value, in case
94  * the function wants to compute how many elements are in each bucket.
95  */
96
97 void
98 afs_lhash_iter
99 ( afs_lhash *lh
100 , void(*f)(size_t index, unsigned key, void *data)
101 );
102
103 /*
104  * afs_lhash_search() searches the given hash table for the given key
105  * and element.
106  *
107  * The element may be incomplete; it is compared to elements in the hash
108  * table using the hash table's equal() function.
109  *
110  * If the element is found, it is moved to the front of its hash chain
111  * list to try to make future lookups faster.
112  *
113  * afs_lhash_search() returns a pointer to the desired data element if
114  * found, 0 otherwise.
115  */
116
117 void *
118 afs_lhash_search
119 ( afs_lhash *lh
120 , unsigned key
121 , const void *data
122 );
123
124 /*
125  * afs_lhash_rosearch() searches the given hash table for the given key
126  * and element.
127  *
128  * The element may be incomplete; it is compared to elements in the hash
129  * table using the hash table's equal() function.
130  *
131  * The hash table is not modified.
132  *
133  * afs_lhash_rosearch() returns a pointer to the desired data element if
134  * found, 0 otherwise.
135  */
136
137 void *
138 afs_lhash_rosearch
139 ( const afs_lhash *lh
140 , unsigned key
141 , const void *data
142 );
143
144 /*
145  * afs_lhash_remove() removes an item matching the given key and data
146  * from the hash table.
147  *
148  * afs_lhash_remove() returns a pointer to the item removed on success,
149  * 0 otherwise.
150  */
151
152 void *
153 afs_lhash_remove
154 ( afs_lhash *lh
155 , unsigned key
156 , const void *data
157 );
158
159 /*
160  * afs_lhash_enter() enters the given data element into the given hash
161  * table using the given key.
162  *
163  * It is not an error to enter the same [key, data] twice, so the
164  * caller should check for duplicates if that is important.
165  *
166  * afs_lhash_enter() returns 0 on success, nonzero otherwise.
167  */
168
169 int
170 afs_lhash_enter
171 ( afs_lhash *lh
172 , unsigned key
173 , void *data
174 );
175
176 /*
177  * afs_lhash_stat() writes certain statistics about the given hash table
178  * into the given afs_lhash_stat structure.
179  *
180  * afs_lhash_stat() returns 0 on success, nonzero otherwise.
181  */
182
183 int
184 afs_lhash_stat
185 ( afs_lhash *lh
186 , struct afs_lhash_stat *sb
187 );
188
189 #endif /* AFS_LHASH_H */