1 /*- 2 * Written by J.T. Conklin <jtc@netbsd.org> 3 * Public domain. 4 * 5 * $NetBSD: search.h,v 1.12 1999/02/22 10:34:28 christos Exp $ 6 * $FreeBSD: release/9.0.0/include/search.h 105250 2002-10-16 14:29:23Z robert $ 7 */ 8 9 #pragma once 10 11 /** 12 * @file search.h 13 * @brief Queues, hash tables, trees, and linear array searches. 14 */ 15 16 #include <sys/cdefs.h> 17 #include <sys/types.h> 18 19 /** See hsearch()/hsearch_r(). */ 20 typedef enum { 21 FIND, 22 ENTER 23 } ACTION; 24 25 /** See hsearch()/hsearch_r(). */ 26 typedef struct entry { 27 /** The string key. */ 28 char* _Nullable key; 29 /** The associated data. */ 30 void* _Nullable data; 31 } ENTRY; 32 33 /** 34 * Constants given to the twalk() visitor. 35 * Note that the constant names are misleading. 36 */ 37 typedef enum { 38 /** 39 * If this is the first visit to a non-leaf node. 40 * Use this for *preorder* traversal. 41 */ 42 preorder, 43 /** 44 * If this is the second visit to a non-leaf node. 45 * Use this for *inorder* traversal. 46 */ 47 postorder, 48 /** 49 * If this is the third visit to a non-leaf node. 50 * Use this for *postorder* traversal. 51 */ 52 endorder, 53 /** If this is the first and only visit to a leaf node. */ 54 leaf 55 } VISIT; 56 57 #if defined(__USE_BSD) || defined(__USE_GNU) 58 /** The hash table type for hcreate_r()/hdestroy_r()/hsearch_r(). */ 59 struct hsearch_data { 60 struct __hsearch* _Nullable __hsearch; 61 }; 62 #endif 63 64 __BEGIN_DECLS 65 66 /** 67 * [insque(3)](http://man7.org/linux/man-pages/man3/insque.3.html) inserts 68 * an item in a queue (an intrusive doubly-linked list). 69 * 70 * Available since API level 21. 71 */ 72 void insque(void* _Nonnull __element, void* _Nullable __previous) __INTRODUCED_IN(21); 73 74 /** 75 * [remque(3)](http://man7.org/linux/man-pages/man3/remque.3.html) removes 76 * an item from a queue (an intrusive doubly-linked list). 77 * 78 * Available since API level 21. 79 */ 80 void remque(void* _Nonnull __element) __INTRODUCED_IN(21); 81 82 /** 83 * [hcreate(3)](http://man7.org/linux/man-pages/man3/hcreate.3.html) 84 * initializes the global hash table, with space for at least `__n` elements. 85 * 86 * See hcreate_r() if you need more than one hash table. 87 * 88 * Returns *non-zero* on success and returns 0 and sets `errno` on failure. 89 * 90 * Available since API level 28. 91 */ 92 int hcreate(size_t __n) __INTRODUCED_IN(28); 93 94 /** 95 * [hdestroy(3)](http://man7.org/linux/man-pages/man3/hdestroy.3.html) destroys 96 * the global hash table. 97 * 98 * See hdestroy_r() if you need more than one hash table. 99 * 100 * Available since API level 28. 101 */ 102 void hdestroy(void) __INTRODUCED_IN(28); 103 104 /** 105 * [hsearch(3)](http://man7.org/linux/man-pages/man3/hsearch.3.html) finds or 106 * inserts `__entry` in the global hash table, based on `__action`. 107 * 108 * See hsearch_r() if you need more than one hash table. 109 * 110 * Returns a pointer to the entry on success, and returns NULL and sets 111 * `errno` on failure. 112 * 113 * Available since API level 28. 114 */ 115 ENTRY* _Nullable hsearch(ENTRY __entry, ACTION __action) __INTRODUCED_IN(28); 116 117 #if defined(__USE_BSD) || defined(__USE_GNU) 118 119 /** 120 * [hcreate_r(3)](http://man7.org/linux/man-pages/man3/hcreate_r.3.html) 121 * initializes a hash table `__table` with space for at least `__n` elements. 122 * 123 * Returns *non-zero* on success and returns 0 and sets `errno` on failure. 124 * 125 * Available since API level 28. 126 */ 127 int hcreate_r(size_t __n, struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 128 129 /** 130 * [hdestroy_r(3)](http://man7.org/linux/man-pages/man3/hdestroy_r.3.html) destroys 131 * the hash table `__table`. 132 * 133 * Available since API level 28. 134 */ 135 void hdestroy_r(struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 136 137 /** 138 * [hsearch_r(3)](http://man7.org/linux/man-pages/man3/hsearch_r.3.html) finds or 139 * inserts `__entry` in the hash table `__table`, based on `__action`. 140 * 141 * Returns *non-zero* on success and returns 0 and sets `errno` on failure. 142 * A pointer to the entry is returned in `*__result`. 143 * 144 * Available since API level 28. 145 */ 146 int hsearch_r(ENTRY __entry, ACTION __action, ENTRY* _Nullable * _Nonnull __result, struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 147 148 #endif 149 150 /** 151 * [lfind(3)](http://man7.org/linux/man-pages/man3/lfind.3.html) brute-force 152 * searches the unsorted array `__array` (of `__count` items each of size `__size`) 153 * for `__key`, using `__comparator`. 154 * 155 * See bsearch() if you have a sorted array. 156 * 157 * Returns a pointer to the matching element on success, or NULL on failure. 158 * 159 * Available since API level 21. 160 */ 161 void* _Nullable lfind(const void* _Nonnull __key, const void* _Nonnull __array, size_t* _Nonnull __count, size_t __size, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)) __INTRODUCED_IN(21); 162 163 /** 164 * [lsearch(3)](http://man7.org/linux/man-pages/man3/lsearch.3.html) brute-force 165 * searches the unsorted array `__array` (of `__count` items each of size `__size`) 166 * for `__key`, using `__comparator`. 167 * 168 * Unlike lfind(), on failure lsearch() will *insert* `__key` at the end of 169 * `__array` and increment `*__count`. 170 * 171 * Returns a pointer to the matching element on success, or to the newly-added 172 * element on failure. 173 * 174 * Available since API level 21. 175 */ 176 void* _Nonnull lsearch(const void* _Nonnull __key, void* _Nonnull __array, size_t* _Nonnull __count, size_t __size, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)) __INTRODUCED_IN(21); 177 178 /** 179 * [tdelete(3)](http://man7.org/linux/man-pages/man3/tdelete.3.html) searches 180 * for and removes an element in the tree `*__root_ptr`. The search is performed 181 * using `__comparator`. 182 * 183 * Returns a pointer to the parent of the deleted node, or NULL on failure. 184 */ 185 void* _Nullable tdelete(const void* _Nonnull __key, void* _Nullable * _Nullable __root_ptr, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)); 186 187 /** 188 * [tdestroy(3)](http://man7.org/linux/man-pages/man3/tdestroy.3.html) destroys 189 * the hash table `__root` using `__free_fn` on each node. 190 */ 191 void tdestroy(void* _Nullable __root, void (* _Nullable __free_fn)(void* _Nullable)); 192 193 /** 194 * [tfind(3)](http://man7.org/linux/man-pages/man3/tfind.3.html) searches 195 * for an element in the tree `*__root_ptr`. The search is performed using 196 * `__comparator`. 197 * 198 * Returns a pointer to the matching node, or NULL on failure. 199 */ 200 void* _Nullable tfind(const void* _Nonnull __key, void* _Nullable const* _Nullable __root_ptr, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)); 201 202 /** 203 * [tsearch(3)](http://man7.org/linux/man-pages/man3/tsearch.3.html) searches 204 * for an element in the tree `*__root_ptr`. The search is performed using 205 * `__comparator`. 206 * 207 * Unlike tfind(), on failure tsearch() will *insert* `__key` into the tree. 208 * 209 * Returns a pointer to the matching node, or to the newly-added node. 210 */ 211 void* _Nullable tsearch(const void* _Nonnull __key, void* _Nullable * _Nullable __root_ptr, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)); 212 213 /** 214 * [twalk(3)](http://man7.org/linux/man-pages/man3/twalk.3.html) calls 215 * `__visitor` on every node in the tree. 216 */ 217 void twalk(const void* _Nullable __root, void (* _Nullable __visitor)(const void* _Nullable, VISIT, int)) __INTRODUCED_IN(21); 218 219 __END_DECLS 220