xref: /freebsd/usr.sbin/nscd/hashtable.h (revision c697fb7f)
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 <string.h>
33 
34 #define HASHTABLE_INITIAL_ENTRIES_CAPACITY 8
35 typedef unsigned int hashtable_index_t;
36 
37 /*
38  * This file contains queue.h-like macro definitions for hash tables.
39  * Hash table is organized as an array of the specified size of the user
40  * defined (with HASTABLE_ENTRY_HEAD) structures. Each hash table
41  * entry (user defined structure) stores its elements in the sorted array.
42  * You can place elements into the hash table, retrieve elements with
43  * specified key, traverse through all elements, and delete them.
44  * New elements are placed into the hash table by using the compare and
45  * hashing functions, provided by the user.
46  */
47 
48 /*
49  * Defines the hash table entry structure, that uses specified type of
50  * elements.
51  */
52 #define HASHTABLE_ENTRY_HEAD(name, type) struct name {			\
53 	type	*values;						\
54 	size_t capacity;						\
55 	size_t size;							\
56 }
57 
58 /*
59  * Defines the hash table structure, which uses the specified type of entries.
60  * The only restriction for entries is that is that they should have the field,
61  * defined with HASHTABLE_ENTRY_HEAD macro.
62  */
63 #define HASHTABLE_HEAD(name, entry) struct name {			\
64 	struct entry	*entries;					\
65 	size_t		entries_size;					\
66 }
67 
68 #define HASHTABLE_ENTRIES_COUNT(table)					\
69 	((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 = calloc(_entries_size,		\
79 			sizeof(*(table)->entries));			\
80 		(table)->entries_size = (_entries_size);		\
81 		for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\
82 			(table)->entries[var].field.capacity = 		\
83 				HASHTABLE_INITIAL_ENTRIES_CAPACITY;	\
84 			(table)->entries[var].field.size = 0;		\
85 			(table)->entries[var].field.values = malloc(	\
86 				sizeof(type) *				\
87 				HASHTABLE_INITIAL_ENTRIES_CAPACITY);	\
88 			assert((table)->entries[var].field.values != NULL);\
89 		}							\
90 	} while (0)
91 
92 /*
93  * All initialized hashtables should be destroyed with this macro.
94  */
95 #define HASHTABLE_DESTROY(table, field)					\
96 	do {								\
97 		hashtable_index_t var;					\
98 		for (var = 0; var < HASHTABLE_ENTRIES_COUNT(table); ++var) {\
99 			free((table)->entries[var].field.values);	\
100 		}							\
101 	} while (0)
102 
103 #define HASHTABLE_GET_ENTRY(table, hash)				\
104 	(&((table)->entries[hash]))
105 
106 /*
107  * Traverses through all hash table entries
108  */
109 #define HASHTABLE_FOREACH(table, var)					\
110 	for ((var) = &((table)->entries[0]);				\
111 		(var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\
112 		++(var))
113 
114 /*
115  * Traverses through all elements of the specified hash table entry
116  */
117 #define HASHTABLE_ENTRY_FOREACH(entry, field, var)			\
118 	for ((var) = &((entry)->field.values[0]);			\
119 		(var) < &((entry)->field.values[(entry)->field.size]);	\
120 		++(var))
121 
122 #define HASHTABLE_ENTRY_CLEAR(entry, field)				\
123 	((entry)->field.size = 0)
124 
125 #define HASHTABLE_ENTRY_SIZE(entry, field)				\
126 	((entry)->field.size)
127 
128 #define HASHTABLE_ENTRY_CAPACITY(entry, field)				\
129 	((entry)->field.capacity)
130 
131 #define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type)		\
132 	do {								\
133 		(entry)->field.capacity *= 2;				\
134 		(entry)->field.values = realloc((entry)->field.values,	\
135 			 (entry)->field.capacity * sizeof(type));	\
136 	} while (0)
137 
138 #define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type)		\
139 	do {								\
140 		(entry)->field.capacity /= 2;				\
141 		(entry)->field.values = realloc((entry)->field.values,	\
142 			(entry)->field.capacity * sizeof(type));	\
143 	} while (0)
144 
145 /*
146  * Generates prototypes for the hash table functions
147  */
148 #define HASHTABLE_PROTOTYPE(name, entry_, type)				\
149 hashtable_index_t name##_CALCULATE_HASH(struct name *, type *);		\
150 void name##_ENTRY_STORE(struct entry_*, type *);			\
151 type *name##_ENTRY_FIND(struct entry_*, type *);			\
152 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *,		\
153 	int (*) (const void *, const void *));				\
154 void name##_ENTRY_REMOVE(struct entry_*, type *);
155 
156 /*
157  * Generates implementations of the hash table functions
158  */
159 #define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP)	\
160 hashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data)	\
161 {									\
162 									\
163 	return HASH(data, table->entries_size);				\
164 }									\
165 									\
166 void name##_ENTRY_STORE(struct entry_ *the_entry, type *data)		\
167 {									\
168 									\
169 	if (the_entry->field.size == the_entry->field.capacity)		\
170 		HASHTABLE_ENTRY_CAPACITY_INCREASE(the_entry, field, type);\
171 									\
172 	memcpy(&(the_entry->field.values[the_entry->field.size++]),	\
173 		data,							\
174 		sizeof(type));						\
175 	qsort(the_entry->field.values, the_entry->field.size, 		\
176 		sizeof(type), CMP);					\
177 }									\
178 									\
179 type *name##_ENTRY_FIND(struct entry_ *the_entry, type *key)		\
180 {									\
181 									\
182 	return ((type *)bsearch(key, the_entry->field.values,	 	\
183 		the_entry->field.size, sizeof(type), CMP));		\
184 }									\
185 									\
186 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key,	\
187 	int (*compar) (const void *, const void *))			\
188 {									\
189 	return ((type *)bsearch(key, the_entry->field.values,	 	\
190 		the_entry->field.size, sizeof(type), compar));		\
191 }									\
192 									\
193 void name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm)	\
194 {									\
195 									\
196 	memmove(del_elm, del_elm + 1, 					\
197 		(&the_entry->field.values[--the_entry->field.size] - del_elm) *\
198 		sizeof(type));						\
199 }
200 
201 /*
202  * Macro definitions below wrap the functions, generaed with
203  * HASHTABLE_GENERATE macro. You should use them and avoid using generated
204  * functions directly.
205  */
206 #define HASHTABLE_CALCULATE_HASH(name, table, data)			\
207 	(name##_CALCULATE_HASH((table), data))
208 
209 #define HASHTABLE_ENTRY_STORE(name, entry, data)			\
210 	name##_ENTRY_STORE((entry), data)
211 
212 #define HASHTABLE_ENTRY_FIND(name, entry, key)				\
213 	(name##_ENTRY_FIND((entry), (key)))
214 
215 #define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp)		\
216 	(name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp)))
217 
218 #define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm)			\
219 	name##_ENTRY_REMOVE((entry), (del_elm))
220 
221 #endif
222