106a99fe3SHajimu UMEMOTO /*- 206a99fe3SHajimu UMEMOTO * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru> 306a99fe3SHajimu UMEMOTO * All rights reserved. 406a99fe3SHajimu UMEMOTO * 506a99fe3SHajimu UMEMOTO * Redistribution and use in source and binary forms, with or without 606a99fe3SHajimu UMEMOTO * modification, are permitted provided that the following conditions 706a99fe3SHajimu UMEMOTO * are met: 806a99fe3SHajimu UMEMOTO * 1. Redistributions of source code must retain the above copyright 906a99fe3SHajimu UMEMOTO * notice, this list of conditions and the following disclaimer. 1006a99fe3SHajimu UMEMOTO * 2. Redistributions in binary form must reproduce the above copyright 1106a99fe3SHajimu UMEMOTO * notice, this list of conditions and the following disclaimer in the 1206a99fe3SHajimu UMEMOTO * documentation and/or other materials provided with the distribution. 1306a99fe3SHajimu UMEMOTO * 1406a99fe3SHajimu UMEMOTO * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1506a99fe3SHajimu UMEMOTO * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1606a99fe3SHajimu UMEMOTO * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1706a99fe3SHajimu UMEMOTO * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1806a99fe3SHajimu UMEMOTO * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1906a99fe3SHajimu UMEMOTO * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2006a99fe3SHajimu UMEMOTO * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2106a99fe3SHajimu UMEMOTO * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2206a99fe3SHajimu UMEMOTO * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2306a99fe3SHajimu UMEMOTO * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2406a99fe3SHajimu UMEMOTO * SUCH DAMAGE. 2506a99fe3SHajimu UMEMOTO * 2606a99fe3SHajimu UMEMOTO * $FreeBSD$ 2706a99fe3SHajimu UMEMOTO */ 2806a99fe3SHajimu UMEMOTO 2906a99fe3SHajimu UMEMOTO #ifndef __CACHELIB_HASHTABLE_H__ 3006a99fe3SHajimu UMEMOTO #define __CACHELIB_HASHTABLE_H__ 3106a99fe3SHajimu UMEMOTO 3206a99fe3SHajimu UMEMOTO #include <string.h> 3306a99fe3SHajimu UMEMOTO 3406a99fe3SHajimu UMEMOTO #define HASHTABLE_INITIAL_ENTRIES_CAPACITY 8 352bdde973SDag-Erling Smørgrav typedef unsigned int hashtable_index_t; 3606a99fe3SHajimu UMEMOTO 3706a99fe3SHajimu UMEMOTO /* 3806a99fe3SHajimu UMEMOTO * This file contains queue.h-like macro definitions for hash tables. 3906a99fe3SHajimu UMEMOTO * Hash table is organized as an array of the specified size of the user 4006a99fe3SHajimu UMEMOTO * defined (with HASTABLE_ENTRY_HEAD) structures. Each hash table 4106a99fe3SHajimu UMEMOTO * entry (user defined structure) stores its elements in the sorted array. 4206a99fe3SHajimu UMEMOTO * You can place elements into the hash table, retrieve elements with 4306a99fe3SHajimu UMEMOTO * specified key, traverse through all elements, and delete them. 4406a99fe3SHajimu UMEMOTO * New elements are placed into the hash table by using the compare and 4506a99fe3SHajimu UMEMOTO * hashing functions, provided by the user. 4606a99fe3SHajimu UMEMOTO */ 4706a99fe3SHajimu UMEMOTO 4806a99fe3SHajimu UMEMOTO /* 4906a99fe3SHajimu UMEMOTO * Defines the hash table entry structure, that uses specified type of 5006a99fe3SHajimu UMEMOTO * elements. 5106a99fe3SHajimu UMEMOTO */ 5206a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_HEAD(name, type) struct name { \ 5306a99fe3SHajimu UMEMOTO type *values; \ 5406a99fe3SHajimu UMEMOTO size_t capacity; \ 5506a99fe3SHajimu UMEMOTO size_t size; \ 5606a99fe3SHajimu UMEMOTO } 5706a99fe3SHajimu UMEMOTO 5806a99fe3SHajimu UMEMOTO /* 5906a99fe3SHajimu UMEMOTO * Defines the hash table structure, which uses the specified type of entries. 6006a99fe3SHajimu UMEMOTO * The only restriction for entries is that is that they should have the field, 6106a99fe3SHajimu UMEMOTO * defined with HASHTABLE_ENTRY_HEAD macro. 6206a99fe3SHajimu UMEMOTO */ 6306a99fe3SHajimu UMEMOTO #define HASHTABLE_HEAD(name, entry) struct name { \ 6406a99fe3SHajimu UMEMOTO struct entry *entries; \ 6506a99fe3SHajimu UMEMOTO size_t entries_size; \ 6606a99fe3SHajimu UMEMOTO } 6706a99fe3SHajimu UMEMOTO 68da77297bSDag-Erling Smørgrav #define HASHTABLE_ENTRIES_COUNT(table) \ 69da77297bSDag-Erling Smørgrav ((table)->entries_size) 7006a99fe3SHajimu UMEMOTO 7106a99fe3SHajimu UMEMOTO /* 7206a99fe3SHajimu UMEMOTO * Unlike most of queue.h data types, hash tables can not be initialized 7306a99fe3SHajimu UMEMOTO * statically - so there is no HASHTABLE_HEAD_INITIALIZED macro. 7406a99fe3SHajimu UMEMOTO */ 7506a99fe3SHajimu UMEMOTO #define HASHTABLE_INIT(table, type, field, _entries_size) \ 7606a99fe3SHajimu UMEMOTO do { \ 7706a99fe3SHajimu UMEMOTO hashtable_index_t var; \ 7887959e27SPedro F. Giffuni (table)->entries = calloc(_entries_size, \ 7987959e27SPedro F. Giffuni sizeof(*(table)->entries)); \ 8006a99fe3SHajimu UMEMOTO (table)->entries_size = (_entries_size); \ 8106a99fe3SHajimu UMEMOTO for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 8206a99fe3SHajimu UMEMOTO (table)->entries[var].field.capacity = \ 8306a99fe3SHajimu UMEMOTO HASHTABLE_INITIAL_ENTRIES_CAPACITY; \ 8406a99fe3SHajimu UMEMOTO (table)->entries[var].field.size = 0; \ 858eeaaffaSDag-Erling Smørgrav (table)->entries[var].field.values = malloc( \ 8606a99fe3SHajimu UMEMOTO sizeof(type) * \ 8706a99fe3SHajimu UMEMOTO HASHTABLE_INITIAL_ENTRIES_CAPACITY); \ 8806a99fe3SHajimu UMEMOTO assert((table)->entries[var].field.values != NULL);\ 8906a99fe3SHajimu UMEMOTO } \ 9006a99fe3SHajimu UMEMOTO } while (0) 9106a99fe3SHajimu UMEMOTO 9206a99fe3SHajimu UMEMOTO /* 9306a99fe3SHajimu UMEMOTO * All initialized hashtables should be destroyed with this macro. 9406a99fe3SHajimu UMEMOTO */ 9506a99fe3SHajimu UMEMOTO #define HASHTABLE_DESTROY(table, field) \ 9606a99fe3SHajimu UMEMOTO do { \ 9706a99fe3SHajimu UMEMOTO hashtable_index_t var; \ 9806a99fe3SHajimu UMEMOTO for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 9906a99fe3SHajimu UMEMOTO free((table)->entries[var].field.values); \ 10006a99fe3SHajimu UMEMOTO } \ 10106a99fe3SHajimu UMEMOTO } while (0) 10206a99fe3SHajimu UMEMOTO 103da77297bSDag-Erling Smørgrav #define HASHTABLE_GET_ENTRY(table, hash) \ 104da77297bSDag-Erling Smørgrav (&((table)->entries[hash])) 10506a99fe3SHajimu UMEMOTO 10606a99fe3SHajimu UMEMOTO /* 10706a99fe3SHajimu UMEMOTO * Traverses through all hash table entries 10806a99fe3SHajimu UMEMOTO */ 10906a99fe3SHajimu UMEMOTO #define HASHTABLE_FOREACH(table, var) \ 11006a99fe3SHajimu UMEMOTO for ((var) = &((table)->entries[0]); \ 11106a99fe3SHajimu UMEMOTO (var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\ 11206a99fe3SHajimu UMEMOTO ++(var)) 11306a99fe3SHajimu UMEMOTO 11406a99fe3SHajimu UMEMOTO /* 11506a99fe3SHajimu UMEMOTO * Traverses through all elements of the specified hash table entry 11606a99fe3SHajimu UMEMOTO */ 11706a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_FOREACH(entry, field, var) \ 11806a99fe3SHajimu UMEMOTO for ((var) = &((entry)->field.values[0]); \ 11906a99fe3SHajimu UMEMOTO (var) < &((entry)->field.values[(entry)->field.size]); \ 12006a99fe3SHajimu UMEMOTO ++(var)) 12106a99fe3SHajimu UMEMOTO 12206a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CLEAR(entry, field) \ 12306a99fe3SHajimu UMEMOTO ((entry)->field.size = 0) 12406a99fe3SHajimu UMEMOTO 12506a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_SIZE(entry, field) \ 12606a99fe3SHajimu UMEMOTO ((entry)->field.size) 12706a99fe3SHajimu UMEMOTO 12806a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CAPACITY(entry, field) \ 12906a99fe3SHajimu UMEMOTO ((entry)->field.capacity) 13006a99fe3SHajimu UMEMOTO 13106a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type) \ 132da77297bSDag-Erling Smørgrav do { \ 13306a99fe3SHajimu UMEMOTO (entry)->field.capacity *= 2; \ 1348eeaaffaSDag-Erling Smørgrav (entry)->field.values = realloc((entry)->field.values, \ 135da77297bSDag-Erling Smørgrav (entry)->field.capacity * sizeof(type)); \ 136da77297bSDag-Erling Smørgrav } while (0) 13706a99fe3SHajimu UMEMOTO 13806a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type) \ 139da77297bSDag-Erling Smørgrav do { \ 14006a99fe3SHajimu UMEMOTO (entry)->field.capacity /= 2; \ 1418eeaaffaSDag-Erling Smørgrav (entry)->field.values = realloc((entry)->field.values, \ 142da77297bSDag-Erling Smørgrav (entry)->field.capacity * sizeof(type)); \ 143da77297bSDag-Erling Smørgrav } while (0) 14406a99fe3SHajimu UMEMOTO 14506a99fe3SHajimu UMEMOTO /* 14606a99fe3SHajimu UMEMOTO * Generates prototypes for the hash table functions 14706a99fe3SHajimu UMEMOTO */ 14806a99fe3SHajimu UMEMOTO #define HASHTABLE_PROTOTYPE(name, entry_, type) \ 14906a99fe3SHajimu UMEMOTO hashtable_index_t name##_CALCULATE_HASH(struct name *, type *); \ 15006a99fe3SHajimu UMEMOTO void name##_ENTRY_STORE(struct entry_*, type *); \ 15106a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND(struct entry_*, type *); \ 15206a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *, \ 15306a99fe3SHajimu UMEMOTO int (*) (const void *, const void *)); \ 15406a99fe3SHajimu UMEMOTO void name##_ENTRY_REMOVE(struct entry_*, type *); 15506a99fe3SHajimu UMEMOTO 15606a99fe3SHajimu UMEMOTO /* 15706a99fe3SHajimu UMEMOTO * Generates implementations of the hash table functions 15806a99fe3SHajimu UMEMOTO */ 15906a99fe3SHajimu UMEMOTO #define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP) \ 16006a99fe3SHajimu UMEMOTO hashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data) \ 16106a99fe3SHajimu UMEMOTO { \ 16206a99fe3SHajimu UMEMOTO \ 16306a99fe3SHajimu UMEMOTO return HASH(data, table->entries_size); \ 16406a99fe3SHajimu UMEMOTO } \ 16506a99fe3SHajimu UMEMOTO \ 16606a99fe3SHajimu UMEMOTO void name##_ENTRY_STORE(struct entry_ *the_entry, type *data) \ 16706a99fe3SHajimu UMEMOTO { \ 16806a99fe3SHajimu UMEMOTO \ 16906a99fe3SHajimu UMEMOTO if (the_entry->field.size == the_entry->field.capacity) \ 17006a99fe3SHajimu UMEMOTO HASHTABLE_ENTRY_CAPACITY_INCREASE(the_entry, field, type);\ 17106a99fe3SHajimu UMEMOTO \ 17206a99fe3SHajimu UMEMOTO memcpy(&(the_entry->field.values[the_entry->field.size++]), \ 17306a99fe3SHajimu UMEMOTO data, \ 17406a99fe3SHajimu UMEMOTO sizeof(type)); \ 17506a99fe3SHajimu UMEMOTO qsort(the_entry->field.values, the_entry->field.size, \ 17606a99fe3SHajimu UMEMOTO sizeof(type), CMP); \ 17706a99fe3SHajimu UMEMOTO } \ 17806a99fe3SHajimu UMEMOTO \ 17906a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND(struct entry_ *the_entry, type *key) \ 18006a99fe3SHajimu UMEMOTO { \ 18106a99fe3SHajimu UMEMOTO \ 18206a99fe3SHajimu UMEMOTO return ((type *)bsearch(key, the_entry->field.values, \ 18306a99fe3SHajimu UMEMOTO the_entry->field.size, sizeof(type), CMP)); \ 18406a99fe3SHajimu UMEMOTO } \ 18506a99fe3SHajimu UMEMOTO \ 18606a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key, \ 18706a99fe3SHajimu UMEMOTO int (*compar) (const void *, const void *)) \ 18806a99fe3SHajimu UMEMOTO { \ 18906a99fe3SHajimu UMEMOTO return ((type *)bsearch(key, the_entry->field.values, \ 19006a99fe3SHajimu UMEMOTO the_entry->field.size, sizeof(type), compar)); \ 19106a99fe3SHajimu UMEMOTO } \ 19206a99fe3SHajimu UMEMOTO \ 19306a99fe3SHajimu UMEMOTO void name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm) \ 19406a99fe3SHajimu UMEMOTO { \ 19506a99fe3SHajimu UMEMOTO \ 19606a99fe3SHajimu UMEMOTO memmove(del_elm, del_elm + 1, \ 19706a99fe3SHajimu UMEMOTO (&the_entry->field.values[--the_entry->field.size] - del_elm) *\ 19806a99fe3SHajimu UMEMOTO sizeof(type)); \ 19906a99fe3SHajimu UMEMOTO } 20006a99fe3SHajimu UMEMOTO 20106a99fe3SHajimu UMEMOTO /* 20206a99fe3SHajimu UMEMOTO * Macro definitions below wrap the functions, generaed with 20306a99fe3SHajimu UMEMOTO * HASHTABLE_GENERATE macro. You should use them and avoid using generated 20406a99fe3SHajimu UMEMOTO * functions directly. 20506a99fe3SHajimu UMEMOTO */ 20606a99fe3SHajimu UMEMOTO #define HASHTABLE_CALCULATE_HASH(name, table, data) \ 20706a99fe3SHajimu UMEMOTO (name##_CALCULATE_HASH((table), data)) 20806a99fe3SHajimu UMEMOTO 20906a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_STORE(name, entry, data) \ 21006a99fe3SHajimu UMEMOTO name##_ENTRY_STORE((entry), data) 21106a99fe3SHajimu UMEMOTO 21206a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_FIND(name, entry, key) \ 21306a99fe3SHajimu UMEMOTO (name##_ENTRY_FIND((entry), (key))) 21406a99fe3SHajimu UMEMOTO 21506a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp) \ 21606a99fe3SHajimu UMEMOTO (name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp))) 21706a99fe3SHajimu UMEMOTO 21806a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm) \ 21906a99fe3SHajimu UMEMOTO name##_ENTRY_REMOVE((entry), (del_elm)) 22006a99fe3SHajimu UMEMOTO 22106a99fe3SHajimu UMEMOTO #endif 222