diff options
Diffstat (limited to 'include/search.h')
| -rw-r--r-- | include/search.h | 208 |
1 files changed, 142 insertions, 66 deletions
diff --git a/include/search.h b/include/search.h index fa3e5c083..2ffba697b 100644 --- a/include/search.h +++ b/include/search.h @@ -1,98 +1,174 @@ -/* Copyright (C) 1993 Ulrich Drepper +/* Declarations for System V style searching functions. + Copyright (C) 1995-1999, 2000 Free Software Foundation, Inc. + This file is part of the GNU C Library. -This file is intended to be included in the GNU C Library and the -Linux C Library. So the copyright notice will be: + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. -Copyright (C) 1993 Free Software Foundation, Inc. -This file is part of the GNU C Library. - -The GNU C Library is free software; you can redistribute it and/or -modify it under the terms of the GNU Library General Public License as -published by the Free Software Foundation; either version 2 of the -License, or (at your option) any later version. - -The GNU C Library is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU -Library General Public License for more details. - -You should have received a copy of the GNU Library General Public -License along with the GNU C Library; see the file COPYING.LIB. If -not, write to the Free Software Foundation, Inc., 675 Mass Ave, -Cambridge, MA 02139, USA. - - -For now the file can be distributed under the LGPL. */ + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA + 02111-1307 USA. */ #ifndef _SEARCH_H -#define _SEARCH_H +#define _SEARCH_H 1 #include <features.h> #define __need_size_t -#define __need_NULL #include <stddef.h> -/* Get __compar_fn_t from stdlib.h */ -#include <stdlib.h> - __BEGIN_DECLS -#if 0 -#ifndef __COMPAR_FN_T -#define __COMPAR_FN_T -typedef int (*__compar_fn_t) __P ((__const __ptr_t, __const __ptr_t)); -#endif +#if defined __USE_SVID || defined __USE_XOPEN_EXTENDED +/* Prototype structure for a linked-list data structure. + This is the type used by the `insque' and `remque' functions. */ + +# ifdef __USE_GNU +struct qelem + { + struct qelem *q_forw; + struct qelem *q_back; + char q_data[1]; + }; +# endif + + +/* Insert ELEM into a doubly-linked list, after PREV. */ +extern void insque (void *__elem, void *__prev) __THROW; + +/* Unlink ELEM from the doubly-linked list that it is in. */ +extern void remque (void *__elem) __THROW; #endif -/* for use with hsearch(3) */ -typedef struct entry { char *key; char *data; } ENTRY; -typedef enum { FIND, ENTER } ACTION; +/* For use with hsearch(3). */ +#ifndef __COMPAR_FN_T +# define __COMPAR_FN_T +typedef int (*__compar_fn_t) (__const void *, __const void *); + +# ifdef __USE_GNU +typedef __compar_fn_t comparison_fn_t; +# endif +#endif -extern ENTRY * hsearch __P((ENTRY __item, ACTION __action)); -extern int hcreate __P((unsigned __nel)); -extern void hdestroy __P((void)); +/* Action which shall be performed in the call the hsearch. */ +typedef enum + { + FIND, + ENTER + } +ACTION; + +typedef struct entry + { + char *key; + void *data; + } +ENTRY; + +/* Opaque type for internal use. */ +struct _ENTRY; + +/* Family of hash table handling functions. The functions also + have reentrant counterparts ending with _r. The non-reentrant + functions all work on a signle internal hashing table. */ + +/* Search for entry matching ITEM.key in internal hash table. If + ACTION is `FIND' return found entry or signal error by returning + NULL. If ACTION is `ENTER' replace existing data (if any) with + ITEM.data. */ +extern ENTRY *hsearch (ENTRY __item, ACTION __action) __THROW; + +/* Create a new hashing table which will at most contain NEL elements. */ +extern int hcreate (size_t __nel) __THROW; + +/* Destroy current internal hashing table. */ +extern void hdestroy (void) __THROW; + +#ifdef __USE_GNU +/* Data type for reentrant functions. */ +struct hsearch_data + { + struct _ENTRY *table; + unsigned int size; + unsigned int filled; + }; + +/* Reentrant versions which can handle multiple hashing tables at the + same time. */ +extern int hsearch_r (ENTRY __item, ACTION __action, ENTRY **__retval, + struct hsearch_data *__htab) __THROW; +extern int hcreate_r (size_t __nel, struct hsearch_data *__htab) __THROW; +extern void hdestroy_r (struct hsearch_data *__htab) __THROW; +#endif /* The tsearch routines are very interesting. They make many - * assumptions about the compiler. It assumpts that the first field - * in node must be the "key" field, which points to the datum. - * Everything depends on that. It is a very tricky stuff. H.J. - */ + assumptions about the compiler. It assumes that the first field + in node must be the "key" field, which points to the datum. + Everything depends on that. */ /* For tsearch */ -typedef enum { preorder, postorder, endorder, leaf } VISIT; +typedef enum +{ + preorder, + postorder, + endorder, + leaf +} +VISIT; + +/* Search for an entry matching the given KEY in the tree pointed to + by *ROOTP and insert a new element if not found. */ +extern void *tsearch (__const void *__key, void **__rootp, + __compar_fn_t __compar); + +/* Search for an entry matching the given KEY in the tree pointed to + by *ROOTP. If no matching entry is available return NULL. */ +extern void *tfind (__const void *__key, void *__const *__rootp, + __compar_fn_t __compar); + +/* Remove the element matching KEY from the tree pointed to by *ROOTP. */ +extern void *tdelete (__const void *__restrict __key, + void **__restrict __rootp, + __compar_fn_t __compar); -extern void *tsearch __P((__const void * __key, void **__rootp, - __compar_fn_t compar)); +#ifndef __ACTION_FN_T +# define __ACTION_FN_T +typedef void (*__action_fn_t) (__const void *__nodep, VISIT __value, + int __level); +#endif -extern void *tfind __P((__const void * __key, void * __const * __rootp, - __compar_fn_t compar)); +/* Walk through the whole tree and call the ACTION callback for every node + or leaf. */ +extern void twalk (__const void *__root, __action_fn_t __action); -extern void *tdelete __P((__const void * __key, void ** __rootp, - __compar_fn_t compar)); +#ifdef __USE_GNU +/* Callback type for function to free a tree node. If the keys are atomic + data this function should do nothing. */ +typedef void (*__free_fn_t) (void *__nodep); -#ifndef __ACTION_FN_T -#define __ACTION_FN_T -/* FYI, the first argument should be a pointer to "key". - * Please read the man page for details. - */ -typedef void (*__action_fn_t) __P((__const void *__nodep, - __const VISIT __value, - __const int __level)); +/* Destroy the whole tree, call FREEFCT for each node or leaf. */ +extern void tdestroy (void *__root, __free_fn_t __freefct); #endif -extern void twalk __P((__const void * __root, __action_fn_t action)); - -extern void * lfind __P((__const void * __key, __const void * __base, - size_t * __nmemb, size_t __size, - __compar_fn_t __compar)); +/* Perform linear search for KEY by comparing by COMPAR in an array + [BASE,BASE+NMEMB*SIZE). */ +extern void *lfind (__const void *__key, __const void *__base, + size_t *__nmemb, size_t __size, __compar_fn_t __compar); -extern void * lsearch __P((__const void * __key, __const void * __base, - size_t * __nmemb, size_t __size, - __compar_fn_t __compar)); +/* Perform linear search for KEY by comparing by COMPAR function in + array [BASE,BASE+NMEMB*SIZE) and insert entry if not found. */ +extern void *lsearch (__const void *__key, void *__base, + size_t *__nmemb, size_t __size, __compar_fn_t __compar); __END_DECLS |