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