|
Packit |
6c4009 |
/* Declarations for System V style searching functions.
|
|
Packit |
6c4009 |
Copyright (C) 1995-2018 Free Software Foundation, Inc.
|
|
Packit |
6c4009 |
This file is part of the GNU C Library.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The GNU C Library is free software; you can redistribute it and/or
|
|
Packit |
6c4009 |
modify it under the terms of the GNU Lesser General Public
|
|
Packit |
6c4009 |
License as published by the Free Software Foundation; either
|
|
Packit |
6c4009 |
version 2.1 of the License, or (at your option) any later version.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The GNU C Library is distributed in the hope that it will be useful,
|
|
Packit |
6c4009 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
6c4009 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit |
6c4009 |
Lesser General Public License for more details.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
You should have received a copy of the GNU Lesser General Public
|
|
Packit |
6c4009 |
License along with the GNU C Library; if not, see
|
|
Packit |
6c4009 |
<http://www.gnu.org/licenses/>. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifndef _SEARCH_H
|
|
Packit |
6c4009 |
#define _SEARCH_H 1
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <features.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#define __need_size_t
|
|
Packit |
6c4009 |
#include <stddef.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
__BEGIN_DECLS
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#if defined __USE_MISC || defined __USE_XOPEN_EXTENDED
|
|
Packit |
6c4009 |
/* Prototype structure for a linked-list data structure.
|
|
Packit |
6c4009 |
This is the type used by the `insque' and `remque' functions. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
# ifdef __USE_GNU
|
|
Packit |
6c4009 |
struct qelem
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct qelem *q_forw;
|
|
Packit |
6c4009 |
struct qelem *q_back;
|
|
Packit |
6c4009 |
char q_data[1];
|
|
Packit |
6c4009 |
};
|
|
Packit |
6c4009 |
# endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Insert ELEM into a doubly-linked list, after PREV. */
|
|
Packit |
6c4009 |
extern void insque (void *__elem, void *__prev) __THROW;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Unlink ELEM from the doubly-linked list that it is in. */
|
|
Packit |
6c4009 |
extern void remque (void *__elem) __THROW;
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* For use with hsearch(3). */
|
|
Packit |
6c4009 |
#ifndef __COMPAR_FN_T
|
|
Packit |
6c4009 |
# define __COMPAR_FN_T
|
|
Packit |
6c4009 |
typedef int (*__compar_fn_t) (const void *, const void *);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
# ifdef __USE_GNU
|
|
Packit |
6c4009 |
typedef __compar_fn_t comparison_fn_t;
|
|
Packit |
6c4009 |
# endif
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Action which shall be performed in the call the hsearch. */
|
|
Packit |
6c4009 |
typedef enum
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
FIND,
|
|
Packit |
6c4009 |
ENTER
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
ACTION;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
typedef struct entry
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
char *key;
|
|
Packit |
6c4009 |
void *data;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
ENTRY;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Opaque type for internal use. */
|
|
Packit |
6c4009 |
struct _ENTRY;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Family of hash table handling functions. The functions also
|
|
Packit |
6c4009 |
have reentrant counterparts ending with _r. The non-reentrant
|
|
Packit |
6c4009 |
functions all work on a signle internal hashing table. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Search for entry matching ITEM.key in internal hash table. If
|
|
Packit |
6c4009 |
ACTION is `FIND' return found entry or signal error by returning
|
|
Packit |
6c4009 |
NULL. If ACTION is `ENTER' replace existing data (if any) with
|
|
Packit |
6c4009 |
ITEM.data. */
|
|
Packit |
6c4009 |
extern ENTRY *hsearch (ENTRY __item, ACTION __action) __THROW;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Create a new hashing table which will at most contain NEL elements. */
|
|
Packit |
6c4009 |
extern int hcreate (size_t __nel) __THROW;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Destroy current internal hashing table. */
|
|
Packit |
6c4009 |
extern void hdestroy (void) __THROW;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef __USE_GNU
|
|
Packit |
6c4009 |
/* Data type for reentrant functions. */
|
|
Packit |
6c4009 |
struct hsearch_data
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct _ENTRY *table;
|
|
Packit |
6c4009 |
unsigned int size;
|
|
Packit |
6c4009 |
unsigned int filled;
|
|
Packit |
6c4009 |
};
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Reentrant versions which can handle multiple hashing tables at the
|
|
Packit |
6c4009 |
same time. */
|
|
Packit |
6c4009 |
extern int hsearch_r (ENTRY __item, ACTION __action, ENTRY **__retval,
|
|
Packit |
6c4009 |
struct hsearch_data *__htab) __THROW;
|
|
Packit |
6c4009 |
extern int hcreate_r (size_t __nel, struct hsearch_data *__htab) __THROW;
|
|
Packit |
6c4009 |
extern void hdestroy_r (struct hsearch_data *__htab) __THROW;
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* The tsearch routines are very interesting. They make many
|
|
Packit |
6c4009 |
assumptions about the compiler. It assumes that the first field
|
|
Packit |
6c4009 |
in node must be the "key" field, which points to the datum.
|
|
Packit |
6c4009 |
Everything depends on that. */
|
|
Packit |
6c4009 |
/* For tsearch */
|
|
Packit |
6c4009 |
typedef enum
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
preorder,
|
|
Packit |
6c4009 |
postorder,
|
|
Packit |
6c4009 |
endorder,
|
|
Packit |
6c4009 |
leaf
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
VISIT;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Search for an entry matching the given KEY in the tree pointed to
|
|
Packit |
6c4009 |
by *ROOTP and insert a new element if not found. */
|
|
Packit |
6c4009 |
extern void *tsearch (const void *__key, void **__rootp,
|
|
Packit |
6c4009 |
__compar_fn_t __compar);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Search for an entry matching the given KEY in the tree pointed to
|
|
Packit |
6c4009 |
by *ROOTP. If no matching entry is available return NULL. */
|
|
Packit |
6c4009 |
extern void *tfind (const void *__key, void *const *__rootp,
|
|
Packit |
6c4009 |
__compar_fn_t __compar);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Remove the element matching KEY from the tree pointed to by *ROOTP. */
|
|
Packit |
6c4009 |
extern void *tdelete (const void *__restrict __key,
|
|
Packit |
6c4009 |
void **__restrict __rootp,
|
|
Packit |
6c4009 |
__compar_fn_t __compar);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifndef __ACTION_FN_T
|
|
Packit |
6c4009 |
# define __ACTION_FN_T
|
|
Packit |
6c4009 |
typedef void (*__action_fn_t) (const void *__nodep, VISIT __value,
|
|
Packit |
6c4009 |
int __level);
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Walk through the whole tree and call the ACTION callback for every node
|
|
Packit |
6c4009 |
or leaf. */
|
|
Packit |
6c4009 |
extern void twalk (const void *__root, __action_fn_t __action);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef __USE_GNU
|
|
Packit |
6c4009 |
/* Callback type for function to free a tree node. If the keys are atomic
|
|
Packit |
6c4009 |
data this function should do nothing. */
|
|
Packit |
6c4009 |
typedef void (*__free_fn_t) (void *__nodep);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Destroy the whole tree, call FREEFCT for each node or leaf. */
|
|
Packit |
6c4009 |
extern void tdestroy (void *__root, __free_fn_t __freefct);
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Perform linear search for KEY by comparing by COMPAR in an array
|
|
Packit |
6c4009 |
[BASE,BASE+NMEMB*SIZE). */
|
|
Packit |
6c4009 |
extern void *lfind (const void *__key, const void *__base,
|
|
Packit |
6c4009 |
size_t *__nmemb, size_t __size, __compar_fn_t __compar);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Perform linear search for KEY by comparing by COMPAR function in
|
|
Packit |
6c4009 |
array [BASE,BASE+NMEMB*SIZE) and insert entry if not found. */
|
|
Packit |
6c4009 |
extern void *lsearch (const void *__key, void *__base,
|
|
Packit |
6c4009 |
size_t *__nmemb, size_t __size, __compar_fn_t __compar);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
__END_DECLS
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#endif /* search.h */
|