include/search.h

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