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