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