1 /*- 2 * Written by J.T. Conklin <[email protected]> 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)](https://man7.org/linux/man-pages/man3/insque.3.html) inserts 68 * an item in a queue (an intrusive doubly-linked list). 69 */ 70 void insque(void* _Nonnull __element, void* _Nullable __previous); 71 72 /** 73 * [remque(3)](https://man7.org/linux/man-pages/man3/remque.3.html) removes 74 * an item from a queue (an intrusive doubly-linked list). 75 */ 76 void remque(void* _Nonnull __element); 77 78 /** 79 * [hcreate(3)](https://man7.org/linux/man-pages/man3/hcreate.3.html) 80 * initializes the global hash table, with space for at least `__n` elements. 81 * 82 * See hcreate_r() if you need more than one hash table. 83 * 84 * Returns *non-zero* on success and returns 0 and sets `errno` on failure. 85 * 86 * Available since API level 28. 87 */ 88 89 #if __BIONIC_AVAILABILITY_GUARD(28) 90 int hcreate(size_t __n) __INTRODUCED_IN(28); 91 92 /** 93 * [hdestroy(3)](https://man7.org/linux/man-pages/man3/hdestroy.3.html) destroys 94 * the global hash table. 95 * 96 * See hdestroy_r() if you need more than one hash table. 97 * 98 * Available since API level 28. 99 */ 100 void hdestroy(void) __INTRODUCED_IN(28); 101 102 /** 103 * [hsearch(3)](https://man7.org/linux/man-pages/man3/hsearch.3.html) finds or 104 * inserts `__entry` in the global hash table, based on `__action`. 105 * 106 * See hsearch_r() if you need more than one hash table. 107 * 108 * Returns a pointer to the entry on success, and returns NULL and sets 109 * `errno` on failure. 110 * 111 * Available since API level 28. 112 */ 113 ENTRY* _Nullable hsearch(ENTRY __entry, ACTION __action) __INTRODUCED_IN(28); 114 #endif /* __BIONIC_AVAILABILITY_GUARD(28) */ 115 116 117 #if defined(__USE_BSD) || defined(__USE_GNU) 118 119 /** 120 * [hcreate_r(3)](https://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 128 #if __BIONIC_AVAILABILITY_GUARD(28) 129 int hcreate_r(size_t __n, struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 130 131 /** 132 * [hdestroy_r(3)](https://man7.org/linux/man-pages/man3/hdestroy_r.3.html) destroys 133 * the hash table `__table`. 134 * 135 * Available since API level 28. 136 */ 137 void hdestroy_r(struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 138 139 /** 140 * [hsearch_r(3)](https://man7.org/linux/man-pages/man3/hsearch_r.3.html) finds or 141 * inserts `__entry` in the hash table `__table`, based on `__action`. 142 * 143 * Returns *non-zero* on success and returns 0 and sets `errno` on failure. 144 * A pointer to the entry is returned in `*__result`. 145 * 146 * Available since API level 28. 147 */ 148 int hsearch_r(ENTRY __entry, ACTION __action, ENTRY* _Nullable * _Nonnull __result, struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 149 #endif /* __BIONIC_AVAILABILITY_GUARD(28) */ 150 151 152 #endif 153 154 /** 155 * [lfind(3)](https://man7.org/linux/man-pages/man3/lfind.3.html) brute-force 156 * searches the unsorted array `__array` (of `__count` items each of size `__size`) 157 * for `__key`, using `__comparator`. 158 * 159 * See bsearch() if you have a sorted array. 160 * 161 * Returns a pointer to the matching element on success, or NULL on failure. 162 */ 163 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)); 164 165 /** 166 * [lsearch(3)](https://man7.org/linux/man-pages/man3/lsearch.3.html) brute-force 167 * searches the unsorted array `__array` (of `__count` items each of size `__size`) 168 * for `__key`, using `__comparator`. 169 * 170 * Unlike lfind(), on failure lsearch() will *insert* `__key` at the end of 171 * `__array` and increment `*__count`. 172 * 173 * Returns a pointer to the matching element on success, or to the newly-added 174 * element on failure. 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)); 177 178 /** 179 * [tdelete(3)](https://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)](https://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)](https://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)](https://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)](https://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)); 218 219 __END_DECLS 220