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
|
// ============================================================================
//
// = LIBRARY
// tests
//
// = FILENAME
// Bug_3332_Regression_Test.cpp
//
// = DESCRIPTION
// This is a test to verify the node unbind/remove stability.
// Originally the deletion of a node from the rb_tree would cause some nodes
// to be "swapped" and the node being deleted to be reused to hold data still
// in the rb_tree, whilst the original "still in the tree" data node would be
// unbound instead. This caused externally held pointers to existing data that
// should still be in the tree to become invalidated unnecessarily. This test
// ensures that the node NOT being deleted always keep their original enteries
// (and thus only the deleted node is actually unbound and released).
//
// = AUTHOR
// Simon Massey <sma@prismtech.com>
//
// ============================================================================
#include "test_config.h" /* Include first to enable ACE_TEST_ASSERT. */
#include "ace/RB_Tree.h"
#include "ace/Null_Mutex.h"
namespace
{
struct Nodes
{
char key;
int value;
ACE_RB_Tree_Node<char, int> *node;
} nodes[] = {{'a', 1, 0},
{'f', 6, 0},
{'c', 3, 0},
{'e', 5, 0},
{'g', 7, 0},
{'b', 2, 0},
{'h', 8, 0},
{'d', 4, 0},
{'i', 9, 0},
{'l', 12, 0},
{'j', 10, 0},
{'k', 11, 0},
{'m', 13, 0}};
}
int
run_main (int, ACE_TCHAR *[])
{
int result = 0;
ACE_START_TEST (ACE_TEXT ("Bug_3332_Regression_Test"));
ACE_RB_Tree<char, int, ACE_Less_Than<char>, ACE_Null_Mutex> tree;
ACE_DEBUG ((LM_DEBUG, "Creating Tree\n"));
{for (size_t i= 0u; i < sizeof(nodes)/sizeof(Nodes); ++i)
{
if (0 != tree.bind (nodes[i].key, nodes[i].value, nodes[i].node))
{
ACE_DEBUG ((LM_ERROR, ": Binding failed for %c=%d\n", nodes[i].key, nodes[i].value));
result = 1;
}
}}
if (!result)
{
ACE_DEBUG ((LM_DEBUG, "Validating Tree\n"));
{for (size_t i= 0u; i < sizeof(nodes)/sizeof(Nodes); ++i)
{
ACE_RB_Tree_Node<char, int> *node = 0;
if (tree.find (nodes[i].key, node))
{
ACE_DEBUG ((LM_ERROR, ": Can't find key %c in tree\n", nodes[i].key));
result = 2;
}
else if (nodes[i].node != node)
{
ACE_DEBUG ((LM_ERROR, ": entry %c=%d has ALREADY moved from %@ to %@\n", nodes[i].key, nodes[i].value, nodes[i].node, node));
result = 3;
}
else for (size_t j= i+1u; j < sizeof(nodes)/sizeof(Nodes); ++j)
{
if (nodes[i].node == nodes[j].node)
{
ACE_DEBUG ((LM_ERROR, ": Duplicate Binding (%@) for %c=%d and %c=%d\n", nodes[i].node, nodes[i].key, nodes[i].value, nodes[j].key, nodes[j].value));
result = 4;
}
}
}}
if (!result)
{
{for (size_t i= 0u; i < sizeof(nodes)/sizeof(Nodes); ++i)
{
ACE_DEBUG ((LM_DEBUG, "Deleting node %c=%d @ %@\n", nodes[i].key, nodes[i].value, nodes[i].node));
if (tree.unbind (nodes[i].key))
{
ACE_DEBUG ((LM_ERROR, ": Can't unbind key %c from tree\n", nodes[i].key));
result = 5;
}
else
{
ACE_RB_Tree_Node<char, int> *node = 0;
if (0 == tree.find (nodes[i].key, node))
{
ACE_DEBUG ((LM_ERROR, ": Found %c=%d @ %@ in tree\n", node->key(), node->item(), node));
result = 6;
}
else {for (size_t j= i+1u; j < sizeof(nodes)/sizeof(Nodes); ++j)
{
if (tree.find (nodes[j].key, node))
{
ACE_DEBUG ((LM_ERROR, ": Can't find key %c in tree\n", nodes[j].key));
result = 7;
}
else if (nodes[j].node != node)
{
ACE_DEBUG ((LM_ERROR, ": entry %c=%d has moved from %@ to %@\n", nodes[j].key, nodes[j].value, nodes[j].node, node));
nodes[j].node = node; // Don't keep reporting this same issue on further deletions.
result = 8;
}
else if (nodes[j].key != node->key() || nodes[j].value != node->item())
{
ACE_DEBUG ((LM_ERROR, ": entry %c=%d has changed to %c=%d\n", nodes[j].key, nodes[j].value, node->key(), node->item()));
nodes[j].key= node->key(); // Don't keep reporting this problem on further deletions.
nodes[j].value = node->item();
result = 9;
}
}}
}
}}
}
}
ACE_DEBUG ((LM_DEBUG, "Finished\n"));
ACE_END_TEST;
return result;
}
|
