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