1 /* 2 * Copyright (C) 2010-2020 Red Hat, Inc. 3 * 4 * Author: Angus Salkeld <asalkeld@redhat.com> 5 * 6 * This file is part of libqb. 7 * 8 * libqb is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Lesser General Public License as published by 10 * the Free Software Foundation, either version 2.1 of the License, or 11 * (at your option) any later version. 12 * 13 * libqb is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public License 19 * along with libqb. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 #ifndef QB_MAP_H_DEFINED 22 #define QB_MAP_H_DEFINED 23 24 #include <stdint.h> 25 #ifndef S_SPLINT_S 26 #include <unistd.h> 27 #endif /* S_SPLINT_S */ 28 29 /* *INDENT-OFF* */ 30 #ifdef __cplusplus 31 extern "C" { 32 #endif 33 /* *INDENT-ON* */ 34 35 /** 36 * @file qbmap.h 37 * This provides a map interface to a Patricia trie, hashtable or skiplist. 38 * 39 * @par Ordering 40 * The hashtable is NOT ordered, but ptrie and skiplist are. 41 * 42 * @par Iterating 43 * Below is a simple example of how to iterate over a map. 44 * @code 45 * const char *p; 46 * void *data; 47 * qb_map_iter_t *it = qb_map_iter_create(m); 48 * for (p = qb_map_iter_next(it, &data); p; p = qb_map_iter_next(it, &data)) { 49 * printf("%s > %s\n", p, (char*) data); 50 * } 51 * qb_map_iter_free(it); 52 * @endcode 53 * 54 * Deletion of items within the iterator is supported. But note do not 55 * free the item memory in the iterator. If you need to free the data 56 * items then register for a notifier and free the memory there. This 57 * is required as the items are reference counted. 58 * @code 59 * qb_map_notify_add(m, NULL, my_map_free_handler, 60 * QB_MAP_NOTIFY_FREE, NULL); 61 * @endcode 62 * 63 * @par Notifications 64 * These allow you to get callbacks when values are inserted/removed or 65 * replaced. 66 * @note hashtable only supports deletion and replacement notificatins. 67 * There is also a special global callback for freeing deleted and replaced 68 * values (QB_MAP_NOTIFY_FREE). 69 * @see qb_map_notify_add() qb_map_notify_del_2() 70 * 71 * @par Prefix matching 72 * The ptrie supports prefixes in the iterator: 73 * 74 * @code 75 * it = qb_map_pref_iter_create(m, "aa"); 76 * while ((p = qb_map_iter_next(it, &data)) != NULL) { 77 * printf("%s > %s\n", p, (char*)data); 78 * } 79 * qb_map_iter_free(it); 80 * @endcode 81 * 82 * The ptrie also supports prefixes in notifications: 83 * (remember to pass QB_MAP_NOTIFY_RECURSIVE into the notify_add. 84 * @code 85 * qb_map_notify_add(m, "root", my_map_notification, 86 * (QB_MAP_NOTIFY_INSERTED| 87 * QB_MAP_NOTIFY_DELETED| 88 * QB_MAP_NOTIFY_REPLACED| 89 * QB_MAP_NOTIFY_RECURSIVE), 90 * NULL); 91 * 92 * @endcode 93 */ 94 95 /** 96 * This is an opaque data type representing an instance of a map. 97 */ 98 typedef struct qb_map qb_map_t; 99 100 /** 101 * This is an opaque data type representing an iterator instance. 102 */ 103 typedef struct qb_map_iter qb_map_iter_t; 104 105 #define QB_MAP_NOTIFY_DELETED 1 106 #define QB_MAP_NOTIFY_REPLACED 2 107 #define QB_MAP_NOTIFY_INSERTED 4 108 #define QB_MAP_NOTIFY_RECURSIVE 8 109 #define QB_MAP_NOTIFY_FREE 16 110 111 typedef void (*qb_map_notify_fn)(uint32_t event, 112 char* key, 113 void* old_value, 114 void* value, 115 void* user_data); 116 117 typedef int32_t (*qb_map_transverse_fn)(const char* key, 118 void* value, 119 void* user_data); 120 121 /** 122 * Create an unsorted map based on a hashtable. 123 * 124 * @param max_size maximum size of the hashtable 125 * 126 * @return the map instance 127 */ 128 qb_map_t* qb_hashtable_create(size_t max_size); 129 130 /** 131 * Create a sorted map using a skiplist. 132 * 133 * @return the map instance 134 */ 135 qb_map_t* qb_skiplist_create(void); 136 137 /** 138 * Create a sorted map using a Patricia trie or "Radix tree". 139 * 140 * @htmlonly 141 * See the wikipedia <a href="http://en.wikipedia.org/wiki/Radix_Tree">Radix_tree</a> 142 * and <a href="http://en.wikipedia.org/wiki/Trie">Trie</a> pages. 143 * @endhtmlonly 144 */ 145 qb_map_t* qb_trie_create(void); 146 147 /** 148 * print out the nodes in the trie 149 * 150 * (for debug purposes) 151 */ 152 void 153 qb_trie_dump(qb_map_t* m); 154 155 /** 156 * Add a notifier to the map. 157 * 158 * @param m the map instance 159 * @param key the key (or prefix) to attach the notification to. 160 * @param fn the callback 161 * @param events the type of events to register for. 162 * @param user_data a pointer to be passed into the callback 163 * 164 * @note QB_MAP_NOTIFY_INSERTED is only valid on tries. 165 * @note you can use key prefixes with trie maps. 166 * 167 * @retval 0 success 168 * @retval -errno failure 169 */ 170 int32_t qb_map_notify_add(qb_map_t* m, const char* key, 171 qb_map_notify_fn fn, int32_t events, 172 void *user_data); 173 174 /** 175 * Delete a notifier from the map. 176 * 177 * @note the key,fn and events must match those you added. 178 * 179 * @param m the map instance 180 * @param key the key (or prefix) to attach the notification to. 181 * @param fn the callback 182 * @param events the type of events to register for. 183 * 184 * @retval 0 success 185 * @retval -errno failure 186 */ 187 int32_t qb_map_notify_del(qb_map_t* m, const char* key, 188 qb_map_notify_fn fn, int32_t events); 189 190 /** 191 * Delete a notifier from the map (including the userdata). 192 * 193 * @note the key, fn, events and userdata must match those you added. 194 * 195 * @param m the map instance 196 * @param key the key (or prefix) to attach the notification to. 197 * @param fn the callback 198 * @param events the type of events to register for. 199 * @param user_data a pointer to be passed into the callback 200 * 201 * @retval 0 success 202 * @retval -errno failure 203 */ 204 int32_t qb_map_notify_del_2(qb_map_t* m, const char* key, 205 qb_map_notify_fn fn, int32_t events, 206 void *user_data); 207 208 /** 209 * Inserts a new key and value into a qb_map_t. 210 * 211 * If the key already exists in the qb_map_t, it gets replaced by the new key. 212 */ 213 void qb_map_put(qb_map_t *map, const char* key, const void* value); 214 215 /** 216 * Gets the value corresponding to the given key. 217 * 218 * @retval NULL (if the key does not exist) 219 * @retval a pointer to the value 220 */ 221 void* qb_map_get(qb_map_t *map, const char* key); 222 223 /** 224 * Removes a key/value pair from a map. 225 */ 226 int32_t qb_map_rm(qb_map_t *map, const char* key); 227 228 /** 229 * Get the number of items in the map. 230 */ 231 size_t qb_map_count_get(qb_map_t *map); 232 233 /** 234 * Calls the given function for each of the key/value pairs in the map. 235 * 236 * The function is passed the key and value of each pair, and the given data 237 * parameter. The map is traversed in sorted order. 238 */ 239 void qb_map_foreach(qb_map_t *map, qb_map_transverse_fn func, void* user_data); 240 241 /** 242 * Create an iterator 243 */ 244 qb_map_iter_t* qb_map_iter_create(qb_map_t *map); 245 246 /** 247 * Create a prefix iterator. 248 * 249 * This will iterate over all items with the given 250 * prefix. 251 * @note this is only supported by the trie. 252 */ 253 qb_map_iter_t* qb_map_pref_iter_create(qb_map_t *map, const char* prefix); 254 255 /** 256 * Get the next item 257 * 258 * @param i the iterator 259 * @param value (out) the next item's value 260 * 261 * @retval the next key 262 * @retval NULL - the end of the iteration 263 */ 264 const char* qb_map_iter_next(qb_map_iter_t* i, void** value); 265 266 /** 267 * free the iterator 268 * 269 * @param i the iterator 270 */ 271 void qb_map_iter_free(qb_map_iter_t* i); 272 273 /** 274 * Destroy the map, removes all the items from the map. 275 */ 276 void qb_map_destroy(qb_map_t *map); 277 278 /* *INDENT-OFF* */ 279 #ifdef __cplusplus 280 } 281 #endif 282 /* *INDENT-ON* */ 283 284 #endif /* QB_MAP_H_DEFINED */ 285