dav: comparison ucx/tree.c

-:e77ccf1c4bb3
+:4d58cbcc9efa
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
 #include "cx/tree.h"
-#include "cx/array_list.h"
 #include <assert.h>
 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
 iter->stack[iter->depth - 1] = next;
 }
 }
 } else {
 // node has children, push the first child onto the stack and enter it
-cx_array_simple_add(iter->stack, children);
+if (iter->stack_size >= iter->stack_capacity) {
+const size_t newcap = iter->stack_capacity + 8;
+if (cxReallocArrayDefault(&iter->stack, newcap, sizeof(void*))) {
+// we cannot return an error in this function
+abort(); // LCOV_EXCL_LINE
+}
+iter->stack_capacity = newcap;
+}
+iter->stack[iter->stack_size] = children;
+iter->stack_size++;
 iter->node = children;
 iter->counter++;
 }
 }
 ptrdiff_t loc_last_child,
 ptrdiff_t loc_prev,
 ptrdiff_t loc_next
 ) {
 *cnode = cfunc(src, cdata);
-if (*cnode == NULL) return 1;
+if (*cnode == NULL) return 1;  // LCOV_EXCL_LINE
 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
 void *match = NULL;
 int result = cx_tree_search(
 root,
 iter->next(iter)) {
 elem = *eptr;
 // create the new node
 void *new_node = cfunc(elem, cdata);
-if (new_node == NULL) return processed;
+if (new_node == NULL) return processed;  // LCOV_EXCL_LINE
 cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
 // start searching from current node
 void *match;
 int result;
 return 0;
 }
 }
 // otherwise, create iterator and hand over to other function
-CxIterator iter = cxIterator(src, elem_size, num, false);
+CxIterator iter = cxIterator(src, elem_size, num);
 return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
 cfunc, cdata, failed, root,
 loc_parent, loc_children, loc_last_child,
 loc_prev, loc_next);
 }
 const void *data
 ) {
 void *node;
 if (tree->root == NULL) {
 node = tree->node_create(data, tree);
-if (node == NULL) return 1;
+if (node == NULL) return 1;  // LCOV_EXCL_LINE
 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
 tree->root = node;
-tree->size = 1;
+tree->collection.size = 1;
 return 0;
 }
 int result = cx_tree_add(data, tree->search, tree->node_create,
 tree, &node, tree->root, cx_tree_node_layout(tree));
 if (0 == result) {
-tree->size++;
+tree->collection.size++;
 } else {
-cxFree(tree->allocator, node);
+cxFree(tree->collection.allocator, node);
 }
 return result;
 }
 static size_t cx_tree_default_insert_many(
 if (!iter->valid(iter)) return 0;
 if (tree->root == NULL) {
 // use the first element from the iter to create the root node
 void **eptr = iter->current(iter);
 void *node = tree->node_create(*eptr, tree);
-if (node == NULL) return 0;
+if (node == NULL) return 0;  // LCOV_EXCL_LINE
 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
 tree->root = node;
 ins = 1;
 iter->next(iter);
 }
 void *failed;
 ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
 tree, &failed, tree->root, cx_tree_node_layout(tree));
-tree->size += ins;
+tree->collection.size += ins;
 if (ins < n) {
-cxFree(tree->allocator, failed);
+cxFree(tree->collection.allocator, failed);
 }
 return ins;
 }
 static void *cx_tree_default_find(
 CxTree *tree,
 const void *subtree,
 const void *data,
 size_t depth
 ) {
-if (tree->root == NULL) return NULL;
+if (tree->root == NULL) return NULL;  // LCOV_EXCL_LINE
 void *found;
 if (0 == cx_tree_search_data(
 subtree,
 depth,
 }
 assert(create_func != NULL);
 assert(search_func != NULL);
 assert(search_data_func != NULL);
-CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
+CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
-if (tree == NULL) return NULL;
+if (tree == NULL) return NULL;  // LCOV_EXCL_LINE
 tree->cl = &cx_tree_default_class;
-tree->allocator = allocator;
+tree->collection.allocator = allocator;
 tree->node_create = create_func;
 tree->search = search_func;
 tree->search_data = search_data_func;
-tree->simple_destructor = NULL;
+tree->collection.advanced_destructor = (cx_destructor_func2) cxFree;
-tree->advanced_destructor = (cx_destructor_func2) cxFree;
+tree->collection.destructor_data = (void *) allocator;
-tree->destructor_data = (void *) allocator;
 tree->loc_parent = loc_parent;
 tree->loc_children = loc_children;
 tree->loc_last_child = loc_last_child;
 tree->loc_prev = loc_prev;
 tree->loc_next = loc_next;
-tree->root = NULL;
-tree->size = 0;
 return tree;
 }
 void cxTreeFree(CxTree *tree) {
 if (tree == NULL) return;
 if (tree->root != NULL) {
 cxTreeClear(tree);
 }
-cxFree(tree->allocator, tree);
+cxFree(tree->collection.allocator, tree);
 }
 CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
 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);
-CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
+CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
-if (tree == NULL) return NULL;
+if (tree == NULL) return NULL;  // LCOV_EXCL_LINE
 tree->cl = &cx_tree_default_class;
 // set the allocator anyway, just in case...
-tree->allocator = allocator;
+tree->collection.allocator = allocator;
-tree->node_create = NULL;
-tree->search = NULL;
-tree->search_data = NULL;
-tree->simple_destructor = NULL;
-tree->advanced_destructor = NULL;
-tree->destructor_data = NULL;
 tree->loc_parent = loc_parent;
 tree->loc_children = loc_children;
 tree->loc_last_child = loc_last_child;
 tree->loc_prev = loc_prev;
 tree->loc_next = loc_next;
 tree->root = root;
-tree->size = cxTreeSubtreeSize(tree, root);
+tree->collection.size = cxTreeSubtreeSize(tree, root);
 return tree;
 }
 void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
 size_t loc_parent = tree->loc_parent;
 if (tree_parent(child) == NULL) {
-tree->size++;
+tree->collection.size++;
 }
 cx_tree_link(parent, child, cx_tree_node_layout(tree));
 }
 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child) {
 cx_tree_link(parent, child, cx_tree_node_layout(tree));
-tree->size++;
+tree->collection.size++;
 }
 int cxTreeAddChild(CxTree *tree, void *parent, const void *data) {
 void *node = tree->node_create(data, tree);
-if (node == NULL) return 1;
+if (node == NULL) return 1; // LCOV_EXCL_LINE
 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
 cx_tree_link(parent, node, cx_tree_node_layout(tree));
-tree->size++;
+tree->collection.size++;
 return 0;
 }
 int cxTreeInsert(CxTree *tree, const void *data) {
 return tree->cl->insert_element(tree, data);
 }
 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);
+CxIterator iter = cxIterator(data, elem_size, n);
 return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
 }
 void *cxTreeFind( CxTree *tree, const void *data) {
 return tree->cl->find(tree, tree->root, data, 0);
 }
 return visitor.depth;
 }
 size_t cxTreeSize(CxTree *tree) {
-return tree->size;
+return tree->collection.size;
 }
 size_t cxTreeDepth(CxTree *tree) {
 CxTreeVisitor visitor = cx_tree_visitor(
 tree->root, tree->loc_children, tree->loc_next
 tree_children(node) = NULL;
 ptrdiff_t loc_last_child = tree->loc_last_child;
 if (loc_last_child >= 0) tree_last_child(node) = NULL;
 // the tree now has one member less
-tree->size--;
+tree->collection.size--;
 return 0;
 }
 void cxTreeRemoveSubtree(CxTree *tree, void *node) {
 if (node == tree->root) {
 tree->root = NULL;
-tree->size = 0;
+tree->collection.size = 0;
 return;
 }
 size_t subtree_size = cxTreeSubtreeSize(tree, node);
 cx_tree_unlink(node, cx_tree_node_layout(tree));
-tree->size -= subtree_size;
+tree->collection.size -= subtree_size;
 }
 int cxTreeDestroyNode(
 CxTree *tree,
 void *node,
 cx_tree_relink_func relink_func
 ) {
 int result = cxTreeRemoveNode(tree, node, relink_func);
 if (result == 0) {
-if (tree->simple_destructor) {
+cx_invoke_destructor(tree, node);
-tree->simple_destructor(node);
-}
-if (tree->advanced_destructor) {
-tree->advanced_destructor(tree->destructor_data, node);
-}
 return 0;
 } else {
 return result;
 }
 }
 node, true,
 tree->loc_children, tree->loc_next
 );
 cx_foreach(void *, child, iter) {
 if (iter.exiting) {
-if (tree->simple_destructor) {
+cx_invoke_destructor(tree, child);
-tree->simple_destructor(child);
+}
 }
-if (tree->advanced_destructor) {
+tree->collection.size -= iter.counter;
-tree->advanced_destructor(tree->destructor_data, child);
-}
-}
-}
-tree->size -= iter.counter;
 if (node == tree->root) {
 tree->root = NULL;
 }
 }
 while (q != NULL) {
 struct cx_tree_visitor_queue_s *next = q->next;
 cxFreeDefault(q);
 q = next;
 }
+visitor->queue_next = visitor->queue_last = NULL;
 }
 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) {
 return cx_tree_iterator(
 node, visit_on_exit,

Mercurial > hg > dav / file comparison

comparison: ucx/tree.c

ucx/tree.c