Mercurial > hg > ucx / file comparison

comparison: tests/test_tree.c

tests/test_tree.c

changeset 872
d607a184925a
parent 871
e29c1f96646d
equal deleted inserted replaced
862:387414a7afd8 872:d607a184925a
47 struct tree_node2 *children; 47 struct tree_node2 *children;
48 struct tree_node2 *last_child; 48 struct tree_node2 *last_child;
49 int data; 49 int data;
50 } tree_node2; 50 } tree_node2;
51 51
52 typedef struct tree_node_file {
53 struct tree_node_file *parent;
54 struct tree_node_file *next;
55 struct tree_node_file *prev;
56 struct tree_node_file *children;
57 struct tree_node_file *last_child;
58 char const *path;
59 } tree_node_file;
60
61 static void *create_tree_node_file(
62 void const *dptr,
63 void *allocator) {
64 if (allocator == NULL) allocator = cxDefaultAllocator;
65
66 tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
67 node->path = dptr;
68
69 // intentionally write garbage into the pointers, it's part of the test
70 node->parent = (void *) 0xf00ba1;
71 node->next = (void *) 0xf00ba2;
72 node->prev = (void *) 0xf00ba3;
73 node->children = (void *) 0xf00ba4;
74 node->last_child = (void *) 0xf00ba5;
75
76 return node;
77 }
78
79 static int tree_node_file_search(void const *l, void const *r) {
80 tree_node_file const *left = l;
81 tree_node_file const *right = r;
82 size_t len1 = strlen(left->path);
83 size_t len2 = strlen(right->path);
84 if (len1 <= len2) {
85 if (memcmp(left->path, right->path, len1) == 0) {
86 return (int) (len2 - len1);
87 } else {
88 return -1;
89 }
90 } else {
91 return -1;
92 }
93 }
94
52 #define tree_node_layout \ 95 #define tree_node_layout \
53 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ 96 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \
54 offsetof(tree_node, prev), offsetof(tree_node, next) 97 offsetof(tree_node, prev), offsetof(tree_node, next)
55 #define tree_node2_layout \ 98 #define tree_node_full_layout(structname) \
56 offsetof(tree_node2, parent), offsetof(tree_node2, children),\ 99 offsetof(structname, parent), offsetof(structname, children),\
57 offsetof(tree_node2, last_child), \ 100 offsetof(structname, last_child), \
58 offsetof(tree_node2, prev), offsetof(tree_node2, next) 101 offsetof(structname, prev), offsetof(structname, next)
102 #define tree_node2_layout tree_node_full_layout(tree_node2)
103 #define tree_node_file_layout tree_node_full_layout(tree_node_file)
59 104
60 #define tree_children(type) offsetof(type, children), offsetof(type, next) 105 #define tree_children(type) offsetof(type, children), offsetof(type, next)
61 106
62 CX_TEST(test_tree_link_new_child) { 107 CX_TEST(test_tree_link_new_child) {
63 tree_node parent = {0}; 108 tree_node parent = {0};
374 int r; 419 int r;
375 tree_node *n; 420 tree_node *n;
376 CX_TEST_DO { 421 CX_TEST_DO {
377 for (unsigned i = 0 ; i <= 10 ; i++) { 422 for (unsigned i = 0 ; i <= 10 ; i++) {
378 s = testdata[i]; 423 s = testdata[i];
379 r = cx_tree_search(&root, &s, test_tree_search_function, 424 r = cx_tree_search_data(&root, &s, test_tree_search_function,
380 (void **) &n, tree_children(tree_node)); 425 (void **) &n, tree_children(tree_node));
381 CX_TEST_ASSERT(r == 0); 426 CX_TEST_ASSERT(r == 0);
382 CX_TEST_ASSERT(n == testnodes[i]); 427 CX_TEST_ASSERT(n == testnodes[i]);
383 } 428 }
384 429
385 s = -5; 430 s = -5;
386 r = cx_tree_search(&root, &s, test_tree_search_function, 431 r = cx_tree_search_data(&root, &s, test_tree_search_function,
387 (void **) &n, tree_children(tree_node)); 432 (void **) &n, tree_children(tree_node));
388 CX_TEST_ASSERT(r < 0); 433 CX_TEST_ASSERT(r < 0);
389 CX_TEST_ASSERT(n == NULL); 434 CX_TEST_ASSERT(n == NULL);
390 435
391 s = 26; 436 s = 26;
392 r = cx_tree_search(&root, &s, test_tree_search_function, 437 r = cx_tree_search_data(&root, &s, test_tree_search_function,
393 (void **) &n, tree_children(tree_node)); 438 (void **) &n, tree_children(tree_node));
394 CX_TEST_ASSERT(r > 0); 439 CX_TEST_ASSERT(r > 0);
395 CX_TEST_ASSERT(n == &ba); 440 CX_TEST_ASSERT(n == &ba);
396 441
397 s = 35; 442 s = 35;
398 r = cx_tree_search(&root, &s, test_tree_search_function, 443 r = cx_tree_search_data(&root, &s, test_tree_search_function,
399 (void **) &n, tree_children(tree_node)); 444 (void **) &n, tree_children(tree_node));
400 CX_TEST_ASSERT(r > 0); 445 CX_TEST_ASSERT(r > 0);
401 CX_TEST_ASSERT(n == &cb); 446 CX_TEST_ASSERT(n == &cb);
402 447
403 s = 38; 448 s = 38;
404 r = cx_tree_search(&root, &s, test_tree_search_function, 449 r = cx_tree_search_data(&root, &s, test_tree_search_function,
405 (void **) &n, tree_children(tree_node)); 450 (void **) &n, tree_children(tree_node));
406 CX_TEST_ASSERT(r > 0); 451 CX_TEST_ASSERT(r > 0);
407 CX_TEST_ASSERT(n == &cba); 452 CX_TEST_ASSERT(n == &cba);
408 453
409 s = 42; 454 s = 42;
410 r = cx_tree_search(&root, &s, test_tree_search_function, 455 r = cx_tree_search_data(&root, &s, test_tree_search_function,
411 (void **) &n, tree_children(tree_node)); 456 (void **) &n, tree_children(tree_node));
412 CX_TEST_ASSERT(r > 0); 457 CX_TEST_ASSERT(r > 0);
413 CX_TEST_ASSERT(n == &cc); 458 CX_TEST_ASSERT(n == &cc);
414 } 459 }
415 } 460 }
990 CX_TEST_ASSERT(cb.data == 0); 1035 CX_TEST_ASSERT(cb.data == 0);
991 CX_TEST_ASSERT(cc.data == 0); 1036 CX_TEST_ASSERT(cc.data == 0);
992 CX_TEST_ASSERT(cba.data == 0); 1037 CX_TEST_ASSERT(cba.data == 0);
993 } 1038 }
994 } 1039 }
1040
1041 CX_TEST(test_tree_add_one) {
1042 CxTestingAllocator talloc;
1043 cx_testing_allocator_init(&talloc);
1044 CxAllocator *alloc = &talloc.base;
1045
1046 tree_node_file root = {0};
1047 root.path = "/";
1048 tree_node_file usr = {0};
1049 usr.path = "/usr/";
1050 cx_tree_link(&root, &usr, tree_node_file_layout);
1051 tree_node_file home = {0};
1052 home.path = "/home/";
1053 cx_tree_link(&root, &home, tree_node_file_layout);
1054 tree_node_file lib = {0};
1055 lib.path = "/usr/lib/";
1056 cx_tree_link(&usr, &lib, tree_node_file_layout);
1057
1058 CX_TEST_DO {
1059 tree_node_file *foo;
1060 int result;
1061 result = cx_tree_add(
1062 "/home/foo/",
1063 tree_node_file_search,
1064 create_tree_node_file, alloc,
1065 (void **) &foo, &root,
1066 tree_node_file_layout
1067 );
1068 CX_TEST_ASSERT(result == 0);
1069 CX_TEST_ASSERT(foo != NULL);
1070 char const *bar_path = "/home/foo/bar/";
1071 void *failed;
1072 size_t added = cx_tree_add_array(
1073 bar_path, 1, sizeof(char const *),
1074 tree_node_file_search,
1075 create_tree_node_file, alloc,
1076 &failed, &root,
1077 tree_node_file_layout
1078 );
1079 CX_TEST_ASSERT(added == 1);
1080 CX_TEST_ASSERT(failed == NULL);
1081 tree_node_file *bar = foo->children;
1082 CX_TEST_ASSERT(bar != NULL);
1083 CX_TEST_ASSERT(bar->parent == foo);
1084 CX_TEST_ASSERT(bar->path == bar_path);
1085 CX_TEST_ASSERT(foo->parent == &home);
1086
1087 tree_node_file *new_node;
1088 result = cx_tree_add(
1089 "newroot",
1090 tree_node_file_search,
1091 create_tree_node_file, alloc,
1092 (void **) &new_node, &root,
1093 tree_node_file_layout
1094 );
1095 CX_TEST_ASSERT(0 != result);
1096 CX_TEST_ASSERT(NULL != new_node);
1097 CX_TEST_ASSERT(new_node->children == NULL);
1098 CX_TEST_ASSERT(new_node->parent == NULL);
1099
1100 CX_TEST_ASSERT(talloc.alloc_total == 3);
1101
1102 cxFree(alloc, foo);
1103 cxFree(alloc, bar);
1104 cxFree(alloc, new_node);
1105
1106 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1107 }
1108 cx_testing_allocator_destroy(&talloc);
1109 }
1110
1111 CX_TEST(test_tree_add_one_existing) {
1112 CxTestingAllocator talloc;
1113 cx_testing_allocator_init(&talloc);
1114 CxAllocator *alloc = &talloc.base;
1115
1116 tree_node_file root = {0};
1117 root.path = "/";
1118 tree_node_file usr = {0};
1119 usr.path = "/usr/";
1120 cx_tree_link(&root, &usr, tree_node_file_layout);
1121 tree_node_file home = {0};
1122 home.path = "/home/";
1123 cx_tree_link(&root, &home, tree_node_file_layout);
1124 tree_node_file lib = {0};
1125 lib.path = "/usr/lib/";
1126 cx_tree_link(&usr, &lib, tree_node_file_layout);
1127
1128 CX_TEST_DO {
1129 tree_node_file *node;
1130 int result = cx_tree_add(
1131 "/usr/lib/",
1132 tree_node_file_search,
1133 create_tree_node_file, alloc,
1134 (void **) &node, &root,
1135 tree_node_file_layout
1136 );
1137 CX_TEST_ASSERT(result == 0);
1138 CX_TEST_ASSERT(node != &lib);
1139 CX_TEST_ASSERT(node->prev == &lib);
1140 CX_TEST_ASSERT(lib.next == node);
1141 CX_TEST_ASSERT(node->parent == &usr);
1142 CX_TEST_ASSERT(talloc.alloc_total == 1);
1143 cxFree(alloc, node);
1144 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1145 }
1146 cx_testing_allocator_destroy(&talloc);
1147 }
1148
1149 CX_TEST(test_tree_add_one_no_match) {
1150 tree_node_file root = {0};
1151 root.path = "/mnt/";
1152
1153 CX_TEST_DO {
1154 tree_node_file *node = NULL;
1155 int result = cx_tree_add(
1156 "/usr/lib/",
1157 tree_node_file_search,
1158 create_tree_node_file, NULL,
1159 (void **) &node, &root,
1160 tree_node_file_layout
1161 );
1162 CX_TEST_ASSERT(result != 0);
1163 CX_TEST_ASSERT(node != NULL);
1164 CX_TEST_ASSERT(node->parent == NULL);
1165 CX_TEST_ASSERT(node->children == NULL);
1166 free(node);
1167 node = NULL;
1168 size_t added = cx_tree_add_array(
1169 "/", 1, sizeof(char const *),
1170 tree_node_file_search,
1171 create_tree_node_file, NULL,
1172 (void **) &node, &root,
1173 tree_node_file_layout
1174 );
1175 CX_TEST_ASSERT(added == 0);
1176 CX_TEST_ASSERT(node != NULL);
1177 CX_TEST_ASSERT(node->parent == NULL);
1178 CX_TEST_ASSERT(node->children == NULL);
1179 free(node);
1180 }
1181 }
1182
1183 CX_TEST(test_tree_add_duplicate_root) {
1184 tree_node_file root = {0};
1185 root.path = "/";
1186 CX_TEST_DO {
1187 tree_node_file *node;
1188 int result = cx_tree_add(
1189 "/",
1190 tree_node_file_search,
1191 create_tree_node_file, NULL,
1192 (void **) &node, &root,
1193 tree_node_file_layout
1194 );
1195 CX_TEST_ASSERT(result == 0);
1196 CX_TEST_ASSERT(root.children == node);
1197 CX_TEST_ASSERT(node->parent == &root);
1198 }
1199 }
1200
1201 CX_TEST(test_tree_add_zero) {
1202 CxTestingAllocator talloc;
1203 cx_testing_allocator_init(&talloc);
1204 CxAllocator *alloc = &talloc.base;
1205
1206 tree_node_file root = {0};
1207 root.path = "/";
1208 CX_TEST_DO {
1209 void *failed;
1210
1211 size_t processed = cx_tree_add_array(
1212 (void *) 0xc0ffee, 0, sizeof(void *),
1213 tree_node_file_search,
1214 create_tree_node_file, alloc,
1215 &failed, &root, tree_node_file_layout
1216 );
1217 CX_TEST_ASSERT(failed == NULL);
1218 CX_TEST_ASSERT(processed == 0);
1219 CX_TEST_ASSERT(talloc.alloc_total == 0);
1220
1221 CxIterator iter = cxIterator(NULL, sizeof(void *), 0);
1222 processed = cx_tree_add_iter(
1223 cxIteratorRef(iter),
1224 tree_node_file_search,
1225 create_tree_node_file, alloc,
1226 &failed, &root, tree_node_file_layout
1227 );
1228 CX_TEST_ASSERT(processed == 0);
1229 CX_TEST_ASSERT(failed == NULL);
1230 CX_TEST_ASSERT(talloc.alloc_total == 0);
1231
1232 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1233 }
1234 cx_testing_allocator_destroy(&talloc);
1235 }
1236
1237 CX_TEST(test_tree_add_many) {
1238 // adds many elements to an existing tree
1239
1240 CxTestingAllocator talloc;
1241 cx_testing_allocator_init(&talloc);
1242 CxAllocator *alloc = &talloc.base;
1243
1244 tree_node_file root = {0};
1245 root.path = "/";
1246 tree_node_file usr = {0};
1247 usr.path = "/usr/";
1248 cx_tree_link(&root, &usr, tree_node_file_layout);
1249 tree_node_file home = {0};
1250 home.path = "/home/";
1251 cx_tree_link(&root, &home, tree_node_file_layout);
1252 tree_node_file lib = {0};
1253 lib.path = "/usr/lib/";
1254 cx_tree_link(&usr, &lib, tree_node_file_layout);
1255
1256 CX_TEST_DO {
1257 void *failed;
1258
1259 char const *paths[] = {
1260 "/home/foo/",
1261 "/home/foo/bar",
1262 "/usr/lib64/",
1263 "/usr/lib/foo.so"
1264 };
1265
1266 size_t processed = cx_tree_add_array(
1267 paths, 4, sizeof(char const *),
1268 tree_node_file_search,
1269 create_tree_node_file, alloc,
1270 &failed, &root, tree_node_file_layout
1271 );
1272
1273 CX_TEST_ASSERT(failed == NULL);
1274 CX_TEST_ASSERT(processed == 4);
1275 CX_TEST_ASSERT(talloc.alloc_total == 4);
1276
1277 CX_TEST_ASSERT(home.children == home.last_child);
1278 tree_node_file *foo = home.children;
1279 CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
1280 CX_TEST_ASSERT(foo->children == foo->last_child);
1281 tree_node_file *bar = foo->children;
1282 CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
1283 CX_TEST_ASSERT(usr.children != usr.last_child);
1284 tree_node_file *lib64 = usr.last_child;
1285 CX_TEST_ASSERT(lib64 != NULL);
1286 CX_TEST_ASSERT(lib64->path == paths[2]);
1287 CX_TEST_ASSERT(lib64->prev == &lib);
1288 CX_TEST_ASSERT(lib64->parent == &usr);
1289 CX_TEST_ASSERT(lib.children != NULL);
1290 tree_node_file *libfoo = lib.children;
1291 CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
1292
1293 cxFree(alloc, foo);
1294 cxFree(alloc, bar);
1295 cxFree(alloc, lib64);
1296 cxFree(alloc, libfoo);
1297
1298 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1299 }
1300 cx_testing_allocator_destroy(&talloc);
1301 }
1302
1303 CX_TEST(test_tree_add_many_with_dupl_and_no_match) {
1304 CxTestingAllocator talloc;
1305 cx_testing_allocator_init(&talloc);
1306 CxAllocator *alloc = &talloc.base;
1307
1308 tree_node_file root = {0};
1309 root.path = "/mnt/";
1310
1311 CX_TEST_DO {
1312 tree_node_file *failed;
1313
1314 char const *paths[] = {
1315 "/mnt/sdcard/",
1316 "/mnt/foo/",
1317 "/mnt/sdcard/",
1318 "/home/",
1319 "/usr/"
1320 };
1321
1322 size_t processed = cx_tree_add_array(
1323 paths, 5, sizeof(char const *),
1324 tree_node_file_search,
1325 create_tree_node_file, alloc,
1326 (void **) &failed, &root, tree_node_file_layout
1327 );
1328
1329 CX_TEST_ASSERT(processed == 3);
1330 CX_TEST_ASSERT(failed != NULL);
1331 CX_TEST_ASSERT(failed->parent == NULL);
1332 CX_TEST_ASSERT(failed->children == NULL);
1333 CX_TEST_ASSERT(strcmp(failed->path, "/home/") == 0);
1334 cxFree(alloc, failed);
1335
1336 CX_TEST_ASSERT(root.children != root.last_child);
1337 CX_TEST_ASSERT(strcmp(root.children->path, "/mnt/sdcard/") == 0);
1338 CX_TEST_ASSERT(strcmp(root.last_child->path, "/mnt/sdcard/") == 0);
1339 CX_TEST_ASSERT(strcmp(root.children->next->path, "/mnt/foo/") == 0);
1340 CX_TEST_ASSERT(strcmp(root.last_child->prev->path, "/mnt/foo/") == 0);
1341
1342 CxTreeIterator iter = cx_tree_iterator(
1343 &root, true,
1344 offsetof(tree_node_file, children),
1345 offsetof(tree_node_file, next)
1346 );
1347 cx_foreach(tree_node_file *, node, iter) {
1348 if (iter.exiting) {
1349 if (node != &root) {
1350 cxFree(alloc, node);
1351 }
1352 }
1353 }
1354
1355 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1356 }
1357 cx_testing_allocator_destroy(&talloc);
1358 }
1359
1360 static CX_TEST_SUBROUTINE(test_tree_add_create_from_array_impl,
1361 CxAllocator *alloc, char const **paths) {
1362 tree_node_file root = {0};
1363 root.path = "/";
1364
1365 void *failed;
1366 size_t processed = cx_tree_add_array(
1367 paths, 10, sizeof(char const *),
1368 tree_node_file_search,
1369 create_tree_node_file, alloc,
1370 &failed, &root, tree_node_file_layout
1371 );
1372
1373 CX_TEST_ASSERT(failed == NULL);
1374 CX_TEST_ASSERT(processed == 10);
1375
1376 char const *exp_order[] = {
1377 "/",
1378 "/usr/",
1379 "/usr/lib/",
1380 "/usr/lib/libbumm.so",
1381 "/home/",
1382 "/home/foo/",
1383 "/var/",
1384 "/var/www/",
1385 "/var/www/vhosts/",
1386 "/var/www/vhosts/live/",
1387 "/var/www/vhosts/live/htdocs/"
1388 };
1389 unsigned exp_depth[] = {
1390 1,
1391 2,
1392 3,
1393 4,
1394 2,
1395 3,
1396 2,
1397 3,
1398 4,
1399 5,
1400 6
1401 };
1402
1403 CxTreeIterator iter = cx_tree_iterator(
1404 &root, true,
1405 offsetof(tree_node_file, children),
1406 offsetof(tree_node_file, next)
1407 );
1408 cx_foreach(tree_node_file *, node, iter) {
1409 if (iter.exiting) {
1410 if (node != &root) {
1411 cxFree(alloc, node);
1412 }
1413 } else {
1414 CX_TEST_ASSERT(iter.counter <= 11);
1415 CX_TEST_ASSERT(iter.depth == exp_depth[iter.counter - 1]);
1416 CX_TEST_ASSERT(strcmp(node->path, exp_order[iter.counter - 1]) == 0);
1417 }
1418 }
1419 }
1420
1421 CX_TEST(test_tree_add_create_from_array) {
1422 // creates an entirely new tree from an array
1423
1424 CxTestingAllocator talloc;
1425 cx_testing_allocator_init(&talloc);
1426 CxAllocator *alloc = &talloc.base;
1427
1428 CX_TEST_DO {
1429 char const *paths[] = {
1430 "/usr/",
1431 "/home/",
1432 "/usr/lib/",
1433 "/usr/lib/libbumm.so",
1434 "/var/",
1435 "/var/www/",
1436 "/var/www/vhosts/",
1437 "/var/www/vhosts/live/",
1438 "/var/www/vhosts/live/htdocs/",
1439 "/home/foo/"
1440 };
1441
1442 char const *scrambled_paths[] = {
1443 "/usr/",
1444 "/home/",
1445 "/var/www/vhosts/live/",
1446 "/usr/lib/",
1447 "/var/",
1448 "/var/www/",
1449 "/usr/lib/libbumm.so",
1450 "/var/www/vhosts/",
1451 "/var/www/vhosts/live/htdocs/",
1452 "/home/foo/"
1453 };
1454
1455 // no matter how the original array is sorted,
1456 // the resulting tree should be the same
1457 CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
1458 paths);
1459 CX_TEST_CALL_SUBROUTINE(test_tree_add_create_from_array_impl, alloc,
1460 scrambled_paths);
1461
1462 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1463 }
1464 cx_testing_allocator_destroy(&talloc);
1465 }
1466
995 1467
996 CxTestSuite *cx_test_suite_tree_low_level(void) { 1468 CxTestSuite *cx_test_suite_tree_low_level(void) {
997 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 1469 CxTestSuite *suite = cx_test_suite_new("tree (low level)");
998 1470
999 cx_test_register(suite, test_tree_link_new_child); 1471 cx_test_register(suite, test_tree_link_new_child);
1014 cx_test_register(suite, test_tree_visitor_no_children); 1486 cx_test_register(suite, test_tree_visitor_no_children);
1015 cx_test_register(suite, test_tree_visitor_no_branching); 1487 cx_test_register(suite, test_tree_visitor_no_branching);
1016 cx_test_register(suite, test_tree_visitor_continue); 1488 cx_test_register(suite, test_tree_visitor_continue);
1017 cx_test_register(suite, test_tree_iterator_continue); 1489 cx_test_register(suite, test_tree_iterator_continue);
1018 cx_test_register(suite, test_tree_iterator_continue_with_exit); 1490 cx_test_register(suite, test_tree_iterator_continue_with_exit);
1491 cx_test_register(suite, test_tree_add_one);
1492 cx_test_register(suite, test_tree_add_one_existing);
1493 cx_test_register(suite, test_tree_add_one_no_match);
1494 cx_test_register(suite, test_tree_add_duplicate_root);
1495 cx_test_register(suite, test_tree_add_zero);
1496 cx_test_register(suite, test_tree_add_many);
1497 cx_test_register(suite, test_tree_add_many_with_dupl_and_no_match);
1498 cx_test_register(suite, test_tree_add_create_from_array);
1019 1499
1020 return suite; 1500 return suite;
1021 } 1501 }

Mercurial Repository: ucx

mercurial