1a23db957SMike Barcroft /*- 29823a90cSPedro F. Giffuni * Written by J.T. Conklin <jtc@NetBSD.org> 364566a3eSAlfred Perlstein * Public domain. 4a23db957SMike Barcroft * 59823a90cSPedro F. Giffuni * $NetBSD: search.h,v 1.16 2005/02/03 04:39:32 perry Exp $ 664566a3eSAlfred Perlstein */ 764566a3eSAlfred Perlstein 864566a3eSAlfred Perlstein #ifndef _SEARCH_H_ 964566a3eSAlfred Perlstein #define _SEARCH_H_ 1064566a3eSAlfred Perlstein 1164566a3eSAlfred Perlstein #include <sys/cdefs.h> 12abbd8902SMike Barcroft #include <sys/_types.h> 1364566a3eSAlfred Perlstein 14abbd8902SMike Barcroft #ifndef _SIZE_T_DECLARED 15abbd8902SMike Barcroft typedef __size_t size_t; 16abbd8902SMike Barcroft #define _SIZE_T_DECLARED 1764566a3eSAlfred Perlstein #endif 1864566a3eSAlfred Perlstein 1964566a3eSAlfred Perlstein typedef struct entry { 2064566a3eSAlfred Perlstein char *key; 2164566a3eSAlfred Perlstein void *data; 2264566a3eSAlfred Perlstein } ENTRY; 2364566a3eSAlfred Perlstein 2464566a3eSAlfred Perlstein typedef enum { 2564566a3eSAlfred Perlstein FIND, ENTER 2664566a3eSAlfred Perlstein } ACTION; 2764566a3eSAlfred Perlstein 2864566a3eSAlfred Perlstein typedef enum { 2964566a3eSAlfred Perlstein preorder, 3064566a3eSAlfred Perlstein postorder, 3164566a3eSAlfred Perlstein endorder, 3264566a3eSAlfred Perlstein leaf 3364566a3eSAlfred Perlstein } VISIT; 3464566a3eSAlfred Perlstein 3564566a3eSAlfred Perlstein #ifdef _SEARCH_PRIVATE 36*4ef9bd22SEd Schouten typedef struct __posix_tnode { 37459d04a5SEd Schouten void *key; 38*4ef9bd22SEd Schouten struct __posix_tnode *llink, *rlink; 39459d04a5SEd Schouten signed char balance; 40*4ef9bd22SEd Schouten } posix_tnode; 41e768c1beSRobert Drehmel 42e768c1beSRobert Drehmel struct que_elem { 43e768c1beSRobert Drehmel struct que_elem *next; 44e768c1beSRobert Drehmel struct que_elem *prev; 45e768c1beSRobert Drehmel }; 46*4ef9bd22SEd Schouten #else 47*4ef9bd22SEd Schouten typedef void posix_tnode; 4864566a3eSAlfred Perlstein #endif 4964566a3eSAlfred Perlstein 509823a90cSPedro F. Giffuni #if __BSD_VISIBLE 519823a90cSPedro F. Giffuni struct hsearch_data { 522747eff1SEd Schouten struct __hsearch *__hsearch; 539823a90cSPedro F. Giffuni }; 549823a90cSPedro F. Giffuni #endif 559823a90cSPedro F. Giffuni 5664566a3eSAlfred Perlstein __BEGIN_DECLS 57bb28f3c2SWarner Losh int hcreate(size_t); 58bb28f3c2SWarner Losh void hdestroy(void); 59bb28f3c2SWarner Losh ENTRY *hsearch(ENTRY, ACTION); 601d717f20SPedro F. Giffuni void insque(void *, void *); 616c84d0b1SRobert Drehmel void *lfind(const void *, const void *, size_t *, size_t, 626c84d0b1SRobert Drehmel int (*)(const void *, const void *)); 636c84d0b1SRobert Drehmel void *lsearch(const void *, void *, size_t *, size_t, 646c84d0b1SRobert Drehmel int (*)(const void *, const void *)); 65e768c1beSRobert Drehmel void remque(void *); 66*4ef9bd22SEd Schouten void *tdelete(const void * __restrict, posix_tnode ** __restrict, 67840b798cSRobert Drehmel int (*)(const void *, const void *)); 68*4ef9bd22SEd Schouten posix_tnode * 69*4ef9bd22SEd Schouten tfind(const void *, posix_tnode * const *, 70a23db957SMike Barcroft int (*)(const void *, const void *)); 71*4ef9bd22SEd Schouten posix_tnode * 72*4ef9bd22SEd Schouten tsearch(const void *, posix_tnode **, 73*4ef9bd22SEd Schouten int (*)(const void *, const void *)); 74*4ef9bd22SEd Schouten void twalk(const posix_tnode *, void (*)(const posix_tnode *, VISIT, int)); 759823a90cSPedro F. Giffuni 769823a90cSPedro F. Giffuni #if __BSD_VISIBLE 779823a90cSPedro F. Giffuni int hcreate_r(size_t, struct hsearch_data *); 789823a90cSPedro F. Giffuni void hdestroy_r(struct hsearch_data *); 799823a90cSPedro F. Giffuni int hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); 809823a90cSPedro F. Giffuni #endif 819823a90cSPedro F. Giffuni 8264566a3eSAlfred Perlstein __END_DECLS 8364566a3eSAlfred Perlstein 8464566a3eSAlfred Perlstein #endif /* !_SEARCH_H_ */ 85