1 /*
2 * SHL - Dynamic hash-table
3 *
4 * Copyright (c) 2010-2013 David Herrmann <dh.herrmann@gmail.com>
5 * Licensed under LGPLv2+ - see LICENSE_htable file for details
6 */
7
8 /*
9 * Dynamic hash-table
10 * Implementation of a self-resizing hashtable to store arbitrary objects.
11 * Entries are not allocated by the table itself but are user-allocated. A
12 * single entry can be stored multiple times in the hashtable. No
13 * maintenance-members need to be embedded in user-allocated objects. However,
14 * the key (and optionally the hash) must be stored in the objects.
15 *
16 * Uses internally the htable from CCAN. See LICENSE_htable.
17 */
18
19 #ifndef SHL_HTABLE_H
20 #define SHL_HTABLE_H
21
22 #include <limits.h>
23 #include <stdbool.h>
24 #include <stddef.h>
25 #include <stdint.h>
26 #include <stdlib.h>
27
28 /* miscellaneous */
29
30 #define shl_htable_offsetof(pointer, type, member) ({ \
31 const typeof(((type*)0)->member) *__ptr = (pointer); \
32 (type*)(((char*)__ptr) - offsetof(type, member)); \
33 })
34
35 /* htable */
36
37 struct shl_htable_int {
38 size_t (*rehash)(const void *elem, void *priv);
39 void *priv;
40 unsigned int bits;
41 size_t elems, deleted, max, max_with_deleted;
42 /* These are the bits which are the same in all pointers. */
43 uintptr_t common_mask, common_bits;
44 uintptr_t perfect_bit;
45 uintptr_t *table;
46 };
47
48 struct shl_htable {
49 bool (*compare) (const void *a, const void *b);
50 struct shl_htable_int htable;
51 };
52
53 #define SHL_HTABLE_INIT(_obj, _compare, _rehash, _priv) \
54 { \
55 .compare = (_compare), \
56 .htable = { \
57 .rehash = (_rehash), \
58 .priv = (_priv), \
59 .bits = 0, \
60 .elems = 0, \
61 .deleted = 0, \
62 .max = 0, \
63 .max_with_deleted = 0, \
64 .common_mask = -1, \
65 .common_bits = 0, \
66 .perfect_bit = 0, \
67 .table = &(_obj).htable.perfect_bit \
68 } \
69 }
70
71 void shl_htable_init(struct shl_htable *htable,
72 bool (*compare) (const void *a, const void *b),
73 size_t (*rehash)(const void *elem, void *priv),
74 void *priv);
75 void shl_htable_clear(struct shl_htable *htable,
76 void (*free_cb) (void *elem, void *ctx),
77 void *ctx);
78 void shl_htable_visit(struct shl_htable *htable,
79 void (*visit_cb) (void *elem, void *ctx),
80 void *ctx);
81 bool shl_htable_lookup(struct shl_htable *htable, const void *obj, size_t hash,
82 void **out);
83 int shl_htable_insert(struct shl_htable *htable, const void *obj, size_t hash);
84 bool shl_htable_remove(struct shl_htable *htable, const void *obj, size_t hash,
85 void **out);
86
87 /* ulong htables */
88
89 #if SIZE_MAX < ULONG_MAX
90 # error "'size_t' is smaller than 'unsigned long'"
91 #endif
92
93 bool shl_htable_compare_ulong(const void *a, const void *b);
94 size_t shl_htable_rehash_ulong(const void *elem, void *priv);
95
96 #define SHL_HTABLE_INIT_ULONG(_obj) \
97 SHL_HTABLE_INIT((_obj), shl_htable_compare_ulong, \
98 shl_htable_rehash_ulong, \
99 NULL)
100
shl_htable_init_ulong(struct shl_htable * htable)101 static inline void shl_htable_init_ulong(struct shl_htable *htable)
102 {
103 shl_htable_init(htable, shl_htable_compare_ulong,
104 shl_htable_rehash_ulong, NULL);
105 }
106
shl_htable_clear_ulong(struct shl_htable * htable,void (* cb)(unsigned long * elem,void * ctx),void * ctx)107 static inline void shl_htable_clear_ulong(struct shl_htable *htable,
108 void (*cb) (unsigned long *elem,
109 void *ctx),
110 void *ctx)
111 {
112 shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx);
113 }
114
shl_htable_visit_ulong(struct shl_htable * htable,void (* cb)(unsigned long * elem,void * ctx),void * ctx)115 static inline void shl_htable_visit_ulong(struct shl_htable *htable,
116 void (*cb) (unsigned long *elem,
117 void *ctx),
118 void *ctx)
119 {
120 shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx);
121 }
122
shl_htable_lookup_ulong(struct shl_htable * htable,unsigned long key,unsigned long ** out)123 static inline bool shl_htable_lookup_ulong(struct shl_htable *htable,
124 unsigned long key,
125 unsigned long **out)
126 {
127 return shl_htable_lookup(htable, (const void*)&key, (size_t)key,
128 (void**)out);
129 }
130
shl_htable_insert_ulong(struct shl_htable * htable,const unsigned long * key)131 static inline int shl_htable_insert_ulong(struct shl_htable *htable,
132 const unsigned long *key)
133 {
134 return shl_htable_insert(htable, (const void*)key, (size_t)*key);
135 }
136
shl_htable_remove_ulong(struct shl_htable * htable,unsigned long key,unsigned long ** out)137 static inline bool shl_htable_remove_ulong(struct shl_htable *htable,
138 unsigned long key,
139 unsigned long **out)
140 {
141 return shl_htable_remove(htable, (const void*)&key, (size_t)key,
142 (void**)out);
143 }
144
145 /* string htables */
146
147 bool shl_htable_compare_str(const void *a, const void *b);
148 size_t shl_htable_rehash_str(const void *elem, void *priv);
149
150 #define SHL_HTABLE_INIT_STR(_obj) \
151 SHL_HTABLE_INIT((_obj), shl_htable_compare_str, \
152 shl_htable_rehash_str, \
153 NULL)
154
shl_htable_init_str(struct shl_htable * htable)155 static inline void shl_htable_init_str(struct shl_htable *htable)
156 {
157 shl_htable_init(htable, shl_htable_compare_str,
158 shl_htable_rehash_str, NULL);
159 }
160
shl_htable_clear_str(struct shl_htable * htable,void (* cb)(char ** elem,void * ctx),void * ctx)161 static inline void shl_htable_clear_str(struct shl_htable *htable,
162 void (*cb) (char **elem,
163 void *ctx),
164 void *ctx)
165 {
166 shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx);
167 }
168
shl_htable_visit_str(struct shl_htable * htable,void (* cb)(char ** elem,void * ctx),void * ctx)169 static inline void shl_htable_visit_str(struct shl_htable *htable,
170 void (*cb) (char **elem,
171 void *ctx),
172 void *ctx)
173 {
174 shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx);
175 }
176
shl_htable_hash_str(struct shl_htable * htable,const char * str,size_t * hash)177 static inline size_t shl_htable_hash_str(struct shl_htable *htable,
178 const char *str, size_t *hash)
179 {
180 size_t h;
181
182 if (hash && *hash) {
183 h = *hash;
184 } else {
185 h = htable->htable.rehash((const void*)&str, NULL);
186 if (hash)
187 *hash = h;
188 }
189
190 return h;
191 }
192
shl_htable_lookup_str(struct shl_htable * htable,const char * str,size_t * hash,char *** out)193 static inline bool shl_htable_lookup_str(struct shl_htable *htable,
194 const char *str, size_t *hash,
195 char ***out)
196 {
197 size_t h;
198
199 h = shl_htable_hash_str(htable, str, hash);
200 return shl_htable_lookup(htable, (const void*)&str, h, (void**)out);
201 }
202
shl_htable_insert_str(struct shl_htable * htable,char ** str,size_t * hash)203 static inline int shl_htable_insert_str(struct shl_htable *htable,
204 char **str, size_t *hash)
205 {
206 size_t h;
207
208 h = shl_htable_hash_str(htable, *str, hash);
209 return shl_htable_insert(htable, (const void*)str, h);
210 }
211
shl_htable_remove_str(struct shl_htable * htable,const char * str,size_t * hash,char *** out)212 static inline bool shl_htable_remove_str(struct shl_htable *htable,
213 const char *str, size_t *hash,
214 char ***out)
215 {
216 size_t h;
217
218 h = shl_htable_hash_str(htable, str, hash);
219 return shl_htable_remove(htable, (const void*)&str, h, (void **)out);
220 }
221
222 #endif /* SHL_HTABLE_H */
223