1 /*
2 * Copyright (c) 2023 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 #if DEVELOPMENT || DEBUG
30
31 #include <kern/startup.h>
32 #include <kern/zalloc.h>
33 #include <sys/proc_ro.h>
34 #include <sys/vm.h>
35
36 #include <tests/ktest.h>
37
38 #include <libkern/tree.h>
39
40 /*
41 * RB tree node that we use for testing.
42 * The nodes are compared using the numeric `rbt_id'.
43 */
44 struct rbt_test_node {
45 RB_ENTRY(rbt_test_node) link;
46 unsigned int rbt_id; /* comparison id */
47 unsigned int rbt_flags;
48 #define RBT_FLAG_IN_USE 1
49 #define RBT_MASK_IN_USE 1
50 };
51
52 typedef struct rbt_test_node * __single rbt_test_node_t;
53
54 /*
55 * Comparison function for rbt test nodes.
56 */
57 static int
rbt_cmp(struct rbt_test_node * a,struct rbt_test_node * b)58 rbt_cmp(struct rbt_test_node *a, struct rbt_test_node *b)
59 {
60 if (!a && !b) {
61 return 0;
62 } else if (a && !b) {
63 return -1;
64 } else if (!a && b) {
65 return 1;
66 } else if (a->rbt_id == b->rbt_id) {
67 return 0;
68 } else if (a->rbt_id < b->rbt_id) {
69 return -1;
70 } else {
71 return 1;
72 }
73 }
74
75 /*
76 * Define a red-black tree type we are going to test.
77 */
78 RB_HEAD(_rb_test_tree, rbt_test_node);
79 RB_PROTOTYPE(_rb_test_tree, rbt_test_node, link, rbt_cmp)
80 RB_GENERATE(_rb_test_tree, rbt_test_node, link, rbt_cmp)
81
82 /*
83 * Array of test nodes that we are going to use.
84 */
85 #define RBT_TEST_NODE_COUNT 7
86 static struct rbt_test_node test_nodes[RBT_TEST_NODE_COUNT];
87 static int test_node_ids[RBT_TEST_NODE_COUNT] = {88, 66, 44, 22, 0, 77, 55 };
88
89
90 static size_t
rb_tree_insert_nodes(struct _rb_test_tree * tree,size_t count)91 rb_tree_insert_nodes(struct _rb_test_tree *tree, size_t count)
92 {
93 unsigned int idx = 0;
94 if (RBT_TEST_NODE_COUNT < count) {
95 count = RBT_TEST_NODE_COUNT;
96 }
97
98 for (idx = 0; idx < count; idx++) {
99 rbt_test_node_t node = &test_nodes[idx];
100 T_EXPECT_EQ_INT(node->rbt_flags & RBT_MASK_IN_USE, 0, "Trying to insert a tree node that is already in use");
101 node->rbt_id = test_node_ids[idx];
102 RB_INSERT(_rb_test_tree, tree, node);
103 node->rbt_flags |= RBT_FLAG_IN_USE;
104 }
105 return count;
106 }
107
108 static size_t
rb_tree_remove_nodes(struct _rb_test_tree * tree,size_t count)109 rb_tree_remove_nodes(struct _rb_test_tree *tree, size_t count)
110 {
111 unsigned int idx = 0;
112 if (RBT_TEST_NODE_COUNT < count) {
113 count = RBT_TEST_NODE_COUNT;
114 }
115
116 for (idx = 0; idx < count; idx++) {
117 rbt_test_node_t node = &test_nodes[idx];
118 T_EXPECT_EQ_INT(node->rbt_flags & RBT_MASK_IN_USE, 1, "Trying to remove a tree node that is not in use");
119 T_EXPECT_EQ_INT(node->rbt_id, test_node_ids[idx], "The node id does not match the node index");
120 RB_REMOVE(_rb_test_tree, tree, node);
121 node->rbt_flags &= ~RBT_FLAG_IN_USE;
122 }
123 return count;
124 }
125
126 static int
rb_tree_test_run(__unused int64_t in,int64_t * out)127 rb_tree_test_run(__unused int64_t in, int64_t *out)
128 {
129 struct _rb_test_tree test_tree;
130 RB_INIT(&test_tree);
131
132 rb_tree_insert_nodes(&test_tree, 7);
133 rb_tree_remove_nodes(&test_tree, 7);
134
135 *out = 0;
136 return 0;
137 }
138
139 SYSCTL_TEST_REGISTER(rb_tree_test, rb_tree_test_run);
140
141 #endif /* DEVELOPMENT || DEBUG */
142