Tue, 04 Oct 2022 19:25:07 +0200
fix over-optimization of strstr
1. it's actually less performant to frequently read bytes
from an array instead of using the native word length
2. the SBO buffer should be local and not static to allow
multi-threading usage
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 | 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 | 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 | } |