1104399Smike/*- 2268943Spfg * Written by J.T. Conklin <jtc@NetBSD.org> 362321Salfred * Public domain. 4104399Smike * 5268943Spfg * $NetBSD: search.h,v 1.16 2005/02/03 04:39:32 perry Exp $ 6104399Smike * $FreeBSD: stable/11/include/search.h 308090 2016-10-29 14:41:22Z ed $ 762321Salfred */ 862321Salfred 962321Salfred#ifndef _SEARCH_H_ 1062321Salfred#define _SEARCH_H_ 1162321Salfred 1262321Salfred#include <sys/cdefs.h> 13102227Smike#include <sys/_types.h> 1462321Salfred 15102227Smike#ifndef _SIZE_T_DECLARED 16102227Smiketypedef __size_t size_t; 17102227Smike#define _SIZE_T_DECLARED 1862321Salfred#endif 1962321Salfred 20104399Smiketypedef struct entry { 21104399Smike char *key; 22104399Smike void *data; 2362321Salfred} ENTRY; 2462321Salfred 25104399Smiketypedef enum { 2662321Salfred FIND, ENTER 2762321Salfred} ACTION; 2862321Salfred 29104399Smiketypedef enum { 3062321Salfred preorder, 3162321Salfred postorder, 3262321Salfred endorder, 3362321Salfred leaf 3462321Salfred} VISIT; 3562321Salfred 3662321Salfred#ifdef _SEARCH_PRIVATE 37308090Sedtypedef struct __posix_tnode { 38308090Sed void *key; 39308090Sed struct __posix_tnode *llink, *rlink; 40308090Sed signed char balance; 41308090Sed} posix_tnode; 42105245Srobert 43105245Srobertstruct que_elem { 44105245Srobert struct que_elem *next; 45105245Srobert struct que_elem *prev; 46105245Srobert}; 47308090Sed#else 48308090Sedtypedef void posix_tnode; 4962321Salfred#endif 5062321Salfred 51268943Spfg#if __BSD_VISIBLE 52268943Spfgstruct hsearch_data { 53292767Sed struct __hsearch *__hsearch; 54268943Spfg}; 55268943Spfg#endif 56268943Spfg 5762321Salfred__BEGIN_DECLS 5893032Simpint hcreate(size_t); 5993032Simpvoid hdestroy(void); 6093032SimpENTRY *hsearch(ENTRY, ACTION); 61268846Spfgvoid insque(void *, void *); 62105250Srobertvoid *lfind(const void *, const void *, size_t *, size_t, 63105250Srobert int (*)(const void *, const void *)); 64105250Srobertvoid *lsearch(const void *, void *, size_t *, size_t, 65105250Srobert int (*)(const void *, const void *)); 66105245Srobertvoid remque(void *); 67308090Sedvoid *tdelete(const void * __restrict, posix_tnode ** __restrict, 68101882Srobert int (*)(const void *, const void *)); 69308090Sedposix_tnode * 70308090Sed tfind(const void *, posix_tnode * const *, 71104399Smike int (*)(const void *, const void *)); 72308090Sedposix_tnode * 73308090Sed tsearch(const void *, posix_tnode **, 74308090Sed int (*)(const void *, const void *)); 75308090Sedvoid twalk(const posix_tnode *, void (*)(const posix_tnode *, VISIT, int)); 76268943Spfg 77268943Spfg#if __BSD_VISIBLE 78268943Spfgint hcreate_r(size_t, struct hsearch_data *); 79268943Spfgvoid hdestroy_r(struct hsearch_data *); 80268943Spfgint hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); 81268943Spfg#endif 82268943Spfg 8362321Salfred__END_DECLS 8462321Salfred 8562321Salfred#endif /* !_SEARCH_H_ */ 86