1 /*****************************************************************************\
3 * Name : packable_tree *
4 * Author : Chris Koeritz *
6 *******************************************************************************
7 * Copyright (c) 1992-$now By Author. This program is free software; you can *
8 * redistribute it and/or modify it under the terms of the GNU General Public *
9 * License as published by the Free Software Foundation; either version 2 of *
10 * the License or (at your option) any later version. This is online at: *
11 * http://www.fsf.org/copyleft/gpl.html *
12 * Please send any updates to: fred@gruntose.com *
13 \*****************************************************************************/
15 #include "packable_tree.h"
17 #include <basis/astring.h>
18 #include <basis/byte_array.h>
19 #include <basis/guards.h>
20 #include <structures/object_packers.h>
21 #include <structures/stack.h>
23 using namespace basis;
24 using namespace structures;
26 //#define DEBUG_PACKABLE_TREE
27 // uncomment for noisy debugging.
30 #ifdef DEBUG_PACKABLE_TREE
32 #define LOG(to_print) printf("%s\n", astring(to_print).s());
34 #define LOG(s) { if (!!s) {} }
39 // tree commands are used to tell the unpacker what to do with the blobs
40 // it finds. BRANCHES_FOLLOW indicates that there are a few branches stored
41 // at the next few contiguous memory positions. ATTACH_BRANCHES means that
42 // the next branch should be the parent of some number of previous branches.
43 // FINISH means that the tree is done being stored (or reconstructed).
44 enum tree_commands { BRANCHES_FOLLOW, ATTACH_BRANCHES, FINISH };
48 packable_tree_factory::~packable_tree_factory() {}
52 //! the TCU stores a command about this packed unit's purpose, the number of branches held, and the size of the contents at this node.
53 struct tree_command_unit : public virtual packable
55 tree_commands command;
59 virtual ~tree_command_unit() {}
61 virtual int packed_size() const { return 3 * PACKED_SIZE_INT32; }
63 virtual void pack(byte_array &packed_form) const {
64 attach(packed_form, int(command));
65 attach(packed_form, number);
66 attach(packed_form, size);
69 virtual bool unpack(byte_array &packed_form) {
71 if (!detach(packed_form, cmd)) return false;
72 command = (tree_commands)cmd;
73 if (!detach(packed_form, number)) return false;
74 if (!detach(packed_form, size)) return false;
81 packable_tree::packable_tree() : tree() {}
83 void packable_tree::calcit(int &size_accumulator, const packable_tree *current_node)
85 LOG(a_sprintf("calcing node %x", current_node));
87 if (!current_node) throw_error(static_class_name(), func, "current node is nil");
88 tree_command_unit temp;
89 size_accumulator += current_node->packed_size() + temp.packed_size();
90 LOG(a_sprintf("len A %d", size_accumulator));
93 void packable_tree::packit(byte_array &packed_form, const packable_tree *current_node)
95 LOG(a_sprintf("packing node %x", current_node));
96 LOG(a_sprintf("size A %d", packed_form.length()));
98 if (!current_node) throw_error(static_class_name(), func, "current node is nil");
100 byte_array temp_store;
102 int guess = current_node->packed_size();
104 current_node->pack(temp_store);
106 if (temp_store.length() != guess)
107 throw_error(current_node->class_name(), func, "failure calculating size");
109 tree_command_unit command;
110 command.size = temp_store.length();
111 //hmmm: do we still need a packed size?
112 if (current_node->branches() == 0) {
113 command.command = BRANCHES_FOLLOW;
114 // the branches following are always just one branch.
117 command.command = ATTACH_BRANCHES;
118 command.number = current_node->branches();
120 // stuff the command unit.
121 command.pack(packed_form);
122 LOG(a_sprintf("size B %d", packed_form.length()));
123 packed_form += temp_store; // main chunk is not packed, just added.
124 LOG(a_sprintf("size C %d", packed_form.length()));
127 int packable_tree::recursive_packed_size() const
129 packable_tree *curr = NIL;
130 int accum = 0; // where we accumulate the length of the packed form.
131 for (iterator zip2 = start(postfix); (curr = (packable_tree *)zip2.next()); )
133 tree_command_unit end_command;
134 accum += end_command.packed_size();
138 void packable_tree::recursive_pack(byte_array &packed_form) const
140 packable_tree *curr = NIL;
141 for (iterator zip2 = start(postfix); (curr = (packable_tree *)zip2.next()); )
142 packit(packed_form, curr);
144 tree_command_unit end_command;
145 end_command.number = 1;
146 end_command.command = FINISH;
147 end_command.size = 0;
148 // end command is stored at end.
149 end_command.pack(packed_form);
152 packable_tree *packable_tree::recursive_unpack(byte_array &packed_form,
153 packable_tree_factory &creator)
155 stack<packable_tree *> accumulated_trees(0); // unbounded.
156 tree_command_unit cmd;
157 // get the first command out of the package.
158 if (!cmd.unpack(packed_form)) {
163 packable_tree *new_branch = NIL;
164 bool failure = false; // set to true if errors occurred.
166 // the packed tree is traversed by grabbing a command and then doing what
167 // it says as far as pulling in children or adding a new branch.
168 while (cmd.command != FINISH) {
169 new_branch = creator.create();
171 new_branch->unpack(packed_form);
173 if (cmd.command == ATTACH_BRANCHES) {
174 if (cmd.number > accumulated_trees.size()) {
175 //log instead: "badly formed packed tree"
179 for (int i = cmd.number; i > 0; i--) {
180 packable_tree *to_add = (packable_tree *)accumulated_trees
181 [accumulated_trees.size()-i];
182 new_branch->attach(to_add);
185 for (int j = 0; j < cmd.number; j++)
186 accumulated_trees.acquire_pop(junk);
187 accumulated_trees.push(new_branch);
188 } else if (cmd.command == BRANCHES_FOLLOW) {
189 accumulated_trees.push(new_branch);
191 //log instead: "invalid command in packed tree"
195 if (!cmd.unpack(packed_form)) {
202 if (accumulated_trees.size() != 1) {
203 //log instead: "not all branches were claimed"
205 } else if (!failure) {
207 accumulated_trees.acquire_pop(junk);
210 // clean up the allocated objects if we saw a failure.
213 packable_tree *to_whack;
214 outcome ret = accumulated_trees.acquire_pop(to_whack);
215 if (ret == common::IS_EMPTY) break;
216 if (to_whack != new_branch)