1 |
1325 |
phoenix |
/* Declarations for System V style searching functions.
|
2 |
|
|
Copyright (C) 1995-1999, 2000 Free Software Foundation, Inc.
|
3 |
|
|
This file is part of the GNU C Library.
|
4 |
|
|
|
5 |
|
|
The GNU C Library is free software; you can redistribute it and/or
|
6 |
|
|
modify it under the terms of the GNU Lesser General Public
|
7 |
|
|
License as published by the Free Software Foundation; either
|
8 |
|
|
version 2.1 of the License, or (at your option) any later version.
|
9 |
|
|
|
10 |
|
|
The GNU C Library is distributed in the hope that it will be useful,
|
11 |
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
12 |
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
13 |
|
|
Lesser General Public License for more details.
|
14 |
|
|
|
15 |
|
|
You should have received a copy of the GNU Lesser General Public
|
16 |
|
|
License along with the GNU C Library; if not, write to the Free
|
17 |
|
|
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
|
18 |
|
|
02111-1307 USA. */
|
19 |
|
|
|
20 |
|
|
#ifndef _SEARCH_H
|
21 |
|
|
#define _SEARCH_H 1
|
22 |
|
|
|
23 |
|
|
#include <features.h>
|
24 |
|
|
|
25 |
|
|
#define __need_size_t
|
26 |
|
|
#include <stddef.h>
|
27 |
|
|
|
28 |
|
|
__BEGIN_DECLS
|
29 |
|
|
|
30 |
|
|
#if defined __USE_SVID || defined __USE_XOPEN_EXTENDED
|
31 |
|
|
/* Prototype structure for a linked-list data structure.
|
32 |
|
|
This is the type used by the `insque' and `remque' functions. */
|
33 |
|
|
|
34 |
|
|
# ifdef __USE_GNU
|
35 |
|
|
struct qelem
|
36 |
|
|
{
|
37 |
|
|
struct qelem *q_forw;
|
38 |
|
|
struct qelem *q_back;
|
39 |
|
|
char q_data[1];
|
40 |
|
|
};
|
41 |
|
|
# endif
|
42 |
|
|
|
43 |
|
|
|
44 |
|
|
/* Insert ELEM into a doubly-linked list, after PREV. */
|
45 |
|
|
extern void insque (void *__elem, void *__prev) __THROW;
|
46 |
|
|
|
47 |
|
|
/* Unlink ELEM from the doubly-linked list that it is in. */
|
48 |
|
|
extern void remque (void *__elem) __THROW;
|
49 |
|
|
#endif
|
50 |
|
|
|
51 |
|
|
|
52 |
|
|
/* For use with hsearch(3). */
|
53 |
|
|
#ifndef __COMPAR_FN_T
|
54 |
|
|
# define __COMPAR_FN_T
|
55 |
|
|
typedef int (*__compar_fn_t) (__const void *, __const void *);
|
56 |
|
|
|
57 |
|
|
# ifdef __USE_GNU
|
58 |
|
|
typedef __compar_fn_t comparison_fn_t;
|
59 |
|
|
# endif
|
60 |
|
|
#endif
|
61 |
|
|
|
62 |
|
|
/* Action which shall be performed in the call the hsearch. */
|
63 |
|
|
typedef enum
|
64 |
|
|
{
|
65 |
|
|
FIND,
|
66 |
|
|
ENTER
|
67 |
|
|
}
|
68 |
|
|
ACTION;
|
69 |
|
|
|
70 |
|
|
typedef struct entry
|
71 |
|
|
{
|
72 |
|
|
char *key;
|
73 |
|
|
void *data;
|
74 |
|
|
}
|
75 |
|
|
ENTRY;
|
76 |
|
|
|
77 |
|
|
/* Opaque type for internal use. */
|
78 |
|
|
struct _ENTRY;
|
79 |
|
|
|
80 |
|
|
/* Family of hash table handling functions. The functions also
|
81 |
|
|
have reentrant counterparts ending with _r. The non-reentrant
|
82 |
|
|
functions all work on a signle internal hashing table. */
|
83 |
|
|
|
84 |
|
|
/* Search for entry matching ITEM.key in internal hash table. If
|
85 |
|
|
ACTION is `FIND' return found entry or signal error by returning
|
86 |
|
|
NULL. If ACTION is `ENTER' replace existing data (if any) with
|
87 |
|
|
ITEM.data. */
|
88 |
|
|
extern ENTRY *hsearch (ENTRY __item, ACTION __action) __THROW;
|
89 |
|
|
|
90 |
|
|
/* Create a new hashing table which will at most contain NEL elements. */
|
91 |
|
|
extern int hcreate (size_t __nel) __THROW;
|
92 |
|
|
|
93 |
|
|
/* Destroy current internal hashing table. */
|
94 |
|
|
extern void hdestroy (void) __THROW;
|
95 |
|
|
|
96 |
|
|
#ifdef __USE_GNU
|
97 |
|
|
/* Data type for reentrant functions. */
|
98 |
|
|
struct hsearch_data
|
99 |
|
|
{
|
100 |
|
|
struct _ENTRY *table;
|
101 |
|
|
unsigned int size;
|
102 |
|
|
unsigned int filled;
|
103 |
|
|
};
|
104 |
|
|
|
105 |
|
|
/* Reentrant versions which can handle multiple hashing tables at the
|
106 |
|
|
same time. */
|
107 |
|
|
extern int hsearch_r (ENTRY __item, ACTION __action, ENTRY **__retval,
|
108 |
|
|
struct hsearch_data *__htab) __THROW;
|
109 |
|
|
extern int hcreate_r (size_t __nel, struct hsearch_data *__htab) __THROW;
|
110 |
|
|
extern void hdestroy_r (struct hsearch_data *__htab) __THROW;
|
111 |
|
|
#endif
|
112 |
|
|
|
113 |
|
|
|
114 |
|
|
/* The tsearch routines are very interesting. They make many
|
115 |
|
|
assumptions about the compiler. It assumes that the first field
|
116 |
|
|
in node must be the "key" field, which points to the datum.
|
117 |
|
|
Everything depends on that. */
|
118 |
|
|
/* For tsearch */
|
119 |
|
|
typedef enum
|
120 |
|
|
{
|
121 |
|
|
preorder,
|
122 |
|
|
postorder,
|
123 |
|
|
endorder,
|
124 |
|
|
leaf
|
125 |
|
|
}
|
126 |
|
|
VISIT;
|
127 |
|
|
|
128 |
|
|
/* Search for an entry matching the given KEY in the tree pointed to
|
129 |
|
|
by *ROOTP and insert a new element if not found. */
|
130 |
|
|
extern void *tsearch (__const void *__key, void **__rootp,
|
131 |
|
|
__compar_fn_t __compar);
|
132 |
|
|
|
133 |
|
|
/* Search for an entry matching the given KEY in the tree pointed to
|
134 |
|
|
by *ROOTP. If no matching entry is available return NULL. */
|
135 |
|
|
extern void *tfind (__const void *__key, void *__const *__rootp,
|
136 |
|
|
__compar_fn_t __compar);
|
137 |
|
|
|
138 |
|
|
/* Remove the element matching KEY from the tree pointed to by *ROOTP. */
|
139 |
|
|
extern void *tdelete (__const void *__restrict __key,
|
140 |
|
|
void **__restrict __rootp,
|
141 |
|
|
__compar_fn_t __compar);
|
142 |
|
|
|
143 |
|
|
#ifndef __ACTION_FN_T
|
144 |
|
|
# define __ACTION_FN_T
|
145 |
|
|
typedef void (*__action_fn_t) (__const void *__nodep, VISIT __value,
|
146 |
|
|
int __level);
|
147 |
|
|
#endif
|
148 |
|
|
|
149 |
|
|
/* Walk through the whole tree and call the ACTION callback for every node
|
150 |
|
|
or leaf. */
|
151 |
|
|
extern void twalk (__const void *__root, __action_fn_t __action);
|
152 |
|
|
|
153 |
|
|
#ifdef __USE_GNU
|
154 |
|
|
/* Callback type for function to free a tree node. If the keys are atomic
|
155 |
|
|
data this function should do nothing. */
|
156 |
|
|
typedef void (*__free_fn_t) (void *__nodep);
|
157 |
|
|
|
158 |
|
|
/* Destroy the whole tree, call FREEFCT for each node or leaf. */
|
159 |
|
|
extern void tdestroy (void *__root, __free_fn_t __freefct);
|
160 |
|
|
#endif
|
161 |
|
|
|
162 |
|
|
|
163 |
|
|
/* Perform linear search for KEY by comparing by COMPAR in an array
|
164 |
|
|
[BASE,BASE+NMEMB*SIZE). */
|
165 |
|
|
extern void *lfind (__const void *__key, __const void *__base,
|
166 |
|
|
size_t *__nmemb, size_t __size, __compar_fn_t __compar);
|
167 |
|
|
|
168 |
|
|
/* Perform linear search for KEY by comparing by COMPAR function in
|
169 |
|
|
array [BASE,BASE+NMEMB*SIZE) and insert entry if not found. */
|
170 |
|
|
extern void *lsearch (__const void *__key, void *__base,
|
171 |
|
|
size_t *__nmemb, size_t __size, __compar_fn_t __compar);
|
172 |
|
|
|
173 |
|
|
__END_DECLS
|
174 |
|
|
|
175 |
|
|
#endif /* search.h */
|