From c28dc24c2c63c4b505009a911083245e1c87ebe8 Mon Sep 17 00:00:00 2001 From: Chris Koeritz Date: Sun, 3 Oct 2021 11:23:53 -0400 Subject: [PATCH] implemented new working destructor for tree got tired of the wayback machine corrupting our nodes, so implemented a more elegant stack based solution. still iterative, but can have some weight in stack. preference is depth first; we add all the branches of current node (in reverse order) to stack, then start chewing on nodes in stack, where each node we pull out gets its kids added in reverse order and then node itself is eliminated. reverse order addition means preserved order on popping (first comes out first). adding kids to stack means that we should start processing first kid, then its first kid, then its first kid and so on. basically same order as previous algorithm, but without bizarre double whack problems. --- nucleus/library/nodes/symbol_tree.cpp | 53 +++--- nucleus/library/nodes/tree.cpp | 169 ++++++++++++++---- nucleus/library/tests_nodes/test_node.cpp | 2 + .../library/tests_nodes/test_symbol_tree.cpp | 23 ++- nucleus/library/tests_nodes/test_tree.cpp | 19 +- 5 files changed, 188 insertions(+), 78 deletions(-) diff --git a/nucleus/library/nodes/symbol_tree.cpp b/nucleus/library/nodes/symbol_tree.cpp index eb8b64c1..ba5c33f9 100644 --- a/nucleus/library/nodes/symbol_tree.cpp +++ b/nucleus/library/nodes/symbol_tree.cpp @@ -19,7 +19,7 @@ #include #include -#define DEBUG_SYMBOL_TREE +//#define DEBUG_SYMBOL_TREE // uncomment for totally noisy version. #include @@ -40,15 +40,6 @@ public: symbol_tree_associations(int estimated_elements) : symbol_table(estimated_elements) {} virtual ~symbol_tree_associations() { - -//hmmm: below was really wrong and things are still wrong because we're letting the symtab destruct our trees? -// real thing would be to just toss any pointers referenced in the sym tab here. -// OR... not at all because sym tab stores objects, and expects objects, and since a pointer isn't an object it will not auto-delete? - - -//hmmm: why was this here? was it ever needed? -//hmmm: maybe it's the missing link? - //probably we don't actually want to whack here??? // for (int i = 0; i < symbols(); i++) { // WHACK(use(i)); @@ -63,16 +54,23 @@ symbol_tree::symbol_tree(const astring &node_name, int estimated_elements) _associations(new symbol_tree_associations(estimated_elements)), _name(new astring(node_name)) { + FUNCDEF("constructor") } symbol_tree::~symbol_tree() { FUNCDEF("destructor"); -LOG("symtree dtor: prior to whacks"); +#ifdef DEBUG_SYMBOL_TREE + LOG("symtree dtor: prior to whacks"); +#endif WHACK(_associations); -LOG("symtree dtor: after whacking associations"); +#ifdef DEBUG_SYMBOL_TREE + LOG("symtree dtor: after whacking associations"); +#endif WHACK(_name); -LOG("symtree dtor: after all whacks"); +#ifdef DEBUG_SYMBOL_TREE + LOG("symtree dtor: after all whacks"); +#endif } int symbol_tree::children() const { return _associations->symbols(); } @@ -103,26 +101,33 @@ outcome symbol_tree::prune(tree *to_zap_in) FUNCDEF("prune"); #endif symbol_tree *to_zap = dynamic_cast(to_zap_in); - if (!to_zap) { + if (to_zap) { #ifdef DEBUG_SYMBOL_TREE - LOG("about to barf due to null symtree after dynamic cast."); + LOG(astring("zapping node for ") + to_zap->name()); #endif - throw("error: symbol_tree::prune: wrong type of node in prune"); - } + int found = which(to_zap); // find the node in the tree. + if (negative(found)) return common::NOT_FOUND; // not found. +#ifdef DEBUG_SYMBOL_TREE + int kids = _associations->symbols(); +#endif + _associations->whack(to_zap->name()); // remove from associations. #ifdef DEBUG_SYMBOL_TREE - LOG(astring("zapping node for ") + to_zap->name()); + if (kids - 1 != _associations->symbols()) + throw("error: symbol_tree::prune: failed to crop kid in symtab"); #endif - int found = which(to_zap); // find the node in the tree. - if (negative(found)) return common::NOT_FOUND; // not found. + } else { #ifdef DEBUG_SYMBOL_TREE - int kids = _associations->symbols(); + LOG("skip symtree prune steps due to null symtree after dynamic cast."); #endif - _associations->whack(to_zap->name()); // remove from associations. +///hmmm: how about not? throw("error: symbol_tree::prune: wrong type of node in prune"); + } #ifdef DEBUG_SYMBOL_TREE - if (kids - 1 != _associations->symbols()) - throw("error: symbol_tree::prune: failed to crop kid in symtab"); + LOG("about to call base tree::prune..."); #endif tree::prune(to_zap); // remove from tree. +#ifdef DEBUG_SYMBOL_TREE + LOG("after called base tree::prune."); +#endif return common::OKAY; } diff --git a/nucleus/library/nodes/tree.cpp b/nucleus/library/nodes/tree.cpp index 38105f74..2a1300da 100644 --- a/nucleus/library/nodes/tree.cpp +++ b/nucleus/library/nodes/tree.cpp @@ -18,16 +18,17 @@ #include #include #include +#include //#define DEBUG_TREE // uncomment if you want lots of debugging info. #undef LOG -///#define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s) #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), astring(s) + a_sprintf(" [obj=%p]", this)) using namespace basis; using namespace loggers; +using namespace structures; namespace nodes { @@ -278,14 +279,17 @@ tree::tree() tree::~tree() { FUNCDEF("destructor"); -LOG("entry to tree destructor"); - // must at least unhook ourselves from the parent so we don't become a lost - // cousin. - tree *my_parent = parent(); - if (my_parent) my_parent->prune(this); - my_parent = NULL_POINTER; // disavow since we are loose now. +#ifdef DEBUG_TREE + LOG("entry to tree destructor"); +#endif + { + // must at least unhook ourselves from the parent so we don't become a lost + // cousin. + tree *my_parent = parent(); + if (my_parent) my_parent->prune(this); + } -#if 1 +#if 0 //hmmm: clean this code when it's been examined long enough. maybe already. LOG("old code for tree destructor activating..."); @@ -300,47 +304,125 @@ LOG("old code for tree destructor activating..."); // iterate over the child nodes and whack each individually. while (branches()) delete branch(0); // this relies on the child getting out of our branch list. -#else -LOG("new code for tree destructor activating..."); +#endif + +#if 0 + LOG("new code for tree destructor activating..."); + +//hmmm: this new code stinks on ice. keeps doing something awful, either double deleting or deleting wrong thing. +// why didn't we just use our own iterator to traverse the tree depth first and clean that way?? // newer version of delete doesn't recurse; it just iterates instead, // which avoids the massive recursive depth of the original approach. - tree *curr_node = this; - tree *stop_node = this; // don't whack self. - while (curr_node != NULL_POINTER) { - // make a breadcrumb for getting back to 'here' in the tree. - tree *way_back = curr_node; - // our main operation here is to go down a node without using any - // stack frames. so we just pick the first kid; it's either valid - // or there are no kids at all. - curr_node = curr_node->branch(0); - - if (curr_node == NULL_POINTER) { - // wayback has no children, so we can take action. + while (branches()) { + // we know we have a branch to work on, due to conditional above. + tree *stop_node = branch(0); // don't whack the node we're at until we're done with its kids. + tree *curr_node = stop_node; + while (curr_node != NULL_POINTER) { + // make a breadcrumb for getting back to 'here' in the tree. + tree *way_back = curr_node; + // our main operation here is to go down a node without using any + // stack frames. so we just pick the first kid; it's either valid + // or there are no kids at all. + curr_node = curr_node->branch(0); + + if (curr_node == NULL_POINTER) { + // wayback has no children, so we can take action. LOG("tree dtor: can take action on childless node..."); - // if wayback is the same as "this", then we exit from iterations since - // we've cleaned all the kids out. - if (way_back == this) { -LOG("tree dtor: breaking out since at wayback node..."); - break; - } + // if wayback is the same as stop_node, then we exit from iterations since + // we've cleaned all the kids out. + if (way_back == stop_node) { +LOG("tree dtor: stopping since at wayback node..."); + // we can actually delete wayback here, because we are at the stopping point. + // and since a tree node whack removes it from its parent, we are clean one branch now. + WHACK(way_back); +LOG("tree dtor: whacked wayback before inner break."); + break; + } + + // we want to whack the wayback node at this point, since it's a parent + // with no kids, i.e. a leaf. we've guaranteed we're not going beyond + // our remit, since wayback is not the same node as the top level one + // in the destructor (as long as there are no cycles in the tree...). + curr_node = way_back->parent(); // go up in tree on next iteration. - // we want to whack the wayback node at this point, since it's a parent - // with no kids, i.e. a leaf. we've guaranteed we're not going beyond - // our remit, since wayback is not the same node as the top level one - // in the destructor (as long as there are no cycles in the tree...). - curr_node = way_back->parent(); // go up in tree on next iteration. LOG("tree dtor: reset currnode, about to whack wayback..."); - WHACK(way_back); // whack a node, finally. + + if (curr_node == stop_node) { +LOG("tree dtor: seeing curr_node hits our stop_node!"); +/// break; + } else if (curr_node == stop_node->parent()) { +LOG("tree dtor: seeing curr_node ABOVE our stop_node!"); + } + + WHACK(way_back); // whack a node, finally. + LOG("tree dtor: after whacking wayback..."); - } else { - // okay, there's a node below here. we will spider down to it. + } else { + // okay, there's a node below here. we will spider down to it. LOG("tree dtor: spidering to node below..."); - continue; + continue; + } } } +#endif +#if 1 +#ifdef DEBUG_TREE + LOG("newest code for tree destructor (stack based) activating..."); +#endif + + // this version of delete doesn't recurse; it just iterates instead, + // which avoids the massive recursive depth of the original approach. + // it does use a stack object however, but that will use main memory, + // which is usually in greater supply than stack/heap space. + + stack sleestak; // accumulates nodes that we still need to clean up. + + // iterate across this node first, to feed the stack. + // we feed it in reverse branch order, so that the first branch will be dealt with first (popped off stack first). + while (branches()) { + // get our current last branch... + tree *bran = branch(branches() - 1); + // pull that branch off the tree (non-destructively)... + prune(bran); + // and add that branch to the stack. +#ifdef DEBUG_TREE + LOG(a_sprintf("tree dtor: adding child %p on stack.", bran)); +#endif + sleestak.push(bran); + } + + // now iterate across our stack until we have dealt with every node in it. + while (sleestak.size()) { + + tree *popper = NULL_POINTER; + sleestak.acquire_pop(popper); +#ifdef DEBUG_TREE + LOG(a_sprintf("tree dtor: popped a tree %p off stack.", popper)); +#endif + + // familiar scheme below; push last branch first, then we'll pop first branch first. + while (popper->branches()) { + tree *bran = popper->branch(popper->branches() - 1); + popper->prune(bran); +#ifdef DEBUG_TREE + LOG(a_sprintf("tree dtor: inner, adding child %p on stack.", bran)); +#endif + sleestak.push(bran); + } + + // now the popper gets cleaned up; this should be totally safe since all its kids + // have been pruned and put into the stack. +#ifdef DEBUG_TREE + LOG(a_sprintf("tree dtor: about to zap a tree %p.", popper)); +#endif + WHACK(popper); +#ifdef DEBUG_TREE + LOG("tree dtor: whacked that tree."); +#endif + } #endif } @@ -396,11 +478,24 @@ outcome tree::prune(tree *branch_to_cut) outcome tree::prune_index(int branch_to_cut) { + FUNCDEF("prune_index"); branch_to_cut++; bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND); +#ifdef DEBUG_TREE + LOG(a_sprintf("got legit branch %d to cut", branch_to_cut)); +#endif tree *that_branch = (tree *)get_link(branch_to_cut); +#ifdef DEBUG_TREE + LOG(a_sprintf("whacking off branch %p", that_branch)); +#endif that_branch->set_link(BACKWARDS_BRANCH, NULL_POINTER); +#ifdef DEBUG_TREE + LOG(a_sprintf("zapping link branch %d", branch_to_cut)); +#endif zap_link(branch_to_cut); +#ifdef DEBUG_TREE + LOG("returning, finished."); +#endif return basis::common::OKAY; } diff --git a/nucleus/library/tests_nodes/test_node.cpp b/nucleus/library/tests_nodes/test_node.cpp index 82dfb77c..e76a8439 100644 --- a/nucleus/library/tests_nodes/test_node.cpp +++ b/nucleus/library/tests_nodes/test_node.cpp @@ -80,6 +80,8 @@ int test_node::execute() george.set_link(0, &g_end1); george.set_link(1, &g_end2); +//do some testing on those results!!! + return final_report(); } diff --git a/nucleus/library/tests_nodes/test_symbol_tree.cpp b/nucleus/library/tests_nodes/test_symbol_tree.cpp index 5ba5bd5f..64e917e0 100644 --- a/nucleus/library/tests_nodes/test_symbol_tree.cpp +++ b/nucleus/library/tests_nodes/test_symbol_tree.cpp @@ -41,12 +41,10 @@ using namespace unit_test; #define LOG(to_print) EMERGENCY_LOG(program_wide_logger().get(), astring(to_print)) -#define DEBUG_SYMBOL_TREE +//#define DEBUG_TEST_SYMBOL_TREE // how many nodes we add to the tree. -//const int MAX_NODES_TESTED = 40000; -//hmmm: TEMPORARY!!! -const int MAX_NODES_TESTED = 2; +const int MAX_NODES_TESTED = 40000; class test_symbol_tree : public unit_base, public application_shell { @@ -75,15 +73,26 @@ int test_symbol_tree::execute() astring rando = string_manipulation::make_random_name(1, 10); curr->add(new symbol_tree(rando)); } -LOG("about to whack dynamic tree..."); +#ifdef DEBUG_TEST_SYMBOL_TREE + LOG("about to whack dynamic tree..."); +#endif WHACK(t); -LOG("dynamic tree whacked."); + ASSERT_EQUAL(t, NULL_POINTER, "ensure pointer cleaned up"); +#ifdef DEBUG_TEST_SYMBOL_TREE + LOG("dynamic tree whacked."); +#endif } catch (...) { +#ifdef DEBUG_TEST_SYMBOL_TREE LOG("crashed during tree stuffing."); +#endif return 1; } -//hmmm: create a more balanced tree structure... + ASSERT_TRUE(true, "testing succeeded without cleanup crashes"); + + + +//hmmm: need more tests, like where we create a more balanced tree structure... // perform known operations and validate shape of tree. return final_report(); diff --git a/nucleus/library/tests_nodes/test_tree.cpp b/nucleus/library/tests_nodes/test_tree.cpp index 1b60c496..d0b0a434 100644 --- a/nucleus/library/tests_nodes/test_tree.cpp +++ b/nucleus/library/tests_nodes/test_tree.cpp @@ -1,15 +1,14 @@ /* -* Name : test_tree * -* Author : Chris Koeritz * -* Purpose: * -* Tests out the tree class. * +* Name : test_tree +* Author : Chris Koeritz +* Purpose: Tests out the tree class. ** -* Copyright (c) 1993-$now By Author. This program is free software; you can * -* redistribute it and/or modify it under the terms of the GNU General Public * -* License as published by the Free Software Foundation; either version 2 of * -* the License or (at your option) any later version. This is online at: * -* http://www.fsf.org/copyleft/gpl.html * -* Please send any updates to: fred@gruntose.com * +* Copyright (c) 1993-$now By Author. This program is free software; you can +* redistribute it and/or modify it under the terms of the GNU General Public +* License as published by the Free Software Foundation; either version 2 of +* the License or (at your option) any later version. This is online at: +* http://www.fsf.org/copyleft/gpl.html +* Please send any updates to: fred@gruntose.com */ #include -- 2.34.1