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