#include <textual/parser_bits.h>
#include <textual/string_manipulation.h>
-#define DEBUG_SYMBOL_TREE
+//#define DEBUG_SYMBOL_TREE
// uncomment for totally noisy version.
#include <loggers/program_wide_logger.h>
symbol_tree_associations(int estimated_elements)
: symbol_table<symbol_tree *>(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));
_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(); }
FUNCDEF("prune");
#endif
symbol_tree *to_zap = dynamic_cast<symbol_tree *>(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;
}
#include <basis/functions.h>
#include <basis/guards.h>
#include <loggers/program_wide_logger.h>
+#include <structures/stack.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(), astring(s) + a_sprintf(" [obj=%p]", this))
using namespace basis;
using namespace loggers;
+using namespace structures;
namespace nodes {
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...");
// 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<tree *> 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
}
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;
}
projects / feisty_meow.git / commitdiff