include/search.h

   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_ */