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