lib/search_.h

   1 /* Tree search.
   2
   3    Copyright (C) 1995, 1996, 1997, 1998, 1999, 2000, 2003 Free
   4    Software Foundation, Inc.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software Foundation,
  18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 /* For use with hsearch(3).  */
  21 #ifndef __COMPAR_FN_T
  22 # define __COMPAR_FN_T
  23 typedef int (*__compar_fn_t) (const void *, const void *);
  24
  25 # ifdef __USE_GNU
  26 typedef __compar_fn_t comparison_fn_t;
  27 # endif
  28 #endif
  29
  30 /* The tsearch routines are very interesting. They make many
  31    assumptions about the compiler.  It assumes that the first field
  32    in node must be the "key" field, which points to the datum.
  33    Everything depends on that.  */
  34 /* For tsearch */
  35 typedef enum
  36 {
  37   preorder,
  38   postorder,
  39   endorder,
  40   leaf
  41 }
  42 VISIT;
  43
  44 /* GCC 2.95 and later have "__restrict"; C99 compilers have
  45    "restrict", and "configure" may have defined "restrict".  */
  46 #ifndef __restrict
  47 # if ! (2 < __GNUC__ || (2 == __GNUC__ && 95 <= __GNUC_MINOR__))
  48 #  if defined restrict || 199901L <= __STDC_VERSION__
  49 #   define __restrict restrict
  50 #  else
  51 #   define __restrict
  52 #  endif
  53 # endif
  54 #endif
  55
  56 /* Search for an entry matching the given KEY in the tree pointed to
  57    by *ROOTP and insert a new element if not found.  */
  58 extern void *tsearch (const void *__key, void **__rootp,
  59                       __compar_fn_t __compar);
  60
  61 /* Search for an entry matching the given KEY in the tree pointed to
  62    by *ROOTP.  If no matching entry is available return NULL.  */
  63 extern void *tfind (const void *__key, void *const *__rootp,
  64                     __compar_fn_t __compar);
  65
  66 /* Remove the element matching KEY from the tree pointed to by *ROOTP.  */
  67 extern void *tdelete (const void *__restrict __key,
  68                       void **__restrict __rootp,
  69                       __compar_fn_t __compar);
  70
  71 #ifndef __ACTION_FN_T
  72 # define __ACTION_FN_T
  73 typedef void (*__action_fn_t) (const void *__nodep, VISIT __value,
  74                                int __level);
  75 #endif
  76
  77 /* Walk through the whole tree and call the ACTION callback for every node
  78    or leaf.  */
  79 extern void twalk (const void *__root, __action_fn_t __action);
  80
  81 #ifdef __USE_GNU
  82 /* Callback type for function to free a tree node.  If the keys are atomic
  83    data this function should do nothing.  */
  84 typedef void (*__free_fn_t) (void *__nodep);
  85
  86 /* Destroy the whole tree, call FREEFCT for each node or leaf.  */
  87 extern void tdestroy (void *__root, __free_fn_t __freefct);
  88 #endif