include/search.h

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