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