feisty meow concerns codebase  2.140
packable_tree.cpp
Go to the documentation of this file.
1 /*****************************************************************************\
2 * *
3 * Name : packable_tree *
4 * Author : Chris Koeritz *
5 * *
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 \*****************************************************************************/
14 
15 #include "packable_tree.h"
16 
17 #include <basis/astring.h>
18 #include <basis/byte_array.h>
19 #include <basis/guards.h>
21 #include <structures/stack.h>
22 
23 using namespace basis;
24 using namespace structures;
25 
26 //#define DEBUG_PACKABLE_TREE
27  // uncomment for noisy debugging.
28 
29 #undef LOG
30 #ifdef DEBUG_PACKABLE_TREE
31  #include <stdio.h>
32  #define LOG(to_print) printf("%s\n", astring(to_print).s());
33 #else
34  #define LOG(s) { if (!!s) {} }
35 #endif
36 
37 namespace nodes {
38 
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).
45 
47 
48 packable_tree_factory::~packable_tree_factory() {}
49 
51 
53 struct tree_command_unit : public virtual packable
54 {
55  tree_commands command;
56  int number;
57  int size;
58 
59  virtual ~tree_command_unit() {}
60 
61  virtual int packed_size() const { return 3 * PACKED_SIZE_INT32; }
62 
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);
67  }
68 
69  virtual bool unpack(byte_array &packed_form) {
70  int cmd;
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;
75  return true;
76  }
77 };
78 
80 
81 packable_tree::packable_tree() : tree() {}
82 
83 void packable_tree::calcit(int &size_accumulator, const packable_tree *current_node)
84 {
85  FUNCDEF("calcit");
86 #ifdef DEBUG_PACKABLE_TREE
87  LOG(a_sprintf("calcing node %x", current_node));
88 #endif
89  if (!current_node) throw_error(static_class_name(), func, "current node is nil");
90  tree_command_unit temp;
91  size_accumulator += current_node->packed_size() + temp.packed_size();
92 #ifdef DEBUG_PACKABLE_TREE
93  LOG(a_sprintf("len A %d", size_accumulator));
94 #endif
95 }
96 
97 void packable_tree::packit(byte_array &packed_form, const packable_tree *current_node)
98 {
99 //LOG(a_sprintf("packing node %x", current_node));
100 //LOG(a_sprintf("size A %d", packed_form.length()));
101  FUNCDEF("packit");
102  if (!current_node) throw_error(static_class_name(), func, "current node is nil");
103 
104  byte_array temp_store;
105 
106 int guess = current_node->packed_size();
107 
108  current_node->pack(temp_store);
109 
110 if (temp_store.length() != guess)
111 throw_error(current_node->class_name(), func, "failure calculating size");
112 
113  tree_command_unit command;
114  command.size = temp_store.length();
115 //hmmm: do we still need a packed size?
116  if (current_node->branches() == 0) {
117  command.command = BRANCHES_FOLLOW;
118  // the branches following are always just one branch.
119  command.number = 1;
120  } else {
121  command.command = ATTACH_BRANCHES;
122  command.number = current_node->branches();
123  }
124  // stuff the command unit.
125  command.pack(packed_form);
126 //LOG(a_sprintf("size B %d", packed_form.length()));
127  packed_form += temp_store; // main chunk is not packed, just added.
128 //LOG(a_sprintf("size C %d", packed_form.length()));
129 }
130 
132 {
133  packable_tree *curr = NULL_POINTER;
134  int accum = 0; // where we accumulate the length of the packed form.
135  for (iterator zip2 = start(postfix); (curr = (packable_tree *)zip2.next()); )
136  calcit(accum, curr);
137  tree_command_unit end_command;
138  accum += end_command.packed_size();
139  return accum;
140 }
141 
143 {
144  packable_tree *curr = NULL_POINTER;
145  for (iterator zip2 = start(postfix); (curr = (packable_tree *)zip2.next()); )
146  packit(packed_form, curr);
147 
148  tree_command_unit end_command;
149  end_command.number = 1;
150  end_command.command = FINISH;
151  end_command.size = 0;
152  // end command is stored at end.
153  end_command.pack(packed_form);
154 }
155 
157  packable_tree_factory &creator)
158 {
159  stack<packable_tree *> accumulated_trees(0); // unbounded.
160  tree_command_unit cmd;
161  // get the first command out of the package.
162  if (!cmd.unpack(packed_form)) {
163 //complain.
164  return NULL_POINTER;
165  }
166 
167  packable_tree *new_branch = NULL_POINTER;
168  bool failure = false; // set to true if errors occurred.
169 
170  // the packed tree is traversed by grabbing a command and then doing what
171  // it says as far as pulling in children or adding a new branch.
172  while (cmd.command != FINISH) {
173  new_branch = creator.create();
174 
175  new_branch->unpack(packed_form);
176 
177  if (cmd.command == ATTACH_BRANCHES) {
178  if (cmd.number > accumulated_trees.size()) {
179 //log instead: "badly formed packed tree"
180  failure = true;
181  break;
182  }
183  for (int i = cmd.number; i > 0; i--) {
184  packable_tree *to_add = (packable_tree *)accumulated_trees
185  [accumulated_trees.size()-i];
186  new_branch->attach(to_add);
187  }
188  packable_tree *junk;
189  for (int j = 0; j < cmd.number; j++)
190  accumulated_trees.acquire_pop(junk);
191  accumulated_trees.push(new_branch);
192  } else if (cmd.command == BRANCHES_FOLLOW) {
193  accumulated_trees.push(new_branch);
194  } else {
195 //log instead: "invalid command in packed tree"
196  failure = true;
197  break;
198  }
199  if (!cmd.unpack(packed_form)) {
200 //complain.
201  failure = true;
202  break;
203  }
204  }
205 
206  if (accumulated_trees.size() != 1) {
207 //log instead: "not all branches were claimed"
208  failure = true;
209  } else if (!failure) {
210  packable_tree *junk;
211  accumulated_trees.acquire_pop(junk);
212  }
213 
214  // clean up the allocated objects if we saw a failure.
215  if (failure) {
216  while (true) {
217  packable_tree *to_whack;
218  outcome ret = accumulated_trees.acquire_pop(to_whack);
219  if (ret == common::IS_EMPTY) break;
220  if (to_whack != new_branch)
221  WHACK(to_whack);
222  }
223  WHACK(new_branch);
224  }
225 
226  return new_branch;
227 }
228 
229 } // namespace.
230 
a_sprintf is a specialization of astring that provides printf style support.
Definition: astring.h:440
int length() const
Returns the current reported length of the allocated C array.
Definition: array.h:115
A very common template for a dynamic array of bytes.
Definition: byte_array.h:36
Outcomes describe the state of completion for an operation.
Definition: outcome.h:31
A base class for objects that can pack into an array of bytes.
Definition: byte_array.h:87
virtual int packed_size() const =0
Estimates the space needed for the packed structure.
virtual bool unpack(byte_array &packed_form)=0
Restores the packable from the "packed_form".
virtual packable_tree * create()=0
a tree factory is needed when we are recreating the packed tree.
A tree object that can be packed into an array of bytes and unpacked again.
Definition: packable_tree.h:30
void recursive_pack(basis::byte_array &packed_form) const
packs the whole tree starting at this node into the packed form.
int recursive_packed_size() const
spiders the tree starting at this node to calculate the packed size.
static packable_tree * recursive_unpack(basis::byte_array &packed_form, packable_tree_factory &creator)
unpacks a tree stored in "packed_form" and returns it.
A dynamically linked tree with an arbitrary number of branches.
Definition: tree.h:40
virtual void attach(tree *new_branch)
Attaches the specified branch to the current tree.
Definition: tree.cpp:453
iterator start(traversal_directions direction) const
Returns a fresh iterator positioned at this tree node.
Definition: tree.cpp:542
@ postfix
Definition: tree.h:94
An abstraction that represents a stack data structure.
Definition: stack.h:30
basis::outcome push(const contents &element)
Enters a new element onto the top of the stack.
Definition: stack.h:139
basis::outcome acquire_pop(contents &to_stuff)
Used to grab the top off of the stack.
Definition: stack.h:196
int size() const
returns the size of the stack.
Definition: stack.h:127
#define NULL_POINTER
The value representing a pointer to nothing.
Definition: definitions.h:32
#define FUNCDEF(func_in)
FUNCDEF sets the name of a function (and plugs it into the callstack).
Definition: enhance_cpp.h:57
The guards collection helps in testing preconditions and reporting errors.
Definition: array.h:30
void WHACK(contents *&ptr)
deletion with clearing of the pointer.
Definition: functions.h:121
void attach(byte_array &packed_form, const char *to_attach)
Packs a character string "to_attach" into "packed_form".
Definition: astring.cpp:1015
void throw_error(const base_string &class_name, const base_string &func_name, const base_string &error_message)
throws an error that incorporates the class name and function name.
Definition: guards.cpp:32
bool detach(byte_array &packed_form, astring &to_detach)
Unpacks a character string "to_attach" from "packed_form".
Definition: astring.cpp:1023
@ BRANCHES_FOLLOW
@ ATTACH_BRANCHES
A dynamic container class that holds any kind of object via pointers.
Definition: amorph.h:55
bool unpack(basis::byte_array &packed_form, set< contents > &to_unpack)
provides a way to unpack any set that stores packable objects.
Definition: set.h:139
void pack(basis::byte_array &packed_form, const set< contents > &to_pack)
provides a way to pack any set that stores packable objects.
Definition: set.h:131
const int PACKED_SIZE_INT32
int packed_size(const byte_array &packed_form)
Reports the size required to pack a byte array into a byte array.
#define LOG(s)
#define static_class_name()