#include <basis/common_outcomes.h>
#include <basis/functions.h>
#include <basis/guards.h>
+#include <loggers/program_wide_logger.h>
//#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(), s)
+#define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), astring(s) + a_sprintf(" [obj=%p]", this))
using namespace basis;
+using namespace loggers;
namespace nodes {
#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) {
#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);
tree::tree()
: node(1)
-{ set_link(BACKWARDS_BRANCH, NIL); }
+{ set_link(BACKWARDS_BRANCH, NULL_POINTER); }
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.
+
+#if 1
+ //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.
+#else
+LOG("new code for tree destructor activating...");
+
+ // 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.
+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;
+ }
+
+ // 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.
+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
}
tree *tree::parent() const { return (tree *)get_link(BACKWARDS_BRANCH); }
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);
}
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<tree *>(traveler);
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--)
branch_to_cut++;
bounds_return(branch_to_cut, 1, branches(), basis::common::NOT_FOUND);
tree *that_branch = (tree *)get_link(branch_to_cut);
- that_branch->set_link(BACKWARDS_BRANCH, NIL);
+ that_branch->set_link(BACKWARDS_BRANCH, NULL_POINTER);
zap_link(branch_to_cut);
return basis::common::OKAY;
}
/*
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");