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