nucleus/library/nodes/packable_tree.cpp

   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>
  20 #include <structures/object_packers.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).
  44 enum tree_commands { BRANCHES_FOLLOW, ATTACH_BRANCHES, FINISH };
  45
  46 //////////////
  47
  48 packable_tree_factory::~packable_tree_factory() {}
  49
  50 //////////////
  51
  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
  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
  79 //////////////
  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
 131 int packable_tree::recursive_packed_size() const
 132 {
 133   packable_tree *curr = NIL;
 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
 142 void packable_tree::recursive_pack(byte_array &packed_form) const
 143 {
 144   packable_tree *curr = NIL;
 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
 156 packable_tree *packable_tree::recursive_unpack(byte_array &packed_form,
 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 NIL;
 165   }
 166
 167   packable_tree *new_branch = NIL;
 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