Gitiles
Code Review Sign In
git01.mediatek.com / haproxy / dbd3befae86e435ad8c685aad5b7346a2020e0b2 / . / src / chtbl.c
blob: 481b3ac637d13b5dbf27ac1b879f943764650c9b [file] [log] [blame]
willy tarreau12350152005-12-18 01:03:27 +0100[diff] [blame]1/*
2 This File is copied from
3
4 http://www.oreilly.com/catalog/masteralgoc/index.html
5 Mastering Algorithms with C
6 By Kyle Loudon
7 ISBN: 1-56592-453-3
8 Publishd by O'Reilly
9
10 */
11
12/*****************************************************************************
13 * *
14 * ------------------------------- chtbl.c -------------------------------- *
15 * *
16 *****************************************************************************/
17
18#include <stdlib.h>
19#include <string.h>
20
21#include <include/list.h>
22#include <include/chtbl.h>
23
24/*****************************************************************************
25 * *
26 * ------------------------------ chtbl_init ------------------------------ *
27 * *
28 *****************************************************************************/
29
30int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key), int
31 (*match)(const void *key1, const void *key2), void (*destroy)(void*data)) {
32
33 int i;
34
35 /*****************************************************************************
36 * *
37 * Allocate space for the hash table. *
38 * *
39 *****************************************************************************/
40
41 if ((htbl->table = (List *)malloc(buckets * sizeof(List))) == NULL)
42 return -1;
43
44 /*****************************************************************************
45 * *
46 * Initialize the buckets. *
47 * *
48 *****************************************************************************/
49
50 htbl->buckets = buckets;
51
52 for (i = 0; i < htbl->buckets; i++)
53 list_init(&htbl->table[i], destroy);
54
55 /*****************************************************************************
56 * *
57 * Encapsulate the functions. *
58 * *
59 *****************************************************************************/
60
61 htbl->h = h;
62 htbl->match = match;
63 htbl->destroy = destroy;
64
65 /*****************************************************************************
66 * *
67 * Initialize the number of elements in the table. *
68 * *
69 *****************************************************************************/
70
71 htbl->size = 0;
72
73 return 0;
74} /* end chtbl_init () */
75
76/*****************************************************************************
77 * *
78 * ---------------------------- chtbl_destroy ----------------------------- *
79 * *
80 *****************************************************************************/
81
82void chtbl_destroy(CHTbl *htbl) {
83
84 int i;
85
86 /*****************************************************************************
87 * *
88 * Destroy each bucket. *
89 * *
90 *****************************************************************************/
91
92 for (i = 0; i < htbl->buckets; i++) {
93 list_destroy(&htbl->table[i]);
94 } /* end for () */
95
96 /*****************************************************************************
97 * *
98 * Free the storage allocated for the hash table. *
99 * *
100 *****************************************************************************/
101
102 free(htbl->table);
103
104 /*****************************************************************************
105 * *
106 * No operations are allowed now, but clear the structure as a precaution. *
107 * *
108 *****************************************************************************/
109
110 memset(htbl, 0, sizeof(CHTbl));
111
112 return;
113} /* end chtbl_destroy() */
114
115/*****************************************************************************
116 * *
117 * ----------------------------- chtbl_insert ----------------------------- *
118 * *
119 *****************************************************************************/
120
121int chtbl_insert(CHTbl *htbl, const void *data) {
122
123 void *temp;
124 int bucket,retval;
125
126 /*****************************************************************************
127 * *
128 * Do nothing if the data is already in the table. *
129 * *
130 *****************************************************************************/
131
132 temp = (void *)data;
133
134 if (chtbl_lookup(htbl, &temp) == 0)
135 return 1;
136
137 /*****************************************************************************
138 * *
139 * Hash the key. *
140 * *
141 *****************************************************************************/
142
143 bucket = htbl->h(data) % htbl->buckets;
144
145 /*****************************************************************************
146 * *
147 * Insert the data into the bucket. *
148 * *
149 *****************************************************************************/
150
151 if ((retval = list_ins_next(&htbl->table[bucket], NULL, data)) == 0)
152 htbl->size++;
153
154 return retval;
155} /* end chtbl_insert() */
156
157/*****************************************************************************
158 * *
159 * ----------------------------- chtbl_remove ----------------------------- *
160 * *
161 *****************************************************************************/
162
163int chtbl_remove(CHTbl *htbl, void **data) {
164
165 ListElmt *element, *prev;
166 int bucket;
167
168 /*****************************************************************************
169 * *
170 * Hash the key. *
171 * *
172 *****************************************************************************/
173
174 bucket = htbl->h(*data) % htbl->buckets;
175
176 /*****************************************************************************
177 * *
178 * Search for the data in the bucket. *
179 * *
180 *****************************************************************************/
181
182 prev = NULL;
183
184 for (element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element)) {
185 if (htbl->match(*data, list_data(element))) {
186
187 /***********************************************************************
188 * *
189 * Remove the data from the bucket. *
190 * *
191 ***********************************************************************/
192
193 if (list_rem_next(&htbl->table[bucket], prev, data) == 0) {
194 htbl->size--;
195 return 0;
196 } /* end if() */
197 else {
198 return -1;
199 }/* end else */
200 }/* end if (htbl->match(*data, list_data(element))) */
201
202 prev = element;
203 }/* end for() */
204
205 /*****************************************************************************
206 * *
207 * Return that the data was not found. *
208 * *
209 *****************************************************************************/
210
211 return -1;
212} /* end int chtbl_remove(CHTbl *htbl, void **data) */
213
214/*****************************************************************************
215 * *
216 * ----------------------------- chtbl_lookup ----------------------------- *
217 * *
218 *****************************************************************************/
219
220int chtbl_lookup(const CHTbl *htbl, void **data) {
221
222 ListElmt *element;
223 int bucket;
224
225 /*****************************************************************************
226 * *
227 * Hash the key. *
228 * *
229 *****************************************************************************/
230
231 bucket = htbl->h(*data) % htbl->buckets;
232
233 /*****************************************************************************
234 * *
235 * Search for the data in the bucket. *
236 * *
237 *****************************************************************************/
238
239 for (element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element)) {
240 if (htbl->match(*data, list_data(element))) {
241
242 /***********************************************************************
243 * *
244 * Pass back the data from the table. *
245 * *
246 ***********************************************************************/
247
248 *data = list_data(element);
249 return 0;
250 }/* end if() */
251 }/* end for() */
252
253 /*****************************************************************************
254 * *
255 * Return that the data was not found. *
256 * *
257 *****************************************************************************/
258
259 return -1;
260} /* end chtbl_lookup() */