1 /*
2 * Copyright (c) 2001 Mark Fullmer and The Ohio State University
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $Id: ftchash.c,v 1.14 2003/08/12 18:04:25 maf Exp $
27 */
28
29 #include "ftconfig.h"
30 #include "ftlib.h"
31
32 #include <stdlib.h>
33 #include <stddef.h>
34
35 #if HAVE_STRINGS_H
36 #include <strings.h>
37 #endif
38 #if HAVE_STRING_H
39 #include <string.h>
40 #endif
41
42 int sort_offset;
43 static int cmp64(const void *a, const void *b);
44 static int cmp40(const void *a, const void *b);
45 static int cmp32(const void *a, const void *b);
46 static int cmp16(const void *a, const void *b);
47 static int cmp8(const void *a, const void *b);
48 static int cmp_double(const void *a, const void *b);
49
50 /*
51 * function: ftchash_new
52 *
53 * allocate and initialize new hash structure.
54 *
55 * h_size - size of hash table (number of buckets)
56 * d_size - size of data record (multiple of long word byte alignment)
57 * key_size - size of key
58 * chunk_entries - number of data entries per chunk
59 *
60 * returns allocated structure or 0L for error.
61 *
62 */
ftchash_new(int h_size,int d_size,int key_size,int chunk_entries)63 struct ftchash *ftchash_new(int h_size, int d_size, int key_size,
64 int chunk_entries)
65 {
66 struct ftchash *ftch;
67 int i;
68
69 /* allocate ftchash */
70 if (!(ftch = (struct ftchash*)malloc(sizeof (struct ftchash)))) {
71 fterr_warn("malloc()");
72 return ftch;
73 }
74
75 /* init */
76 bzero(ftch, sizeof (struct ftchash));
77 ftch->h_size = h_size;
78 ftch->d_size = d_size;
79 ftch->key_size = key_size;
80 ftch->chunk_size = chunk_entries * d_size;
81 FT_SLIST_INIT(&ftch->chunk_list);
82
83 /* allocate h_size buckets */
84 if (!(ftch->buckets = (struct ftchash_bhead*)malloc(
85 sizeof (struct ftchash_bhead)*h_size))) {
86 fterr_warn("malloc()");
87 free (ftch);
88 return (struct ftchash*)0L;
89 }
90
91 /* init buckets */
92 for (i = 0; i < h_size; ++i)
93 FT_SLIST_INIT(&(*ftch).buckets[i]);
94
95 return ftch;
96
97 } /* ftchash_new */
98
99 /*
100 * function: ftchash_free
101 *
102 * free storage allocated with ftchash_new
103 */
ftchash_free(struct ftchash * ftch)104 void ftchash_free(struct ftchash *ftch)
105 {
106 struct ftchash_chunk *chunk;
107
108 if (ftch) {
109
110 if (ftch->buckets)
111 free (ftch->buckets);
112
113 if (ftch->sorted_recs)
114 free (ftch->sorted_recs);
115
116 while ((chunk = FT_SLIST_FIRST(&ftch->chunk_list))) {
117 FT_SLIST_REMOVE_HEAD(&ftch->chunk_list, chain);
118 free (chunk->base);
119 free (chunk);
120 }
121
122 free (ftch);
123 }
124 } /* ftchash_free */
125
126 /*
127 * function: ftchash_lookup
128 *
129 * lookup record in hash table
130 *
131 * returns pointer to record found or
132 * *0L if not found
133 */
ftchash_lookup(struct ftchash * ftch,void * key,uint32_t hash)134 void *ftchash_lookup(struct ftchash *ftch, void *key, uint32_t hash)
135 {
136
137 struct ftchash_rec_gen *rec;
138 struct ftchash_bhead *bhead;
139 int keyoff;
140
141 /* offset to key */
142 keyoff = offsetof(struct ftchash_rec_gen, data);
143
144 /* lookup hash entry */
145 bhead = &(*ftch).buckets[hash];
146
147 /* walk down chain */
148 FT_SLIST_FOREACH(rec, bhead, chain) {
149
150 /* if found return pointer */
151 if (!bcmp((char*)rec+keyoff, (char*)key, ftch->key_size))
152 return rec;
153
154 }
155
156 return (void*)0L;
157
158 } /* ftchash_lookup */
159
160 /*
161 * function: ftchash_update
162 *
163 * add record to hash table. key_size bytes will be copied from rec to
164 * the allocated hash record. The caller must update the remaining
165 * area of rec. hash value must be less than h_size.
166 *
167 * returns 0L on error
168 * or pointer to allocated record
169 */
ftchash_update(struct ftchash * ftch,void * newrec,uint32_t hash)170 void *ftchash_update(struct ftchash *ftch, void *newrec, uint32_t hash)
171 {
172
173 struct ftchash_rec_gen *rec;
174 struct ftchash_bhead *bhead;
175 int keyoff;
176
177 /* no longer sorted */
178 ftch->sort_flags &= ~FT_CHASH_SORTED;
179
180 /* offset to key */
181 keyoff = offsetof(struct ftchash_rec_gen, data);
182
183 /* lookup hash entry */
184 bhead = &(*ftch).buckets[hash];
185
186 /* walk down chain */
187 FT_SLIST_FOREACH(rec, bhead, chain) {
188
189 /* if found return pointer */
190 if (!bcmp((char*)rec+keyoff, (char*)newrec+keyoff, ftch->key_size))
191 return rec;
192
193 }
194
195 /* not found, allocate new entry */
196 if (!(rec = (struct ftchash_rec_gen*) ftchash_alloc_rec(ftch))) {
197 fterr_warnx("ftchash_alloc_rec(): failed");
198 return (void*)0L;
199 }
200
201 /* add to chain */
202 FT_SLIST_INSERT_HEAD(bhead, rec, chain);
203
204 /* copy in key */
205 bcopy((char*)newrec+keyoff, (char*)rec+keyoff, ftch->key_size);
206
207 /* increment storage counter */
208 ftch->entries ++;
209
210 /* return new record pointer */
211 return rec;
212
213 } /* ftchash_update */
214
215 /*
216 * function: ftchash_alloc_rec
217 *
218 * allocate a new record
219 *
220 * chunk pointer is added to ftch->chunk_list when adding new chunk
221 *
222 * a chunk will always contain at least 1 record
223 *
224 * returns 0L on error
225 * or pointer to allocated record
226 */
ftchash_alloc_rec(struct ftchash * ftch)227 void *ftchash_alloc_rec(struct ftchash *ftch)
228 {
229 void *p;
230 struct ftchash_chunk *chunk;
231
232 if ((!ftch->active_chunk) || (ftch->active_chunk->next >= ftch->chunk_size)) {
233
234 /* allocate the chunk */
235 if (!(p = malloc(ftch->chunk_size))) {
236 fterr_warnx("malloc()");
237 return (void*)0L;
238 }
239
240 bzero(p, ftch->chunk_size);
241
242 /* allocate the chunk holder */
243 if (!(chunk = (struct ftchash_chunk*)malloc(
244 sizeof (struct ftchash_chunk)))) {
245 fterr_warnx("malloc()");
246 free (p);
247 return (void*)0L;
248 }
249
250 bzero(chunk, sizeof (struct ftchash_chunk));
251 chunk->base = p;
252
253 ftch->active_chunk = chunk;
254
255 FT_SLIST_INSERT_HEAD(&ftch->chunk_list, chunk, chain);
256
257 }
258
259 p = (char*)ftch->active_chunk->base + ftch->active_chunk->next;
260 ftch->active_chunk->next += ftch->d_size;
261 return p;
262
263 } /* ftchash_alloc_rec */
264
265 /*
266 * function: ftchash_first
267 *
268 * setup ftchash_foreach to first entry;
269 */
ftchash_first(struct ftchash * ftch)270 void ftchash_first(struct ftchash *ftch)
271 {
272 struct ftchash_chunk *chunk;
273
274 if (ftch->sort_flags & FT_CHASH_SORTED) {
275 if (ftch->sort_flags & FT_CHASH_SORT_ASCENDING)
276 ftch->traverse_srec = ftch->entries;
277 else
278 ftch->traverse_srec = 0;
279 } else {
280
281 chunk = FT_SLIST_FIRST(&ftch->chunk_list);
282
283 if (chunk) {
284 ftch->traverse_chunk = chunk;
285 ftch->traverse_rec = chunk->base;
286 } else {
287 ftch->traverse_rec = (void*)0L;
288 ftch->traverse_chunk = (void*)0L;
289 }
290 } /* sorted? */
291 } /* ftchash_first */
292
293 /*
294 * function: ftchash_foreach
295 *
296 * returns next entry in hash table, or NULL if the last entry
297 * ftchash_first() must be called first.
298 *
299 */
ftchash_foreach(struct ftchash * ftch)300 void *ftchash_foreach(struct ftchash *ftch)
301 {
302 struct ftchash_chunk *chunk;
303 void *ret;
304
305 if (ftch->sort_flags & FT_CHASH_SORTED) {
306 if (ftch->sort_flags & FT_CHASH_SORT_ASCENDING) {
307 if (ftch->traverse_srec > 0)
308 return (ftch->sorted_recs[--ftch->traverse_srec]);
309 else
310 return (void*)0L;
311 } else {
312 if (ftch->traverse_srec < ftch->entries)
313 return (ftch->sorted_recs[ftch->traverse_srec++]);
314 else
315 return (void*)0L;
316 }
317 } else {
318
319 /* only happens on empty hash table -- done */
320 if (!ftch->traverse_chunk)
321 return (void*)0L;
322
323
324 /* more entries in this chunk *? */
325 if ((char*)ftch->traverse_rec <
326 (char*)ftch->traverse_chunk->base+ftch->traverse_chunk->next) {
327
328 ret = ftch->traverse_rec;
329 ftch->traverse_rec = (char*)ftch->traverse_rec + ftch->d_size;
330
331 return ret;
332
333 } else {
334
335 /* go to next chunk */
336 chunk = FT_SLIST_NEXT(ftch->traverse_chunk, chain);
337
338 /* if this is a valid chunk, return first record */
339 if (chunk) {
340 ftch->traverse_chunk = chunk;
341 ftch->traverse_rec = (char*)ftch->traverse_chunk->base + ftch->d_size;
342 return (chunk->base);
343 } else { /* else that was the last chunk, done */
344 return (void*)0L;
345 }
346 }
347 } /* sorted? */
348 } /* ftchash_foreach */
349
350 /*
351 * function: ftchash_sort
352 *
353 * creates an array of pointers to the sorted records
354 *
355 * returns -1 on error
356 * 0 otherwise
357 */
ftchash_sort(struct ftchash * ftch,int offset,int flags)358 int ftchash_sort(struct ftchash *ftch, int offset, int flags)
359 {
360 void *rec;
361 uint64_t x;
362
363 /* entries to sort? */
364 if (!ftch->entries)
365 return 0;
366
367 /* free memory from previous call */
368 if (ftch->sorted_recs)
369 free(ftch->sorted_recs);
370
371 /* allocate ftch->entries * sizeof 32 bit pointer */
372 if (!(ftch->sorted_recs = (struct ftchash_rec_gen**)
373 malloc(sizeof (struct ftchash_rec_gen*)*ftch->entries))) {
374 fterr_warn("malloc()");
375 return -1;
376 }
377
378 ftch->sort_flags = flags;
379
380 /* copy in the unsorted entries */
381 ftchash_first(ftch);
382 x = 0;
383 while ((rec = ftchash_foreach(ftch))) {
384
385 ftch->sorted_recs[x++] = (struct ftchash_rec_gen*)rec;
386
387 } /* while */
388
389 sort_offset = offset;
390
391 if (flags & FT_CHASH_SORT_64)
392 qsort(ftch->sorted_recs, ftch->entries, sizeof (void*), cmp64);
393 else if (flags & FT_CHASH_SORT_40)
394 qsort(ftch->sorted_recs, ftch->entries, sizeof (void*), cmp40);
395 else if (flags & FT_CHASH_SORT_32)
396 qsort(ftch->sorted_recs, ftch->entries, sizeof (void*), cmp32);
397 else if (flags & FT_CHASH_SORT_16)
398 qsort(ftch->sorted_recs, ftch->entries, sizeof (void*), cmp16);
399 else if (flags & FT_CHASH_SORT_8)
400 qsort(ftch->sorted_recs, ftch->entries, sizeof (void*), cmp8);
401 else if (flags & FT_CHASH_SORT_DOUBLE)
402 qsort(ftch->sorted_recs, ftch->entries, sizeof (void*), cmp_double);
403 else
404 fterr_errx(1, "ftchash_sort(): internal error");
405
406 ftch->sort_flags |= FT_CHASH_SORTED;
407
408 return 0;
409
410 } /* ftchash_sort */
411
cmp64(const void * a,const void * b)412 static int cmp64(const void *a, const void *b)
413 {
414 uint64_t *la, *lb;
415 char *d;
416
417 d = *(char**)a;
418 la = (uint64_t*)(d+sort_offset);
419
420 d = *(char**)b;
421 lb = (uint64_t*)(d+sort_offset);
422
423 if (*la < *lb)
424 return -1;
425 if (*la > *lb)
426 return 1;
427 return 0;
428
429 } /* cmp64 */
430
cmp40(const void * a,const void * b)431 static int cmp40(const void *a, const void *b)
432 {
433 uint32_t *la, *lb;
434 uint8_t *ca, *cb;
435 char *d;
436
437 d = *(char**)a;
438 la = (uint32_t*)(d+sort_offset);
439
440 d = *(char**)b;
441 lb = (uint32_t*)(d+sort_offset);
442
443 if (*la < *lb)
444 return -1;
445 if (*la > *lb)
446 return 1;
447
448 d = *(char**)a;
449 ca = (uint8_t*)(d+sort_offset+4);
450
451 d = *(char**)b;
452 cb = (uint8_t*)(d+sort_offset+4);
453
454 if (*ca < *cb)
455 return -1;
456 if (*ca > *cb)
457 return 1;
458
459 return 0;
460
461 } /* cmp40 */
462
cmp32(const void * a,const void * b)463 static int cmp32(const void *a, const void *b)
464 {
465 uint32_t *la, *lb;
466 char *d;
467
468 d = *(char**)a;
469 la = (uint32_t*)(d+sort_offset);
470
471 d = *(char**)b;
472 lb = (uint32_t*)(d+sort_offset);
473
474 if (*la < *lb)
475 return -1;
476 if (*la > *lb)
477 return 1;
478 return 0;
479
480 } /* cmp32 */
481
cmp16(const void * a,const void * b)482 static int cmp16(const void *a, const void *b)
483 {
484 uint16_t *la, *lb;
485 char *d;
486
487 d = *(char**)a;
488 la = (uint16_t*)(d+sort_offset);
489
490 d = *(char**)b;
491 lb = (uint16_t*)(d+sort_offset);
492
493 if (*la < *lb)
494 return -1;
495 if (*la > *lb)
496 return 1;
497 return 0;
498
499 } /* cmp16 */
500
cmp8(const void * a,const void * b)501 static int cmp8(const void *a, const void *b)
502 {
503 uint8_t *la, *lb;
504 char *d;
505
506 d = *(char**)a;
507 la = (uint8_t*)(d+sort_offset);
508
509 d = *(char**)b;
510 lb = (uint8_t*)(d+sort_offset);
511
512 if (*la < *lb)
513 return -1;
514 if (*la > *lb)
515 return 1;
516 return 0;
517
518 } /* cmp8 */
519
cmp_double(const void * a,const void * b)520 static int cmp_double(const void *a, const void *b)
521 {
522 double *la, *lb;
523 char *d;
524
525 d = *(char**)a;
526 la = (double*)(d+sort_offset);
527
528 d = *(char**)b;
529 lb = (double*)(d+sort_offset);
530
531 if (*la < *lb)
532 return -1;
533 if (*la > *lb)
534 return 1;
535 return 0;
536
537 } /* cmp_double */
538
539