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