1 /* $NetBSD: search.h,v 1.19 2011/09/14 23:34:26 christos Exp $ */ 2 3 /* 4 * Written by J.T. Conklin <jtc@NetBSD.org> 5 * Public domain. 6 */ 7 8 #ifndef _SEARCH_H_ 9 #define _SEARCH_H_ 10 11 #include <sys/cdefs.h> 12 #include <machine/ansi.h> 13 14 #ifdef _BSD_SIZE_T_ 15 typedef _BSD_SIZE_T_ size_t; 16 #undef _BSD_SIZE_T_ 17 #endif 18 19 typedef struct entry { 20 char *key; 21 void *data; 22 } ENTRY; 23 24 #ifdef _NETBSD_SOURCE 25 struct _ENTRY; 26 struct hsearch_data { 27 struct _ENTRY *table; 28 size_t size; 29 size_t filled; 30 }; 31 #endif 32 33 typedef enum { 34 FIND, ENTER 35 } ACTION; 36 37 typedef enum { 38 preorder, 39 postorder, 40 endorder, 41 leaf 42 } VISIT; 43 44 #ifdef _SEARCH_PRIVATE 45 typedef struct node { 46 char *key; 47 struct node *llink, *rlink; 48 } node_t; 49 #endif 50 51 __BEGIN_DECLS 52 #ifndef __BSEARCH_DECLARED 53 #define __BSEARCH_DECLARED 54 /* also in stdlib.h */ 55 void *bsearch(const void *, const void *, size_t, size_t, 56 int (*)(const void *, const void *)); 57 #endif /* __BSEARCH_DECLARED */ 58 59 int hcreate(size_t); 60 void hdestroy(void); 61 ENTRY *hsearch(ENTRY, ACTION); 62 63 #ifdef _NETBSD_SOURCE 64 int hcreate_r(size_t, struct hsearch_data *); 65 void hdestroy_r(struct hsearch_data *); 66 int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); 67 #endif /* _NETBSD_SOURCE */ 68 69 void *lfind(const void *, const void *, size_t *, size_t, 70 int (*)(const void *, const void *)); 71 void *lsearch(const void *, void *, size_t *, size_t, 72 int (*)(const void *, const void *)); 73 void insque(void *, void *); 74 void remque(void *); 75 76 void *tdelete(const void * __restrict, void ** __restrict, 77 int (*)(const void *, const void *)); 78 void *tfind(const void *, void * const *, 79 int (*)(const void *, const void *)); 80 void *tsearch(const void *, void **, 81 int (*)(const void *, const void *)); 82 void twalk(const void *, void (*)(const void *, VISIT, int)); 83 __END_DECLS 84 85 #endif /* !_SEARCH_H_ */ 86