1 /*- 2 * Written by J.T. Conklin <jtc@NetBSD.org> 3 * Public domain. 4 * 5 * $NetBSD: search.h,v 1.16 2005/02/03 04:39:32 perry Exp $ 6 */ 7 8 #ifndef _SEARCH_H_ 9 #define _SEARCH_H_ 10 11 #include <sys/cdefs.h> 12 #include <sys/_types.h> 13 14 #ifndef _SIZE_T_DECLARED 15 typedef __size_t size_t; 16 #define _SIZE_T_DECLARED 17 #endif 18 19 typedef struct entry { 20 char *key; 21 void *data; 22 } ENTRY; 23 24 typedef enum { 25 FIND, ENTER 26 } ACTION; 27 28 typedef enum { 29 preorder, 30 postorder, 31 endorder, 32 leaf 33 } VISIT; 34 35 #ifdef _SEARCH_PRIVATE 36 typedef struct __posix_tnode { 37 void *key; 38 struct __posix_tnode *llink, *rlink; 39 signed char balance; 40 } posix_tnode; 41 42 struct que_elem { 43 struct que_elem *next; 44 struct que_elem *prev; 45 }; 46 #else 47 typedef void posix_tnode; 48 #endif 49 50 #if __BSD_VISIBLE 51 struct hsearch_data { 52 struct __hsearch *__hsearch; 53 }; 54 #endif 55 56 __BEGIN_DECLS 57 int hcreate(size_t); 58 void hdestroy(void); 59 ENTRY *hsearch(ENTRY, ACTION); 60 void insque(void *, void *); 61 void *lfind(const void *, const void *, size_t *, size_t, 62 int (*)(const void *, const void *)); 63 void *lsearch(const void *, void *, size_t *, size_t, 64 int (*)(const void *, const void *)); 65 void remque(void *); 66 void *tdelete(const void * __restrict, posix_tnode ** __restrict, 67 int (*)(const void *, const void *)); 68 posix_tnode * 69 tfind(const void *, posix_tnode * const *, 70 int (*)(const void *, const void *)); 71 posix_tnode * 72 tsearch(const void *, posix_tnode **, 73 int (*)(const void *, const void *)); 74 void twalk(const posix_tnode *, void (*)(const posix_tnode *, VISIT, int)); 75 76 #if __BSD_VISIBLE 77 int hcreate_r(size_t, struct hsearch_data *); 78 void hdestroy_r(struct hsearch_data *); 79 int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); 80 #endif 81 82 __END_DECLS 83 84 #endif /* !_SEARCH_H_ */ 85