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 2706a99fe3SHajimu UMEMOTO #ifndef __CACHELIB_HASHTABLE_H__ 2806a99fe3SHajimu UMEMOTO #define __CACHELIB_HASHTABLE_H__ 2906a99fe3SHajimu UMEMOTO 3006a99fe3SHajimu UMEMOTO #include <string.h> 3106a99fe3SHajimu UMEMOTO 3206a99fe3SHajimu UMEMOTO #define HASHTABLE_INITIAL_ENTRIES_CAPACITY 8 332bdde973SDag-Erling Smørgrav typedef unsigned int hashtable_index_t; 3406a99fe3SHajimu UMEMOTO 3506a99fe3SHajimu UMEMOTO /* 3606a99fe3SHajimu UMEMOTO * This file contains queue.h-like macro definitions for hash tables. 3706a99fe3SHajimu UMEMOTO * Hash table is organized as an array of the specified size of the user 3806a99fe3SHajimu UMEMOTO * defined (with HASTABLE_ENTRY_HEAD) structures. Each hash table 3906a99fe3SHajimu UMEMOTO * entry (user defined structure) stores its elements in the sorted array. 4006a99fe3SHajimu UMEMOTO * You can place elements into the hash table, retrieve elements with 4106a99fe3SHajimu UMEMOTO * specified key, traverse through all elements, and delete them. 4206a99fe3SHajimu UMEMOTO * New elements are placed into the hash table by using the compare and 4306a99fe3SHajimu UMEMOTO * hashing functions, provided by the user. 4406a99fe3SHajimu UMEMOTO */ 4506a99fe3SHajimu UMEMOTO 4606a99fe3SHajimu UMEMOTO /* 4706a99fe3SHajimu UMEMOTO * Defines the hash table entry structure, that uses specified type of 4806a99fe3SHajimu UMEMOTO * elements. 4906a99fe3SHajimu UMEMOTO */ 5006a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_HEAD(name, type) struct name { \ 5106a99fe3SHajimu UMEMOTO type *values; \ 5206a99fe3SHajimu UMEMOTO size_t capacity; \ 5306a99fe3SHajimu UMEMOTO size_t size; \ 5406a99fe3SHajimu UMEMOTO } 5506a99fe3SHajimu UMEMOTO 5606a99fe3SHajimu UMEMOTO /* 5706a99fe3SHajimu UMEMOTO * Defines the hash table structure, which uses the specified type of entries. 5806a99fe3SHajimu UMEMOTO * The only restriction for entries is that is that they should have the field, 5906a99fe3SHajimu UMEMOTO * defined with HASHTABLE_ENTRY_HEAD macro. 6006a99fe3SHajimu UMEMOTO */ 6106a99fe3SHajimu UMEMOTO #define HASHTABLE_HEAD(name, entry) struct name { \ 6206a99fe3SHajimu UMEMOTO struct entry *entries; \ 6306a99fe3SHajimu UMEMOTO size_t entries_size; \ 6406a99fe3SHajimu UMEMOTO } 6506a99fe3SHajimu UMEMOTO 66da77297bSDag-Erling Smørgrav #define HASHTABLE_ENTRIES_COUNT(table) \ 67da77297bSDag-Erling Smørgrav ((table)->entries_size) 6806a99fe3SHajimu UMEMOTO 6906a99fe3SHajimu UMEMOTO /* 7006a99fe3SHajimu UMEMOTO * Unlike most of queue.h data types, hash tables can not be initialized 7106a99fe3SHajimu UMEMOTO * statically - so there is no HASHTABLE_HEAD_INITIALIZED macro. 7206a99fe3SHajimu UMEMOTO */ 7306a99fe3SHajimu UMEMOTO #define HASHTABLE_INIT(table, type, field, _entries_size) \ 7406a99fe3SHajimu UMEMOTO do { \ 7506a99fe3SHajimu UMEMOTO hashtable_index_t var; \ 7687959e27SPedro F. Giffuni (table)->entries = calloc(_entries_size, \ 7787959e27SPedro F. Giffuni sizeof(*(table)->entries)); \ 7806a99fe3SHajimu UMEMOTO (table)->entries_size = (_entries_size); \ 7906a99fe3SHajimu UMEMOTO for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 8006a99fe3SHajimu UMEMOTO (table)->entries[var].field.capacity = \ 8106a99fe3SHajimu UMEMOTO HASHTABLE_INITIAL_ENTRIES_CAPACITY; \ 8206a99fe3SHajimu UMEMOTO (table)->entries[var].field.size = 0; \ 838eeaaffaSDag-Erling Smørgrav (table)->entries[var].field.values = malloc( \ 8406a99fe3SHajimu UMEMOTO sizeof(type) * \ 8506a99fe3SHajimu UMEMOTO HASHTABLE_INITIAL_ENTRIES_CAPACITY); \ 8606a99fe3SHajimu UMEMOTO assert((table)->entries[var].field.values != NULL);\ 8706a99fe3SHajimu UMEMOTO } \ 8806a99fe3SHajimu UMEMOTO } while (0) 8906a99fe3SHajimu UMEMOTO 9006a99fe3SHajimu UMEMOTO /* 9106a99fe3SHajimu UMEMOTO * All initialized hashtables should be destroyed with this macro. 9206a99fe3SHajimu UMEMOTO */ 9306a99fe3SHajimu UMEMOTO #define HASHTABLE_DESTROY(table, field) \ 9406a99fe3SHajimu UMEMOTO do { \ 9506a99fe3SHajimu UMEMOTO hashtable_index_t var; \ 9606a99fe3SHajimu UMEMOTO for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 9706a99fe3SHajimu UMEMOTO free((table)->entries[var].field.values); \ 9806a99fe3SHajimu UMEMOTO } \ 9906a99fe3SHajimu UMEMOTO } while (0) 10006a99fe3SHajimu UMEMOTO 101da77297bSDag-Erling Smørgrav #define HASHTABLE_GET_ENTRY(table, hash) \ 102da77297bSDag-Erling Smørgrav (&((table)->entries[hash])) 10306a99fe3SHajimu UMEMOTO 10406a99fe3SHajimu UMEMOTO /* 10506a99fe3SHajimu UMEMOTO * Traverses through all hash table entries 10606a99fe3SHajimu UMEMOTO */ 10706a99fe3SHajimu UMEMOTO #define HASHTABLE_FOREACH(table, var) \ 10806a99fe3SHajimu UMEMOTO for ((var) = &((table)->entries[0]); \ 10906a99fe3SHajimu UMEMOTO (var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\ 11006a99fe3SHajimu UMEMOTO ++(var)) 11106a99fe3SHajimu UMEMOTO 11206a99fe3SHajimu UMEMOTO /* 11306a99fe3SHajimu UMEMOTO * Traverses through all elements of the specified hash table entry 11406a99fe3SHajimu UMEMOTO */ 11506a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_FOREACH(entry, field, var) \ 11606a99fe3SHajimu UMEMOTO for ((var) = &((entry)->field.values[0]); \ 11706a99fe3SHajimu UMEMOTO (var) < &((entry)->field.values[(entry)->field.size]); \ 11806a99fe3SHajimu UMEMOTO ++(var)) 11906a99fe3SHajimu UMEMOTO 12006a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CLEAR(entry, field) \ 12106a99fe3SHajimu UMEMOTO ((entry)->field.size = 0) 12206a99fe3SHajimu UMEMOTO 12306a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_SIZE(entry, field) \ 12406a99fe3SHajimu UMEMOTO ((entry)->field.size) 12506a99fe3SHajimu UMEMOTO 12606a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CAPACITY(entry, field) \ 12706a99fe3SHajimu UMEMOTO ((entry)->field.capacity) 12806a99fe3SHajimu UMEMOTO 12906a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type) \ 130da77297bSDag-Erling Smørgrav do { \ 13106a99fe3SHajimu UMEMOTO (entry)->field.capacity *= 2; \ 1328eeaaffaSDag-Erling Smørgrav (entry)->field.values = realloc((entry)->field.values, \ 133da77297bSDag-Erling Smørgrav (entry)->field.capacity * sizeof(type)); \ 134da77297bSDag-Erling Smørgrav } while (0) 13506a99fe3SHajimu UMEMOTO 13606a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type) \ 137da77297bSDag-Erling Smørgrav do { \ 13806a99fe3SHajimu UMEMOTO (entry)->field.capacity /= 2; \ 1398eeaaffaSDag-Erling Smørgrav (entry)->field.values = realloc((entry)->field.values, \ 140da77297bSDag-Erling Smørgrav (entry)->field.capacity * sizeof(type)); \ 141da77297bSDag-Erling Smørgrav } while (0) 14206a99fe3SHajimu UMEMOTO 14306a99fe3SHajimu UMEMOTO /* 14406a99fe3SHajimu UMEMOTO * Generates prototypes for the hash table functions 14506a99fe3SHajimu UMEMOTO */ 14606a99fe3SHajimu UMEMOTO #define HASHTABLE_PROTOTYPE(name, entry_, type) \ 14706a99fe3SHajimu UMEMOTO hashtable_index_t name##_CALCULATE_HASH(struct name *, type *); \ 14806a99fe3SHajimu UMEMOTO void name##_ENTRY_STORE(struct entry_*, type *); \ 14906a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND(struct entry_*, type *); \ 15006a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *, \ 15106a99fe3SHajimu UMEMOTO int (*) (const void *, const void *)); \ 15206a99fe3SHajimu UMEMOTO void name##_ENTRY_REMOVE(struct entry_*, type *); 15306a99fe3SHajimu UMEMOTO 15406a99fe3SHajimu UMEMOTO /* 15506a99fe3SHajimu UMEMOTO * Generates implementations of the hash table functions 15606a99fe3SHajimu UMEMOTO */ 15706a99fe3SHajimu UMEMOTO #define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP) \ 15806a99fe3SHajimu UMEMOTO hashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data) \ 15906a99fe3SHajimu UMEMOTO { \ 16006a99fe3SHajimu UMEMOTO \ 16106a99fe3SHajimu UMEMOTO return HASH(data, table->entries_size); \ 16206a99fe3SHajimu UMEMOTO } \ 16306a99fe3SHajimu UMEMOTO \ 16406a99fe3SHajimu UMEMOTO void name##_ENTRY_STORE(struct entry_ *the_entry, type *data) \ 16506a99fe3SHajimu UMEMOTO { \ 16606a99fe3SHajimu UMEMOTO \ 16706a99fe3SHajimu UMEMOTO if (the_entry->field.size == the_entry->field.capacity) \ 16806a99fe3SHajimu UMEMOTO HASHTABLE_ENTRY_CAPACITY_INCREASE(the_entry, field, type);\ 16906a99fe3SHajimu UMEMOTO \ 17006a99fe3SHajimu UMEMOTO memcpy(&(the_entry->field.values[the_entry->field.size++]), \ 17106a99fe3SHajimu UMEMOTO data, \ 17206a99fe3SHajimu UMEMOTO sizeof(type)); \ 17306a99fe3SHajimu UMEMOTO qsort(the_entry->field.values, the_entry->field.size, \ 17406a99fe3SHajimu UMEMOTO sizeof(type), CMP); \ 17506a99fe3SHajimu UMEMOTO } \ 17606a99fe3SHajimu UMEMOTO \ 17706a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND(struct entry_ *the_entry, type *key) \ 17806a99fe3SHajimu UMEMOTO { \ 17906a99fe3SHajimu UMEMOTO \ 18006a99fe3SHajimu UMEMOTO return ((type *)bsearch(key, the_entry->field.values, \ 18106a99fe3SHajimu UMEMOTO the_entry->field.size, sizeof(type), CMP)); \ 18206a99fe3SHajimu UMEMOTO } \ 18306a99fe3SHajimu UMEMOTO \ 18406a99fe3SHajimu UMEMOTO type *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key, \ 18506a99fe3SHajimu UMEMOTO int (*compar) (const void *, const void *)) \ 18606a99fe3SHajimu UMEMOTO { \ 18706a99fe3SHajimu UMEMOTO return ((type *)bsearch(key, the_entry->field.values, \ 18806a99fe3SHajimu UMEMOTO the_entry->field.size, sizeof(type), compar)); \ 18906a99fe3SHajimu UMEMOTO } \ 19006a99fe3SHajimu UMEMOTO \ 19106a99fe3SHajimu UMEMOTO void name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm) \ 19206a99fe3SHajimu UMEMOTO { \ 19306a99fe3SHajimu UMEMOTO \ 19406a99fe3SHajimu UMEMOTO memmove(del_elm, del_elm + 1, \ 19506a99fe3SHajimu UMEMOTO (&the_entry->field.values[--the_entry->field.size] - del_elm) *\ 19606a99fe3SHajimu UMEMOTO sizeof(type)); \ 19706a99fe3SHajimu UMEMOTO } 19806a99fe3SHajimu UMEMOTO 19906a99fe3SHajimu UMEMOTO /* 20006a99fe3SHajimu UMEMOTO * Macro definitions below wrap the functions, generaed with 20106a99fe3SHajimu UMEMOTO * HASHTABLE_GENERATE macro. You should use them and avoid using generated 20206a99fe3SHajimu UMEMOTO * functions directly. 20306a99fe3SHajimu UMEMOTO */ 20406a99fe3SHajimu UMEMOTO #define HASHTABLE_CALCULATE_HASH(name, table, data) \ 20506a99fe3SHajimu UMEMOTO (name##_CALCULATE_HASH((table), data)) 20606a99fe3SHajimu UMEMOTO 20706a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_STORE(name, entry, data) \ 20806a99fe3SHajimu UMEMOTO name##_ENTRY_STORE((entry), data) 20906a99fe3SHajimu UMEMOTO 21006a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_FIND(name, entry, key) \ 21106a99fe3SHajimu UMEMOTO (name##_ENTRY_FIND((entry), (key))) 21206a99fe3SHajimu UMEMOTO 21306a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp) \ 21406a99fe3SHajimu UMEMOTO (name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp))) 21506a99fe3SHajimu UMEMOTO 21606a99fe3SHajimu UMEMOTO #define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm) \ 21706a99fe3SHajimu UMEMOTO name##_ENTRY_REMOVE((entry), (del_elm)) 21806a99fe3SHajimu UMEMOTO 21906a99fe3SHajimu UMEMOTO #endif 220