nucleus/library/tests_structures/test_stack.cpp

   1 /*
   2 *  Name   : t_stack
   3 *  Author : Chris Koeritz
   4 *  Purpose:
   5 *    Tests out the stack object with both flat objects (byte_array) but also
   6 *  deep objects (pointer to byte_array).  Both bounded and unbounded stacks
   7 *  are tested for each.
   8 **
   9 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
  10 * redistribute it and/or modify it under the terms of the GNU General Public  *
  11 * License as published by the Free Software Foundation; either version 2 of   *
  12 * the License or (at your option) any later version.  This is online at:      *
  13 *     http://www.fsf.org/copyleft/gpl.html                                    *
  14 * Please send any updates to: fred@gruntose.com                               *
  15 \*****************************************************************************/
  16
  17 #include <application/hoople_main.h>
  18 #include <basis/byte_array.h>
  19 #include <basis/guards.h>
  20 #include <basis/astring.h>
  21 #include <loggers/program_wide_logger.h>
  22 #include <mathematics/chaos.h>
  23 #include <structures/stack.h>
  24 #include <structures/static_memory_gremlin.h>
  25 #include <unit_test/unit_base.h>
  26
  27 #ifdef DEBUG_STACK
  28   #define LOG(to_print) EMERGENCY_LOG(program_wide_logger::get(), to_print)
  29 #endif
  30
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 using namespace application;
  35 using namespace basis;
  36 ///using namespace configuration;
  37 using namespace mathematics;
  38 using namespace filesystem;
  39 using namespace loggers;
  40 using namespace structures;
  41 using namespace textual;
  42 using namespace timely;
  43 using namespace unit_test;
  44
  45 //HOOPLE_STARTUP_CODE;
  46
  47 //#define DEBUG_STACK
  48   // uncomment for a noisier version.
  49
  50 const int test_iterations = 40;
  51
  52
  53 class test_stack : public virtual unit_base, public virtual application_shell
  54 {
  55 public:
  56   test_stack() {}
  57   DEFINE_CLASS_NAME("test_stack");
  58   int execute();
  59
  60   void test_stack_with_objects();
  61   void test_stack_with_pointers();
  62
  63   void CHECK_STACK_RESULT(outcome retval, const astring &place);
  64   byte_array generate_flat(const char *to_store);
  65   byte_array *generate_deep(const char *to_store);
  66   astring text_form(stack<byte_array *> &s);
  67   astring text_form(stack<byte_array> &s);
  68 };
  69
  70 // CHECK_STACK_RESULT: a function that takes care of error testing for a
  71 // stack command.  if executing the command ends in full or empty, then
  72 // that is reported.
  73 void test_stack::CHECK_STACK_RESULT(outcome retval, const astring &place)
  74 {
  75 #ifdef DEBUG_STACK
  76   if (retval == common::IS_FULL)
  77     LOG(astring(astring::SPRINTF, "returned IS_FULL at %s", place.s()))
  78   else if (retval == common::IS_EMPTY)
  79     LOG(astring(astring::SPRINTF, "returned IS_EMPTY at %s", place.s()));
  80 #else
  81   if (retval.value() || !place) {}
  82 #endif
  83 }
  84
  85 byte_array test_stack::generate_flat(const char *to_store)
  86 {
  87   byte_array to_return = byte_array(int(strlen(to_store) + 1), (abyte *)to_store);
  88   return to_return;
  89 }
  90
  91 byte_array *test_stack::generate_deep(const char *to_store)
  92 {
  93   byte_array *to_return = new byte_array(int(strlen(to_store) + 1),
  94       (abyte *)to_store);
  95   return to_return;
  96 }
  97
  98 astring test_stack::text_form(stack<byte_array *> &s)
  99 {
 100   astring to_return;
 101   for (int i = 0; i < s.elements(); i++) {
 102     to_return += astring(astring::SPRINTF, "#%d: %s\n", i, s[i]->observe());
 103   }
 104   return to_return;
 105 }
 106
 107 astring test_stack::text_form(stack<byte_array> &s)
 108 {
 109   astring to_return;
 110   for (int i = 0; i < s.elements(); i++) {
 111     to_return += astring(astring::SPRINTF, "#%d: %s\n", i, s[i].observe());
 112   }
 113   return to_return;
 114 }
 115
 116 void test_stack::test_stack_with_objects()
 117 {
 118   FUNCDEF("test_stack_with_objects");
 119   for (int qq = 0; qq < test_iterations; qq++) {
 120 #ifdef DEBUG_STACK
 121     LOG(astring(astring::SPRINTF, "index %d", qq));
 122 #endif
 123     stack<byte_array > bounded_stack(3);
 124     stack<byte_array > unlimited_stack(0);
 125     chaos randomizer;
 126
 127     {
 128 #ifdef DEBUG_STACK
 129       LOG("testing the bounded stack first:");
 130 #endif
 131       CHECK_STACK_RESULT(bounded_stack.push(generate_flat("the first line")), "first push");
 132       CHECK_STACK_RESULT(bounded_stack.push(generate_flat("the second line")), "second push");
 133       CHECK_STACK_RESULT(bounded_stack.push(generate_flat("the final and third")), "third push");
 134       byte_array gend = generate_flat("this shouldn't work");
 135       ASSERT_EQUAL(bounded_stack.push(gend).value(), common::IS_FULL,
 136           "the bounded stack push should catch IS_FULL");
 137 #ifdef DEBUG_STACK
 138       LOG("pushing worked successfully...");
 139       LOG("printing the stack in element order");
 140 #endif
 141       for (int i = 0; i < bounded_stack.size(); i++) {
 142 #ifdef DEBUG_STACK
 143         LOG(astring(astring::SPRINTF, "depth %d has %s.", i,
 144             bounded_stack[i].observe()));
 145 #endif
 146       }
 147 #ifdef DEBUG_STACK
 148       LOG("now popping the stack all the way back.");
 149 #endif
 150       int full_size = bounded_stack.size();
 151       for (int j = 0; j < full_size; j++) {
 152 #ifdef DEBUG_STACK
 153         LOG(astring(astring::SPRINTF, "pop %d, stack size is %d, has %s", j+1,
 154             bounded_stack.size(), bounded_stack.top().observe()));
 155 #endif
 156         byte_array found;
 157         bounded_stack.acquire_pop(found);
 158         astring got((char *)found.observe());
 159         switch (j) {
 160         case 0:
 161           ASSERT_EQUAL(got, astring("the final and third"),
 162               "acquire_pop should have right contents at 2");
 163           break;
 164         case 1:
 165           ASSERT_EQUAL(got, astring("the second line"),
 166               "acquire_pop should have right contents at 1");
 167           break;
 168         case 2:
 169           ASSERT_EQUAL(got, astring("the first line"),
 170               "acquire_pop should have right contents at 0");
 171           break;
 172         }
 173       }
 174       ASSERT_EQUAL(bounded_stack.pop().value(), common::IS_EMPTY,
 175           "bounded pop should have right outcome");
 176     }
 177
 178     {
 179 #ifdef DEBUG_STACK
 180       LOG("testing the unbounded stack now:");
 181 #endif
 182       for (int j = 0; j < 24; j++) {
 183         astring line(astring::SPRINTF, "{posn %d here}", j);
 184         CHECK_STACK_RESULT(unlimited_stack.push(generate_flat(line.s())), "unbound push");
 185       }
 186 #ifdef DEBUG_STACK
 187       LOG("unbounded stack in element order:");
 188 #endif
 189       for (int k = 0; k < unlimited_stack.size(); k++) {
 190 #ifdef DEBUG_STACK
 191         LOG(astring(astring::SPRINTF, "#%d is %s", k, unlimited_stack[k].observe()));
 192 #endif
 193       }
 194 #ifdef DEBUG_STACK
 195       LOG("now popping fresh order:");
 196 #endif
 197       while (unlimited_stack.size()) {
 198 #ifdef DEBUG_STACK
 199         LOG(astring(astring::SPRINTF, "size %d, content %s",
 200             unlimited_stack.size(), unlimited_stack.top().observe()));
 201 #endif
 202         unlimited_stack.pop();
 203       }
 204 #ifdef DEBUG_STACK
 205       LOG("");
 206 #endif
 207       ASSERT_EQUAL(unlimited_stack.pop().value(), common::IS_EMPTY,
 208           "unlimited pop should return empty as expected");
 209 #ifdef DEBUG_STACK
 210       LOG("\
 211 ----------------------------------------------\n\
 212 both types of stack exercises were successful.\n\
 213 ----------------------------------------------");
 214 #endif
 215     }
 216
 217 #ifdef DEBUG_STACK
 218     LOG("now setting up some simple stacks...");
 219 #endif
 220
 221     {
 222 #ifdef DEBUG_STACK
 223       LOG("bounded first...");
 224 #endif
 225       stack<byte_array > bounder(randomizer.inclusive(30, 80));
 226 #ifdef DEBUG_STACK
 227       LOG(astring(astring::SPRINTF, "length of bounder is max %d, curr %d", bounder.elements(), bounder.size()));
 228 #endif
 229       int max = bounder.elements();
 230       for (int i = 0; i < max; i++) {
 231         ASSERT_EQUAL(bounder.size(), i, "the bounder size should be in step with loop");
 232         int byte_array_size = randomizer.inclusive(259, 287);
 233         byte_array to_stuff(byte_array_size);
 234         astring visible(astring::SPRINTF, "entry %d...", i);
 235         visible.stuff((char *)to_stuff.access(), visible.length() + 1);
 236         for (int j = visible.length() + 1; j < to_stuff.length(); j++)
 237           *(to_stuff.access() + j) = '\0';
 238 #ifdef DEBUG_STACK
 239         LOG(astring(astring::SPRINTF, "pushing index %d", i));
 240 #endif
 241         outcome ret = bounder.push(to_stuff);
 242         ASSERT_EQUAL(ret.value(), common::OKAY, "pushing should not fail in simple test");
 243       }
 244       ASSERT_EQUAL(bounder.elements(), bounder.size(), "bounder set should see size and max same");
 245 #ifdef DEBUG_STACK
 246       LOG("inverting:");
 247 #endif
 248       bounder.invert();
 249 #ifdef DEBUG_STACK
 250       LOG(astring(astring::SPRINTF, "inverted is:\n%s", text_form(bounder).s()));
 251 #endif
 252       while (bounder.size()) bounder.pop();
 253     }
 254   }
 255 }
 256
 257 void test_stack::test_stack_with_pointers()
 258 {
 259   FUNCDEF("test_stack_with_pointers")
 260   for (int qq = 0; qq < test_iterations; qq++) {
 261 #ifdef DEBUG_STACK
 262     LOG(astring(astring::SPRINTF, "index %d", qq));
 263 #endif
 264     stack<byte_array *> bounded_stack(3);
 265     stack<byte_array *> unlimited_stack(0);
 266     chaos randomizer;
 267
 268     {
 269 #ifdef DEBUG_STACK
 270       LOG("testing the bounded stack first:");
 271 #endif
 272       CHECK_STACK_RESULT(bounded_stack.push(generate_deep("the first line")), "first push");
 273       CHECK_STACK_RESULT(bounded_stack.push(generate_deep("the second line")), "second push");
 274       CHECK_STACK_RESULT(bounded_stack.push(generate_deep("the final and third")), "third push");
 275       byte_array *gend = generate_deep("this shouldn't work");
 276       ASSERT_EQUAL(bounded_stack.push(gend).value(), common::IS_FULL,
 277           "the bounded stack push should catch IS_FULL");
 278       delete gend;
 279 #ifdef DEBUG_STACK
 280       LOG("pushing worked successfully...");
 281       LOG("printing the stack in element order");
 282 #endif
 283       for (int i = 0; i < bounded_stack.size(); i++) {
 284 #ifdef DEBUG_STACK
 285         LOG(astring(astring::SPRINTF, "depth %d has: %s", i, bounded_stack[i]->observe()));
 286 #endif
 287       }
 288 #ifdef DEBUG_STACK
 289       LOG("now popping the stack all the way back.");
 290 #endif
 291       int full_size = bounded_stack.size();
 292       for (int j = 0; j < full_size; j++) {
 293 #ifdef DEBUG_STACK
 294         LOG(astring(astring::SPRINTF, "pop %d, stack size is %d, has %s", j+1, bounded_stack.size(), bounded_stack.top()->observe()));
 295 #endif
 296         byte_array *found;
 297         bounded_stack.acquire_pop(found);
 298         ASSERT_TRUE(found, "acquire_pop test should not return nil");
 299         ASSERT_TRUE(found->observe(), "acquire_pop test should have non-nil observe");
 300         astring got((char *)found->observe());
 301         switch (j) {
 302         case 0:
 303           ASSERT_EQUAL(got, astring("the final and third"),
 304               "popping should have right contents at 2");
 305           break;
 306         case 1:
 307           ASSERT_EQUAL(got, astring("the second line"),
 308               "popping should have right contents at 1");
 309           break;
 310         case 2:
 311           ASSERT_EQUAL(got, astring("the first line"),
 312               "popping should have right contents at 0");
 313           break;
 314         }
 315         delete found;
 316       }
 317       ASSERT_EQUAL(bounded_stack.pop().value(), common::IS_EMPTY,
 318           "bounded pop failure in result");
 319     }
 320
 321     {
 322 #ifdef DEBUG_STACK
 323       LOG("testing the unbounded stack now:");
 324 #endif
 325       for (int j = 0; j < 24; j++) {
 326         astring line(astring::SPRINTF, "{posn %d here}", j);
 327         CHECK_STACK_RESULT(unlimited_stack.push(generate_deep(line.s())), "unbound push");
 328       }
 329 #ifdef DEBUG_STACK
 330       LOG("unbounded stack in element order:");
 331 #endif
 332       for (int k = 0; k < unlimited_stack.size(); k++) {
 333 #ifdef DEBUG_STACK
 334         LOG(astring(astring::SPRINTF, "#%d is %s", k, unlimited_stack[k]->observe()));
 335 #endif
 336       }
 337 #ifdef DEBUG_STACK
 338       LOG("\nnow popping order:");
 339 #endif
 340       while (unlimited_stack.size()) {
 341 #ifdef DEBUG_STACK
 342         LOG(astring(astring::SPRINTF, "size %d, content %s", unlimited_stack.size(), unlimited_stack.top()->observe()));
 343 #endif
 344         byte_array *to_zap = unlimited_stack.top();
 345         unlimited_stack.pop();
 346         delete to_zap;
 347           // okay because the pointer was copied, and the reference from top
 348           // is not being relied on.
 349       }
 350 #ifdef DEBUG_STACK
 351       LOG("");
 352 #endif
 353       ASSERT_EQUAL(unlimited_stack.pop().value(), common::IS_EMPTY,
 354           "unlimited pop should return empty as expected");
 355 #ifdef DEBUG_STACK
 356       LOG("\n\
 357 ----------------------------------------------\n\
 358 both types of stack exercises were successful.\n\
 359 ----------------------------------------------");
 360 #endif
 361     }
 362
 363 #ifdef DEBUG_STACK
 364     LOG("now setting up some simple stacks...");
 365 #endif
 366
 367     {
 368 #ifdef DEBUG_STACK
 369       LOG("bounded first...");
 370 #endif
 371       stack<byte_array *> bounder(randomizer.inclusive(30, 80));
 372 #ifdef DEBUG_STACK
 373       LOG(astring(astring::SPRINTF, "length of bounder is max %d, curr %d",
 374           bounder.elements(), bounder.size()));
 375 #endif
 376       int max = bounder.elements();
 377       for (int i = 0; i < max; i++) {
 378         ASSERT_EQUAL(bounder.size(), i, "bounder size should remain in step with loop");
 379         int byte_array_size = randomizer.inclusive(259, 287);
 380         byte_array *to_stuff = new byte_array(byte_array(byte_array_size));
 381         astring visible(astring::SPRINTF, "entry %d...", i);
 382         visible.stuff((char *)to_stuff->observe(), visible.length() + 1);
 383         for (int j = visible.length() + 1; j < to_stuff->length(); j++)
 384           *(to_stuff->access() + j) = '\0';
 385         ASSERT_EQUAL(bounder.push(to_stuff).value(), common::OKAY,
 386             "pushing should not fail in bound simple test");
 387       }
 388       ASSERT_EQUAL(bounder.elements(), bounder.size(), "bounder set must have size and max agree");
 389 #ifdef DEBUG_STACK
 390       LOG("inverting:");
 391 #endif
 392       bounder.invert();
 393 #ifdef DEBUG_STACK
 394       LOG(astring(astring::SPRINTF, "inverted is:\n%s", text_form(bounder).s()));
 395 #endif
 396       while (bounder.size()) {
 397         byte_array *to_zap = bounder.top();
 398         bounder.pop();
 399         delete to_zap;
 400       }
 401     }
 402   }
 403 }
 404
 405 int test_stack::execute()
 406 {
 407   test_stack_with_objects();
 408   test_stack_with_pointers();
 409   return final_report();
 410 }
 411
 412 HOOPLE_MAIN(test_stack, )
 413