test/test_tree.cpp

Sun, 20 Nov 2022 17:48:42 +0100

author
Mike Becker <universe@uap-core.de>
date
Sun, 20 Nov 2022 17:48:42 +0100
changeset 627
cc8cbabd27cd
parent 515
6d3909bf1609
permissions
-rw-r--r--

fix cx_array_copy() unintentionally shrinking the array

425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1 /*
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
3 *
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
5 *
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8 *
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 *
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
15 *
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 */
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
28
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
29 #include "cx/tree.h"
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
30 #include <gtest/gtest.h>
425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
31
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32 struct TestNode {
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
33 TestNode *parent = nullptr;
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
34 TestNode *prev = nullptr;
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
35 TestNode *next = nullptr;
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
36
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
37 TestNode *children_begin = nullptr;
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
38 TestNode *children_end = nullptr;
425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39 };
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
41 TEST(Tree, cx_tree_add_sibling) {
425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42 // prepare test tree
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
43 TestNode root, a;
425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44 root.children_begin = &a;
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 root.children_end = &a;
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 a.parent = &root;
449
68ad5750ba6b minor code changes
Mike Becker <universe@uap-core.de>
parents: 443
diff changeset
47
425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 // new test nodes
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
49 TestNode b, c;
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
50
425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51 // test
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
52 cx_tree_add_sibling(&a, offsetof(TestNode, prev), offsetof(TestNode, next), offsetof(TestNode, parent), &b);
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
53 EXPECT_EQ(b.parent, &root);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
54 EXPECT_EQ(b.prev, &a);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
55 EXPECT_EQ(b.next, nullptr);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
56 EXPECT_EQ(a.next, &b);
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
57
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
58 cx_tree_add_sibling(&a, -1, offsetof(TestNode, next), -1, &c);
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
59 EXPECT_EQ(c.parent, nullptr);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
60 EXPECT_EQ(c.prev, nullptr);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
61 EXPECT_EQ(c.next, nullptr);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
62 EXPECT_EQ(b.next, &c);
425
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 }
a75b808d653b add cx_tree_add_node test
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
65 TEST(Tree, cx_tree_add_child) {
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
66 TestNode root, a, b, c, a1;
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
67
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
68 cx_tree_add_child(
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
69 (void **) &root.children_begin,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
70 (void **) &root.children_end,
430
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
71 offsetof(TestNode, prev),
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
72 offsetof(TestNode, next),
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
73 &a,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
74 offsetof(TestNode, parent),
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
75 &root);
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
76 EXPECT_EQ(root.children_begin, &a);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
77 EXPECT_EQ(root.children_end, &a);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
78 EXPECT_EQ(a.parent, &root);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
79 EXPECT_EQ(a.prev, nullptr);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
80 EXPECT_EQ(a.next, nullptr);
449
68ad5750ba6b minor code changes
Mike Becker <universe@uap-core.de>
parents: 443
diff changeset
81
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
82 cx_tree_add_child(
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
83 (void **) &root.children_begin,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
84 (void **) &root.children_end,
430
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
85 offsetof(TestNode, prev),
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
86 offsetof(TestNode, next),
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
87 &b,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
88 offsetof(TestNode, parent),
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
89 &root);
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
90 EXPECT_EQ(root.children_begin, &a);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
91 EXPECT_EQ(root.children_begin->next, &b);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
92 EXPECT_EQ(root.children_end, &b);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
93 EXPECT_EQ(b.parent, &root);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
94 EXPECT_EQ(b.prev, &a);
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
95
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
96 cx_tree_add_child(
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
97 (void **) &root.children_begin,
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
98 nullptr,
430
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
99 -1,
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
100 offsetof(TestNode, next),
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
101 &c,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
102 -1,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
103 &root);
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
104 EXPECT_EQ(root.children_end, &b); // children_end unchanged
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
105 EXPECT_EQ(b.next, &c);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
106 EXPECT_EQ(c.prev, nullptr);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
107 EXPECT_EQ(c.next, nullptr);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
108 EXPECT_EQ(c.parent, nullptr);
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
109
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
110 cx_tree_add_child(
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
111 (void **) &a.children_begin,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
112 (void **) &a.children_end,
430
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
113 offsetof(TestNode, prev),
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
114 offsetof(TestNode, next),
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
115 &a1,
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
116 offsetof(TestNode, parent),
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 449
diff changeset
117 &a);
515
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
118 EXPECT_EQ(a.children_begin, &a1);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
119 EXPECT_EQ(a1.parent, &a);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
120 EXPECT_EQ(root.children_begin, &a);
6d3909bf1609 migrate tree tests to gtest
Mike Becker <universe@uap-core.de>
parents: 455
diff changeset
121 EXPECT_EQ(root.children_begin->children_begin, &a1);
430
d4d643def2ac add cx_tree_add_child_node tests
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 425
diff changeset
122 }

mercurial