tree.cc raw
1
2 // The program tests part of the C++ functionality provided by `gc_cpp.h`
3 // file (and `gctba` library) by creating balanced trees of various depth
4 // and arity.
5
6 #ifdef HAVE_CONFIG_H
7 # include "config.h"
8 #endif
9
10 #undef GC_BUILD
11
12 #define GC_DONT_INCL_WINDOWS_H
13 #define GC_NAMESPACE
14 #include "gc_cpp.h"
15
16 #include <stdio.h>
17 #include <stdlib.h>
18
19 #define NO_GC GC_NS_QUALIFY(NoGC)
20 #define PTRFREE_GC GC_NS_QUALIFY(PointerFreeGC)
21 #define USE_GC GC_NS_QUALIFY(UseGC)
22
23 #ifdef GC_ATOMIC_UNCOLLECTABLE
24 # define PTRFREE_NOGC GC_NS_QUALIFY(PointerFreeNoGC)
25 #endif
26
27 class Tree;
28
29 class PTree : public GC_NS_QUALIFY(gc)
30 {
31 public:
32 Tree *ptr;
33 };
34
35 class Tree : public GC_NS_QUALIFY(gc)
36 {
37 public:
38 GC_ATTR_EXPLICIT
39 Tree(int a, int d, bool uncollectable);
40 ~Tree();
41 void verify();
42
43 private:
44 void verify(int a, int d);
45 void verify_node(int a, int d);
46 int arity, depth;
47 PTree *m_nodes;
48 };
49
50 Tree::Tree(int a, int d, bool uncollectable) : arity(a), depth(d)
51 {
52 PTree *nodes = 0;
53 if (depth > 0) {
54 #ifdef GC_OPERATOR_NEW_ARRAY
55 nodes =
56 # ifndef CPPCHECK
57 uncollectable ? new (NO_GC) PTree[arity] :
58 # endif
59 new (USE_GC) PTree[arity];
60 #else
61 nodes = reinterpret_cast<PTree *>(
62 uncollectable
63 ? GC_MALLOC_UNCOLLECTABLE(sizeof(PTree) * (unsigned)arity)
64 : GC_MALLOC(sizeof(PTree) * (unsigned)arity));
65 GC_OP_NEW_OOM_CHECK(nodes);
66 #endif
67 for (int i = 0; i < arity; i++) {
68 Tree const *pnode
69 = depth > 1
70 ? (uncollectable ? new (NO_GC) Tree(arity, depth - 1, true)
71 : new (USE_GC) Tree(arity, depth - 1, false))
72 :
73 #ifdef GC_ATOMIC_UNCOLLECTABLE
74 uncollectable ? new (PTRFREE_NOGC) Tree(arity, 0, true)
75 :
76 #endif
77 new (PTRFREE_GC) Tree(arity, 0, uncollectable);
78 GC_PTR_STORE_AND_DIRTY(&nodes[i].ptr, pnode);
79 }
80 }
81 this->m_nodes = nodes;
82 GC_END_STUBBORN_CHANGE(this);
83 GC_reachable_here(nodes);
84 }
85
86 Tree::~Tree()
87 {
88 if (depth > 0) {
89 for (int i = 0; i < arity; i++) {
90 delete m_nodes[i].ptr;
91 }
92 #ifdef GC_OPERATOR_NEW_ARRAY
93 delete[] m_nodes;
94 #else
95 GC_FREE(m_nodes);
96 #endif
97 }
98 }
99
100 void
101 Tree::verify()
102 {
103 verify(arity, depth);
104 }
105
106 void
107 Tree::verify_node(int a, int d)
108 {
109 if (a != arity || d != depth) {
110 fprintf(stderr, "Wrong stored arity or depth! arity=%d, depth=%d\n", arity,
111 depth);
112 exit(1);
113 }
114 if (0 == depth) {
115 if (m_nodes != 0) {
116 fprintf(stderr, "Found nonempty node!\n");
117 exit(1);
118 }
119 } else if (0 == m_nodes) {
120 fprintf(stderr, "Found empty node! depth=%d\n", depth);
121 exit(1);
122 }
123 }
124
125 void
126 Tree::verify(int a, int d)
127 {
128 verify_node(a, d);
129 if (0 == depth)
130 return;
131 for (int i = 0; i < arity; i++) {
132 m_nodes[i].ptr->verify(a, d - 1);
133 }
134 }
135
136 #ifndef MAX_ARITY
137 # define MAX_ARITY 5
138 #endif
139
140 #ifndef MAX_DEPTH
141 # define MAX_DEPTH 9
142 #endif
143
144 #ifndef DEL_EVERY_N_TREE
145 # define DEL_EVERY_N_TREE 7
146 #endif
147
148 static void
149 create_trees(bool is_find_leak, bool uncollectable)
150 {
151 int trees_cnt = 0;
152 for (int arity = 2; arity <= MAX_ARITY; arity++) {
153 for (int depth = 1; depth <= MAX_DEPTH; depth++) {
154 Tree *tree = new (USE_GC) Tree(arity, depth, uncollectable);
155 tree->verify();
156 if (is_find_leak || uncollectable || ++trees_cnt % DEL_EVERY_N_TREE == 0)
157 delete tree;
158 }
159 }
160 }
161
162 int
163 main(void)
164 {
165 #ifdef TEST_MANUAL_VDB
166 GC_set_manual_vdb_allowed(1);
167 #endif
168 #ifndef CPPCHECK
169 GC_INIT();
170 #endif
171 bool is_find_leak = static_cast<bool>(GC_get_find_leak());
172 #ifndef NO_INCREMENTAL
173 GC_enable_incremental();
174 #endif
175 Tree *keep_tree = new (USE_GC) Tree(MAX_ARITY, MAX_DEPTH, false);
176 keep_tree->verify();
177 create_trees(is_find_leak, false);
178 create_trees(is_find_leak, true);
179 keep_tree->verify(); /*< recheck */
180 if (is_find_leak)
181 delete keep_tree;
182 printf("SUCCEEDED\n");
183 return 0;
184 }
185