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 void insque(void* _Nonnull __element, void* _Nullable __previous); 71 72 /** 73 * [remque(3)](http://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)](http://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 int hcreate(size_t __n) __INTRODUCED_IN(28); 89 90 /** 91 * [hdestroy(3)](http://man7.org/linux/man-pages/man3/hdestroy.3.html) destroys 92 * the global hash table. 93 * 94 * See hdestroy_r() if you need more than one hash table. 95 * 96 * Available since API level 28. 97 */ 98 void hdestroy(void) __INTRODUCED_IN(28); 99 100 /** 101 * [hsearch(3)](http://man7.org/linux/man-pages/man3/hsearch.3.html) finds or 102 * inserts `__entry` in the global hash table, based on `__action`. 103 * 104 * See hsearch_r() if you need more than one hash table. 105 * 106 * Returns a pointer to the entry on success, and returns NULL and sets 107 * `errno` on failure. 108 * 109 * Available since API level 28. 110 */ 111 ENTRY* _Nullable hsearch(ENTRY __entry, ACTION __action) __INTRODUCED_IN(28); 112 113 #if defined(__USE_BSD) || defined(__USE_GNU) 114 115 /** 116 * [hcreate_r(3)](http://man7.org/linux/man-pages/man3/hcreate_r.3.html) 117 * initializes a hash table `__table` with space for at least `__n` elements. 118 * 119 * Returns *non-zero* on success and returns 0 and sets `errno` on failure. 120 * 121 * Available since API level 28. 122 */ 123 int hcreate_r(size_t __n, struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 124 125 /** 126 * [hdestroy_r(3)](http://man7.org/linux/man-pages/man3/hdestroy_r.3.html) destroys 127 * the hash table `__table`. 128 * 129 * Available since API level 28. 130 */ 131 void hdestroy_r(struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 132 133 /** 134 * [hsearch_r(3)](http://man7.org/linux/man-pages/man3/hsearch_r.3.html) finds or 135 * inserts `__entry` in the hash table `__table`, based on `__action`. 136 * 137 * Returns *non-zero* on success and returns 0 and sets `errno` on failure. 138 * A pointer to the entry is returned in `*__result`. 139 * 140 * Available since API level 28. 141 */ 142 int hsearch_r(ENTRY __entry, ACTION __action, ENTRY* _Nullable * _Nonnull __result, struct hsearch_data* _Nonnull __table) __INTRODUCED_IN(28); 143 144 #endif 145 146 /** 147 * [lfind(3)](http://man7.org/linux/man-pages/man3/lfind.3.html) brute-force 148 * searches the unsorted array `__array` (of `__count` items each of size `__size`) 149 * for `__key`, using `__comparator`. 150 * 151 * See bsearch() if you have a sorted array. 152 * 153 * Returns a pointer to the matching element on success, or NULL on failure. 154 */ 155 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)); 156 157 /** 158 * [lsearch(3)](http://man7.org/linux/man-pages/man3/lsearch.3.html) brute-force 159 * searches the unsorted array `__array` (of `__count` items each of size `__size`) 160 * for `__key`, using `__comparator`. 161 * 162 * Unlike lfind(), on failure lsearch() will *insert* `__key` at the end of 163 * `__array` and increment `*__count`. 164 * 165 * Returns a pointer to the matching element on success, or to the newly-added 166 * element on failure. 167 */ 168 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)); 169 170 /** 171 * [tdelete(3)](http://man7.org/linux/man-pages/man3/tdelete.3.html) searches 172 * for and removes an element in the tree `*__root_ptr`. The search is performed 173 * using `__comparator`. 174 * 175 * Returns a pointer to the parent of the deleted node, or NULL on failure. 176 */ 177 void* _Nullable tdelete(const void* _Nonnull __key, void* _Nullable * _Nullable __root_ptr, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)); 178 179 /** 180 * [tdestroy(3)](http://man7.org/linux/man-pages/man3/tdestroy.3.html) destroys 181 * the hash table `__root` using `__free_fn` on each node. 182 */ 183 void tdestroy(void* _Nullable __root, void (* _Nullable __free_fn)(void* _Nullable)); 184 185 /** 186 * [tfind(3)](http://man7.org/linux/man-pages/man3/tfind.3.html) searches 187 * for an element in the tree `*__root_ptr`. The search is performed using 188 * `__comparator`. 189 * 190 * Returns a pointer to the matching node, or NULL on failure. 191 */ 192 void* _Nullable tfind(const void* _Nonnull __key, void* _Nullable const* _Nullable __root_ptr, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)); 193 194 /** 195 * [tsearch(3)](http://man7.org/linux/man-pages/man3/tsearch.3.html) searches 196 * for an element in the tree `*__root_ptr`. The search is performed using 197 * `__comparator`. 198 * 199 * Unlike tfind(), on failure tsearch() will *insert* `__key` into the tree. 200 * 201 * Returns a pointer to the matching node, or to the newly-added node. 202 */ 203 void* _Nullable tsearch(const void* _Nonnull __key, void* _Nullable * _Nullable __root_ptr, int (* _Nonnull __comparator)(const void* _Nonnull, const void* _Nonnull)); 204 205 /** 206 * [twalk(3)](http://man7.org/linux/man-pages/man3/twalk.3.html) calls 207 * `__visitor` on every node in the tree. 208 */ 209 void twalk(const void* _Nullable __root, void (* _Nullable __visitor)(const void* _Nullable, VISIT, int)); 210 211 __END_DECLS 212