Software and Services, Portable Libraries  2019.Mar.01
A library for managing digital certificates
strsearch.hpp
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 #ifdef __cplusplus
23 extern "C" {
24 #endif
25 
26 
27  struct node_t
28  {
29  node_t();
30 
31  ~node_t();
32 
33  const void * key;
34 
35  struct node_t * left;
36 
37  struct node_t * right;
38 
39  unsigned int red;
40 
41  };
42 
43  typedef node_t * node;
44  typedef const struct node_t * const_node;
45 
46  /*
47  * See <http://www.opengroup.org/susv3xbd/search.h.html>,
48  * <http://www.opengroup.org/susv3xsh/tsearch.html>
49  * for details.
50  */
51 
52  typedef enum
53  {
54  preorder,
55  postorder,
56  endorder,
57  leaf
58  }
59  VISIT;
60 
61  typedef int (*strcompare_fn_t) (const void *, const void *);
62  typedef void (*straction_fn_t) (const node_t *, VISIT, int);
63  typedef void (*strfree_fn_t) (node_t *__nodep);
64 
65  /*
66  * Searches an element in the tree *VROOTP that compares equal to KEY.
67  * If one is found, it is returned. Otherwise, a new element equal to KEY
68  * is inserted in the tree and is returned.
69  */
70  void * strsearch(const void * key,
71  node_t * const * vrootp,
72  strcompare_fn_t compare);
73 
74  /*
75  * Searches an element in the tree *VROOTP that compares equal to KEY.
76  * If one is found, it is returned. Otherwise, nullptr is returned.
77  */
78  void * strfind(const void * key,
79  node_t * const * vrootp,
80  strcompare_fn_t compare);
81  /*
82  * Searches an element in the tree *VROOTP that compares equal to KEY.
83  * If one is found, it is removed from the tree, and its parent node is
84  * returned. Otherwise, nullptr is returned.
85  */
86  void * strdelete(const void * key,
87  node_t ** vrootp,
88  strcompare_fn_t compare);
89 
90  /*
91  * Perform a depth-first, left-to-right traversal of the tree VROOT.
92  *The ACTION function is called:
93  * - for non-leaf nodes: 3 times, before the left subtree traversal,
94  * after the left subtree traversal but before the right subtree traversal,
95  * and after the right subtree traversal,
96  * - for leaf nodes: once.
97  * The arguments passed to ACTION are:
98  * 1. the node; it can be casted to a 'const void * const *', i.e. into a
99  * pointer to the key,
100  * 2. an indicator which visit of the node this is,
101  * 3. the level of the node in the tree (0 for the root).
102  */
103  extern void strwalk (const node_t * vroot,
104  void (*action) (const node_t *, VISIT, int));
105 
106 #ifdef __cplusplus
107 }
108 #endif
109 
110 #endif /* _TSEARCH_H */