Back to index

glibc  2.9
search.h
Go to the documentation of this file.
00001 /* Declarations for System V style searching functions.
00002    Copyright (C) 1995-1999, 2000 Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004 
00005    The GNU C Library is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Lesser General Public
00007    License as published by the Free Software Foundation; either
00008    version 2.1 of the License, or (at your option) any later version.
00009 
00010    The GNU C Library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Lesser General Public License for more details.
00014 
00015    You should have received a copy of the GNU Lesser General Public
00016    License along with the GNU C Library; if not, write to the Free
00017    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00018    02111-1307 USA.  */
00019 
00020 #ifndef _SEARCH_H
00021 #define       _SEARCH_H 1
00022 
00023 #include <features.h>
00024 
00025 #define __need_size_t
00026 #include <stddef.h>
00027 
00028 __BEGIN_DECLS
00029 
00030 #if defined __USE_SVID || defined __USE_XOPEN_EXTENDED
00031 /* Prototype structure for a linked-list data structure.
00032    This is the type used by the `insque' and `remque' functions.  */
00033 
00034 # ifdef __USE_GNU
00035 struct qelem
00036   {
00037     struct qelem *q_forw;
00038     struct qelem *q_back;
00039     char q_data[1];
00040   };
00041 # endif
00042 
00043 
00044 /* Insert ELEM into a doubly-linked list, after PREV.  */
00045 extern void insque (void *__elem, void *__prev) __THROW;
00046 
00047 /* Unlink ELEM from the doubly-linked list that it is in.  */
00048 extern void remque (void *__elem) __THROW;
00049 #endif
00050 
00051 
00052 /* For use with hsearch(3).  */
00053 #ifndef __COMPAR_FN_T
00054 # define __COMPAR_FN_T
00055 typedef int (*__compar_fn_t) (__const void *, __const void *);
00056 
00057 # ifdef       __USE_GNU
00058 typedef __compar_fn_t comparison_fn_t;
00059 # endif
00060 #endif
00061 
00062 /* Action which shall be performed in the call the hsearch.  */
00063 typedef enum
00064   {
00065     FIND,
00066     ENTER
00067   }
00068 ACTION;
00069 
00070 typedef struct entry
00071   {
00072     char *key;
00073     void *data;
00074   }
00075 ENTRY;
00076 
00077 /* Opaque type for internal use.  */
00078 struct _ENTRY;
00079 
00080 /* Family of hash table handling functions.  The functions also
00081    have reentrant counterparts ending with _r.  The non-reentrant
00082    functions all work on a signle internal hashing table.  */
00083 
00084 /* Search for entry matching ITEM.key in internal hash table.  If
00085    ACTION is `FIND' return found entry or signal error by returning
00086    NULL.  If ACTION is `ENTER' replace existing data (if any) with
00087    ITEM.data.  */
00088 extern ENTRY *hsearch (ENTRY __item, ACTION __action) __THROW;
00089 
00090 /* Create a new hashing table which will at most contain NEL elements.  */
00091 extern int hcreate (size_t __nel) __THROW;
00092 
00093 /* Destroy current internal hashing table.  */
00094 extern void hdestroy (void) __THROW;
00095 
00096 #ifdef __USE_GNU
00097 /* Data type for reentrant functions.  */
00098 struct hsearch_data
00099   {
00100     struct _ENTRY *table;
00101     unsigned int size;
00102     unsigned int filled;
00103   };
00104 
00105 /* Reentrant versions which can handle multiple hashing tables at the
00106    same time.  */
00107 extern int hsearch_r (ENTRY __item, ACTION __action, ENTRY **__retval,
00108                     struct hsearch_data *__htab) __THROW;
00109 extern int hcreate_r (size_t __nel, struct hsearch_data *__htab) __THROW;
00110 extern void hdestroy_r (struct hsearch_data *__htab) __THROW;
00111 #endif
00112 
00113 
00114 /* The tsearch routines are very interesting. They make many
00115    assumptions about the compiler.  It assumes that the first field
00116    in node must be the "key" field, which points to the datum.
00117    Everything depends on that.  */
00118 /* For tsearch */
00119 typedef enum
00120 {
00121   preorder,
00122   postorder,
00123   endorder,
00124   leaf
00125 }
00126 VISIT;
00127 
00128 /* Search for an entry matching the given KEY in the tree pointed to
00129    by *ROOTP and insert a new element if not found.  */
00130 extern void *tsearch (__const void *__key, void **__rootp,
00131                     __compar_fn_t __compar);
00132 
00133 /* Search for an entry matching the given KEY in the tree pointed to
00134    by *ROOTP.  If no matching entry is available return NULL.  */
00135 extern void *tfind (__const void *__key, void *__const *__rootp,
00136                   __compar_fn_t __compar);
00137 
00138 /* Remove the element matching KEY from the tree pointed to by *ROOTP.  */
00139 extern void *tdelete (__const void *__restrict __key,
00140                     void **__restrict __rootp,
00141                     __compar_fn_t __compar);
00142 
00143 #ifndef __ACTION_FN_T
00144 # define __ACTION_FN_T
00145 typedef void (*__action_fn_t) (__const void *__nodep, VISIT __value,
00146                             int __level);
00147 #endif
00148 
00149 /* Walk through the whole tree and call the ACTION callback for every node
00150    or leaf.  */
00151 extern void twalk (__const void *__root, __action_fn_t __action);
00152 
00153 #ifdef __USE_GNU
00154 /* Callback type for function to free a tree node.  If the keys are atomic
00155    data this function should do nothing.  */
00156 typedef void (*__free_fn_t) (void *__nodep);
00157 
00158 /* Destroy the whole tree, call FREEFCT for each node or leaf.  */
00159 extern void tdestroy (void *__root, __free_fn_t __freefct);
00160 #endif
00161 
00162 
00163 /* Perform linear search for KEY by comparing by COMPAR in an array
00164    [BASE,BASE+NMEMB*SIZE).  */
00165 extern void *lfind (__const void *__key, __const void *__base,
00166                   size_t *__nmemb, size_t __size, __compar_fn_t __compar);
00167 
00168 /* Perform linear search for KEY by comparing by COMPAR function in
00169    array [BASE,BASE+NMEMB*SIZE) and insert entry if not found.  */
00170 extern void *lsearch (__const void *__key, void *__base,
00171                     size_t *__nmemb, size_t __size, __compar_fn_t __compar);
00172 
00173 __END_DECLS
00174 
00175 #endif /* search.h */