1 /* Licensed under LGPLv2+ - see LICENSE file for details */
2 #ifndef CCAN_HTABLE_TYPE_H
3 #define CCAN_HTABLE_TYPE_H
4 #include <ccan/htable/htable.h>
5 #include <ccan/compiler/compiler.h>
9 * HTABLE_DEFINE_TYPE - create a set of htable ops for a type
10 * @type: a type whose pointers will be values in the hash.
11 * @keyof: a function/macro to extract a key: <keytype> @keyof(const type *elem)
12 * @hashfn: a hash function for a @key: size_t @hashfn(const <keytype> *)
13 * @eqfn: an equality function keys: bool @eqfn(const type *, const <keytype> *)
14 * @prefix: a prefix for all the functions to define (of form <name>_*)
16 * NULL values may not be placed into the hash table.
18 * This defines the type hashtable type and an iterator type:
22 * It also defines initialization and freeing functions:
23 * void <name>_init(struct <name> *);
24 * bool <name>_init_sized(struct <name> *, size_t);
25 * void <name>_clear(struct <name> *);
26 * bool <name>_copy(struct <name> *dst, const struct <name> *src);
29 * size_t <name>_count(const struct <name> *ht);
31 * Add function only fails if we run out of memory:
32 * bool <name>_add(struct <name> *ht, const <type> *e);
34 * Delete and delete-by key return true if it was in the set:
35 * bool <name>_del(struct <name> *ht, const <type> *e);
36 * bool <name>_delkey(struct <name> *ht, const <keytype> *k);
39 * bool <name>_delval(struct <name> *ht, struct <name>_iter *i);
41 * Find and return the (first) matching element, or NULL:
42 * type *<name>_get(const struct @name *ht, const <keytype> *k);
44 * Find and return all matching elements, or NULL:
45 * type *<name>_getfirst(const struct @name *ht, const <keytype> *k,
46 * struct <name>_iter *i);
47 * type *<name>_getnext(const struct @name *ht, const <keytype> *k,
48 * struct <name>_iter *i);
50 * Iteration over hashtable is also supported:
51 * type *<name>_first(const struct <name> *ht, struct <name>_iter *i);
52 * type *<name>_next(const struct <name> *ht, struct <name>_iter *i);
53 * type *<name>_prev(const struct <name> *ht, struct <name>_iter *i);
54 * type *<name>_pick(const struct <name> *ht, size_t seed,
55 * struct <name>_iter *i);
56 * It's currently safe to iterate over a changing hashtable, but you might
57 * miss an element. Iteration isn't very efficient, either.
59 * You can use HTABLE_INITIALIZER like so:
60 * struct <name> ht = { HTABLE_INITIALIZER(ht.raw, <name>_hash, NULL) };
62 #define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name) \
63 struct name { struct htable raw; }; \
64 struct name##_iter { struct htable_iter i; }; \
65 static inline size_t name##_hash(const void *elem, void *priv) \
68 return hashfn(keyof((const type *)elem)); \
70 static inline UNNEEDED void name##_init(struct name *ht) \
72 htable_init(&ht->raw, name##_hash, NULL); \
74 static inline UNNEEDED bool name##_init_sized(struct name *ht, \
77 return htable_init_sized(&ht->raw, name##_hash, NULL, s); \
79 static inline UNNEEDED size_t name##_count(const struct name *ht) \
81 return htable_count(&ht->raw); \
83 static inline UNNEEDED void name##_clear(struct name *ht) \
85 htable_clear(&ht->raw); \
87 static inline UNNEEDED bool name##_copy(struct name *dst, \
88 const struct name *src) \
90 return htable_copy(&dst->raw, &src->raw); \
92 static inline bool name##_add(struct name *ht, const type *elem) \
94 return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \
96 static inline UNNEEDED bool name##_del(struct name *ht, \
99 return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \
101 static inline UNNEEDED type *name##_get(const struct name *ht, \
102 const HTABLE_KTYPE(keyof, type) k) \
104 struct htable_iter i; \
105 size_t h = hashfn(k); \
108 for (c = htable_firstval(&ht->raw,&i,h); \
110 c = htable_nextval(&ht->raw,&i,h)) { \
116 static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \
117 const HTABLE_KTYPE(keyof, type) k, \
120 struct name##_iter *iter) \
125 v = htable_nextval(&ht->raw, &iter->i, h); \
129 static inline UNNEEDED type *name##_getfirst(const struct name *ht, \
130 const HTABLE_KTYPE(keyof, type) k, \
131 struct name##_iter *iter) \
133 size_t h = hashfn(k); \
134 type *v = htable_firstval(&ht->raw, &iter->i, h); \
135 return name##_getmatch_(ht, k, h, v, iter); \
137 static inline UNNEEDED type *name##_getnext(const struct name *ht, \
138 const HTABLE_KTYPE(keyof, type) k, \
139 struct name##_iter *iter) \
141 size_t h = hashfn(k); \
142 type *v = htable_nextval(&ht->raw, &iter->i, h); \
143 return name##_getmatch_(ht, k, h, v, iter); \
145 static inline UNNEEDED bool name##_delkey(struct name *ht, \
146 const HTABLE_KTYPE(keyof, type) k) \
148 type *elem = name##_get(ht, k); \
150 return name##_del(ht, elem); \
153 static inline UNNEEDED void name##_delval(struct name *ht, \
154 struct name##_iter *iter) \
156 htable_delval(&ht->raw, &iter->i); \
158 static inline UNNEEDED type *name##_pick(const struct name *ht, \
160 struct name##_iter *iter) \
162 /* Note &iter->i == NULL iff iter is NULL */ \
163 return htable_pick(&ht->raw, seed, &iter->i); \
165 static inline UNNEEDED type *name##_first(const struct name *ht, \
166 struct name##_iter *iter) \
168 return htable_first(&ht->raw, &iter->i); \
170 static inline UNNEEDED type *name##_next(const struct name *ht, \
171 struct name##_iter *iter) \
173 return htable_next(&ht->raw, &iter->i); \
175 static inline UNNEEDED type *name##_prev(const struct name *ht, \
176 struct name##_iter *iter) \
178 return htable_prev(&ht->raw, &iter->i); \
182 #define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL))
184 /* Assumes keys are a pointer: if not, override. */
186 #define HTABLE_KTYPE(keyof, type) void *
189 #endif /* CCAN_HTABLE_TYPE_H */