gettext-runtime/intl/tsearch.h

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