X-Git-Url: https://feistymeow.org/gitweb/?a=blobdiff_plain;f=nucleus%2Flibrary%2Fnodes%2Ftree.cpp;h=2a1300dab06d1e65eb1512a1c43cfa1aa4faab07;hb=c28dc24c2c63c4b505009a911083245e1c87ebe8;hp=a087b0b74edaeb032771f1b725eb80d3a4e000bb;hpb=457b128b77b5b4a0b7dd3094de543de2ce1477ad;p=feisty_meow.git diff --git a/nucleus/library/nodes/tree.cpp b/nucleus/library/nodes/tree.cpp index a087b0b7..2a1300da 100644 --- a/nucleus/library/nodes/tree.cpp +++ b/nucleus/library/nodes/tree.cpp @@ -17,14 +17,18 @@ #include #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 { @@ -50,12 +54,12 @@ bool tree::iterator::next_node(tree *&to_return) #ifdef DEBUG_TREE FUNCDEF("next_node"); #endif - to_return = NIL; + to_return = NULL_POINTER; #ifdef DEBUG_TREE if ( (_order != to_branches) && (_order != reverse_branches) ) { - if (_aim == AWAY_FROM_ROOT) LOG("going down") - else LOG("going up"); + if (_aim == AWAY_FROM_ROOT) LOG("going down...") + else LOG("going up..."); } #endif switch (_order) { @@ -255,7 +259,7 @@ tree *tree::iterator::next() #ifdef DEBUG_TREE FUNCDEF("next"); #endif - tree *to_return = NIL; + tree *to_return = NULL_POINTER; bool found_tree = false; while (!found_tree) { bool still_running = next_node(to_return); @@ -270,18 +274,156 @@ tree *tree::iterator::next() tree::tree() : node(1) -{ set_link(BACKWARDS_BRANCH, NIL); } +{ set_link(BACKWARDS_BRANCH, NULL_POINTER); } tree::~tree() { - // 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); + FUNCDEF("destructor"); +#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 0 + //hmmm: clean this code when it's been examined long enough. maybe already. +LOG("old code for tree destructor activating..."); + + //original version suffers from being too recursive on windoze, + //which blows out the stack. linux never showed this problem. so, i + //guess i'm glad i tested on windows. + //anyway, it's a general problem for a degenerate tree like the one + //i've constructed. current version has ~40000 direct descendants of + //the root in a single line, so the stack has to support 40000 frames + //for the delete implementation below to work. // 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. +#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. + 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 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. + +LOG("tree dtor: reset currnode, about to whack wayback..."); + + 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. +LOG("tree dtor: spidering to node below..."); + 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 } tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); } @@ -291,7 +433,7 @@ int tree::branches() const { return links() - 1; } tree *tree::branch(int branch_number) const { branch_number++; - bounds_return(branch_number, 1, branches(), NIL); + bounds_return(branch_number, 1, branches(), NULL_POINTER); return (tree *)get_link(branch_number); } @@ -301,8 +443,8 @@ int tree::which(tree *branch_to_find) const tree *tree::root() const { const tree *traveler = this; - // keep looking at the backwards branch until it is a NIL. the tree with - // a NIL BACKWARDS_BRANCH is the root. return that tree. + // keep looking at the backwards branch until it is a NULL_POINTER. the tree with + // a NULL_POINTER BACKWARDS_BRANCH is the root. return that tree. while (traveler->get_link(BACKWARDS_BRANCH)) traveler = (tree *)traveler->get_link(BACKWARDS_BRANCH); return const_cast(traveler); @@ -318,7 +460,7 @@ void tree::attach(tree *new_branch) void tree::insert(int branch_place, tree *new_branch) { branch_place++; - insert_link(links(), NIL); + insert_link(links(), NULL_POINTER); if (branch_place >= links()) branch_place = links() - 1; for (int i = links() - 1; i > branch_place; i--) @@ -336,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); - that_branch->set_link(BACKWARDS_BRANCH, NIL); +#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; } @@ -364,7 +519,7 @@ if (to_follow.size()) {} /* tree *traveller = this; path to_accumulate(root()); - while (traveller->parent() != NIL) { + while (traveller->parent() != NULL_POINTER) { // int branch_number = traveller->parent()->which(traveller); // if (branch_number == BRANCH_NOT_FOUND) non_continuable_error // (class_name(), "generate_path", "branch not found during path construction");