---

---

---

001: /* Declarations for System V style searching functions.
002:    Copyright (C) 1995-1999, 2000 Free Software Foundation, Inc.
003:    This file is part of the GNU C Library.
004: 
005:    The GNU C Library is free software; you can redistribute it and/or
006:    modify it under the terms of the GNU Lesser General Public
007:    License as published by the Free Software Foundation; either
008:    version 2.1 of the License, or (at your option) any later version.
009: 
010:    The GNU C Library is distributed in the hope that it will be useful,
011:    but WITHOUT ANY WARRANTY; without even the implied warranty of
012:    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
013:    Lesser General Public License for more details.
014: 
015:    You should have received a copy of the GNU Lesser General Public
016:    License along with the GNU C Library; if not, write to the Free
017:    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
018:    02111-1307 USA.  */
019: 
020: #ifndef _SEARCH_H
021: #define _SEARCH_H 1
022: 
023: #include <features.h>
024: 
025: #define __need_size_t
026: #include <stddef.h>
027: 
028: __BEGIN_DECLS
029: 
030: #if defined __USE_SVID || defined __USE_XOPEN_EXTENDED
031: /* Prototype structure for a linked-list data structure.
032:    This is the type used by the `insque' and `remque' functions.  */
033: 
034: # ifdef __USE_GNU
035: struct qelem
036:   {
037:     struct qelem *q_forw;
038:     struct qelem *q_back;
039:     char q_data[1];
040:   };
041: # endif
042: 
043: 
044: /* Insert ELEM into a doubly-linked list, after PREV.  */
045: extern void insque (void *__elem, void *__prev) __THROW;
046: 
047: /* Unlink ELEM from the doubly-linked list that it is in.  */
048: extern void remque (void *__elem) __THROW;
049: #endif
050: 
051: 
052: /* For use with hsearch(3).  */
053: #ifndef __COMPAR_FN_T
054: # define __COMPAR_FN_T
055: typedef int (*__compar_fn_t) (__const void *, __const void *);
056: 
057: # ifdef __USE_GNU
058: typedef __compar_fn_t comparison_fn_t;
059: # endif
060: #endif
061: 
062: /* Action which shall be performed in the call the hsearch.  */
063: typedef enum
064:   {
065:     FIND,
066:     ENTER
067:   }
068: ACTION;
069: 
070: typedef struct entry
071:   {
072:     char *key;
073:     void *data;
074:   }
075: ENTRY;
076: 
077: /* Opaque type for internal use.  */
078: struct _ENTRY;
079: 
080: /* Family of hash table handling functions.  The functions also
081:    have reentrant counterparts ending with _r.  The non-reentrant
082:    functions all work on a signle internal hashing table.  */
083: 
084: /* Search for entry matching ITEM.key in internal hash table.  If
085:    ACTION is `FIND' return found entry or signal error by returning
086:    NULL.  If ACTION is `ENTER' replace existing data (if any) with
087:    ITEM.data.  */
088: extern ENTRY *hsearch (ENTRY __item, ACTION __action) __THROW;
089: 
090: /* Create a new hashing table which will at most contain NEL elements.  */
091: extern int hcreate (size_t __nel) __THROW;
092: 
093: /* Destroy current internal hashing table.  */
094: extern void hdestroy (void) __THROW;
095: 
096: #ifdef __USE_GNU
097: /* Data type for reentrant functions.  */
098: struct hsearch_data
099:   {
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 */
176: 

---

---

---