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