682db8674165e59ad3c78e0e26df8a53bb5fa02d
[dragonfly.git] / usr.sbin / nscd / hashtable.h
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: src/usr.sbin/nscd/hashtable.h,v 1.3 2008/10/12 00:44:27 delphij Exp $
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 *)calloc(1,                    \
79                         sizeof(*(table)->entries) * (_entries_size));   \
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 = (type *)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)        (&((table)->entries[hash]))
104
105 /*
106  * Traverses through all hash table entries
107  */
108 #define HASHTABLE_FOREACH(table, var)                                   \
109         for ((var) = &((table)->entries[0]);                            \
110                 (var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\
111                 ++(var))
112
113 /*
114  * Traverses through all elements of the specified hash table entry
115  */
116 #define HASHTABLE_ENTRY_FOREACH(entry, field, var)                      \
117         for ((var) = &((entry)->field.values[0]);                       \
118                 (var) < &((entry)->field.values[(entry)->field.size]);  \
119                 ++(var))
120
121 #define HASHTABLE_ENTRY_CLEAR(entry, field)                             \
122         ((entry)->field.size = 0)
123
124 #define HASHTABLE_ENTRY_SIZE(entry, field)                              \
125         ((entry)->field.size)
126
127 #define HASHTABLE_ENTRY_CAPACITY(entry, field)                          \
128         ((entry)->field.capacity)
129
130 #define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type)           \
131         do {                                                            \
132                 (entry)->field.capacity *= 2;                           \
133                 (entry)->field.values = (type *)realloc((entry)->field.values, \
134                         (entry)->field.capacity * sizeof(type));        \
135         while (0)
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