hashtable.h revision 194109
161931Scokane/*- 261931Scokane * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru> 361931Scokane * All rights reserved. 461931Scokane * 561931Scokane * Redistribution and use in source and binary forms, with or without 661931Scokane * modification, are permitted provided that the following conditions 761931Scokane * are met: 861931Scokane * 1. Redistributions of source code must retain the above copyright 961931Scokane * notice, this list of conditions and the following disclaimer. 1061931Scokane * 2. Redistributions in binary form must reproduce the above copyright 1161931Scokane * notice, this list of conditions and the following disclaimer in the 1261931Scokane * documentation and/or other materials provided with the distribution. 1361931Scokane * 1461931Scokane * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 1561931Scokane * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1661931Scokane * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 1761931Scokane * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 1861931Scokane * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 1961931Scokane * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2061931Scokane * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2161931Scokane * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2261931Scokane * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2361931Scokane * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2461931Scokane * SUCH DAMAGE. 2561931Scokane * 2661931Scokane * $FreeBSD: head/usr.sbin/nscd/hashtable.h 194109 2009-06-13 13:54:03Z des $ 2761931Scokane */ 2861931Scokane 2961931Scokane#ifndef __CACHELIB_HASHTABLE_H__ 3061931Scokane#define __CACHELIB_HASHTABLE_H__ 3161931Scokane 3261931Scokane#include <string.h> 3361931Scokane 3461911Scokane#define HASHTABLE_INITIAL_ENTRIES_CAPACITY 8 3561911Scokanetypedef unsigned int hashtable_index_t; 3661931Scokane 3761911Scokane/* 3861911Scokane * This file contains queue.h-like macro definitions for hash tables. 3961911Scokane * Hash table is organized as an array of the specified size of the user 4061911Scokane * defined (with HASTABLE_ENTRY_HEAD) structures. Each hash table 4161911Scokane * entry (user defined structure) stores its elements in the sorted array. 4261911Scokane * You can place elements into the hash table, retrieve elements with 4361911Scokane * specified key, traverse through all elements, and delete them. 4461911Scokane * New elements are placed into the hash table by using the compare and 4561911Scokane * hashing functions, provided by the user. 4661911Scokane */ 4761911Scokane 4861911Scokane/* 4961911Scokane * Defines the hash table entry structure, that uses specified type of 5061911Scokane * elements. 5161911Scokane */ 5261911Scokane#define HASHTABLE_ENTRY_HEAD(name, type) struct name { \ 5361911Scokane type *values; \ 5461911Scokane size_t capacity; \ 5561911Scokane size_t size; \ 5661911Scokane} 5761911Scokane 5861911Scokane/* 5961911Scokane * Defines the hash table structure, which uses the specified type of entries. 6061911Scokane * The only restriction for entries is that is that they should have the field, 6161911Scokane * defined with HASHTABLE_ENTRY_HEAD macro. 6261911Scokane */ 6361911Scokane#define HASHTABLE_HEAD(name, entry) struct name { \ 6461911Scokane struct entry *entries; \ 6561911Scokane size_t entries_size; \ 6661911Scokane} 6761911Scokane 6861911Scokane#define HASHTABLE_ENTRIES_COUNT(table) \ 6961911Scokane ((table)->entries_size) 7061911Scokane 7161911Scokane/* 7261911Scokane * Unlike most of queue.h data types, hash tables can not be initialized 7361911Scokane * statically - so there is no HASHTABLE_HEAD_INITIALIZED macro. 7461911Scokane */ 7561911Scokane#define HASHTABLE_INIT(table, type, field, _entries_size) \ 7661911Scokane do { \ 7761931Scokane hashtable_index_t var; \ 7861931Scokane (table)->entries = calloc(1, \ 7961931Scokane sizeof(*(table)->entries) * (_entries_size)); \ 8061911Scokane (table)->entries_size = (_entries_size); \ 8161911Scokane for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 8261911Scokane (table)->entries[var].field.capacity = \ 8361911Scokane HASHTABLE_INITIAL_ENTRIES_CAPACITY; \ 8461911Scokane (table)->entries[var].field.size = 0; \ 8561911Scokane (table)->entries[var].field.values = malloc( \ 8661911Scokane sizeof(type) * \ 8761911Scokane HASHTABLE_INITIAL_ENTRIES_CAPACITY); \ 8861911Scokane assert((table)->entries[var].field.values != NULL);\ 8961911Scokane } \ 9061911Scokane } while (0) 9161911Scokane 9261911Scokane/* 9361911Scokane * All initialized hashtables should be destroyed with this macro. 9461911Scokane */ 9561911Scokane#define HASHTABLE_DESTROY(table, field) \ 9661911Scokane do { \ 9761911Scokane hashtable_index_t var; \ 9861911Scokane for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 9961911Scokane free((table)->entries[var].field.values); \ 10061911Scokane } \ 10161911Scokane } while (0) 10261911Scokane 10361911Scokane#define HASHTABLE_GET_ENTRY(table, hash) \ 10461931Scokane (&((table)->entries[hash])) 10561931Scokane 10661931Scokane/* 10761931Scokane * Traverses through all hash table entries 10861911Scokane */ 10961911Scokane#define HASHTABLE_FOREACH(table, var) \ 11061911Scokane for ((var) = &((table)->entries[0]); \ 11161911Scokane (var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\ 11261911Scokane ++(var)) 11361911Scokane 11461911Scokane/* 11561911Scokane * Traverses through all elements of the specified hash table entry 11661911Scokane */ 11761911Scokane#define HASHTABLE_ENTRY_FOREACH(entry, field, var) \ 11861911Scokane for ((var) = &((entry)->field.values[0]); \ 11961911Scokane (var) < &((entry)->field.values[(entry)->field.size]); \ 12061911Scokane ++(var)) 12161911Scokane 12261911Scokane#define HASHTABLE_ENTRY_CLEAR(entry, field) \ 12361911Scokane ((entry)->field.size = 0) 12461911Scokane 12561911Scokane#define HASHTABLE_ENTRY_SIZE(entry, field) \ 12661911Scokane ((entry)->field.size) 12761911Scokane 12861911Scokane#define HASHTABLE_ENTRY_CAPACITY(entry, field) \ 12961911Scokane ((entry)->field.capacity) 13061911Scokane 13161911Scokane#define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type) \ 13261911Scokane do { \ 13361911Scokane (entry)->field.capacity *= 2; \ 13461911Scokane (entry)->field.values = realloc((entry)->field.values, \ 13561911Scokane (entry)->field.capacity * sizeof(type)); \ 13661911Scokane } while (0) 13761911Scokane 13861911Scokane#define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type) \ 13961911Scokane do { \ 14061911Scokane (entry)->field.capacity /= 2; \ 14161911Scokane (entry)->field.values = realloc((entry)->field.values, \ 14261911Scokane (entry)->field.capacity * sizeof(type)); \ 14361911Scokane } while (0) 14461911Scokane 14561911Scokane/* 14661911Scokane * Generates prototypes for the hash table functions 14761911Scokane */ 14861911Scokane#define HASHTABLE_PROTOTYPE(name, entry_, type) \ 14961911Scokanehashtable_index_t name##_CALCULATE_HASH(struct name *, type *); \ 15061911Scokanevoid name##_ENTRY_STORE(struct entry_*, type *); \ 15161911Scokanetype *name##_ENTRY_FIND(struct entry_*, type *); \ 15261911Scokanetype *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *, \ 15361911Scokane int (*) (const void *, const void *)); \ 15461911Scokanevoid name##_ENTRY_REMOVE(struct entry_*, type *); 15561911Scokane 15661911Scokane/* 15761911Scokane * Generates implementations of the hash table functions 15861911Scokane */ 15961911Scokane#define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP) \ 16061911Scokanehashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data) \ 16161911Scokane{ \ 16261911Scokane \ 16361911Scokane return HASH(data, table->entries_size); \ 16461911Scokane} \ 16561911Scokane \ 16661911Scokanevoid name##_ENTRY_STORE(struct entry_ *the_entry, type *data) \ 16761911Scokane{ \ 16861911Scokane \ 16961911Scokane if (the_entry->field.size == the_entry->field.capacity) \ 17061911Scokane HASHTABLE_ENTRY_CAPACITY_INCREASE(the_entry, field, type);\ 17161911Scokane \ 17261911Scokane memcpy(&(the_entry->field.values[the_entry->field.size++]), \ 17361911Scokane data, \ 17461911Scokane sizeof(type)); \ 17561911Scokane qsort(the_entry->field.values, the_entry->field.size, \ 17661911Scokane sizeof(type), CMP); \ 17761911Scokane} \ 17861911Scokane \ 17961911Scokanetype *name##_ENTRY_FIND(struct entry_ *the_entry, type *key) \ 18061911Scokane{ \ 18161911Scokane \ 18261911Scokane return ((type *)bsearch(key, the_entry->field.values, \ 18361911Scokane the_entry->field.size, sizeof(type), CMP)); \ 18461911Scokane} \ 18561911Scokane \ 18661911Scokanetype *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key, \ 18761911Scokane int (*compar) (const void *, const void *)) \ 18861911Scokane{ \ 18961911Scokane return ((type *)bsearch(key, the_entry->field.values, \ 19061911Scokane the_entry->field.size, sizeof(type), compar)); \ 19161911Scokane} \ 19261911Scokane \ 19361911Scokanevoid name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm) \ 19461911Scokane{ \ 19561911Scokane \ 19661911Scokane memmove(del_elm, del_elm + 1, \ 19761911Scokane (&the_entry->field.values[--the_entry->field.size] - del_elm) *\ 19861911Scokane sizeof(type)); \ 19961931Scokane} 20061911Scokane 20161911Scokane/* 20261911Scokane * Macro definitions below wrap the functions, generaed with 20361911Scokane * HASHTABLE_GENERATE macro. You should use them and avoid using generated 20461911Scokane * functions directly. 20561911Scokane */ 20661911Scokane#define HASHTABLE_CALCULATE_HASH(name, table, data) \ 20761931Scokane (name##_CALCULATE_HASH((table), data)) 20861911Scokane 20961911Scokane#define HASHTABLE_ENTRY_STORE(name, entry, data) \ 21061911Scokane name##_ENTRY_STORE((entry), data) 21161911Scokane 21261911Scokane#define HASHTABLE_ENTRY_FIND(name, entry, key) \ 21361911Scokane (name##_ENTRY_FIND((entry), (key))) 21461931Scokane 21561911Scokane#define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp) \ 21661911Scokane (name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp))) 21761911Scokane 21861911Scokane#define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm) \ 21961911Scokane name##_ENTRY_REMOVE((entry), (del_elm)) 22061911Scokane 22161911Scokane#endif 22261911Scokane