lib/tsearch.h

   1 /* Binary tree data structure.
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  17
  18 #ifndef _TSEARCH_H
  19 #define _TSEARCH_H
  20
  21 #if HAVE_TSEARCH
  22
  23 /* Get tseach(), tfind(), tdelete(), twalk() declarations.  */
  24 #include <search.h>
  25
  26 #else
  27
  28 #ifdef __cplusplus
  29 extern "C" {
  30 #endif
  31
  32 /* See <http://www.opengroup.org/susv3xbd/search.h.html>,
  33        <http://www.opengroup.org/susv3xsh/tsearch.html>
  34    for details.  */
  35
  36 typedef enum
  37 {
  38   preorder,
  39   postorder,
  40   endorder,
  41   leaf
  42 }
  43 VISIT;
  44
  45 /* Searches an element in the tree *VROOTP that compares equal to KEY.
  46    If one is found, it is returned.  Otherwise, a new element equal to KEY
  47    is inserted in the tree and is returned.  */
  48 extern void * tsearch (const void *key, void **vrootp,
  49                        int (*compar) (const void *, const void *));
  50
  51 /* Searches an element in the tree *VROOTP that compares equal to KEY.
  52    If one is found, it is returned.  Otherwise, NULL is returned.  */
  53 extern void * tfind (const void *key, void *const *vrootp,
  54                      int (*compar) (const void *, const void *));
  55
  56 /* Searches an element in the tree *VROOTP that compares equal to KEY.
  57    If one is found, it is removed from the tree, and its parent node is
  58    returned.  Otherwise, NULL is returned.  */
  59 extern void * tdelete (const void *key, void **vrootp,
  60                        int (*compar) (const void *, const void *));
  61
  62 /* Perform a depth-first, left-to-right traversal of the tree VROOT.
  63    The ACTION function is called:
  64      - for non-leaf nodes: 3 times, before the left subtree traversal,
  65        after the left subtree traversal but before the right subtree traversal,
  66        and after the right subtree traversal,
  67      - for leaf nodes: once.
  68    The arguments passed to ACTION are:
  69      1. the node; it can be casted to a 'const void * const *', i.e. into a
  70         pointer to the key,
  71      2. an indicator which visit of the node this is,
  72      3. the level of the node in the tree (0 for the root).  */
  73 extern void twalk (const void *vroot,
  74                    void (*action) (const void *, VISIT, int));
  75
  76 #ifdef __cplusplus
  77 }
  78 #endif
  79
  80 #endif
  81
  82 #endif /* _TSEARCH_H */