dav: comparison ucx/tree.c

-:b60487c3ec36
+:af685cc9d623
 cx_foreach(void *, elem, iter) {
 // investigate the current node
 int ret_elem = sfunc(elem, node);
 if (ret_elem == 0) {
 // if found, exit the search
-*result = (void *) elem;
+*result = elem;
 ret = 0;
 break;
 } else if (ret_elem > 0 && ret_elem < ret) {
 // new distance is better
 *result = elem;
 ret = ret_elem;
-} else {
+} else if (ret_elem < 0 || ret_elem > ret) {
 // not contained or distance is worse, skip entire subtree
 cxTreeIteratorContinue(iter);
 }
 // when we reached the max depth, skip the subtree
 }
 }
 if (children == NULL) {
 // search for the next node
-void *next;
+void *next = NULL;
 cx_tree_iter_search_next:
-// check if there is a sibling
+// check if there is a sibling, but only if we are not a (subtree-)root
 if (iter->exiting) {
 next = iter->node_next;
-} else {
+} else if (iter->depth > 1) {
 next = tree_next(iter->node);
 iter->node_next = next;
 }
 if (next == NULL) {
 // no sibling, we are done with this node and exit
 if (iter->depth == 1) {
 // there is no parent - we have iterated the entire tree
 // invalidate the iterator and free the node stack
 iter->node = iter->node_next = NULL;
 iter->stack_capacity = iter->depth = 0;
-free(iter->stack);
+cxFreeDefault(iter->stack);
 iter->stack = NULL;
 } else {
 // the parent node can be obtained from the top of stack
 // this way we can avoid the loc_parent in the iterator
 iter->depth--;
 iter.node_next = NULL;
 iter.exiting = false;
 iter.skip = false;
 // assign base iterator functions
-iter.base.mutating = false;
+iter.base.allow_remove = false;
 iter.base.remove = false;
 iter.base.current_impl = NULL;
 iter.base.valid = cx_tree_iter_valid;
 iter.base.next = cx_tree_iter_next;
 iter.base.current = cx_tree_iter_current;
 // visit the root node
 iter.node = root;
 if (root != NULL) {
 iter.stack_capacity = 16;
-iter.stack = malloc(sizeof(void *) * 16);
+iter.stack = cxMallocDefault(sizeof(void *) * 16);
 iter.stack[0] = root;
 iter.counter = 1;
 iter.depth = 1;
 } else {
 iter.stack_capacity = 0;
 static void cx_tree_visitor_enqueue_siblings(
 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
 node = tree_next(node);
 while (node != NULL) {
 struct cx_tree_visitor_queue_s *q;
-q = malloc(sizeof(struct cx_tree_visitor_queue_s));
+q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
 q->depth = iter->queue_last->depth;
 q->node = node;
 iter->queue_last->next = q;
 iter->queue_last = q;
 node = tree_next(node);
 } else {
 children = tree_children(iter->node);
 }
 if (children != NULL) {
 struct cx_tree_visitor_queue_s *q;
-q = malloc(sizeof(struct cx_tree_visitor_queue_s));
+q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
 q->depth = iter->depth + 1;
 q->node = children;
 if (iter->queue_last == NULL) {
 assert(iter->queue_next == NULL);
 iter->queue_next = q;
 iter->queue_next = q->next;
 if (iter->queue_next == NULL) {
 assert(iter->queue_last == q);
 iter->queue_last = NULL;
 }
-free(q);
+cxFreeDefault(q);
 }
 // increment the node counter
 iter->counter++;
 }
 iter.skip = false;
 iter.queue_next = NULL;
 iter.queue_last = NULL;
 // assign base iterator functions
-iter.base.mutating = false;
+iter.base.allow_remove = false;
 iter.base.remove = false;
 iter.base.current_impl = NULL;
 iter.base.valid = cx_tree_visitor_valid;
 iter.base.next = cx_tree_visitor_next;
 iter.base.current = cx_tree_visitor_current;
 return 0;
 }
 }
 // otherwise, create iterator and hand over to other function
-CxIterator iter = cxIterator(src, elem_size, num);
+CxIterator iter = cxIterator(src, elem_size, num, false);
 return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
 cfunc, cdata, failed, root,
 loc_parent, loc_children, loc_last_child,
 loc_prev, loc_next);
 }
 cx_tree_default_insert_element,
 cx_tree_default_insert_many,
 cx_tree_default_find
 };
-CxTree *cxTreeCreate(
+CxTree *cxTreeCreate(const CxAllocator *allocator,
-const CxAllocator *allocator,
 cx_tree_node_create_func create_func,
 cx_tree_search_func search_func,
 cx_tree_search_data_func search_data_func,
-ptrdiff_t loc_parent,
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-ptrdiff_t loc_children,
+ptrdiff_t loc_prev, ptrdiff_t loc_next
-ptrdiff_t loc_last_child,
-ptrdiff_t loc_prev,
-ptrdiff_t loc_next
 ) {
 if (allocator == NULL) {
 allocator = cxDefaultAllocator;
 }
 assert(create_func != NULL);
 cxTreeClear(tree);
 }
 cxFree(tree->allocator, tree);
 }
-CxTree *cxTreeCreateWrapped(
+CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
-const CxAllocator *allocator,
+ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
-void *root,
+ptrdiff_t loc_prev, ptrdiff_t loc_next) {
-ptrdiff_t loc_parent,
-ptrdiff_t loc_children,
-ptrdiff_t loc_last_child,
-ptrdiff_t loc_prev,
-ptrdiff_t loc_next
-) {
 if (allocator == NULL) {
 allocator = cxDefaultAllocator;
 }
 assert(root != NULL);
 tree->root = root;
 tree->size = cxTreeSubtreeSize(tree, root);
 return tree;
 }
-void cxTreeSetParent(
+void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
-CxTree *tree,
-void *parent,
-void *child
-) {
 size_t loc_parent = tree->loc_parent;
 if (tree_parent(child) == NULL) {
 tree->size++;
 }
 cx_tree_link(parent, child, cx_tree_node_layout(tree));
 }
-void cxTreeAddChildNode(
+void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) {
-CxTree *tree,
-void *parent,
-void *child
-) {
 cx_tree_link(parent, child, cx_tree_node_layout(tree));
 tree->size++;
 }
-int cxTreeAddChild(
+int cxTreeAddChild(CxTree *tree, void *parent, const void *data) {
-CxTree *tree,
-void *parent,
-const void *data) {
 void *node = tree->node_create(data, tree);
 if (node == NULL) return 1;
 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
 cx_tree_link(parent, node, cx_tree_node_layout(tree));
 tree->size++;
 return 0;
+}
+int cxTreeInsert(CxTree *tree, const void *data) {
+return tree->cl->insert_element(tree, data);
+}
+size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n) {
+return tree->cl->insert_many(tree, iter, n);
+}
+size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n) {
+if (n == 0) return 0;
+if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
+CxIterator iter = cxIterator(data, elem_size, n, false);
+return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
+}
+void *cxTreeFind( CxTree *tree, const void *data) {
+return tree->cl->find(tree, tree->root, data, 0);
+}
+void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth) {
+return tree->cl->find(tree, subtree_root, data, max_depth);
 }
 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
 CxTreeVisitor visitor = cx_tree_visitor(
 subtree_root,
 );
 while (cxIteratorValid(visitor)) {
 cxIteratorNext(visitor);
 }
 return visitor.depth;
+}
+size_t cxTreeSize(CxTree *tree) {
+return tree->size;
 }
 size_t cxTreeDepth(CxTree *tree) {
 CxTreeVisitor visitor = cx_tree_visitor(
 tree->root, tree->loc_children, tree->loc_next
 tree->size -= iter.counter;
 if (node == tree->root) {
 tree->root = NULL;
 }
 }
+void cxTreeIteratorDispose(CxTreeIterator *iter) {
+cxFreeDefault(iter->stack);
+iter->stack = NULL;
+}
+void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
+struct cx_tree_visitor_queue_s *q = visitor->queue_next;
+while (q != NULL) {
+struct cx_tree_visitor_queue_s *next = q->next;
+cxFreeDefault(q);
+q = next;
+}
+}
+CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) {
+return cx_tree_iterator(
+node, visit_on_exit,
+tree->loc_children, tree->loc_next
+);
+}
+CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
+return cx_tree_visitor(
+node, tree->loc_children, tree->loc_next
+);
+}
+CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit) {
+return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
+}
+CxTreeVisitor cxTreeVisit(CxTree *tree) {
+return cxTreeVisitSubtree(tree, tree->root);
+}

Mercurial > hg > dav / file comparison

comparison: ucx/tree.c

ucx/tree.c