Merge branch 'main' of feistymeow.org:feisty_meow
[feisty_meow.git] / 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 = 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
142 void packable_tree::recursive_pack(byte_array &packed_form) const
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
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 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