Mercurial > hg > ucx / file comparison

comparison: src/tree.c

src/tree.c

changeset 905
39aa4f106a71
parent 904
cdc49211d87f
child 907
1f72fb9af87e
equal deleted inserted replaced
904:cdc49211d87f 905:39aa4f106a71
239 239
240 static void cx_tree_iter_next(void *it) { 240 static void cx_tree_iter_next(void *it) {
241 struct cx_tree_iterator_s *iter = it; 241 struct cx_tree_iterator_s *iter = it;
242 ptrdiff_t const loc_next = iter->loc_next; 242 ptrdiff_t const loc_next = iter->loc_next;
243 ptrdiff_t const loc_children = iter->loc_children; 243 ptrdiff_t const loc_children = iter->loc_children;
244 // protect us from misuse
245 if (!iter->base.valid(iter)) return;
244 246
245 void *children; 247 void *children;
246 248
247 // check if we are currently exiting or entering nodes 249 // check if we are currently exiting or entering nodes
248 if (iter->exiting) { 250 if (iter->exiting) {
324 CxTreeIterator iter; 326 CxTreeIterator iter;
325 iter.loc_children = loc_children; 327 iter.loc_children = loc_children;
326 iter.loc_next = loc_next; 328 iter.loc_next = loc_next;
327 iter.visit_on_exit = visit_on_exit; 329 iter.visit_on_exit = visit_on_exit;
328 330
329 // allocate stack 331 // initialize members
330 iter.stack_capacity = 16;
331 iter.stack = malloc(sizeof(void *) * 16);
332 iter.depth = 0;
333
334 // visit the root node
335 iter.node = root;
336 iter.node_next = NULL; 332 iter.node_next = NULL;
337 iter.counter = 1;
338 iter.depth = 1;
339 iter.stack[0] = root;
340 iter.exiting = false; 333 iter.exiting = false;
341 iter.skip = false; 334 iter.skip = false;
342 335
343 // assign base iterator functions 336 // assign base iterator functions
344 iter.base.mutating = false; 337 iter.base.mutating = false;
345 iter.base.remove = false; 338 iter.base.remove = false;
346 iter.base.current_impl = NULL; 339 iter.base.current_impl = NULL;
347 iter.base.valid = cx_tree_iter_valid; 340 iter.base.valid = cx_tree_iter_valid;
348 iter.base.next = cx_tree_iter_next; 341 iter.base.next = cx_tree_iter_next;
349 iter.base.current = cx_tree_iter_current; 342 iter.base.current = cx_tree_iter_current;
343
344 // visit the root node
345 iter.node = root;
346 if (root != NULL) {
347 iter.stack_capacity = 16;
348 iter.stack = malloc(sizeof(void *) * 16);
349 iter.stack[0] = root;
350 iter.counter = 1;
351 iter.depth = 1;
352 } else {
353 iter.stack_capacity = 0;
354 iter.stack = NULL;
355 iter.counter = 0;
356 iter.depth = 0;
357 }
350 358
351 return iter; 359 return iter;
352 } 360 }
353 361
354 static bool cx_tree_visitor_valid(const void *it) { 362 static bool cx_tree_visitor_valid(const void *it) {
377 iter->queue_last->next = NULL; 385 iter->queue_last->next = NULL;
378 } 386 }
379 387
380 static void cx_tree_visitor_next(void *it) { 388 static void cx_tree_visitor_next(void *it) {
381 struct cx_tree_visitor_s *iter = it; 389 struct cx_tree_visitor_s *iter = it;
390 // protect us from misuse
391 if (!iter->base.valid(iter)) return;
392
382 ptrdiff_t const loc_next = iter->loc_next; 393 ptrdiff_t const loc_next = iter->loc_next;
383 ptrdiff_t const loc_children = iter->loc_children; 394 ptrdiff_t const loc_children = iter->loc_children;
384 395
385 // add the children of the current node to the queue 396 // add the children of the current node to the queue
386 // unless the skip flag is set 397 // unless the skip flag is set
436 ) { 447 ) {
437 CxTreeVisitor iter; 448 CxTreeVisitor iter;
438 iter.loc_children = loc_children; 449 iter.loc_children = loc_children;
439 iter.loc_next = loc_next; 450 iter.loc_next = loc_next;
440 451
441 // allocate stack 452 // initialize members
442 iter.depth = 0;
443
444 // visit the root node
445 iter.node = root;
446 iter.counter = 1;
447 iter.depth = 1;
448 iter.skip = false; 453 iter.skip = false;
449 iter.queue_next = NULL; 454 iter.queue_next = NULL;
450 iter.queue_last = NULL; 455 iter.queue_last = NULL;
451 456
452 // assign base iterator functions 457 // assign base iterator functions
454 iter.base.remove = false; 459 iter.base.remove = false;
455 iter.base.current_impl = NULL; 460 iter.base.current_impl = NULL;
456 iter.base.valid = cx_tree_visitor_valid; 461 iter.base.valid = cx_tree_visitor_valid;
457 iter.base.next = cx_tree_visitor_next; 462 iter.base.next = cx_tree_visitor_next;
458 iter.base.current = cx_tree_visitor_current; 463 iter.base.current = cx_tree_visitor_current;
464
465 // visit the root node
466 iter.node = root;
467 if (root != NULL) {
468 iter.counter = 1;
469 iter.depth = 1;
470 } else {
471 iter.counter = 0;
472 iter.depth = 0;
473 }
459 474
460 return iter; 475 return iter;
461 } 476 }
462 477
463 static void cx_tree_add_link_duplicate( 478 static void cx_tree_add_link_duplicate(
745 cxFree(tree->allocator, failed); 760 cxFree(tree->allocator, failed);
746 } 761 }
747 return ins; 762 return ins;
748 } 763 }
749 764
765 static void *cx_tree_default_find(
766 CxTree *tree,
767 const void *subtree,
768 const void *data
769 ) {
770 if (tree->root == NULL) return NULL;
771
772 void *found;
773 if (0 == cx_tree_search_data(
774 subtree,
775 data,
776 tree->search_data,
777 &found,
778 tree->loc_children,
779 tree->loc_next
780 )) {
781 return found;
782 } else {
783 return NULL;
784 }
785 }
786
750 static cx_tree_class cx_tree_default_class = { 787 static cx_tree_class cx_tree_default_class = {
751 cx_tree_default_destructor, 788 cx_tree_default_destructor,
752 cx_tree_default_insert_element, 789 cx_tree_default_insert_element,
753 cx_tree_default_insert_many, 790 cx_tree_default_insert_many,
754 NULL, 791 cx_tree_default_find,
755 cx_tree_default_iterator, 792 cx_tree_default_iterator,
756 cx_tree_default_visitor 793 cx_tree_default_visitor
757 }; 794 };
758 795
759 CxTree *cxTreeCreate( 796 CxTree *cxTreeCreate(
760 const CxAllocator *allocator, 797 const CxAllocator *allocator,
761 cx_tree_node_create_func create_func, 798 cx_tree_node_create_func create_func,
762 cx_tree_search_func search_func, 799 cx_tree_search_func search_func,
800 cx_tree_search_data_func search_data_func,
763 ptrdiff_t loc_parent, 801 ptrdiff_t loc_parent,
764 ptrdiff_t loc_children, 802 ptrdiff_t loc_children,
765 ptrdiff_t loc_last_child, 803 ptrdiff_t loc_last_child,
766 ptrdiff_t loc_prev, 804 ptrdiff_t loc_prev,
767 ptrdiff_t loc_next 805 ptrdiff_t loc_next
771 809
772 tree->cl = &cx_tree_default_class; 810 tree->cl = &cx_tree_default_class;
773 tree->allocator = allocator; 811 tree->allocator = allocator;
774 tree->node_create = create_func; 812 tree->node_create = create_func;
775 tree->search = search_func; 813 tree->search = search_func;
814 tree->search_data = search_data_func;
776 tree->advanced_destructor = (cx_destructor_func2) cxFree; 815 tree->advanced_destructor = (cx_destructor_func2) cxFree;
777 tree->destructor_data = (void *) allocator; 816 tree->destructor_data = (void *) allocator;
778 tree->loc_parent = loc_parent; 817 tree->loc_parent = loc_parent;
779 tree->loc_children = loc_children; 818 tree->loc_children = loc_children;
780 tree->loc_last_child = loc_last_child; 819 tree->loc_last_child = loc_last_child;
785 824
786 return tree; 825 return tree;
787 } 826 }
788 827
789 CxTree *cxTreeCreateWrapped( 828 CxTree *cxTreeCreateWrapped(
829 const CxAllocator *allocator,
790 void *root, 830 void *root,
791 ptrdiff_t loc_parent, 831 ptrdiff_t loc_parent,
792 ptrdiff_t loc_children, 832 ptrdiff_t loc_children,
793 ptrdiff_t loc_last_child, 833 ptrdiff_t loc_last_child,
794 ptrdiff_t loc_prev, 834 ptrdiff_t loc_prev,
795 ptrdiff_t loc_next 835 ptrdiff_t loc_next
796 ) { 836 ) {
797 CxTree *tree = malloc(sizeof(CxTree)); 837 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
798 if (tree == NULL) return NULL; 838 if (tree == NULL) return NULL;
799 839
800 tree->cl = &cx_tree_default_class; 840 tree->cl = &cx_tree_default_class;
801 // set the allocator anyway, just in case... 841 // set the allocator anyway, just in case...
802 tree->allocator = cxDefaultAllocator; 842 tree->allocator = allocator;
803 tree->node_create = NULL; 843 tree->node_create = NULL;
804 tree->search = NULL; 844 tree->search = NULL;
845 tree->search_data = NULL;
846 tree->simple_destructor = NULL;
805 tree->advanced_destructor = NULL; 847 tree->advanced_destructor = NULL;
806 tree->destructor_data = NULL; 848 tree->destructor_data = NULL;
807 tree->loc_parent = loc_parent; 849 tree->loc_parent = loc_parent;
808 tree->loc_children = loc_children; 850 tree->loc_children = loc_children;
809 tree->loc_last_child = loc_last_child; 851 tree->loc_last_child = loc_last_child;
847 while (cxIteratorValid(visitor)) { 889 while (cxIteratorValid(visitor)) {
848 cxIteratorNext(visitor); 890 cxIteratorNext(visitor);
849 } 891 }
850 return visitor.depth; 892 return visitor.depth;
851 } 893 }
894
895 size_t cxTreeDepth(CxTree *tree) {
896 CxTreeVisitor visitor = tree->cl->visitor(tree);
897 while (cxIteratorValid(visitor)) {
898 cxIteratorNext(visitor);
899 }
900 return visitor.depth;
901 }
902
903 void cxTreeRemove(CxTree *tree, void *node) {
904 size_t subtree_size = cxTreeSubtreeSize(tree, node);
905 cx_tree_unlink(node, cx_tree_node_layout(tree));
906 tree->size -= subtree_size;
907 }

Mercurial Repository: ucx

mercurial