windows-kfw-sdk-20060921
[openafs.git] / src / WINNT / kfw / inc / netidmgr / hashtable.h
1 /*
2  * Copyright (c) 2005 Massachusetts Institute of Technology
3  *
4  * Permission is hereby granted, free of charge, to any person
5  * obtaining a copy of this software and associated documentation
6  * files (the "Software"), to deal in the Software without
7  * restriction, including without limitation the rights to use, copy,
8  * modify, merge, publish, distribute, sublicense, and/or sell copies
9  * of the Software, and to permit persons to whom the Software is
10  * furnished to do so, subject to the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be
13  * included in all copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24
25 /* $Id$ */
26
27 #ifndef __KHIMAIRA_HASHTABLE_H
28 #define __KHIMAIRA_HASHTABLE_H
29
30 /*! \addtogroup util
31   @{ */
32
33 /*! \defgroup util_ht Hashtable
34   @{*/
35
36 #include<khdefs.h>
37 #include<khlist.h>
38
39 /*! \brief A hash function
40
41     The function should take a key as a parameter and return an
42     khm_int32 that serves as the hash of the key.
43  */
44 typedef khm_int32 (*hash_function_t)(const void *key);
45
46 /*! \brief A comparison function
47
48     The function takes two keys and returns a value indicating the
49     relative ordering of the two keys.
50
51     The return value should be:
52     - \b Zero if \a key1 == \a key2
53     - \b Negative if \a key1 &lt; \a key2
54     - \b Positive if \a key1 &gt; \a key2
55  */
56 typedef khm_int32 (*comp_function_t)(const void *key1, const void *key2);
57
58 /*! \brief Add-reference function
59
60     When an object is successfully added to a hashtable, this function
61     will be called with the \a key and \a data used to add the object.
62     The function is allowed to modify \a data, however, the
63     modification should not alter the \a key or the relationship
64     between \a key and \a data.
65  */
66 typedef void (*add_ref_function_t)(const void *key, void *data);
67
68 /*! \brief Delete-reference function
69
70     When an object is successfully removed from the hashtable, this
71     function will be called.  As with the add-ref function, the object
72     can be modified, but the \a key and the relationship between \a
73     key and \a data should remain intact.
74
75     An object is removed if it is explicitly removed from the
76     hashtable or another object with the same \a key is added to the
77     hashtable.  There should be a 1-1 correspondence with keys and
78     objects in the hashtable.  The delete-reference function will be
79     called on all the remaining objects in the hashtable when the
80     hashtable is deleted.
81  */
82 typedef void (*del_ref_function_t)(const void *key, void *data);
83
84 typedef struct tag_hash_bin {
85     void * data;
86     void * key;
87
88     LDCL(struct tag_hash_bin);
89 } hash_bin;
90
91 typedef struct hashtable_t {
92     khm_int32 n;
93     hash_function_t hash;
94     comp_function_t comp;
95     add_ref_function_t addr;
96     del_ref_function_t delr;
97     hash_bin ** bins;
98 } hashtable;
99
100 /*! \brief Create a new hashtable
101
102     \param[in] n Number of bins in hashtable.
103     \param[in] hash A hash function. Required.
104     \param[in] comp A comparator.  Required.
105     \param[in] addr An add-ref function.  Optional; can be NULL.
106     \param[in] delr A del-ref function. Optional; can be NULL.
107
108  */
109 KHMEXP hashtable * KHMAPI hash_new_hashtable(khm_int32 n, 
110                                hash_function_t hash, 
111                                comp_function_t comp,
112                                add_ref_function_t addr,
113                                del_ref_function_t delr);
114
115 /*! \brief Delete a hashtable
116
117     \note Not thread-safe.  Applications must serialize calls that
118         reference the same hashtable.
119  */
120 KHMEXP void KHMAPI hash_del_hashtable(hashtable * h);
121
122 /*! \brief Add an object to a hashtable
123
124     Creates an association between the \a key and \a data in the
125     hashtable \a h.  If there is an add-ref function defined for the
126     hashtable, it will be called with \a key and \data after the
127     object is added.  If there is already an object with the same key
128     in the hashtable, that object will be removed (and the del-ref
129     function called, if appilcable) before adding the new object and
130     before the add-ref function is called for the new object.
131
132     Note that two keys \a key1 and \a key2 are equal (or same) in a
133     hashtable if the comparator returns zero when called with \a key1
134     and \a key2.
135
136     Also note that all additions and removals to the hashtable are
137     done by reference.  No data is copied.  Any objects pointed to are
138     expected to exist for the duration that the object and key are
139     contained in the hashtable.
140
141     \param[in] h Hashtable
142     \param[in] key A key.  If \a key points to a location in memory,
143         it should be within the object pointed to by \a data, or be a
144         constant. Can be NULL.
145     \param[in] data Data. Cannot be NULL.
146
147     \note Not thread-safe.  Applications must serialize calls that
148         reference the same hashtable.
149  */
150 KHMEXP void KHMAPI hash_add(hashtable * h, void * key, void * data);
151
152 /*! \brief Delete an object from a hashtable
153
154     Deletes the object in the hashtable \a h that is associated with
155     key \a key.  An object is associated with key \a key if the key \a
156     key_o that the object is associated with is the same as \a key as
157     determined by the comparator.  If the del-ref function is defined
158     for the hash-table, it will be called with the \a key_o and \a
159     data that was used to add the object.
160
161     \note Not thread-safe.  Applications must serialize calls that
162         reference the same hashtable.
163  */
164 KHMEXP void KHMAPI hash_del(hashtable * h, void * key);
165
166 /*! \brief Resolve and association
167
168     Return the object that is associated with key \a key in hashtable
169     \a h.  An object \a data is associated with key \a key in \a h if
170     the key \a key_o that was used to add \a data to \a h is equal to
171     \a key as determined by the comparator.
172
173     Returns NULL if no association is found.
174
175     \note Not thread-safe.  Applications must serialize calls that
176         reference the same hashtable.
177  */
178 KHMEXP void * KHMAPI hash_lookup(hashtable * h, void * key);
179
180 /*! \brief Check for the presence of an association
181
182     Returns non-zero if there exists an association between key \a key
183     and some object in hashtable \a h.  See hash_lookup() for
184     definition of "association".
185
186     Returns zero if there is no association.
187
188     \note (hash_lookup(h,key) == NULL) iff (hash_exist(h,key)==0)
189
190     \note Not thead-safe.  Application must serialize calls that
191         reference the same hashtable.
192  */
193 KHMEXP khm_boolean KHMAPI hash_exist(hashtable * h, void * key);
194
195 /*! \brief Compute a hashvalue for a unicode string
196
197     The hash value is computed using DJB with parameter 13331.
198
199     This function is suitable for use as the hash function for a
200     hashtable if the keys are NULL terminated safe unicode strings
201     that are either part of the data objects or are constants.
202
203     \param[in] str A pointer to a NULL terminated wchar_t string cast
204         as (void *).
205  */
206 KHMEXP khm_int32 hash_string(const void *str);
207
208 /*! \brief Compare two strings
209
210     Compares two strings are returns a value that is in accordance
211     with the comparator for a hashtable.
212
213     \param[in] vs1 A pointer to a NULL terminated wchar_t string cast
214         as (void *).
215     \param[in] vs2 A pointer to a NULL terminated wchar_t string cast
216         as (void *).
217  */
218 KHMEXP khm_int32 hash_string_comp(const void *vs1, const void *vs2);
219
220 /*@}*/
221 /*@}*/
222
223 #endif