--- a/src/tree.c Mon Aug 19 18:46:49 2024 +0200
+++ b/src/tree.c Mon Aug 19 20:46:36 2024 +0200
@@ -40,6 +40,26 @@
#define tree_prev(node) CX_TREE_PTR(node, loc_prev)
#define tree_next(node) CX_TREE_PTR(node, loc_next)
+#define cx_tree_ptr_locations \
+ loc_parent, loc_children, loc_last_child, loc_prev, loc_next
+
+static void cx_tree_zero_pointers(
+ void *node,
+ ptrdiff_t loc_parent,
+ ptrdiff_t loc_children,
+ ptrdiff_t loc_last_child,
+ ptrdiff_t loc_prev,
+ ptrdiff_t loc_next
+) {
+ tree_parent(node) = NULL;
+ tree_prev(node) = NULL;
+ tree_next(node) = NULL;
+ tree_children(node) = NULL;
+ if (loc_last_child >= 0) {
+ tree_last_child(node) = NULL;
+ }
+}
+
void cx_tree_link(
void *restrict parent,
void *restrict node,
@@ -52,8 +72,7 @@
void *current_parent = tree_parent(node);
if (current_parent == parent) return;
if (current_parent != NULL) {
- cx_tree_unlink(node, loc_parent, loc_children, loc_last_child,
- loc_prev, loc_next);
+ cx_tree_unlink(node, cx_tree_ptr_locations);
}
if (tree_children(parent) == NULL) {
@@ -438,8 +457,50 @@
ptrdiff_t loc_prev,
ptrdiff_t loc_next
) {
- // TODO: implement
- return NULL;
+ if (*root == NULL) {
+ void *node = cfunc(src, NULL, cdata);
+ if (node == NULL) return NULL;
+ cx_tree_zero_pointers(node, cx_tree_ptr_locations);
+ *root = node;
+ return node;
+ }
+
+ void *match = NULL;
+ int result = cx_tree_search(
+ *root,
+ src,
+ sfunc,
+ &match,
+ loc_children,
+ loc_next
+ );
+
+ void *node;
+ if (result < 0) {
+ // new node is created as new parent
+ node = cfunc(src, NULL, cdata);
+ if (node == NULL) return NULL;
+ cx_tree_zero_pointers(node, cx_tree_ptr_locations);
+ cx_tree_link(node, *root, cx_tree_ptr_locations);
+ *root = node;
+ return node;
+ } else if (result == 0) {
+ // data already found in the tree, let cfunc decide
+ node = cfunc(src, match, cdata);
+ if (node == NULL) return NULL;
+ if (node != match) {
+ cx_tree_zero_pointers(node, cx_tree_ptr_locations);
+ cx_tree_link(match, node, cx_tree_ptr_locations);
+ }
+ } else {
+ // closest match found, add new node as child
+ node = cfunc(src, NULL, cdata);
+ if (node == NULL) return NULL;
+ cx_tree_zero_pointers(node, cx_tree_ptr_locations);
+ cx_tree_link(match, node, cx_tree_ptr_locations);
+ }
+
+ return node;
}
unsigned int cx_tree_add_look_around_depth = 3;
@@ -456,8 +517,87 @@
ptrdiff_t loc_prev,
ptrdiff_t loc_next
) {
- // TODO: implement
- return 0;
+ size_t processed = 0;
+ void *current_node = *root;
+ for (void **eptr;
+ iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
+ iter->next(iter)) {
+ void *elem = *eptr;
+
+ if (current_node == NULL) {
+ // no node in tree, yet - add a new one
+ current_node = cfunc(elem, NULL, cdata);
+ // node creation failed - stop processing
+ if (current_node == NULL) {
+ // but honestly... nothing should have been processed
+ assert(processed == 0);
+ return 0;
+ }
+ cx_tree_zero_pointers(current_node, cx_tree_ptr_locations);
+ *root = current_node;
+ processed++;
+ continue;
+ }
+
+ // start searching from current node
+ void *match;
+ int result;
+ unsigned int look_around_retries = cx_tree_add_look_around_depth;
+ cx_tree_add_look_around_retry:
+ result = cx_tree_search(
+ current_node,
+ elem,
+ sfunc,
+ &match,
+ loc_children,
+ loc_next
+ );
+
+ void *node;
+ if (result < 0) {
+ // traverse upwards and try to find better parents
+ void *parent = tree_parent(current_node);
+ if (parent != NULL) {
+ if (look_around_retries > 0) {
+ look_around_retries--;
+ current_node = parent;
+ } else {
+ // look around retries exhausted, start from the root
+ current_node = *root;
+ }
+ goto cx_tree_add_look_around_retry;
+ } else {
+ // no parents. so we (try to) create a new root node
+ void *new_root = cfunc(elem, NULL, cdata);
+ if (new_root == NULL) return processed;
+ cx_tree_zero_pointers(new_root, cx_tree_ptr_locations);
+ cx_tree_link(new_root, current_node, cx_tree_ptr_locations);
+ current_node = new_root;
+ *root = new_root;
+ }
+ } else if (result == 0) {
+ // data already found in the tree, let cfunc decide
+ node = cfunc(elem, match, cdata);
+ if (node == NULL) return processed;
+ if (node != match) {
+ cx_tree_zero_pointers(node, cx_tree_ptr_locations);
+ cx_tree_link(match, node, cx_tree_ptr_locations);
+ }
+ current_node = node;
+ } else {
+ // closest match found, add new node as child
+ node = cfunc(elem, NULL, cdata);
+ if (node == NULL) return processed;
+ cx_tree_zero_pointers(node, cx_tree_ptr_locations);
+ cx_tree_link(match, node, cx_tree_ptr_locations);
+ // but make the match current and not the new node
+ // (usually saves one traversal when a lot of siblings are added)
+ current_node = match;
+ }
+
+ processed++;
+ }
+ return processed;
}
size_t cx_tree_add_array(