1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
|
/*
* Copyright (c) International Business Machines Corp., 2014
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
/*! @file tree_iter.h
* @brief Binary Tree Iterator
* @details For example,
* @code
* ...
* data_t * d;
* ...
* tree_iter_t it;
* tree_iter_init(&it, &t, TI_FLAG_DFT_FWD);
* ...
* tree_for_each(&it, d, node) {
* printf("depth first (FWD) i[%d] f[%f]\n", d->i, d->f);
* }
* ...
* @endcode
* @author Shaun Wetzstein <shaun@us.ibm.com>
* @date 2010-2012
*/
#ifndef __TREE_ITER_H__
#define __TREE_ITER_H__
#include <stdint.h>
#include <stdbool.h>
#include "builtin.h"
#include "compare.h"
#include "type.h"
#include "tree.h"
/* ======================================================== */
typedef struct tree_iter tree_iter_t; //!< Alias for the @em tree_iter class
/*!
* @brief tree iterator
* @details Binary tree container iterator
*/
struct tree_iter {
tree_t *tree; //!< Tree container to iterate
tree_node_t *node; //!< Current position in the iteration
tree_node_t *safe;
uint32_t flags; //!< Iterator configuration flags
};
/* ======================================================== */
#define TI_FLAG_NONE 0x00000000 //!< All flag mask
#define TI_FLAG_FWD 0x00000001 //!< Depth-first-traversal Forward (FWD) flag mask
#define TI_FLAG_BWD 0x00000002 //!< Depth-first-traversal Backward (BWD) flag mask
#define TI_FLAG_MASK 0x00000003 //!< Depth-first-traversal All flag mask
/*!
* @brief Initializes an @em tree_iter iterator object
* @memberof tree_iter
* @param self [in] tree_iter object @em self pointer
* @param tree [in] tree container object to iterate
* @param flags [in] iterator configuration flags
* @return None
* @throws UNEXPECTED if @em self pointer is NULL
* @throws UNEXPECTED if @em tree pointer is NULL
*/
extern int tree_iter_init(tree_iter_t * self, tree_t * tree, uint32_t flags)
/*! @cond */
__nonnull((1, 2)) /*! @endcond */ ;
/*!
* @brief Resets an @em tree iterator object
* @memberof tree_iter
* @param self [in] tree_iter object @em self pointer
* @return None
* @throws UNEXPECTED if @em self pointer is NULL
*/
extern int tree_iter_clear(tree_iter_t * self)
/*! @cond */
__nonnull((1)) /*! @endcond */ ;
/*!
* @brief Return a pointer to a @em tree_node element at the current
* iterator position
* @memberof tree_iter
* @param self [in] tree_iter object @em self pointer
* @return non-NULL on success, NULL otherwise
* @throws UNEXPECTED if @em self pointer is NULL
*/
extern tree_node_t *tree_iter_elem(tree_iter_t * self)
/*! @cond */
__nonnull((1)) /*! @endcond */ ;
/*!
* @fn tree_node_t * tree_iter_inc(tree_iter_t * self, size_t count = 1)
* @brief Increment the position of an @em tree iterator
* @details If the second (2nd) parameter is omitted, the iterator is
* incremented by one (1) position.
* @details For example,
* @code
* ...
* tree_t l;
* tree_init(&l);
* ...
* tree_iter_t it;
* tree_iter_init(&it, &l, LI_FLAG_FWD);
* ...
* tree_iter_inc(&it);
* ...
* @endcode
* @memberof tree_iter
* @param self [in] tree_iter object @em self pointer
* @param count [in] Number of positions to increment (optional)
* @return None
* @throws UNEXPECTED if @em self pointer is NULL
*/
#define tree_iter_inc(...) STRCAT(tree_iter_inc, NARGS(__VA_ARGS__))(__VA_ARGS__)
extern tree_node_t *tree_iter_inc1(tree_iter_t * self)
/*! @cond */
__nonnull((1)) /*! @endcond */ ;
extern tree_node_t *tree_iter_inc2(tree_iter_t * self, size_t count)
/*! @cond */
__nonnull((1)) /*! @endcond */ ;
/*!
* @fn tree_node_td * tree_iter_dec(tree_iter_t * self, size_t count = 1)
* @brief decrement the position of an @em list iterator
* @note If the second (2nd) parameter is omitted, the iterator is decremented
* by one (1) position.
* @details For example,
* @code
* ...
* tree_t l;
* tree_init(&l);
* ...
* tree_iter_t it;
* tree_iter_init(&it, &l, LI_FLAG_FWD);
* ...
* tree_iter_dec(&it, 3);
* ...
* @endcode
* @memberof tree_iter
* @param self [in] tree_iter object @em self pointer
* @param count [in] Number of positions to decrement (optional)
* @return None
* @throws UNEXPECTED if @em self pointer is NULL
*/
#define tree_iter_dec(...) STRCAT(tree_iter_dec, NARGS(__VA_ARGS__))(__VA_ARGS__)
extern tree_node_t *tree_iter_dec1(tree_iter_t * self)
/*! @cond */
__nonnull((1)) /*! @endcond */ ;
extern tree_node_t *tree_iter_dec2(tree_iter_t * self, size_t count)
/*! @cond */
__nonnull((1)) /*! @endcond */ ;
/*!
* @def tree_for_each(it, i, m)
* @hideinitializer
* @brief Tree for-each algorithm
* @param it [in] Tree iterator object
* @param i [in] Tree element variable
* @param m [in] Member name
*/
#define tree_for_each(it, i, m) \
for (tree_iter_clear(it), i = container_of_var(tree_iter_elem(it), i, m); \
tree_iter_elem(it) != NULL; \
i = container_of_var(tree_iter_inc(it), i, m))
/* ======================================================== */
#endif /* __TREE_ITER_H__ */
|
