tests/test_gc17.pcc

   1 //
   2 //  Testing garbage collection with polymorphic datatypes
   3 //
   4
   5 #include <iostream.h>
   6 #include <stdlib.h>
   7 #include <assert.h>
   8 #include <unistd.h>
   9 #include <AD/gc/gcheaps.h>
  10
  11 #define NODES (256 * 1024)
  12 #define TRIALS 10
  13 #define SHARING
  14
  15 //////////////////////////////////////////////////////////////////////////////
  16 //  Datatype TREE is just a simple binary tree (actually a dag in our case).
  17 //////////////////////////////////////////////////////////////////////////////
  18 datatype TREE<T> :: collectable
  19    = empty
  20    | leaf (class T)
  21    | node (TREE<T>, class T, TREE<T>)
  22    ;
  23
  24 instantiate datatype TREE<int>, TREE<const char *>;
  25
  26 //////////////////////////////////////////////////////////////////////////////
  27 //  Compute the sum of all nodes of a tree
  28 //////////////////////////////////////////////////////////////////////////////
  29 int sum (TREE<int> t)
  30 {  match (t) {
  31       case empty:        return 0;
  32       case leaf i:       return i;
  33       case node(x,i,y):  return sum(x) + i + sum(y);
  34    }
  35 }
  36
  37 //////////////////////////////////////////////////////////////////////////////
  38 //  Count the number of pointer sharings.
  39 //////////////////////////////////////////////////////////////////////////////
  40 int sharing (TREE<int> t)
  41 {  match (t) {
  42       case empty:        return 0;
  43       case leaf _:       return 0;
  44       case node(x,i,y):  return sharing(x) + sharing(y)
  45                                  + ((x != empty && x == y) ? 1 : 0);
  46    }
  47 }
  48
  49 //////////////////////////////////////////////////////////////////////////////
  50 //  Compute the size of a tree
  51 //////////////////////////////////////////////////////////////////////////////
  52 template <class T>
  53    int size (TREE<T> t)
  54    {  match (t) {
  55          case empty:        return 0;
  56          case leaf _:       return 1;
  57          case node(x,i,y):  return size(x) + 1 + size(y);
  58       }
  59    }
  60
  61 //////////////////////////////////////////////////////////////////////////////
  62 //  Check a tree for correctness.
  63 //////////////////////////////////////////////////////////////////////////////
  64 template <class T>
  65    void check (TREE<T> t)
  66    {  match (t) {
  67          case empty:        return;
  68          case leaf _:       return;
  69          case node(x,i,y):
  70             assert (HM::is_mapped(t) &&
  71                     HM::page_gc(t) == GC::get_default_gc().gc_id());
  72             assert (HM::get_object_map().is_marked(t));
  73             check(x); check(y);
  74       }
  75    }
  76
  77 //////////////////////////////////////////////////////////////////////////////
  78 //  Routine to make a random tree of a certain size.
  79 //////////////////////////////////////////////////////////////////////////////
  80 TREE<int> make_tree(int n)
  81 {  if (n == 0) return empty;
  82    int split = rand() % n;
  83    int data  = rand() % n;
  84 #ifdef SHARING
  85    if ((n % 2 == 1) && (rand() % 2 == 1)) {
  86       TREE<int> t = make_tree(n/2);
  87       return node(t, data, t);
  88    }
  89 #endif
  90    return node(make_tree(split), data, make_tree(n - split - 1));
  91 }
  92
  93 void testing()
  94 {
  95    for (int trial = 1; trial <= TRIALS; trial++) {
  96        cout << "Trial number " << trial << '\n' << flush;
  97        TREE<int> tree1    = make_tree(NODES);
  98        int       size1    = size(tree1);
  99        int       sum1     = sum(tree1);
 100        int       sharing1 = sharing (tree1);
 101        check(tree1);
 102
 103        cout << "Size = " << size1 << " check sum = " << sum1
 104             << " pointer sharing = " << sharing1 << '\n' << flush;
 105
 106        make_tree(NODES);              // this just generates a lot of garbage
 107
 108        // Now traverse the tree check things.
 109        assert(size(tree1)     == NODES);
 110        assert(sum(tree1)      == sum1);
 111        assert(sharing(tree1)  == sharing1);
 112        check(tree1);
 113        cout << "Trial number " << trial << " has passed\n";
 114    }
 115 }
 116
 117 int main()
 118 {
 119    cout <<
 120      "This test generate random dags and try to see if garbage collection\n"
 121      "works on preserving pointer sharing correctly.  I'll do this "
 122       << TRIALS << " times.\n";
 123    srand(getpid());
 124    testing();
 125    // force an explicit garbage collection
 126    cout << "Finished.  Now I'm forcing another garbage collection to clean\n"
 127            "things up.  There should be very little garbage left at the end.\n";
 128    GC::garbage_collect();
 129    return 0;
 130 }