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