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