1 /*- 2 * Copyright (c) 2005 Michael Bushkov <bushman@rsu.ru> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 * 26 * $FreeBSD$ 27 */ 28 29 #ifndef __CACHELIB_HASHTABLE_H__ 30 #define __CACHELIB_HASHTABLE_H__ 31 32 #include <search.h> 33 #include <string.h> 34 35 #define HASHTABLE_INITIAL_ENTRIES_CAPACITY 8 36 typedef int hashtable_index_t; 37 38 /* 39 * This file contains queue.h-like macro definitions for hash tables. 40 * Hash table is organized as an array of the specified size of the user 41 * defined (with HASTABLE_ENTRY_HEAD) structures. Each hash table 42 * entry (user defined structure) stores its elements in the sorted array. 43 * You can place elements into the hash table, retrieve elements with 44 * specified key, traverse through all elements, and delete them. 45 * New elements are placed into the hash table by using the compare and 46 * hashing functions, provided by the user. 47 */ 48 49 /* 50 * Defines the hash table entry structure, that uses specified type of 51 * elements. 52 */ 53 #define HASHTABLE_ENTRY_HEAD(name, type) struct name { \ 54 type *values; \ 55 size_t capacity; \ 56 size_t size; \ 57 } 58 59 /* 60 * Defines the hash table structure, which uses the specified type of entries. 61 * The only restriction for entries is that is that they should have the field, 62 * defined with HASHTABLE_ENTRY_HEAD macro. 63 */ 64 #define HASHTABLE_HEAD(name, entry) struct name { \ 65 struct entry *entries; \ 66 size_t entries_size; \ 67 } 68 69 #define HASHTABLE_ENTRIES_COUNT(table) ((table)->entries_size) 70 71 /* 72 * Unlike most of queue.h data types, hash tables can not be initialized 73 * statically - so there is no HASHTABLE_HEAD_INITIALIZED macro. 74 */ 75 #define HASHTABLE_INIT(table, type, field, _entries_size) \ 76 do { \ 77 hashtable_index_t var; \ 78 (table)->entries = (void *)malloc( \ 79 sizeof(*(table)->entries) * (_entries_size)); \ 80 memset((table)->entries, 0, \ 81 sizeof(*(table)->entries) * (_entries_size)); \ 82 (table)->entries_size = (_entries_size); \ 83 for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 84 (table)->entries[var].field.capacity = \ 85 HASHTABLE_INITIAL_ENTRIES_CAPACITY; \ 86 (table)->entries[var].field.size = 0; \ 87 (table)->entries[var].field.values = (type *)malloc(\ 88 sizeof(type) * \ 89 HASHTABLE_INITIAL_ENTRIES_CAPACITY); \ 90 assert((table)->entries[var].field.values != NULL);\ 91 } \ 92 } while (0) 93 94 /* 95 * All initialized hashtables should be destroyed with this macro. 96 */ 97 #define HASHTABLE_DESTROY(table, field) \ 98 do { \ 99 hashtable_index_t var; \ 100 for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\ 101 free((table)->entries[var].field.values); \ 102 } \ 103 } while (0) 104 105 #define HASHTABLE_GET_ENTRY(table, hash) (&((table)->entries[hash])) 106 107 /* 108 * Traverses through all hash table entries 109 */ 110 #define HASHTABLE_FOREACH(table, var) \ 111 for ((var) = &((table)->entries[0]); \ 112 (var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\ 113 ++(var)) 114 115 /* 116 * Traverses through all elements of the specified hash table entry 117 */ 118 #define HASHTABLE_ENTRY_FOREACH(entry, field, var) \ 119 for ((var) = &((entry)->field.values[0]); \ 120 (var) < &((entry)->field.values[(entry)->field.size]); \ 121 ++(var)) 122 123 #define HASHTABLE_ENTRY_CLEAR(entry, field) \ 124 ((entry)->field.size = 0) 125 126 #define HASHTABLE_ENTRY_SIZE(entry, field) \ 127 ((entry)->field.size) 128 129 #define HASHTABLE_ENTRY_CAPACITY(entry, field) \ 130 ((entry)->field.capacity) 131 132 #define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type) \ 133 (entry)->field.capacity *= 2; \ 134 (entry)->field.values = (type *)realloc((entry)->field.values, \ 135 (entry)->field.capacity * sizeof(type)); 136 137 #define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type) \ 138 (entry)->field.capacity /= 2; \ 139 (entry)->field.values = (type *)realloc((entry)->field.values, \ 140 (entry)->field.capacity * sizeof(type)); 141 142 /* 143 * Generates prototypes for the hash table functions 144 */ 145 #define HASHTABLE_PROTOTYPE(name, entry_, type) \ 146 hashtable_index_t name##_CALCULATE_HASH(struct name *, type *); \ 147 void name##_ENTRY_STORE(struct entry_*, type *); \ 148 type *name##_ENTRY_FIND(struct entry_*, type *); \ 149 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *, \ 150 int (*) (const void *, const void *)); \ 151 void name##_ENTRY_REMOVE(struct entry_*, type *); 152 153 /* 154 * Generates implementations of the hash table functions 155 */ 156 #define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP) \ 157 hashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data) \ 158 { \ 159 \ 160 return HASH(data, table->entries_size); \ 161 } \ 162 \ 163 void name##_ENTRY_STORE(struct entry_ *the_entry, type *data) \ 164 { \ 165 \ 166 if (the_entry->field.size == the_entry->field.capacity) \ 167 HASHTABLE_ENTRY_CAPACITY_INCREASE(the_entry, field, type);\ 168 \ 169 memcpy(&(the_entry->field.values[the_entry->field.size++]), \ 170 data, \ 171 sizeof(type)); \ 172 qsort(the_entry->field.values, the_entry->field.size, \ 173 sizeof(type), CMP); \ 174 } \ 175 \ 176 type *name##_ENTRY_FIND(struct entry_ *the_entry, type *key) \ 177 { \ 178 \ 179 return ((type *)bsearch(key, the_entry->field.values, \ 180 the_entry->field.size, sizeof(type), CMP)); \ 181 } \ 182 \ 183 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key, \ 184 int (*compar) (const void *, const void *)) \ 185 { \ 186 return ((type *)bsearch(key, the_entry->field.values, \ 187 the_entry->field.size, sizeof(type), compar)); \ 188 } \ 189 \ 190 void name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm) \ 191 { \ 192 \ 193 memmove(del_elm, del_elm + 1, \ 194 (&the_entry->field.values[--the_entry->field.size] - del_elm) *\ 195 sizeof(type)); \ 196 } 197 198 /* 199 * Macro definitions below wrap the functions, generaed with 200 * HASHTABLE_GENERATE macro. You should use them and avoid using generated 201 * functions directly. 202 */ 203 #define HASHTABLE_CALCULATE_HASH(name, table, data) \ 204 (name##_CALCULATE_HASH((table), data)) 205 206 #define HASHTABLE_ENTRY_STORE(name, entry, data) \ 207 name##_ENTRY_STORE((entry), data) 208 209 #define HASHTABLE_ENTRY_FIND(name, entry, key) \ 210 (name##_ENTRY_FIND((entry), (key))) 211 212 #define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp) \ 213 (name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp))) 214 215 #define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm) \ 216 name##_ENTRY_REMOVE((entry), (del_elm)) 217 218 #endif 219