tests/hashcons2.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 //  This file is generated automatically using Prop (version 2.0.6),
   3 //  last updated on Apr 5th, 1995.  Please be sure not to alter this file
   4 //  directly.  Instead, refer to the original source file "hashcons2.pcc".
   5 //////////////////////////////////////////////////////////////////////////////
   6 #define PROP_REFERENCE_COUNTING_USED
   7 #define PROP_HASH_CONSING_USED
   8 #include <propinc.h>
   9
  10 #line 1 "hashcons2.pcc"
  11 //
  12 //  This is a simple (and useless) example for testing the hash cons feature
  13 //  in Prop.
  14 //
  15 #include <iostream.h>
  16 #include <new.h>
  17
  18 int balance = 0;
  19
  20 #line 10 "hashcons2.pcc"
  21 ////////////////////////////////////////////////////////////////////////
  22 // Forward declarations for datatype EXP
  23 ////////////////////////////////////////////////////////////////////////
  24 #ifndef datatype_EXP_defined
  25 #define datatype_EXP_defined
  26    class a_EXP;
  27    typedef ConstRef<a_EXP> EXP;
  28 #endif
  29 class EXP_num;
  30 class EXP_add;
  31 class EXP_sub;
  32 class EXP_mul;
  33 class EXP_div;
  34 ////////////////////////////////////////////////////////////////////////
  35 // Forward declarations for datatype LIST
  36 ////////////////////////////////////////////////////////////////////////
  37 #ifndef datatype_LIST_defined
  38 #define datatype_LIST_defined
  39    class a_LIST;
  40    typedef ConstRef<a_LIST> LIST;
  41 #endif
  42 ////////////////////////////////////////////////////////////////////////
  43 // Definition of datatype EXP
  44 ////////////////////////////////////////////////////////////////////////
  45 class a_EXP : public RefObj  {
  46 public:
  47    /////////////////////////////////////////////////////////////////
  48    //  Variant tags for datatype EXP
  49    /////////////////////////////////////////////////////////////////
  50 #line 10 "hashcons2.pcc"
  51    enum Tag_EXP {
  52       tag_num = 0, tag_add = 1, tag_sub = 2, tag_mul = 3, tag_div = 4
  53    };
  54
  55 protected:
  56    /////////////////////////////////////////////////////////////////
  57    //  The variant tag and its constructor
  58    /////////////////////////////////////////////////////////////////
  59    const Tag_EXP tag;
  60    inline a_EXP(Tag_EXP t) : tag(t) {}
  61 public:
  62    /////////////////////////////////////////////////////////////////
  63    //  Untagging and variant testing functions
  64    /////////////////////////////////////////////////////////////////
  65    inline int untag() const { return tag; }
  66    inline friend int boxed(EXP& x) { return 1; }
  67    inline friend int untag(EXP& x) { return x->tag; }
  68    /////////////////////////////////////////////////////////////////
  69    // Downcasting functions for datatype EXP
  70    /////////////////////////////////////////////////////////////////
  71    inline friend const EXP_num * _num(EXP& _x_) { return (const EXP_num *)_x_._raw(); }
  72    inline friend const EXP_add * _add(EXP& _x_) { return (const EXP_add *)_x_._raw(); }
  73    inline friend const EXP_sub * _sub(EXP& _x_) { return (const EXP_sub *)_x_._raw(); }
  74    inline friend const EXP_mul * _mul(EXP& _x_) { return (const EXP_mul *)_x_._raw(); }
  75    inline friend const EXP_div * _div(EXP& _x_) { return (const EXP_div *)_x_._raw(); }
  76 public:
  77
  78 #line 15 "hashcons2.pcc"
  79   inline void * operator new    (size_t n) { balance++; cerr << '+'; return new char [n]; }
  80            inline void   operator delete (void * x) { balance--; cerr << '-'; delete [] ((char*)x); }
  81            ///////////////////////////////////////////////////////////////////////////
  82    //  Interface for hash consing
  83    ///////////////////////////////////////////////////////////////////////////
  84    friend Bool         equal(EXP, EXP);
  85    friend unsigned int hash (EXP);
  86    static a_EXP * make_hash_cons(a_EXP *);
  87
  88    /////////////////////////////////////////////////////////////////
  89    //  Destructor
  90    /////////////////////////////////////////////////////////////////
  91    virtual ~a_EXP();
  92 };
  93
  94
  95 ////////////////////////////////////////////////////////////////////////
  96 // Subclass for implementing constructor 'num int ' of EXP
  97 ////////////////////////////////////////////////////////////////////////
  98 class EXP_num : public a_EXP {
  99 public:
 100 #line 10 "hashcons2.pcc"
 101    int num;
 102 public:
 103    inline EXP_num(int _x_)
 104       : a_EXP(a_EXP::tag_num), num(_x_) {}
 105    inline friend EXP num(int _x_)
 106       { return a_EXP::make_hash_cons(new EXP_num (_x_)); }
 107    /////////////////////////////////////////////////////////////////
 108    //  Destructor
 109    /////////////////////////////////////////////////////////////////
 110    virtual ~EXP_num();
 111 };
 112
 113
 114 ////////////////////////////////////////////////////////////////////////
 115 // Subclass for implementing constructor 'add (EXP , EXP ) ' of EXP
 116 ////////////////////////////////////////////////////////////////////////
 117 class EXP_add : public a_EXP {
 118 public:
 119 #line 11 "hashcons2.pcc"
 120    EXP _1; EXP _2;
 121 public:
 122    inline EXP_add(EXP& _x_1, EXP& _x_2)
 123       : a_EXP(a_EXP::tag_add), _1(_x_1), _2(_x_2) {}
 124    inline friend EXP add(EXP& _x_1, EXP& _x_2)
 125       { return a_EXP::make_hash_cons(new EXP_add (_x_1, _x_2)); }
 126    /////////////////////////////////////////////////////////////////
 127    //  Destructor
 128    /////////////////////////////////////////////////////////////////
 129    virtual ~EXP_add();
 130 };
 131
 132
 133 ////////////////////////////////////////////////////////////////////////
 134 // Subclass for implementing constructor 'sub (EXP , EXP ) ' of EXP
 135 ////////////////////////////////////////////////////////////////////////
 136 class EXP_sub : public a_EXP {
 137 public:
 138 #line 12 "hashcons2.pcc"
 139    EXP _1; EXP _2;
 140 public:
 141    inline EXP_sub(EXP& _x_1, EXP& _x_2)
 142       : a_EXP(a_EXP::tag_sub), _1(_x_1), _2(_x_2) {}
 143    inline friend EXP sub(EXP& _x_1, EXP& _x_2)
 144       { return a_EXP::make_hash_cons(new EXP_sub (_x_1, _x_2)); }
 145    /////////////////////////////////////////////////////////////////
 146    //  Destructor
 147    /////////////////////////////////////////////////////////////////
 148    virtual ~EXP_sub();
 149 };
 150
 151
 152 ////////////////////////////////////////////////////////////////////////
 153 // Subclass for implementing constructor 'mul (EXP , EXP ) ' of EXP
 154 ////////////////////////////////////////////////////////////////////////
 155 class EXP_mul : public a_EXP {
 156 public:
 157 #line 13 "hashcons2.pcc"
 158    EXP _1; EXP _2;
 159 public:
 160    inline EXP_mul(EXP& _x_1, EXP& _x_2)
 161       : a_EXP(a_EXP::tag_mul), _1(_x_1), _2(_x_2) {}
 162    inline friend EXP mul(EXP& _x_1, EXP& _x_2)
 163       { return a_EXP::make_hash_cons(new EXP_mul (_x_1, _x_2)); }
 164    /////////////////////////////////////////////////////////////////
 165    //  Destructor
 166    /////////////////////////////////////////////////////////////////
 167    virtual ~EXP_mul();
 168 };
 169
 170
 171 ////////////////////////////////////////////////////////////////////////
 172 // Subclass for implementing constructor 'div (EXP , EXP ) ' of EXP
 173 ////////////////////////////////////////////////////////////////////////
 174 class EXP_div : public a_EXP {
 175 public:
 176 #line 14 "hashcons2.pcc"
 177    EXP _1; EXP _2;
 178 public:
 179    inline EXP_div(EXP& _x_1, EXP& _x_2)
 180       : a_EXP(a_EXP::tag_div), _1(_x_1), _2(_x_2) {}
 181    inline friend EXP div(EXP& _x_1, EXP& _x_2)
 182       { return a_EXP::make_hash_cons(new EXP_div (_x_1, _x_2)); }
 183    /////////////////////////////////////////////////////////////////
 184    //  Destructor
 185    /////////////////////////////////////////////////////////////////
 186    virtual ~EXP_div();
 187 };
 188
 189 ////////////////////////////////////////////////////////////////////////
 190 // Definition of datatype LIST
 191 ////////////////////////////////////////////////////////////////////////
 192 class a_LIST : public RefObj  {
 193 public:
 194    /////////////////////////////////////////////////////////////////
 195    //  Untagging and variant testing functions
 196    /////////////////////////////////////////////////////////////////
 197    inline friend int boxed(LIST& x) { return x != 0; }
 198    inline friend int untag(LIST& x) { return x ? 1 : 0; }
 199 #  define nil (LIST)0
 200 #line 20 "hashcons2.pcc"
 201    EXP _1; LIST _2;
 202 public:
 203    inline a_LIST(EXP& _x_1, LIST& _x_2) : _1(_x_1), _2(_x_2) {}
 204    inline friend LIST list(EXP& _x_1, LIST& _x_2)
 205       { return a_LIST::make_hash_cons(new a_LIST (_x_1, _x_2)); }
 206 public:
 207
 208 #line 21 "hashcons2.pcc"
 209   inline void * operator new    (size_t n) { balance++; cerr << '>'; return new char [n]; }
 210            inline void   operator delete (void * x) { balance--; cerr << '<'; delete [] ((char*)x); }
 211            ///////////////////////////////////////////////////////////////////////////
 212    //  Interface for hash consing
 213    ///////////////////////////////////////////////////////////////////////////
 214    friend Bool         equal(LIST, LIST);
 215    friend unsigned int hash (LIST);
 216    static a_LIST * make_hash_cons(a_LIST *);
 217
 218    /////////////////////////////////////////////////////////////////
 219    //  Destructor
 220    /////////////////////////////////////////////////////////////////
 221    virtual ~a_LIST();
 222 };
 223
 224 #line 24 "hashcons2.pcc"
 225
 226
 227 //
 228 //  implement the datatypes.
 229 //
 230 #line 29 "hashcons2.pcc"
 231 //////////////////////////////////////////////////////////////////////////////
 232 //  Equality function for EXP
 233 //  Shallow equality is assumed
 234 //////////////////////////////////////////////////////////////////////////////
 235 Bool equal(EXP _x_, EXP _y_)
 236 {
 237    int _x_tag_ = untag(_x_);
 238    int _y_tag_ = untag(_y_);
 239    if (_x_tag_ != _y_tag_) return false;
 240    switch (_x_tag_) {
 241       case 0:
 242          if (_num(_x_)->num != _num(_y_)->num) return false;
 243       break;
 244       case 1:
 245          if (_add(_x_)->_2 != _add(_y_)->_2) return false;
 246          if (_add(_x_)->_1 != _add(_y_)->_1) return false;
 247       break;
 248       case 2:
 249          if (_sub(_x_)->_2 != _sub(_y_)->_2) return false;
 250          if (_sub(_x_)->_1 != _sub(_y_)->_1) return false;
 251       break;
 252       case 3:
 253          if (_mul(_x_)->_2 != _mul(_y_)->_2) return false;
 254          if (_mul(_x_)->_1 != _mul(_y_)->_1) return false;
 255       break;
 256       case 4:
 257          if (_div(_x_)->_2 != _div(_y_)->_2) return false;
 258          if (_div(_x_)->_1 != _div(_y_)->_1) return false;
 259       break;
 260    }
 261    return true;
 262 }
 263
 264 //////////////////////////////////////////////////////////////////////////////
 265 //  Hashing function for EXP
 266 //  Shallow hashing is used
 267 //////////////////////////////////////////////////////////////////////////////
 268 unsigned int hash(EXP _x_)
 269 {
 270    unsigned int _h_;
 271    switch (_h_ = untag(_x_)) {
 272       case 0:
 273          _h_ = hash(_num(_x_)->num);
 274       break;
 275       case 1:
 276          _h_ += (unsigned int)(_add(_x_)->_1);
 277          _h_ += (unsigned int)(_add(_x_)->_2);
 278       break;
 279       case 2:
 280          _h_ += (unsigned int)(_sub(_x_)->_1);
 281          _h_ += (unsigned int)(_sub(_x_)->_2);
 282       break;
 283       case 3:
 284          _h_ += (unsigned int)(_mul(_x_)->_1);
 285          _h_ += (unsigned int)(_mul(_x_)->_2);
 286       break;
 287       case 4:
 288          _h_ += (unsigned int)(_div(_x_)->_1);
 289          _h_ += (unsigned int)(_div(_x_)->_2);
 290       break;
 291    }
 292    return _h_;
 293 }
 294
 295 //////////////////////////////////////////////////////////////////////////////
 296 //  Hash consing implementation for EXP
 297 //////////////////////////////////////////////////////////////////////////////
 298 static LHashTable<EXP, EXP> EXP_universe;
 299 a_EXP * a_EXP::make_hash_cons(a_EXP * _x_)
 300 {  EXP _r_(_x_);
 301    Ix i = EXP_universe.lookup(_r_);
 302    if (i == 0) { EXP_universe.insert(_r_,_r_); return _x_; }
 303    else        { return EXP_universe.value(i)._pin(); }
 304 }
 305
 306 ////////////////////////////////////////////////////////////////////
 307 //  Destructor(s) for class EXP
 308 ////////////////////////////////////////////////////////////////////
 309 #line 29 "hashcons2.pcc"
 310 a_EXP::~a_EXP() {}
 311 EXP_num::~EXP_num() {}
 312 EXP_add::~EXP_add() {}
 313 EXP_sub::~EXP_sub() {}
 314 EXP_mul::~EXP_mul() {}
 315 EXP_div::~EXP_div() {}
 316 //////////////////////////////////////////////////////////////////////////////
 317 //  Equality function for LIST
 318 //  Shallow equality is assumed
 319 //////////////////////////////////////////////////////////////////////////////
 320 Bool equal(LIST _x_, LIST _y_)
 321 {
 322    int _x_tag_ = untag(_x_);
 323    int _y_tag_ = untag(_y_);
 324    if (_x_tag_ != _y_tag_) return false;
 325    switch (_x_tag_) {
 326       case 0:
 327       break;
 328       case 1:
 329          if ((_x_)->_2 != (_y_)->_2) return false;
 330          if ((_x_)->_1 != (_y_)->_1) return false;
 331       break;
 332    }
 333    return true;
 334 }
 335
 336 //////////////////////////////////////////////////////////////////////////////
 337 //  Hashing function for LIST
 338 //  Shallow hashing is used
 339 //////////////////////////////////////////////////////////////////////////////
 340 unsigned int hash(LIST _x_)
 341 {
 342    unsigned int _h_;
 343    switch (_h_ = untag(_x_)) {
 344       case 0:
 345          _h_ = (unsigned int)_x_;
 346       break;
 347       case 1:
 348          _h_ += (unsigned int)((_x_)->_1);
 349          _h_ += (unsigned int)((_x_)->_2);
 350       break;
 351    }
 352    return _h_;
 353 }
 354
 355 //////////////////////////////////////////////////////////////////////////////
 356 //  Hash consing implementation for LIST
 357 //////////////////////////////////////////////////////////////////////////////
 358 static LHashTable<LIST, LIST> LIST_universe;
 359 a_LIST * a_LIST::make_hash_cons(a_LIST * _x_)
 360 {  LIST _r_(_x_);
 361    Ix i = LIST_universe.lookup(_r_);
 362    if (i == 0) { LIST_universe.insert(_r_,_r_); return _x_; }
 363    else        { return LIST_universe.value(i)._pin(); }
 364 }
 365
 366 ////////////////////////////////////////////////////////////////////
 367 //  Destructor(s) for class LIST
 368 ////////////////////////////////////////////////////////////////////
 369 #line 29 "hashcons2.pcc"
 370 a_LIST::~a_LIST() {}
 371 #line 29 "hashcons2.pcc"
 372
 373
 374 ostream& operator << (ostream& f, EXP e)
 375 {
 376
 377 #line 33 "hashcons2.pcc"
 378 { switch (e->untag()) {
 379 case a_EXP::tag_num: {
 380 #line 34 "hashcons2.pcc"
 381  return f << (_num(e)->num); } break;
 382 case a_EXP::tag_add: {
 383 #line 35 "hashcons2.pcc"
 384  return f << '(' << (_add(e))->_1 << " + " << (_add(e))->_2 << ')'; } break;
 385 case a_EXP::tag_sub: {
 386 #line 36 "hashcons2.pcc"
 387  return f << '(' << (_sub(e))->_1 << " - " << (_sub(e))->_2 << ')'; } break;
 388 case a_EXP::tag_mul: {
 389 #line 37 "hashcons2.pcc"
 390  return f << '(' << (_mul(e))->_1 << " * " << (_mul(e))->_2 << ')'; } break;
 391 default:; {
 392 #line 38 "hashcons2.pcc"
 393  return f << '(' << (_div(e))->_1 << " / " << (_div(e))->_2 << ')'; }
 394 } }
 395
 396 #line 39 "hashcons2.pcc"
 397
 398 }
 399
 400 ostream& operator << (ostream& f, LIST l)
 401 {
 402
 403 #line 44 "hashcons2.pcc"
 404 { if (l) {
 405 if ((l)->_2) {
 406 {
 407 #line 47 "hashcons2.pcc"
 408      return f << (l)->_1 << ',' << (l)->_2;
 409    }} else {
 410 {
 411 #line 46 "hashcons2.pcc"
 412    return f << (l)->_1;
 413       }}
 414 } else {
 415 {
 416 #line 45 "hashcons2.pcc"
 417            return f;
 418       }}
 419 }
 420
 421 #line 48 "hashcons2.pcc"
 422
 423 }
 424
 425 void do_something()
 426 {
 427    cout << "Balance = " << balance << '\n'
 428         << "EXP  hash table size = " << EXP_universe.size() << '\n'
 429         << "LIST hash table size = " << LIST_universe.size() << '\n';
 430    EXP e1 = mul(add(num(1),num(2)), add(num(2), num(3)));
 431    EXP e2 = mul(add(num(1),num(2)), add(num(2), num(3)));
 432    LIST l1 = list(e1, list(e2, nil));
 433    cout << l1 << '\n';
 434    cout << ((e1 == e2) ? "Good!\n" : "Bad boy! Naughty, naughty boy!\n");
 435    cout << ((num(1) == num(1)) ? "Good!\n" : "Bad boy! Naughty, naughty boy!\n");
 436    cout << ((num(1) != num(2)) ? "Good!\n" : "Bad boy! Naughty, naughty boy!\n");
 437    cout << ((add(e1,e2) == add(e1,e2)) ? "Good!\n" : "Bad boy! Naughty, naughty boy!\n");
 438    cout << ((add(e1,e2) != add(e1,num(2))) ? "Good!\n" : "Bad boy! Naughty, naughty boy!\n");
 439    cout << "Balance = " << balance << '\n'
 440         << "EXP  hash table size = " << EXP_universe.size() << '\n'
 441         << "LIST hash table size = " << LIST_universe.size() << '\n';
 442 }
 443
 444 int main()
 445 {
 446    do_something();
 447    cout << "Balance = " << balance << '\n'
 448         << "EXP  hash table size = " << EXP_universe.size() << '\n'
 449         << "LIST hash table size = " << LIST_universe.size() << '\n';
 450    return 0;
 451 }
 452 /*
 453 ----------------------------- Statistics -------------------------------
 454 Number of decision nodes merged = 0
 455 Number of switches generated    = 1
 456 Number of ifs      generated    = 2
 457 Number of labels   generated    = 0
 458 Number of gotos    generated    = 0
 459 Number of temporary variables   = 0
 460 ------------------------------------------------------------------------
 461 */