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