1: /* Declarations for System V style searching functions.
    2:    Copyright (C) 1995-1999, 2000 Free Software Foundation, Inc.
    3:    This file is part of the GNU C Library.
    4: 
    5:    The GNU C Library is free software; you can redistribute it and/or
    6:    modify it under the terms of the GNU Lesser General Public
    7:    License as published by the Free Software Foundation; either
    8:    version 2.1 of the License, or (at your option) any later version.
    9: 
   10:    The GNU C Library is distributed in the hope that it will be useful,
   11:    but WITHOUT ANY WARRANTY; without even the implied warranty of
   12:    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   13:    Lesser General Public License for more details.
   14: 
   15:    You should have received a copy of the GNU Lesser General Public
   16:    License along with the GNU C Library; if not, write to the Free
   17:    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   18:    02111-1307 USA.  */
   19: 
   20: #ifndef _SEARCH_H
   21: #define _SEARCH_H 1
   22: 
   23: #include <features.h>
   24: 
   25: #define __need_size_t
   26: #include <stddef.h>
   27: 
   28: __BEGIN_DECLS
   29: 
   30: #if defined __USE_SVID || defined __USE_XOPEN_EXTENDED
   31: /* Prototype structure for a linked-list data structure.
   32:    This is the type used by the `insque' and `remque' functions.  */
   33: 
   34: # ifdef __USE_GNU
   35: struct qelem
   36:   {
   37:     struct qelem *q_forw;
   38:     struct qelem *q_back;
   39:     char q_data[1];
   40:   };
   41: # endif
   42: 
   43: 
   44: /* Insert ELEM into a doubly-linked list, after PREV.  */
   45: extern void insque (void *__elem, void *__prev) __THROW;
   46: 
   47: /* Unlink ELEM from the doubly-linked list that it is in.  */
   48: extern void remque (void *__elem) __THROW;
   49: #endif
   50: 
   51: 
   52: /* For use with hsearch(3).  */
   53: #ifndef __COMPAR_FN_T
   54: # define __COMPAR_FN_T
   55: typedef int (*__compar_fn_t) (__const void *, __const void *);
   56: 
   57: # ifdef __USE_GNU
   58: typedef __compar_fn_t comparison_fn_t;
   59: # endif
   60: #endif
   61: 
   62: /* Action which shall be performed in the call the hsearch.  */
   63: typedef enum
   64:   {
   65:     FIND,
   66:     ENTER
   67:   }
   68: ACTION;
   69: 
   70: typedef struct entry
   71:   {
   72:     char *key;
   73:     void *data;
   74:   }
   75: ENTRY;
   76: 
   77: /* Opaque type for internal use.  */
   78: struct _ENTRY;
   79: 
   80: /* Family of hash table handling functions.  The functions also
   81:    have reentrant counterparts ending with _r.  The non-reentrant
   82:    functions all work on a signle internal hashing table.  */
   83: 
   84: /* Search for entry matching ITEM.key in internal hash table.  If
   85:    ACTION is `FIND' return found entry or signal error by returning
   86:    NULL.  If ACTION is `ENTER' replace existing data (if any) with
   87:    ITEM.data.  */
   88: extern ENTRY *hsearch (ENTRY __item, ACTION __action) __THROW;
   89: 
   90: /* Create a new hashing table which will at most contain NEL elements.  */
   91: extern int hcreate (size_t __nel) __THROW;
   92: 
   93: /* Destroy current internal hashing table.  */
   94: extern void hdestroy (void) __THROW;
   95: 
   96: #ifdef __USE_GNU
   97: /* Data type for reentrant functions.  */
   98: struct hsearch_data
   99:   {
  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 */