1 /* 2 * Copyright 2026 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include <string.h> 11 12 #include "testutil.h" 13 #include "internal/nelem.h" 14 #include "internal/ossl_rbtree.h" 15 16 static const char *test_data[] = { 17 "alpha", 18 "bravo", 19 "charlie", 20 "delta", 21 "echo", 22 "foxtrot", 23 "golf", 24 "hotel", 25 "india", 26 "juliet", 27 "kilo", 28 "lima", 29 "mike", 30 "november", 31 "oscar", 32 "papa", 33 "quebec", 34 "romeo", 35 "sierra", 36 "tango", 37 "uniform", 38 "victor", 39 "whiskey", 40 "x-ray", 41 "yankey", 42 "zulu", 43 }; 44 45 typedef struct test_rbt { 46 OSSL_RBT_ENTRY(test_rbt) 47 rbt_entry; 48 const char *rbt_data; 49 } TEST_RBT_T; 50 51 static OSSL_RBT_HEAD(ossl_rbt, test_rbt) 52 rbt_head; 53 54 static TEST_RBT_T nodes_rbt[26]; 55 56 static int cmp(const TEST_RBT_T *a, const TEST_RBT_T *b); 57 58 OSSL_RBT_PROTOTYPE(ossl_rbt, test_rbt, rbt_entry, cmp) 59 60 OSSL_RBT_GENERATE(ossl_rbt, test_rbt, rbt_entry, cmp); 61 62 static int cmp(const TEST_RBT_T *a_rbt, const TEST_RBT_T *b_rbt) 63 { 64 return strcmp(a_rbt->rbt_data, b_rbt->rbt_data); 65 } 66 67 static int test_rbt_insert(void) 68 { 69 unsigned int i; 70 TEST_RBT_T *found_rbt, *node_rbt; 71 72 OSSL_RBT_INIT(ossl_rbt, &rbt_head); 73 74 for (i = OSSL_NELEM(test_data); i != 0; i--) { 75 node_rbt = &nodes_rbt[i - 1]; 76 OSSL_RBT_INIT_RBE(ossl_rbt, node_rbt); 77 node_rbt->rbt_data = test_data[i - 1]; 78 found_rbt = OSSL_RBT_INSERT(ossl_rbt, &rbt_head, node_rbt); 79 if (!TEST_ptr_eq(found_rbt, NULL)) { 80 TEST_info("%s %p(%s) found already %p(%s) @ %u\n", OPENSSL_FUNC, 81 (void *)node_rbt, node_rbt->rbt_data, 82 (void *)found_rbt, found_rbt->rbt_data, i); 83 return 0; 84 } 85 } 86 87 return 1; 88 } 89 90 static int test_rbt_min(void) 91 { 92 unsigned int i; 93 int match; 94 TEST_RBT_T *node_rbt; 95 96 if (test_rbt_insert() == 0) 97 return 0; 98 99 node_rbt = OSSL_RBT_MIN(ossl_rbt, &rbt_head); 100 if (!TEST_ptr(node_rbt)) { 101 TEST_info("%s OSSL_RBT_MIN() returns NULL", OPENSSL_FUNC); 102 return 0; 103 } 104 105 for (i = 0; i < OSSL_NELEM(test_data); i++) { 106 match = strcmp(node_rbt->rbt_data, test_data[i]); 107 if (!TEST_int_eq(match, 0)) { 108 TEST_info("%s %s != %s @ %u", OPENSSL_FUNC, 109 node_rbt->rbt_data, test_data[i], i); 110 return 0; 111 } 112 node_rbt = OSSL_RBT_NEXT(ossl_rbt, node_rbt); 113 } 114 115 if (!TEST_ptr_eq(node_rbt, NULL)) { 116 TEST_info("%s OSSL_RBT_NEXT() is not NULL", OPENSSL_FUNC); 117 return 0; 118 } 119 120 return 1; 121 } 122 123 static int test_rbt_max(void) 124 { 125 unsigned int i; 126 int match; 127 TEST_RBT_T *node_rbt; 128 129 if (test_rbt_insert() == 0) 130 return 0; 131 132 node_rbt = OSSL_RBT_MAX(ossl_rbt, &rbt_head); 133 if (!TEST_ptr(node_rbt)) { 134 TEST_info("%s OSSL_RBT_MIN() returns NULL", OPENSSL_FUNC); 135 return 0; 136 } 137 138 for (i = OSSL_NELEM(test_data); i > 0; i--) { 139 match = strcmp(node_rbt->rbt_data, test_data[i - 1]); 140 if (!TEST_int_eq(match, 0)) { 141 TEST_info("%s %s != %s @ %u", OPENSSL_FUNC, 142 node_rbt->rbt_data, test_data[i - 1], i); 143 return 0; 144 } 145 node_rbt = OSSL_RBT_PREV(ossl_rbt, node_rbt); 146 } 147 148 if (!TEST_ptr_eq(node_rbt, NULL)) { 149 TEST_info("%s OSSL_RBT_PREV() is not NULL", OPENSSL_FUNC); 150 return 0; 151 } 152 153 return 1; 154 } 155 156 static int test_rbt_find_remove(void) 157 { 158 unsigned int i; 159 TEST_RBT_T *node_rbt, *removed_rbt; 160 TEST_RBT_T key_rbt; 161 162 if (test_rbt_insert() == 0) 163 return 0; 164 165 for (i = 0; i < OSSL_NELEM(test_data); i++) { 166 key_rbt.rbt_data = test_data[i]; 167 node_rbt = OSSL_RBT_FIND(ossl_rbt, &rbt_head, &key_rbt); 168 if (!TEST_ptr(node_rbt)) { 169 TEST_info("%s %s not found in tree @ %u", OPENSSL_FUNC, 170 key_rbt.rbt_data, i); 171 return 0; 172 } 173 removed_rbt = OSSL_RBT_REMOVE(ossl_rbt, &rbt_head, node_rbt); 174 if (!TEST_ptr_eq(node_rbt, removed_rbt)) { 175 TEST_info("%s node_rbt(%p) != removed_rbt(%p) @ %u", 176 OPENSSL_FUNC, (void *)node_rbt, (void *)removed_rbt, i); 177 return 0; 178 } 179 180 node_rbt = OSSL_RBT_FIND(ossl_rbt, &rbt_head, &key_rbt); 181 if (!TEST_ptr_eq(node_rbt, NULL)) { 182 TEST_info("%s %s(%p) still found after being removed @ %u", 183 OPENSSL_FUNC, node_rbt->rbt_data, (void *)node_rbt, i); 184 return 0; 185 } 186 } 187 188 if (!TEST_int_ne(OSSL_RBT_EMPTY(ossl_rbt, &rbt_head), 0)) { 189 TEST_info("%s rbt is not empty", OPENSSL_FUNC); 190 return 0; 191 } 192 193 return 1; 194 } 195 196 static int test_rbt_dup_insert(void) 197 { 198 unsigned int i; 199 int match; 200 TEST_RBT_T *conflict_rbt; 201 TEST_RBT_T insert_rbt; 202 203 if (test_rbt_insert() == 0) 204 return 0; 205 206 for (i = 0; i < OSSL_NELEM(test_data); i++) { 207 OSSL_RBT_INIT_RBE(ossl_rbt, &insert_rbt); 208 insert_rbt.rbt_data = test_data[i]; 209 conflict_rbt = OSSL_RBT_INSERT(ossl_rbt, &rbt_head, &insert_rbt); 210 if (!TEST_ptr(conflict_rbt)) { 211 TEST_info("%s %s not found in tree @ %u", OPENSSL_FUNC, 212 insert_rbt.rbt_data, i); 213 return 0; 214 } 215 match = strcmp(conflict_rbt->rbt_data, insert_rbt.rbt_data); 216 if (!TEST_int_eq(match, 0)) { 217 TEST_info("%s insert(%s) != conflict(%s) @ %u", 218 OPENSSL_FUNC, insert_rbt.rbt_data, conflict_rbt->rbt_data, i); 219 return 0; 220 } 221 } 222 223 return 1; 224 } 225 226 static int test_rbt_foreach(void) 227 { 228 unsigned int i; 229 int match; 230 TEST_RBT_T *walk_rbt, *save_rbt; 231 232 if (test_rbt_insert() == 0) 233 return 0; 234 235 i = 0; 236 OSSL_RBT_FOREACH (walk_rbt, ossl_rbt, &rbt_head) { 237 match = strcmp(walk_rbt->rbt_data, test_data[i]); 238 if (!TEST_int_eq(match, 0)) { 239 TEST_info("%s expected: %s got: %s @ %u", 240 OPENSSL_FUNC, walk_rbt->rbt_data, test_data[i], i); 241 return 0; 242 } 243 i++; 244 } 245 246 i = 0; 247 OSSL_RBT_FOREACH_SAFE (walk_rbt, ossl_rbt, &rbt_head, save_rbt) { 248 match = strcmp(walk_rbt->rbt_data, test_data[i]); 249 if (!TEST_int_eq(match, 0)) { 250 TEST_info("%s expected: %s got: %s @ %u", 251 OPENSSL_FUNC, walk_rbt->rbt_data, test_data[i], i); 252 return 0; 253 } 254 OSSL_RBT_REMOVE(ossl_rbt, &rbt_head, walk_rbt); 255 i++; 256 } 257 258 if (!TEST_int_ne(OSSL_RBT_EMPTY(ossl_rbt, &rbt_head), 0)) { 259 TEST_info("%s rbt is not empty", OPENSSL_FUNC); 260 return 0; 261 } 262 263 return 1; 264 } 265 266 int setup_tests(void) 267 { 268 ADD_TEST(test_rbt_insert); 269 ADD_TEST(test_rbt_min); 270 ADD_TEST(test_rbt_max); 271 ADD_TEST(test_rbt_find_remove); 272 ADD_TEST(test_rbt_dup_insert); 273 ADD_TEST(test_rbt_foreach); 274 275 return 1; 276 } 277