Blame include/search.h

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