1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
/* Licensed under LGPLv2+ - see LICENSE file for details */
#ifndef CCAN_HTABLE_TYPE_H
#define CCAN_HTABLE_TYPE_H
#include <ccan/htable/htable.h>
#include <ccan/compiler/compiler.h>
#include "config.h"
/**
* HTABLE_DEFINE_TYPE - create a set of htable ops for a type
* @type: a type whose pointers will be values in the hash.
* @keyof: a function/macro to extract a key: <keytype> @keyof(const type *elem)
* @hashfn: a hash function for a @key: size_t @hashfn(const <keytype> *)
* @eqfn: an equality function keys: bool @eqfn(const type *, const <keytype> *)
* @prefix: a prefix for all the functions to define (of form <name>_*)
*
* NULL values may not be placed into the hash table.
*
* This defines the type hashtable type and an iterator type:
* struct <name>;
* struct <name>_iter;
*
* It also defines initialization and freeing functions:
* void <name>_init(struct <name> *);
* bool <name>_init_sized(struct <name> *, size_t);
* void <name>_clear(struct <name> *);
* bool <name>_copy(struct <name> *dst, const struct <name> *src);
*
* Count entries:
* size_t <name>_count(const struct <name> *ht);
*
* Add function only fails if we run out of memory:
* bool <name>_add(struct <name> *ht, const <type> *e);
*
* Delete and delete-by key return true if it was in the set:
* bool <name>_del(struct <name> *ht, const <type> *e);
* bool <name>_delkey(struct <name> *ht, const <keytype> *k);
*
* Delete by iterator:
* bool <name>_delval(struct <name> *ht, struct <name>_iter *i);
*
* Find and return the (first) matching element, or NULL:
* type *<name>_get(const struct @name *ht, const <keytype> *k);
*
* Find and return all matching elements, or NULL:
* type *<name>_getfirst(const struct @name *ht, const <keytype> *k,
* struct <name>_iter *i);
* type *<name>_getnext(const struct @name *ht, const <keytype> *k,
* struct <name>_iter *i);
*
* Iteration over hashtable is also supported:
* type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
* type *<name>_next(const struct <name> *ht, struct <name>_iter *i);
* type *<name>_prev(const struct <name> *ht, struct <name>_iter *i);
* type *<name>_pick(const struct <name> *ht, size_t seed,
* struct <name>_iter *i);
* It's currently safe to iterate over a changing hashtable, but you might
* miss an element. Iteration isn't very efficient, either.
*
* You can use HTABLE_INITIALIZER like so:
* struct <name> ht = { HTABLE_INITIALIZER(ht.raw, <name>_hash, NULL) };
*/
#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name) \
struct name { struct htable raw; }; \
struct name##_iter { struct htable_iter i; }; \
static inline size_t name##_hash(const void *elem, void *priv) \
{ \
(void)priv; \
return hashfn(keyof((const type *)elem)); \
} \
static inline UNNEEDED void name##_init(struct name *ht) \
{ \
htable_init(&ht->raw, name##_hash, NULL); \
} \
static inline UNNEEDED bool name##_init_sized(struct name *ht, \
size_t s) \
{ \
return htable_init_sized(&ht->raw, name##_hash, NULL, s); \
} \
static inline UNNEEDED size_t name##_count(const struct name *ht) \
{ \
return htable_count(&ht->raw); \
} \
static inline UNNEEDED void name##_clear(struct name *ht) \
{ \
htable_clear(&ht->raw); \
} \
static inline UNNEEDED bool name##_copy(struct name *dst, \
const struct name *src) \
{ \
return htable_copy(&dst->raw, &src->raw); \
} \
static inline bool name##_add(struct name *ht, const type *elem) \
{ \
return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \
} \
static inline UNNEEDED bool name##_del(struct name *ht, \
const type *elem) \
{ \
return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \
} \
static inline UNNEEDED type *name##_get(const struct name *ht, \
const HTABLE_KTYPE(keyof, type) k) \
{ \
struct htable_iter i; \
size_t h = hashfn(k); \
void *c; \
\
for (c = htable_firstval(&ht->raw,&i,h); \
c; \
c = htable_nextval(&ht->raw,&i,h)) { \
if (eqfn(c, k)) \
return c; \
} \
return NULL; \
} \
static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \
const HTABLE_KTYPE(keyof, type) k, \
size_t h, \
type *v, \
struct name##_iter *iter) \
{ \
while (v) { \
if (eqfn(v, k)) \
break; \
v = htable_nextval(&ht->raw, &iter->i, h); \
} \
return v; \
} \
static inline UNNEEDED type *name##_getfirst(const struct name *ht, \
const HTABLE_KTYPE(keyof, type) k, \
struct name##_iter *iter) \
{ \
size_t h = hashfn(k); \
type *v = htable_firstval(&ht->raw, &iter->i, h); \
return name##_getmatch_(ht, k, h, v, iter); \
} \
static inline UNNEEDED type *name##_getnext(const struct name *ht, \
const HTABLE_KTYPE(keyof, type) k, \
struct name##_iter *iter) \
{ \
size_t h = hashfn(k); \
type *v = htable_nextval(&ht->raw, &iter->i, h); \
return name##_getmatch_(ht, k, h, v, iter); \
} \
static inline UNNEEDED bool name##_delkey(struct name *ht, \
const HTABLE_KTYPE(keyof, type) k) \
{ \
type *elem = name##_get(ht, k); \
if (elem) \
return name##_del(ht, elem); \
return false; \
} \
static inline UNNEEDED void name##_delval(struct name *ht, \
struct name##_iter *iter) \
{ \
htable_delval(&ht->raw, &iter->i); \
} \
static inline UNNEEDED type *name##_pick(const struct name *ht, \
size_t seed, \
struct name##_iter *iter) \
{ \
return htable_pick(&ht->raw, seed, iter ? &iter->i : NULL); \
} \
static inline UNNEEDED type *name##_first(const struct name *ht, \
struct name##_iter *iter) \
{ \
return htable_first(&ht->raw, &iter->i); \
} \
static inline UNNEEDED type *name##_next(const struct name *ht, \
struct name##_iter *iter) \
{ \
return htable_next(&ht->raw, &iter->i); \
} \
static inline UNNEEDED type *name##_prev(const struct name *ht, \
struct name##_iter *iter) \
{ \
return htable_prev(&ht->raw, &iter->i); \
}
#if HAVE_TYPEOF
#define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL))
#else
/* Assumes keys are a pointer: if not, override. */
#ifndef HTABLE_KTYPE
#define HTABLE_KTYPE(keyof, type) void *
#endif
#endif
#endif /* CCAN_HTABLE_TYPE_H */
|
