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