1 /*-
36  * This file contains queue.h-like macro definitions for hash tables.
39  * entry (user defined structure) stores its elements in the sorted array.
47  * Defines the hash table entry structure, that uses specified type of
50 #define HASHTABLE_ENTRY_HEAD(name, type) struct name {			\  argument
61 #define HASHTABLE_HEAD(name, entry) struct name {			\  argument
62 	struct entry	*entries;					\
67 	((table)->entries_size)
71  * statically - so there is no HASHTABLE_HEAD_INITIALIZED macro.
76 		(table)->entries = calloc(_entries_size,		\
77 			sizeof(*(table)->entries));			\
78 		(table)->entries_size = (_entries_size);		\
80 			(table)->entries[var].field.capacity = 		\
82 			(table)->entries[var].field.size = 0;		\
83 			(table)->entries[var].field.values = malloc(	\
86 			assert((table)->entries[var].field.values != NULL);\
97 			free((table)->entries[var].field.values);	\
102 	(&((table)->entries[hash]))
108 	for ((var) = &((table)->entries[0]);				\
109 		(var) < &((table)->entries[HASHTABLE_ENTRIES_COUNT(table)]);\
113  * Traverses through all elements of the specified hash table entry
115 #define HASHTABLE_ENTRY_FOREACH(entry, field, var)			\  argument
116 	for ((var) = &((entry)->field.values[0]);			\
117 		(var) < &((entry)->field.values[(entry)->field.size]);	\
120 #define HASHTABLE_ENTRY_CLEAR(entry, field)				\  argument
121 	((entry)->field.size = 0)
123 #define HASHTABLE_ENTRY_SIZE(entry, field)				\  argument
124 	((entry)->field.size)
126 #define HASHTABLE_ENTRY_CAPACITY(entry, field)				\  argument
127 	((entry)->field.capacity)
129 #define HASHTABLE_ENTRY_CAPACITY_INCREASE(entry, field, type)		\  argument
131 		(entry)->field.capacity *= 2;				\
132 		(entry)->field.values = realloc((entry)->field.values,	\
133 			 (entry)->field.capacity * sizeof(type));	\
136 #define HASHTABLE_ENTRY_CAPACITY_DECREASE(entry, field, type)		\  argument
138 		(entry)->field.capacity /= 2;				\
139 		(entry)->field.values = realloc((entry)->field.values,	\
140 			(entry)->field.capacity * sizeof(type));	\
146 #define HASHTABLE_PROTOTYPE(name, entry_, type)				\  argument
147 hashtable_index_t name##_CALCULATE_HASH(struct name *, type *);		\
148 void name##_ENTRY_STORE(struct entry_*, type *);			\
149 type *name##_ENTRY_FIND(struct entry_*, type *);			\
150 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *, type *,		\
152 void name##_ENTRY_REMOVE(struct entry_*, type *);
157 #define HASHTABLE_GENERATE(name, entry_, type, field, HASH, CMP)	\  argument
158 hashtable_index_t name##_CALCULATE_HASH(struct name *table, type *data)	\
161 	return HASH(data, table->entries_size);				\
164 void name##_ENTRY_STORE(struct entry_ *the_entry, type *data)		\
167 	if (the_entry->field.size == the_entry->field.capacity)		\
170 	memcpy(&(the_entry->field.values[the_entry->field.size++]),	\
173 	qsort(the_entry->field.values, the_entry->field.size, 		\
177 type *name##_ENTRY_FIND(struct entry_ *the_entry, type *key)		\
180 	return ((type *)bsearch(key, the_entry->field.values,	 	\
181 		the_entry->field.size, sizeof(type), CMP));		\
184 type *name##_ENTRY_FIND_SPECIAL(struct entry_ *the_entry, type *key,	\
187 	return ((type *)bsearch(key, the_entry->field.values,	 	\
188 		the_entry->field.size, sizeof(type), compar));		\
191 void name##_ENTRY_REMOVE(struct entry_ *the_entry, type *del_elm)	\
195 		(&the_entry->field.values[--the_entry->field.size] - del_elm) *\
204 #define HASHTABLE_CALCULATE_HASH(name, table, data)			\  argument
205 	(name##_CALCULATE_HASH((table), data))
207 #define HASHTABLE_ENTRY_STORE(name, entry, data)			\  argument
208 	name##_ENTRY_STORE((entry), data)
210 #define HASHTABLE_ENTRY_FIND(name, entry, key)				\  argument
211 	(name##_ENTRY_FIND((entry), (key)))
213 #define HASHTABLE_ENTRY_FIND_SPECIAL(name, entry, key, cmp)		\  argument
214 	(name##_ENTRY_FIND_SPECIAL((entry), (key), (cmp)))
216 #define HASHTABLE_ENTRY_REMOVE(name, entry, del_elm)			\  argument
217 	name##_ENTRY_REMOVE((entry), (del_elm))