1158115Sume/*- 2158115Sume * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru> 3158115Sume * All rights reserved. 4158115Sume * 5158115Sume * Redistribution and use in source and binary forms, with or without 6158115Sume * modification, are permitted provided that the following conditions 7158115Sume * are met: 8158115Sume * 1. Redistributions of source code must retain the above copyright 9158115Sume * notice, this list of conditions and the following disclaimer. 10158115Sume * 2. Redistributions in binary form must reproduce the above copyright 11158115Sume * notice, this list of conditions and the following disclaimer in the 12158115Sume * documentation and/or other materials provided with the distribution. 13158115Sume * 14158115Sume * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15158115Sume * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16158115Sume * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17158115Sume * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18158115Sume * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19158115Sume * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20158115Sume * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21158115Sume * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22158115Sume * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23158115Sume * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24158115Sume * SUCH DAMAGE. 25158115Sume * 26158115Sume * $FreeBSD: stable/10/usr.sbin/nscd/hashtable.h 315600 2017-03-20 00:55:24Z pfg $ 27158115Sume */ 28158115Sume 29158115Sume#ifndef __CACHELIB_HASHTABLE_H__ 30158115Sume#define __CACHELIB_HASHTABLE_H__ 31158115Sume 32158115Sume#include <string.h> 33158115Sume 34158115Sume#define HASHTABLE_INITIAL_ENTRIES_CAPACITY 8 35194095Sdestypedef unsigned int hashtable_index_t; 36158115Sume 37158115Sume/* 38158115Sume * This file contains queue.h-like macro definitions for hash tables. 39158115Sume * Hash table is organized as an array of the specified size of the user 40158115Sume * defined (with HASTABLE_ENTRY_HEAD) structures. Each hash table 41158115Sume * entry (user defined structure) stores its elements in the sorted array. 42158115Sume * You can place elements into the hash table, retrieve elements with 43158115Sume * specified key, traverse through all elements, and delete them. 44158115Sume * New elements are placed into the hash table by using the compare and 45158115Sume * hashing functions, provided by the user. 46158115Sume */ 47158115Sume 48158115Sume/* 49158115Sume * Defines the hash table entry structure, that uses specified type of 50158115Sume * elements. 51158115Sume */ 52158115Sume#define HASHTABLE_ENTRY_HEAD(name, type) struct name { \ 53158115Sume type *values; \ 54158115Sume size_t capacity; \ 55158115Sume size_t size; \ 56158115Sume} 57158115Sume 58158115Sume/* 59158115Sume * Defines the hash table structure, which uses the specified type of entries. 60158115Sume * The only restriction for entries is that is that they should have the field, 61158115Sume * defined with HASHTABLE_ENTRY_HEAD macro. 62158115Sume */ 63158115Sume#define HASHTABLE_HEAD(name, entry) struct name { \ 64158115Sume struct entry *entries; \ 65158115Sume size_t entries_size; \ 66158115Sume} 67158115Sume 68194109Sdes#define HASHTABLE_ENTRIES_COUNT(table) \ 69194109Sdes ((table)->entries_size) 70158115Sume 71158115Sume/* 72158115Sume * Unlike most of queue.h data types, hash tables can not be initialized 73158115Sume * statically - so there is no HASHTABLE_HEAD_INITIALIZED macro. 74158115Sume */ 75158115Sume#define HASHTABLE_INIT(table, type, field, _entries_size) \ 76158115Sume do { \ 77158115Sume hashtable_index_t var; \ 78315600Spfg (table)->entries = calloc(_entries_size, \ 79315600Spfg sizeof(*(table)->entries)); \ 80158115Sume (table)->entries_size = (_entries_size); \ 81158115Sume for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 82158115Sume (table)->entries[var].field.capacity = \ 83158115Sume HASHTABLE_INITIAL_ENTRIES_CAPACITY; \ 84158115Sume (table)->entries[var].field.size = 0; \ 85194104Sdes (table)->entries[var].field.values = malloc( \ 86194104Sdes sizeof(type) * \ 87194104Sdes HASHTABLE_INITIAL_ENTRIES_CAPACITY); \ 88158115Sume assert((table)->entries[var].field.values != NULL);\ 89158115Sume } \ 90158115Sume } while (0) 91158115Sume 92158115Sume/* 93158115Sume * All initialized hashtables should be destroyed with this macro. 94158115Sume */ 95158115Sume#define HASHTABLE_DESTROY(table, field) \ 96158115Sume do { \ 97158115Sume hashtable_index_t var; \ 98158115Sume for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 99158115Sume free((table)->entries[var].field.values); \ 100158115Sume } \ 101158115Sume } while (0) 102158115Sume 103194109Sdes#define HASHTABLE_GET_ENTRY(table, hash) \ 104194109Sdes (&((table)->entries[hash])) 105158115Sume 106158115Sume/* 107158115Sume * Traverses through all hash table entries 108158115Sume */ 109158115Sume#define HASHTABLE_FOREACH(table, var) \ 110158115Sume for ((var) = &((table)->entries[0]); \ 111158115Sume (var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\ 112158115Sume ++(var)) 113158115Sume 114158115Sume/* 115158115Sume * Traverses through all elements of the specified hash table entry 116158115Sume */ 117158115Sume#define HASHTABLE_ENTRY_FOREACH(entry, field, var) \ 118158115Sume for ((var) = &((entry)->field.values[0]); \ 119158115Sume (var) < &((entry)->field.values[(entry)->field.size]); \ 120158115Sume ++(var)) 121158115Sume 122158115Sume#define HASHTABLE_ENTRY_CLEAR(entry, field) \ 123158115Sume ((entry)->field.size = 0) 124158115Sume 125158115Sume#define HASHTABLE_ENTRY_SIZE(entry, field) \ 126158115Sume ((entry)->field.size) 127158115Sume 128158115Sume#define HASHTABLE_ENTRY_CAPACITY(entry, field) \ 129158115Sume ((entry)->field.capacity) 130158115Sume 131158115Sume#define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type) \ 132194109Sdes do { \ 133194109Sdes (entry)->field.capacity *= 2; \ 134194109Sdes (entry)->field.values = realloc((entry)->field.values, \ 135194109Sdes (entry)->field.capacity * sizeof(type)); \ 136194109Sdes } while (0) 137158115Sume 138158115Sume#define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type) \ 139194109Sdes do { \ 140194109Sdes (entry)->field.capacity /= 2; \ 141194109Sdes (entry)->field.values = realloc((entry)->field.values, \ 142194109Sdes (entry)->field.capacity * sizeof(type)); \ 143194109Sdes } while (0) 144158115Sume 145158115Sume/* 146158115Sume * Generates prototypes for the hash table functions 147158115Sume */ 148158115Sume#define HASHTABLE_PROTOTYPE(name, entry_, type) \ 149158115Sumehashtable_index_t name##_CALCULATE_HASH(struct name *, type *); \ 150158115Sumevoid name##_ENTRY_STORE(struct entry_*, type *); \ 151158115Sumetype *name##_ENTRY_FIND(struct entry_*, type *); \ 152158115Sumetype *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *, \ 153158115Sume int (*) (const void *, const void *)); \ 154158115Sumevoid name##_ENTRY_REMOVE(struct entry_*, type *); 155158115Sume 156158115Sume/* 157158115Sume * Generates implementations of the hash table functions 158158115Sume */ 159158115Sume#define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP) \ 160158115Sumehashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data) \ 161158115Sume{ \ 162158115Sume \ 163158115Sume return HASH(data, table->entries_size); \ 164158115Sume} \ 165158115Sume \ 166158115Sumevoid name##_ENTRY_STORE(struct entry_ *the_entry, type *data) \ 167158115Sume{ \ 168158115Sume \ 169158115Sume if (the_entry->field.size == the_entry->field.capacity) \ 170158115Sume HASHTABLE_ENTRY_CAPACITY_INCREASE(the_entry, field, type);\ 171158115Sume \ 172158115Sume memcpy(&(the_entry->field.values[the_entry->field.size++]), \ 173158115Sume data, \ 174158115Sume sizeof(type)); \ 175158115Sume qsort(the_entry->field.values, the_entry->field.size, \ 176158115Sume sizeof(type), CMP); \ 177158115Sume} \ 178158115Sume \ 179158115Sumetype *name##_ENTRY_FIND(struct entry_ *the_entry, type *key) \ 180158115Sume{ \ 181158115Sume \ 182158115Sume return ((type *)bsearch(key, the_entry->field.values, \ 183158115Sume the_entry->field.size, sizeof(type), CMP)); \ 184158115Sume} \ 185158115Sume \ 186158115Sumetype *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key, \ 187158115Sume int (*compar) (const void *, const void *)) \ 188158115Sume{ \ 189158115Sume return ((type *)bsearch(key, the_entry->field.values, \ 190158115Sume the_entry->field.size, sizeof(type), compar)); \ 191158115Sume} \ 192158115Sume \ 193158115Sumevoid name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm) \ 194158115Sume{ \ 195158115Sume \ 196158115Sume memmove(del_elm, del_elm + 1, \ 197158115Sume (&the_entry->field.values[--the_entry->field.size] - del_elm) *\ 198158115Sume sizeof(type)); \ 199158115Sume} 200158115Sume 201158115Sume/* 202158115Sume * Macro definitions below wrap the functions, generaed with 203158115Sume * HASHTABLE_GENERATE macro. You should use them and avoid using generated 204158115Sume * functions directly. 205158115Sume */ 206158115Sume#define HASHTABLE_CALCULATE_HASH(name, table, data) \ 207158115Sume (name##_CALCULATE_HASH((table), data)) 208158115Sume 209158115Sume#define HASHTABLE_ENTRY_STORE(name, entry, data) \ 210158115Sume name##_ENTRY_STORE((entry), data) 211158115Sume 212158115Sume#define HASHTABLE_ENTRY_FIND(name, entry, key) \ 213158115Sume (name##_ENTRY_FIND((entry), (key))) 214158115Sume 215158115Sume#define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp) \ 216158115Sume (name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp))) 217158115Sume 218158115Sume#define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm) \ 219158115Sume name##_ENTRY_REMOVE((entry), (del_elm)) 220158115Sume 221158115Sume#endif 222