Oops, fix up my previous commit properly.
[dragonfly.git] / usr.sbin / nscd / hashtable.h
CommitLineData
ed5d5720
PA
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
36typedef 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) \
8d411d7d
SW
131 do { \
132 (entry)->field.capacity *= 2; \
133 (entry)->field.values = (type *)realloc((entry)->field.values, \
134 (entry)->field.capacity * sizeof(type)); \
3c4c8f78 135 } while (0)
ed5d5720
PA
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) \
146hashtable_index_t name##_CALCULATE_HASH(struct name *, type *); \
147void name##_ENTRY_STORE(struct entry_*, type *); \
148type *name##_ENTRY_FIND(struct entry_*, type *); \
149type *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *, \
150 int (*) (const void *, const void *)); \
151void 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) \
157hashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data) \
158{ \
159 \
160 return HASH(data, table->entries_size); \
161} \
162 \
163void 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 \
176type *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 \
183type *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 \
190void 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