Mercurial > hg > ucx / file comparison

comparison: tests/test_tree.c

tests/test_tree.c

branch
feature/tree_add
changeset 866
1f636de4a63f
parent 862
387414a7afd8
child 871
e29c1f96646d
equal deleted inserted replaced
865:4b325b639117 866:1f636de4a63f
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 const *nptr,
64 void *allocator) {
65 if (allocator == NULL) allocator = cxDefaultAllocator;
66
67 char const *data = dptr;
68 tree_node_file const *existing = nptr;
69
70 if (existing != NULL && strcmp(existing->path, data) == 0) {
71 return (void *) existing;
72 } else {
73 tree_node_file *node = cxMalloc(allocator, sizeof(tree_node_file));
74
75 node->path = data;
76
77 // intentionally write garbage into the pointers, it's part of the test
78 node->parent = (void *) 0xf00ba1;
79 node->next = (void *) 0xf00ba2;
80 node->prev = (void *) 0xf00ba3;
81 node->children = (void *) 0xf00ba4;
82 node->last_child = (void *) 0xf00ba5;
83
84 return node;
85 }
86 }
87
88 static int tree_node_file_search(void const *nptr, void const *data) {
89 tree_node_file const *node = nptr;
90 size_t len1 = strlen(node->path);
91 size_t len2 = strlen(data);
92 if (len1 <= len2) {
93 if (memcmp(node->path, data, len1) == 0) {
94 return (int) (len2 - len1);
95 } else {
96 return -1;
97 }
98 } else {
99 return -1;
100 }
101 }
102
52 #define tree_node_layout \ 103 #define tree_node_layout \
53 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ 104 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \
54 offsetof(tree_node, prev), offsetof(tree_node, next) 105 offsetof(tree_node, prev), offsetof(tree_node, next)
55 #define tree_node2_layout \ 106 #define tree_node_full_layout(structname) \
56 offsetof(tree_node2, parent), offsetof(tree_node2, children),\ 107 offsetof(structname, parent), offsetof(structname, children),\
57 offsetof(tree_node2, last_child), \ 108 offsetof(structname, last_child), \
58 offsetof(tree_node2, prev), offsetof(tree_node2, next) 109 offsetof(structname, prev), offsetof(structname, next)
110 #define tree_node2_layout tree_node_full_layout(tree_node2)
111 #define tree_node_file_layout tree_node_full_layout(tree_node_file)
59 112
60 #define tree_children(type) offsetof(type, children), offsetof(type, next) 113 #define tree_children(type) offsetof(type, children), offsetof(type, next)
61 114
62 CX_TEST(test_tree_link_new_child) { 115 CX_TEST(test_tree_link_new_child) {
63 tree_node parent = {0}; 116 tree_node parent = {0};
990 CX_TEST_ASSERT(cb.data == 0); 1043 CX_TEST_ASSERT(cb.data == 0);
991 CX_TEST_ASSERT(cc.data == 0); 1044 CX_TEST_ASSERT(cc.data == 0);
992 CX_TEST_ASSERT(cba.data == 0); 1045 CX_TEST_ASSERT(cba.data == 0);
993 } 1046 }
994 } 1047 }
1048
1049 CX_TEST(test_tree_add_one) {
1050 CxTestingAllocator talloc;
1051 cx_testing_allocator_init(&talloc);
1052 CxAllocator *alloc = &talloc.base;
1053
1054 tree_node_file root = {0};
1055 root.path = "/";
1056 tree_node_file usr = {0};
1057 usr.path = "/usr/";
1058 cx_tree_link(&root, &usr, tree_node_file_layout);
1059 tree_node_file home = {0};
1060 home.path = "/home/";
1061 cx_tree_link(&root, &home, tree_node_file_layout);
1062 tree_node_file lib = {0};
1063 lib.path = "/usr/lib/";
1064 cx_tree_link(&usr, &lib, tree_node_file_layout);
1065
1066 CX_TEST_DO {
1067 void *newroot = &root;
1068
1069 tree_node_file *foo = cx_tree_add(
1070 "/home/foo/",
1071 tree_node_file_search,
1072 create_tree_node_file, alloc,
1073 &newroot, tree_node_file_layout
1074 );
1075 CX_TEST_ASSERT(newroot == &root);
1076 tree_node_file *bar = cx_tree_add(
1077 "/home/foo/bar/",
1078 tree_node_file_search,
1079 create_tree_node_file, alloc,
1080 &newroot, tree_node_file_layout
1081 );
1082 CX_TEST_ASSERT(newroot == &root);
1083
1084 CX_TEST_ASSERT(bar->parent == foo);
1085 CX_TEST_ASSERT(foo->parent == &home);
1086
1087 CX_TEST_ASSERT(talloc.alloc_total == 2);
1088
1089 cxFree(&talloc.base, foo);
1090 cxFree(&talloc.base, bar);
1091
1092 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1093 }
1094 cx_testing_allocator_destroy(&talloc);
1095 }
1096
1097 CX_TEST(test_tree_add_one_to_empty_tree) {
1098 tree_node_file *node = NULL;
1099 CX_TEST_DO {
1100 tree_node_file *root = NULL;
1101 char const *data = "/home/foo/bar/";
1102
1103 node = cx_tree_add(
1104 data,
1105 tree_node_file_search,
1106 create_tree_node_file, NULL,
1107 (void **) &root, tree_node_file_layout
1108 );
1109
1110 CX_TEST_ASSERT(root != NULL);
1111 CX_TEST_ASSERT(root->path == data);
1112 CX_TEST_ASSERT(root->next == NULL);
1113 CX_TEST_ASSERT(root->prev == NULL);
1114 CX_TEST_ASSERT(root->children == NULL);
1115 CX_TEST_ASSERT(root->last_child == NULL);
1116 CX_TEST_ASSERT(root->parent == NULL);
1117 }
1118 free(node);
1119 }
1120
1121 CX_TEST(test_tree_add_one_existing) {
1122 CxTestingAllocator talloc;
1123 cx_testing_allocator_init(&talloc);
1124 CxAllocator *alloc = &talloc.base;
1125
1126 tree_node_file root = {0};
1127 root.path = "/";
1128 tree_node_file usr = {0};
1129 usr.path = "/usr/";
1130 cx_tree_link(&root, &usr, tree_node_file_layout);
1131 tree_node_file home = {0};
1132 home.path = "/home/";
1133 cx_tree_link(&root, &home, tree_node_file_layout);
1134 tree_node_file lib = {0};
1135 lib.path = "/usr/lib/";
1136 cx_tree_link(&usr, &lib, tree_node_file_layout);
1137
1138 CX_TEST_DO {
1139 void *newroot = &root;
1140
1141 tree_node_file *node;
1142 node = cx_tree_add(
1143 "/usr/lib/",
1144 tree_node_file_search,
1145 create_tree_node_file, alloc,
1146 &newroot, tree_node_file_layout
1147 );
1148 CX_TEST_ASSERT(newroot == &root);
1149 CX_TEST_ASSERT(node == &lib);
1150
1151 node = cx_tree_add(
1152 "/home/",
1153 tree_node_file_search,
1154 create_tree_node_file, alloc,
1155 &newroot, tree_node_file_layout
1156 );
1157 CX_TEST_ASSERT(newroot == &root);
1158 CX_TEST_ASSERT(node == &home);
1159
1160 CX_TEST_ASSERT(talloc.alloc_total == 0);
1161 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1162 }
1163 cx_testing_allocator_destroy(&talloc);
1164 }
1165
1166 CX_TEST(test_tree_add_many) {
1167 // adds many elements to an existing tree
1168
1169 CxTestingAllocator talloc;
1170 cx_testing_allocator_init(&talloc);
1171 CxAllocator *alloc = &talloc.base;
1172
1173 tree_node_file root = {0};
1174 root.path = "/";
1175 tree_node_file usr = {0};
1176 usr.path = "/usr/";
1177 cx_tree_link(&root, &usr, tree_node_file_layout);
1178 tree_node_file home = {0};
1179 home.path = "/home/";
1180 cx_tree_link(&root, &home, tree_node_file_layout);
1181 tree_node_file lib = {0};
1182 lib.path = "/usr/lib/";
1183 cx_tree_link(&usr, &lib, tree_node_file_layout);
1184
1185 CX_TEST_DO {
1186 void *newroot = &root;
1187
1188 char const *paths[] = {
1189 "/home/foo/",
1190 "/home/foo/bar",
1191 "/usr/lib64/",
1192 "/usr/lib/foo.so"
1193 };
1194
1195 size_t processed = cx_tree_add_array(
1196 paths, 4, sizeof(char const *),
1197 tree_node_file_search,
1198 create_tree_node_file, alloc,
1199 &newroot, tree_node_file_layout
1200 );
1201 CX_TEST_ASSERT(newroot == &root);
1202
1203 CX_TEST_ASSERT(processed == 4);
1204 CX_TEST_ASSERT(talloc.alloc_total == 4);
1205
1206 CX_TEST_ASSERT(home.children == home.last_child);
1207 tree_node_file *foo = home.children;
1208 CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
1209 CX_TEST_ASSERT(foo->children == foo->last_child);
1210 tree_node_file *bar = foo->children;
1211 CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
1212 CX_TEST_ASSERT(usr.children != usr.last_child);
1213 tree_node_file *lib64 = usr.last_child;
1214 CX_TEST_ASSERT(lib64 != NULL);
1215 CX_TEST_ASSERT(lib64->path == paths[2]);
1216 CX_TEST_ASSERT(lib64->prev == &lib);
1217 CX_TEST_ASSERT(lib64->parent == &usr);
1218 CX_TEST_ASSERT(lib.children != NULL);
1219 tree_node_file *libfoo = lib.children;
1220 CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
1221
1222 cxFree(&talloc.base, foo);
1223 cxFree(&talloc.base, bar);
1224 cxFree(&talloc.base, lib64);
1225 cxFree(&talloc.base, libfoo);
1226
1227 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1228 }
1229 cx_testing_allocator_destroy(&talloc);
1230 }
1231
1232 CX_TEST(test_tree_add_many_skip_duplicates) {
1233 // adds many elements to an existing tree
1234 CxTestingAllocator talloc;
1235 cx_testing_allocator_init(&talloc);
1236 CxAllocator *alloc = &talloc.base;
1237
1238 tree_node_file root = {0};
1239 root.path = "/";
1240 tree_node_file usr = {0};
1241 usr.path = "/usr/";
1242 cx_tree_link(&root, &usr, tree_node_file_layout);
1243 tree_node_file home = {0};
1244 home.path = "/home/";
1245 cx_tree_link(&root, &home, tree_node_file_layout);
1246 tree_node_file lib = {0};
1247 lib.path = "/usr/lib/";
1248 cx_tree_link(&usr, &lib, tree_node_file_layout);
1249
1250 CX_TEST_DO {
1251 void *newroot = &root;
1252
1253 char const *paths[] = {
1254 "/home/foo/",
1255 "/home/foo/bar",
1256 "/usr/lib/",
1257 "/usr/lib/foo.so"
1258 };
1259
1260 size_t processed = cx_tree_add_array(
1261 paths, 4, sizeof(char const *),
1262 tree_node_file_search,
1263 create_tree_node_file, alloc,
1264 &newroot, tree_node_file_layout
1265 );
1266 CX_TEST_ASSERT(newroot == &root);
1267
1268 CX_TEST_ASSERT(processed == 4);
1269 CX_TEST_ASSERT(talloc.alloc_total == 3);
1270
1271 CX_TEST_ASSERT(home.children == home.last_child);
1272 tree_node_file *foo = home.children;
1273 CX_TEST_ASSERT(foo != NULL && foo->path == paths[0]);
1274 CX_TEST_ASSERT(foo->children == foo->last_child);
1275 tree_node_file *bar = foo->children;
1276 CX_TEST_ASSERT(bar != NULL && bar->path == paths[1]);
1277 CX_TEST_ASSERT(usr.children == usr.last_child);
1278 CX_TEST_ASSERT(usr.children == &lib);
1279 CX_TEST_ASSERT(lib.children != NULL);
1280 tree_node_file *libfoo = lib.children;
1281 CX_TEST_ASSERT(libfoo != NULL && libfoo->path == paths[3]);
1282
1283 cxFree(&talloc.base, foo);
1284 cxFree(&talloc.base, bar);
1285 cxFree(&talloc.base, libfoo);
1286
1287 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1288 }
1289 cx_testing_allocator_destroy(&talloc);
1290 }
1291
1292 CX_TEST(test_tree_add_create_from_array) {
1293 // creates an entirely new tree from an array
1294 CX_TEST_DO {
1295
1296 }
1297 }
1298
995 1299
996 CxTestSuite *cx_test_suite_tree_low_level(void) { 1300 CxTestSuite *cx_test_suite_tree_low_level(void) {
997 CxTestSuite *suite = cx_test_suite_new("tree (low level)"); 1301 CxTestSuite *suite = cx_test_suite_new("tree (low level)");
998 1302
999 cx_test_register(suite, test_tree_link_new_child); 1303 cx_test_register(suite, test_tree_link_new_child);
1014 cx_test_register(suite, test_tree_visitor_no_children); 1318 cx_test_register(suite, test_tree_visitor_no_children);
1015 cx_test_register(suite, test_tree_visitor_no_branching); 1319 cx_test_register(suite, test_tree_visitor_no_branching);
1016 cx_test_register(suite, test_tree_visitor_continue); 1320 cx_test_register(suite, test_tree_visitor_continue);
1017 cx_test_register(suite, test_tree_iterator_continue); 1321 cx_test_register(suite, test_tree_iterator_continue);
1018 cx_test_register(suite, test_tree_iterator_continue_with_exit); 1322 cx_test_register(suite, test_tree_iterator_continue_with_exit);
1323 cx_test_register(suite, test_tree_add_one);
1324 cx_test_register(suite, test_tree_add_one_existing);
1325 cx_test_register(suite, test_tree_add_one_to_empty_tree);
1326 cx_test_register(suite, test_tree_add_many);
1327 cx_test_register(suite, test_tree_add_many_skip_duplicates);
1328 cx_test_register(suite, test_tree_add_create_from_array);
1019 1329
1020 return suite; 1330 return suite;
1021 } 1331 }

Mercurial Repository: ucx

mercurial