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 * Count entries: 29 * size_t <name>_count(const struct <name> *ht); 30 * 31 * Add function only fails if we run out of memory: 32 * bool <name>_add(struct <name> *ht, const <type> *e); 33 * 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); 37 * 38 * Delete by iterator: 39 * bool <name>_delval(struct <name> *ht, struct <name>_iter *i); 40 * 41 * Find and return the (first) matching element, or NULL: 42 * type *<name>_get(const struct @name *ht, const <keytype> *k); 43 * 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); 49 * 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. 58 * 59 * You can use HTABLE_INITIALIZER like so: 60 * struct <name> ht = { HTABLE_INITIALIZER(ht.raw, <name>_hash, NULL) }; 61 */ 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) \ 66 { \ 67 (void)priv; \ 68 return hashfn(keyof((const type *)elem)); \ 69 } \ 70 static inline UNNEEDED void name##_init(struct name *ht) \ 71 { \ 72 htable_init(&ht->raw, name##_hash, NULL); \ 73 } \ 74 static inline UNNEEDED bool name##_init_sized(struct name *ht, \ 75 size_t s) \ 76 { \ 77 return htable_init_sized(&ht->raw, name##_hash, NULL, s); \ 78 } \ 79 static inline UNNEEDED size_t name##_count(const struct name *ht) \ 80 { \ 81 return htable_count(&ht->raw); \ 82 } \ 83 static inline UNNEEDED void name##_clear(struct name *ht) \ 84 { \ 85 htable_clear(&ht->raw); \ 86 } \ 87 static inline UNNEEDED bool name##_copy(struct name *dst, \ 88 const struct name *src) \ 89 { \ 90 return htable_copy(&dst->raw, &src->raw); \ 91 } \ 92 static inline bool name##_add(struct name *ht, const type *elem) \ 93 { \ 94 return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \ 95 } \ 96 static inline UNNEEDED bool name##_del(struct name *ht, \ 97 const type *elem) \ 98 { \ 99 return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \ 100 } \ 101 static inline UNNEEDED type *name##_get(const struct name *ht, \ 102 const HTABLE_KTYPE(keyof, type) k) \ 103 { \ 104 struct htable_iter i; \ 105 size_t h = hashfn(k); \ 106 void *c; \ 107 \ 108 for (c = htable_firstval(&ht->raw,&i,h); \ 109 c; \ 110 c = htable_nextval(&ht->raw,&i,h)) { \ 111 if (eqfn(c, k)) \ 112 return c; \ 113 } \ 114 return NULL; \ 115 } \ 116 static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \ 117 const HTABLE_KTYPE(keyof, type) k, \ 118 size_t h, \ 119 type *v, \ 120 struct name##_iter *iter) \ 121 { \ 122 while (v) { \ 123 if (eqfn(v, k)) \ 124 break; \ 125 v = htable_nextval(&ht->raw, &iter->i, h); \ 126 } \ 127 return v; \ 128 } \ 129 static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ 130 const HTABLE_KTYPE(keyof, type) k, \ 131 struct name##_iter *iter) \ 132 { \ 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); \ 136 } \ 137 static inline UNNEEDED type *name##_getnext(const struct name *ht, \ 138 const HTABLE_KTYPE(keyof, type) k, \ 139 struct name##_iter *iter) \ 140 { \ 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); \ 144 } \ 145 static inline UNNEEDED bool name##_delkey(struct name *ht, \ 146 const HTABLE_KTYPE(keyof, type) k) \ 147 { \ 148 type *elem = name##_get(ht, k); \ 149 if (elem) \ 150 return name##_del(ht, elem); \ 151 return false; \ 152 } \ 153 static inline UNNEEDED void name##_delval(struct name *ht, \ 154 struct name##_iter *iter) \ 155 { \ 156 htable_delval(&ht->raw, &iter->i); \ 157 } \ 158 static inline UNNEEDED type *name##_pick(const struct name *ht, \ 159 size_t seed, \ 160 struct name##_iter *iter) \ 161 { \ 162 /* Note &iter->i == NULL iff iter is NULL */ \ 163 return htable_pick(&ht->raw, seed, &iter->i); \ 164 } \ 165 static inline UNNEEDED type *name##_first(const struct name *ht, \ 166 struct name##_iter *iter) \ 167 { \ 168 return htable_first(&ht->raw, &iter->i); \ 169 } \ 170 static inline UNNEEDED type *name##_next(const struct name *ht, \ 171 struct name##_iter *iter) \ 172 { \ 173 return htable_next(&ht->raw, &iter->i); \ 174 } \ 175 static inline UNNEEDED type *name##_prev(const struct name *ht, \ 176 struct name##_iter *iter) \ 177 { \ 178 return htable_prev(&ht->raw, &iter->i); \ 179 } 180 181 #if HAVE_TYPEOF 182 #define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL)) 183 #else 184 /* Assumes keys are a pointer: if not, override. */ 185 #ifndef HTABLE_KTYPE 186 #define HTABLE_KTYPE(keyof, type) void * 187 #endif 188 #endif 189 #endif /* CCAN_HTABLE_TYPE_H */ 190