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); |