root/lang/c/rbtree/branches/bst_inherit_impl/test_bstree.c @ 5251

Revision 5251, 7.9 kB (checked in by mrkn, 6 years ago)

lang/c/rbtree/branches/bst_inherit_impl/test_bstree.c (dfs_index): correct index order.

  • Property svn:keywords set to Id
Line 
1/* $Id$
2 *
3 * Copyright (C) 2008 Kenta Murata.
4 *
5 * This file is part of rbtree.
6 *
7 * rbtree is free software: you can redistribute it and/or modify it
8 * under the terms of the GNU Lesser General Public License as
9 * published by the Free Software Foundation, either version 3 of the
10 * License, or (at your option) any later version.
11 *
12 * rbtree is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with rbtree.  If not, see
19 * <http://www.gnu.org/licenses/>.
20 */
21/* gcc -g -Wall -DNOT_RUBY -o test_rbtree test_rbtree.c -lcunit */
22/* gcc -g -Wall -I/usr/lib/ruby/1.8/i486-linux/ -o test_rbtree
23   test_rbtree.c -lcunit -lruby1.8 */
24
25#include "bstree.h"
26
27#include <CUnit/CUnit.h>
28#include <CUnit/Basic.h>
29
30#include <stdio.h>
31#include <stdlib.h>
32
33#define ALLOC_NODE() \
34  (struct bstree_node*)malloc(sizeof(struct bstree_node))
35
36static inline void
37print_intnode(struct bstree_node const* node)
38{
39  printf("<%p:%llu, %s, %p, %p, %p>",
40         node, BSTREE_NODE_VALUE(node), BSTREE_NODE_PARENT(node),
41         BSTREE_NODE_LEFT(node), BSTREE_NODE_RIGHT(node));
42}
43
44static inline void
45println_strnode(struct bstree_node const* node)
46{
47  print_strnode(node);
48  putchar('\n');
49}
50
51/*                      index---.   ,---value
52 *                             ( 5: 5)
53 *                ,---------------^---------------.
54 *             ( 2: 2)                         ( 9: 9)
55 *        ,-------^-------.               ,-------^-------.
56 *     ( 1: 1)         ( 3: 2)         ( 7: 7)         (11:11)
57 *    ,---^---.       ,---^---.       ,---^---.       ,---^---.
58 * ( 0: 0)   (:)     (:)   ( 4: 2) ( 6: 6) ( 8: 8) (10:10)   (:)
59 *  ,-^-.                   ,-^-.   ,-^-.   ,-^-.   ,-^-.
60 * (:) (:)                 (:) (:) (:) (:) (:) (:) (:) (:)
61 *       '---null node
62 */
63
64static struct bstree_node* nodes[12] = { 0, };
65static struct bstree_node* root = 0;
66static int dfs_index[12] = { 5, 2, 1, 0, 3, 4, 9, 7, 6, 8, 11, 10 };
67static int bfs_index[12] = { 5, 2, 9, 1, 3, 7, 11, 0, 4, 6, 8, 10 };
68
69static int
70suite_rbtree_init(void)
71{
72  int i;
73
74  for (i = 0; i < 12; ++i) {
75    nodes[i] = ALLOC_NODE();
76    BSTREE_NODE_PARENT(nodes[i]) = 0;
77    BSTREE_NODE_LEFT(nodes[i]) = 0;
78    BSTREE_NODE_RIGHT(nodes[i]) = 0;
79    BSTREE_NODE_VALUE(nodes[i]) = BSTREE_DATA(i);
80  }
81
82  for (i = 2; i < 3; ++i) {
83    BSTREE_VALUE(nodes[i]) = 2;
84  }
85
86  BSTREE_NODE_PARENT(nodes[0]) = nodes[1];
87  BSTREE_NODE_LEFT(nodes[1]) = nodes[0];
88
89  BSTREE_NODE_PARENT(nodes[1]) = nodes[2];
90  BSTREE_NODE_LEFT(nodes[2]) = nodes[1];
91
92  BSTREE_NODE_PARENT(nodes[2]) = nodes[5];
93  BSTREE_NODE_LEFT(nodes[5]) = nodes[2];
94
95  BSTREE_NODE_PARENT(nodes[3]) = nodes[2];
96  BSTREE_NODE_RIGHT(nodes[2]) = nodes[3];
97
98  BSTREE_NODE_PARENT(nodes[4]) = nodes[3];
99  BSTREE_NODE_RIGHT(nodes[3]) = nodes[4];
100
101  root = nodes[5];
102
103  BSTREE_NODE_PARENT(nodes[6]) = nodes[7];
104  BSTREE_NODE_LEFT(nodes[7]) = nodes[6];
105
106  BSTREE_NODE_PARENT(nodes[7]) = nodes[9];
107  BSTREE_NODE_LEFT(nodes[9]) = nodes[7];
108
109  BSTREE_NODE_PARENT(nodes[8]) = nodes[7];
110  BSTREE_NODE_RIGHT(nodes[7]) = nodes[8];
111
112  BSTREE_NODE_PARENT(nodes[9]) = nodes[5];
113  BSTREE_NODE_RIGHT(nodes[5]) = nodes[9];
114
115  BSTREE_NODE_PARENT(nodes[10]) = nodes[11];
116  BSTREE_NODE_RIGHT(nodes[11]) = nodes[10];
117
118  BSTREE_NODE_PARENT(nodes[11]) = nodes[9];
119  BSTREE_NODE_RIGHT(nodes[9]) = nodes[11];
120
121  return 0;
122}
123
124static int
125suite_rbtree_clean(void)
126{
127  int i;
128  for (i = 0; i < 12; ++i) {
129    free(nodes[i]);
130  }
131
132  return 0;
133}
134
135static void
136test_lookup_lower_bound(void)
137{
138  CU_ASSERT_EQUAL(nodes[2],
139                  bstree_node_lookup_lower_bound(
140                    root, bstree_intcmp, 0, 2));
141  CU_ASSERT_EQUAL(nodes[5],
142                  bstree_node_lookup_lower_bound(
143                    root, bstree_intcmp, 0, 5));
144  CU_ASSERT_EQUAL(nodes[10],
145                  bstree_node_lookup_lower_bound(
146                    root, bstree_intcmp, 0, 10));
147}
148
149static void
150test_lookup_upper_bound(void)
151{
152  CU_ASSERT_EQUAL(nodes[4],
153                  bstree_node_lookup_upper_bound(
154                    root, bstree_intcmp, 0, 2));
155  CU_ASSERT_EQUAL(nodes[5],
156                  bstree_node_lookup_upper_bound(
157                    root, bstree_intcmp, 0, 5));
158  CU_ASSERT_EQUAL(nodes[10],
159                  bstree_node_lookup_upper_bound(
160                    root, bstree_intcmp, 0, 10));
161}
162
163static int
164callback_test_foreach(struct bstree_node* node, void* callback_data)
165{
166  int* index = callback_data;
167  CU_ASSERT_EQUAL(nodes[*index], node);
168  (*index)++;
169  return BSTREE_CONTINUE;
170}
171
172static void
173test_foreach(void)
174{
175  int index = 0;
176  bstree_node_foreach(root, callback_test_foreach, &index);
177  CU_ASSERT_EQUAL(12, data.index);
178}
179
180struct test_foreach_range_data {
181  int index, inf, sup, count;
182};
183
184static int
185callback_test_foreach(struct bstree_node* node, void* callback_data)
186{
187  struct test_foreach_range_data* data = callback_data;
188  CU_ASSERT_EQUAL(nodes[data->index], node);
189  data->index++;
190  data->count++;
191  return BSTREE_CONTINUE;
192}
193
194static void
195test_foreach_range(void)
196{
197  struct test_foreach_range_data data;
198
199  data.index = 2;
200  data.inf   = 2;
201  data.sup   = 2;
202  data.count = 0;
203  bstree_node_foreach_range(root, bstree_intcmp, 0,
204                            callback_test_foreach_range, &data,
205                            data.inf, data.sup);
206  CU_ASSERT_EQUAL(3, data.count);
207
208  data.index = 2;
209  data.inf   = 2;
210  data.sup   = 7;
211  data.count = 0;
212  bstree_node_foreach_range(root, bstree_intcmp, 0,
213                            callback_test_foreach_range, &data,
214                            data.inf, data.sup);
215  CU_ASSERT_EQUAL(6, data.count);
216
217  data.index = 5;
218  data.inf   = 5;
219  data.sup   = 5;
220  data.count = 0;
221  bstree_node_foreach_range(root, bstree_intcmp, 0,
222                            callback_test_foreach_range, &data,
223                            data.inf, data.sup);
224  CU_ASSERT_EQUAL(1, data.count);
225}
226
227static int
228callback_test_dfs_foreach(struct bstree_node* node, void* callback_data)
229{
230  int* index = callback_data;
231  CU_ASSERT_EQUAL(nodes[dfs_index[*index]], node);
232  (*index)++;
233  return BSTREE_CONTINUE;
234}
235
236static void
237test_dfs_foreach(void)
238{
239  int index = 0;
240  bstree_node_dfs_foreach(root, callback_test_dfs_foreach, &index);
241  CU_ASSERT_EQUAL(12, data.index);
242}
243
244static int
245callback_test_bfs_foreach(struct bstree_node* node, void* callback_data)
246{
247  int* index = callback_data;
248  CU_ASSERT_EQUAL(nodes[bsf_index[*index]], node);
249  (*index)++;
250  return BSTREE_CONTINUE;
251}
252
253static void
254test_bfs_foreach(void)
255{
256  int index = 0;
257  bstree_node_bfs_foreach(root, callback_test_bfs_foreach, &index);
258  CU_ASSERT_EQUAL(12, data.index);
259}
260
261static CU_TestInfo tests_bstree[] = {
262  { "test_lookup_lower_bound", test_lookup_lower_bound },
263  { "test_lookup_upper_bound", test_lookup_upper_bound },
264  { "test_foreach", test_foreach },
265  { "test_foreach_range", test_foreach_range },
266  { "test_dfs_foreach", test_dfs_foreach },
267  { "test_bfs_foreach", test_bfs_foreach },
268  CU_TEST_INFO_NULL,
269};
270
271static CU_SuiteInfo suites[] = {
272  { "suite_bstree", suite_bstree_init, suite_bstree_clean, tests_bstree },
273  CU_SUITE_INFO_NULL,
274};
275
276int
277main(int argc, char** argv)
278{
279  CU_BasicRunMode mode = CU_BRM_VERBOSE;
280  CU_ErrorAction error_action = CUEA_IGNORE;
281
282  setvbuf(stdout, NULL, _IONBF, 0);
283  if (CU_initialize_registry()) {
284    fprintf(stderr, "Initialization of Test Registry failed.\n");
285  }
286  else {
287    if (CU_register_suites(suites) != CUE_SUCCESS) {
288      fprintf(stderr, "suite registration failed - %s\n", CU_get_error_msg());
289      return EXIT_FAILURE;
290    }
291    CU_basic_set_mode(mode);
292    CU_set_error_action(error_action);
293    printf("\nTests completed with return value %d.\n", CU_basic_run_tests());
294    CU_cleanup_registry();
295  }
296
297  return 0;
298}
299
300/*
301 * Local Variables:
302 * coding: utf-8
303 * mode: c
304 * c-basic-offset: 2
305 * indent-tabs-mode: nil
306 * End:
307 */
Note: See TracBrowser for help on using the browser.