tests/test_gc17.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.3.5),
   3 //  last updated on Jun 18, 1997.
   4 //  The original source file is "test_gc17.pcc".
   5 ///////////////////////////////////////////////////////////////////////////////
   6
   7 #define PROP_GARBAGE_COLLECTION_USED
   8 #include <propdefs.h>
   9 #line 1 "test_gc17.pcc"
  10 //
  11 //  Testing garbage collection with polymorphic datatypes
  12 //
  13
  14 #include <iostream.h>
  15 #include <stdlib.h>
  16 #include <assert.h>
  17 #include <unistd.h>
  18 #include <AD/gc/gcheaps.h>
  19
  20 #define NODES (256 * 1024)
  21 #define TRIALS 10
  22 #define SHARING
  23
  24 //////////////////////////////////////////////////////////////////////////////
  25 //  Datatype TREE is just a simple binary tree (actually a dag in our case).
  26 //////////////////////////////////////////////////////////////////////////////
  27 #line 18 "test_gc17.pcc"
  28 #line 22 "test_gc17.pcc"
  29 ///////////////////////////////////////////////////////////////////////////////
  30 //
  31 // Forward class definition for TREE<T>
  32 //
  33 ///////////////////////////////////////////////////////////////////////////////
  34 #ifndef datatype_TREE_defined
  35 #define datatype_TREE_defined
  36 template <class T> class a_TREE;
  37 #define TREE(T) a_TREE<T> *
  38 #endif
  39
  40 #  define empty 0
  41
  42 ///////////////////////////////////////////////////////////////////////////////
  43 //
  44 // Base class for datatype TREE<T>
  45 //
  46 ///////////////////////////////////////////////////////////////////////////////
  47 template <class T> class a_TREE : public GCObject {
  48 public:
  49    enum Tag_TREE {
  50       tag_leaf = 0, tag_node = 1
  51    };
  52
  53 public:
  54    const Tag_TREE tag__; // variant tag
  55 protected:
  56    inline a_TREE(Tag_TREE t__) : tag__(t__) {}
  57 public:
  58    inline virtual ~a_TREE()
  59    {
  60    }
  61    ////////////////////////////////////////////////////////////////////////////
  62    //
  63    // Method for garbage collection tracing
  64    //
  65    ////////////////////////////////////////////////////////////////////////////
  66 protected:
  67    virtual void trace(GC *);
  68 public:
  69 };
  70 template <class T> inline int boxed(const a_TREE<T> * x) { return x != 0; }
  71 template <class T> inline int untag(const a_TREE<T> * x) { return x ? (x->tag__+1) : 0; }
  72 ///////////////////////////////////////////////////////////////////////////////
  73 //
  74 // Class for datatype constructor TREE<T>::leaf
  75 //
  76 ///////////////////////////////////////////////////////////////////////////////
  77 template <class T> class TREE_leaf : public a_TREE<T>  {
  78 public:
  79 #line 20 "test_gc17.pcc"
  80    T leaf;
  81    inline TREE_leaf (T const & x_leaf)
  82     : a_TREE<T>(tag_leaf), leaf(x_leaf)
  83    {
  84    }
  85    inline ~TREE_leaf()
  86    {
  87    }
  88    ////////////////////////////////////////////////////////////////////////////
  89    //
  90    // Method for garbage collection tracing
  91    //
  92    ////////////////////////////////////////////////////////////////////////////
  93 protected:
  94    virtual void trace(GC *);
  95 public:
  96 };
  97
  98 ///////////////////////////////////////////////////////////////////////////////
  99 //
 100 // Class for datatype constructor TREE<T>::node
 101 //
 102 ///////////////////////////////////////////////////////////////////////////////
 103 template <class T> class TREE_node : public a_TREE<T>  {
 104 public:
 105 #line 21 "test_gc17.pcc"
 106    a_TREE<T> *  _1; T _2; a_TREE<T> *  _3;
 107    inline TREE_node (a_TREE<T> *  x_1, T const & x_2, a_TREE<T> *  x_3)
 108     : a_TREE<T>(tag_node), _1(x_1), _2(x_2), _3(x_3)
 109    {
 110    }
 111    inline ~TREE_node()
 112    {
 113    }
 114    ////////////////////////////////////////////////////////////////////////////
 115    //
 116    // Method for garbage collection tracing
 117    //
 118    ////////////////////////////////////////////////////////////////////////////
 119 protected:
 120    virtual void trace(GC *);
 121 public:
 122 };
 123
 124 ///////////////////////////////////////////////////////////////////////////////
 125 //
 126 // Datatype constructor functions for TREE<T>
 127 //
 128 ///////////////////////////////////////////////////////////////////////////////
 129 template <class T> inline a_TREE<T> * leaf (T const & x_leaf)
 130 {
 131    return new TREE_leaf<T> (x_leaf);
 132 }
 133 template <class T> inline a_TREE<T> * node (a_TREE<T> *  x_1, T const & x_2, a_TREE<T> *  x_3)
 134 {
 135    return new TREE_node<T> (x_1, x_2, x_3);
 136 }
 137 ///////////////////////////////////////////////////////////////////////////////
 138 //
 139 // Downcasting functions for TREE<T>
 140 //
 141 ///////////////////////////////////////////////////////////////////////////////
 142 template <class T> inline TREE_leaf<T> * _leaf(const a_TREE<T> * _x_) { return (TREE_leaf<T> *)_x_; }
 143 template <class T> inline TREE_node<T> * _node(const a_TREE<T> * _x_) { return (TREE_node<T> *)_x_; }
 144
 145 #line 22 "test_gc17.pcc"
 146 #line 22 "test_gc17.pcc"
 147
 148
 149 #line 24 "test_gc17.pcc"
 150 #line 24 "test_gc17.pcc"
 151 ///////////////////////////////////////////////////////////////////////////////
 152 //
 153 // Interface specification of datatype TREE<int>
 154 //
 155 ///////////////////////////////////////////////////////////////////////////////
 156 #line 24 "test_gc17.pcc"
 157
 158
 159 ///////////////////////////////////////////////////////////////////////////////
 160 //
 161 // Interface specification of datatype TREE<char const *>
 162 //
 163 ///////////////////////////////////////////////////////////////////////////////
 164 #line 24 "test_gc17.pcc"
 165
 166
 167 ///////////////////////////////////////////////////////////////////////////////
 168 //
 169 // Instantiation of datatype TREE<int>
 170 //
 171 ///////////////////////////////////////////////////////////////////////////////
 172 #line 24 "test_gc17.pcc"
 173 #ifdef PROP_EXPLICIT_TEMPLATE_INSTANTIATION
 174 template class a_TREE<int>;
 175 template class TREE_leaf<int>;
 176 template a_TREE<int> * leaf(char const * const & x_leaf);
 177 template class TREE_node<int>;
 178 template a_TREE<int> * node(a_TREE<char const *> *  x_1, char const * const & x_2, a_TREE<char const *> *  x_3);
 179 template int boxed(const a_TREE<int> *);
 180 template int untag(const a_TREE<int> *);
 181 template a_TREE<int> * _leaf(const a_TREE<int> *);
 182 template a_TREE<int> * _node(const a_TREE<int> *);
 183 #endif /* PROP_EXPLICIT_TEMPLATE_INSTANTIATION */
 184 void a_TREE<int>::trace(GC * gc__)
 185 {
 186 }
 187
 188 void TREE_leaf<int>::trace(GC * gc__)
 189 {
 190    // call to method a_TREE<int>::trace() has been optimized out
 191    // omitted int const &
 192 }
 193
 194 void TREE_node<int>::trace(GC * gc__)
 195 {
 196    // call to method a_TREE<int>::trace() has been optimized out
 197    this->_1 = (a_TREE<int> *  )gc__->trace(this->_1); // TREE<int>
 198    // omitted int const &
 199    this->_3 = (a_TREE<int> *  )gc__->trace(this->_3); // TREE<int>
 200 }
 201
 202
 203
 204 ///////////////////////////////////////////////////////////////////////////////
 205 //
 206 // Instantiation of datatype TREE<char const *>
 207 //
 208 ///////////////////////////////////////////////////////////////////////////////
 209 #line 24 "test_gc17.pcc"
 210 #ifdef PROP_EXPLICIT_TEMPLATE_INSTANTIATION
 211 template class a_TREE<char const *>;
 212 template class TREE_leaf<char const *>;
 213 template a_TREE<char const *> * leaf(int const & x_leaf);
 214 template class TREE_node<char const *>;
 215 template a_TREE<char const *> * node(a_TREE<int> *  x_1, int const & x_2, a_TREE<int> *  x_3);
 216 template int boxed(const a_TREE<char const *> *);
 217 template int untag(const a_TREE<char const *> *);
 218 template a_TREE<char const *> * _leaf(const a_TREE<char const *> *);
 219 template a_TREE<char const *> * _node(const a_TREE<char const *> *);
 220 #endif /* PROP_EXPLICIT_TEMPLATE_INSTANTIATION */
 221 void a_TREE<char const *>::trace(GC * gc__)
 222 {
 223 }
 224
 225 void TREE_leaf<char const *>::trace(GC * gc__)
 226 {
 227    // call to method a_TREE<char const *>::trace() has been optimized out
 228    // omitted char const * const &
 229 }
 230
 231 void TREE_node<char const *>::trace(GC * gc__)
 232 {
 233    // call to method a_TREE<char const *>::trace() has been optimized out
 234    this->_1 = (a_TREE<char const *> *  )gc__->trace(this->_1); // TREE<char const *>
 235    // omitted char const * const &
 236    this->_3 = (a_TREE<char const *> *  )gc__->trace(this->_3); // TREE<char const *>
 237 }
 238
 239
 240
 241 #line 24 "test_gc17.pcc"
 242 #line 24 "test_gc17.pcc"
 243
 244
 245 //////////////////////////////////////////////////////////////////////////////
 246 //  Compute the sum of all nodes of a tree
 247 //////////////////////////////////////////////////////////////////////////////
 248 int sum (
 249 #line 29 "test_gc17.pcc"
 250 a_TREE<int> *
 251 #line 29 "test_gc17.pcc"
 252  t)
 253 {
 254 #line 34 "test_gc17.pcc"
 255 {
 256    if (t) {
 257       if (t->tag__) {
 258
 259 #line 33 "test_gc17.pcc"
 260        return sum(_node(t)->_1) + _node(t)->_2 + sum(_node(t)->_3);
 261
 262 #line 34 "test_gc17.pcc"
 263       } else {
 264
 265 #line 32 "test_gc17.pcc"
 266   return _leaf(t)->leaf;
 267
 268 #line 33 "test_gc17.pcc"
 269       }
 270    } else {
 271 #line 31 "test_gc17.pcc"
 272   return 0;
 273
 274 #line 32 "test_gc17.pcc"
 275    }
 276 }
 277 #line 34 "test_gc17.pcc"
 278 #line 34 "test_gc17.pcc"
 279
 280 }
 281
 282 //////////////////////////////////////////////////////////////////////////////
 283 //  Count the number of pointer sharings.
 284 //////////////////////////////////////////////////////////////////////////////
 285 int sharing (
 286 #line 40 "test_gc17.pcc"
 287 a_TREE<int> *
 288 #line 40 "test_gc17.pcc"
 289  t)
 290 {
 291 #line 46 "test_gc17.pcc"
 292 {
 293    if (t) {
 294       if (t->tag__) {
 295
 296 #line 44 "test_gc17.pcc"
 297        return sharing(_node(t)->_1) + sharing(_node(t)->_3)
 298          + ((_node(t)->_1 != empty && _node(t)->_1 == _node(t)->_3) ? 1 : 0);
 299
 300 #line 46 "test_gc17.pcc"
 301       } else {
 302
 303 #line 43 "test_gc17.pcc"
 304   return 0;
 305
 306 #line 44 "test_gc17.pcc"
 307       }
 308    } else {
 309 #line 42 "test_gc17.pcc"
 310   return 0;
 311
 312 #line 43 "test_gc17.pcc"
 313    }
 314 }
 315 #line 46 "test_gc17.pcc"
 316 #line 46 "test_gc17.pcc"
 317
 318 }
 319
 320 //////////////////////////////////////////////////////////////////////////////
 321 //  Compute the size of a tree
 322 //////////////////////////////////////////////////////////////////////////////
 323 template <class T>
 324    int size (
 325 #line 53 "test_gc17.pcc"
 326 a_TREE<T> *
 327 #line 53 "test_gc17.pcc"
 328  t)
 329    {
 330 #line 58 "test_gc17.pcc"
 331 {
 332    if (t) {
 333       if (t->tag__) {
 334
 335 #line 57 "test_gc17.pcc"
 336        return size(_node(t)->_1) + 1 + size(_node(t)->_3);
 337
 338 #line 58 "test_gc17.pcc"
 339       } else {
 340
 341 #line 56 "test_gc17.pcc"
 342   return 1;
 343
 344 #line 57 "test_gc17.pcc"
 345       }
 346    } else {
 347 #line 55 "test_gc17.pcc"
 348   return 0;
 349
 350 #line 56 "test_gc17.pcc"
 351    }
 352 }
 353 #line 58 "test_gc17.pcc"
 354 #line 58 "test_gc17.pcc"
 355
 356    }
 357
 358 //////////////////////////////////////////////////////////////////////////////
 359 //  Check a tree for correctness.
 360 //////////////////////////////////////////////////////////////////////////////
 361 template <class T>
 362    void check (
 363 #line 65 "test_gc17.pcc"
 364 a_TREE<T> *
 365 #line 65 "test_gc17.pcc"
 366  t)
 367    {
 368 #line 74 "test_gc17.pcc"
 369 {
 370    if (t) {
 371       if (t->tag__) {
 372
 373 #line 69 "test_gc17.pcc"
 374
 375          assert (HM::is_mapped(t) &&
 376                  HM::page_gc(t) == GC::get_default_gc().gc_id());
 377          assert (HM::get_object_map().is_marked(t));
 378          check(_node(t)->_1); check(_node(t)->_3);
 379
 380 #line 74 "test_gc17.pcc"
 381       } else {
 382
 383 #line 68 "test_gc17.pcc"
 384   return;
 385
 386 #line 69 "test_gc17.pcc"
 387       }
 388    } else {
 389 #line 67 "test_gc17.pcc"
 390   return;
 391
 392 #line 68 "test_gc17.pcc"
 393    }
 394 }
 395 #line 74 "test_gc17.pcc"
 396 #line 74 "test_gc17.pcc"
 397
 398    }
 399
 400 //////////////////////////////////////////////////////////////////////////////
 401 //  Routine to make a random tree of a certain size.
 402 //////////////////////////////////////////////////////////////////////////////
 403 #line 80 "test_gc17.pcc"
 404 a_TREE<int> *
 405 #line 80 "test_gc17.pcc"
 406  make_tree(int n)
 407 {  if (n == 0) return empty;
 408    int split = rand() % n;
 409    int data  = rand() % n;
 410 #ifdef SHARING
 411    if ((n % 2 == 1) && (rand() % 2 == 1)) {
 412       a_TREE<int> *
 413 #line 86 "test_gc17.pcc"
 414  t = make_tree(n/2);
 415       return node(t, data, t);
 416    }
 417 #endif
 418    return node(make_tree(split), data, make_tree(n - split - 1));
 419 }
 420
 421 void testing()
 422 {
 423    for (int trial = 1; trial <= TRIALS; trial++) {
 424        cout << "Trial number " << trial << '\n' << flush;
 425        a_TREE<int> *
 426 #line 97 "test_gc17.pcc"
 427  tree1    = make_tree(NODES);
 428        int       size1    = size(tree1);
 429        int       sum1     = sum(tree1);
 430        int       sharing1 = sharing (tree1);
 431        check(tree1);
 432
 433        cout << "Size = " << size1 << " check sum = " << sum1
 434             << " pointer sharing = " << sharing1 << '\n' << flush;
 435
 436        make_tree(NODES);              // this just generates a lot of garbage
 437
 438        // Now traverse the tree check things.
 439        assert(size(tree1)     == NODES);
 440        assert(sum(tree1)      == sum1);
 441        assert(sharing(tree1)  == sharing1);
 442        check(tree1);
 443        cout << "Trial number " << trial << " has passed\n";
 444    }
 445 }
 446
 447 int main()
 448 {
 449    cout <<
 450      "This test generate random dags and try to see if garbage collection\n"
 451      "works on preserving pointer sharing correctly.  I'll do this "
 452       << TRIALS << " times.\n";
 453    srand(getpid());
 454    testing();
 455    // force an explicit garbage collection
 456    cout << "Finished.  Now I'm forcing another garbage collection to clean\n"
 457            "things up.  There should be very little garbage left at the end.\n";
 458    GC::garbage_collect();
 459    return 0;
 460 }
 461 /*
 462 ------------------------------- Statistics -------------------------------
 463 Merge matching rules         = yes
 464 Number of DFA nodes merged   = 0
 465 Number of ifs generated      = 8
 466 Number of switches generated = 0
 467 Number of labels             = 0
 468 Number of gotos              = 0
 469 Adaptive matching            = disabled
 470 Fast string matching         = disabled
 471 Inline downcasts             = disabled
 472 --------------------------------------------------------------------------
 473 */