gcc/testsuite/g++.old-deja/g++.mike/p1989.C

   1 // { dg-do assemble  }
   2 // prms-id: 1989
   3
   4 #define TRUE true
   5 #define FALSE false
   6 typedef void *Pix;
   7
   8 template<class T>
   9 struct link {
  10     T item;
  11     link *next;
  12     link *prev;
  13
  14     link(const T& t): item(t), prev(0), next(0)
  15         { }
  16     link(const T& t, link<T> *p, link<T> *n): item(t), prev(p), next(n)
  17         { }
  18 };
  19
  20 template<class T>
  21 class List_DL {
  22 public:
  23     List_DL();
  24     List_DL(const List_DL&);
  25     ~List_DL();
  26
  27     void append(const T& item);
  28     void prepend(const T& item);
  29     void insert(const T& item, Pix x, bool before);
  30
  31     void remove(Pix& x)
  32         { T tmp; remove(x, tmp); }
  33     void remove(Pix& x, T& item);
  34
  35     void clear();
  36
  37     unsigned length() const
  38         { return count; }
  39
  40 private:
  41
  42     unsigned count;
  43     link<T> *head;
  44     link<T> *tail;
  45
  46 public:
  47     Pix first() const
  48         { return Pix(head); }
  49     Pix last() const
  50         { return Pix(tail); }
  51     void next(Pix& x) const
  52         { if (0 != x) x = ((link<T> *) x)->next; }
  53     void prev(Pix& x) const
  54         { if (0 != x) x = ((link<T> *) x)->prev; }
  55     T& operator()(Pix x) const
  56         { return ((link<T> *) x)->item; }
  57 };
  58
  59 template<class T>
  60 List_DL<T>::List_DL():
  61 count(0),
  62 head(0)
  63 { }
  64
  65 template<class T>
  66 List_DL<T>::List_DL(const List_DL& other):
  67 count(0),
  68 head(0)
  69 {
  70     for (Pix x=other.first(); 0 != x; other.next(x))
  71         append(other(x));
  72 }
  73
  74 template<class T>
  75 List_DL<T>::~List_DL()
  76 {
  77     clear();
  78 }
  79
  80 template<class T>
  81 void
  82 List_DL<T>::append(const T& item)
  83 {
  84     count++;
  85     if (0 == head) {
  86         head = new link<T>(item);
  87         tail = head;
  88     } else {
  89         tail->next = new link<T>(item, tail, 0);
  90         tail = tail->next;
  91     }
  92 }
  93
  94 template<class T>
  95 void
  96 List_DL<T>::prepend(const T& item)
  97 {
  98     count++;
  99     if (0 == head) {
 100         head = new link<T>(item);
 101         tail = head;
 102     } else {
 103         head = new link<T>(item, 0, head);
 104         if (tail == head)
 105             tail = tail->next;
 106     }
 107 }
 108
 109 template<class T>
 110 void
 111 List_DL<T>::insert(const T& item, Pix x, bool before = TRUE)
 112 {
 113     link<T> *l = (link<T> *) x;
 114
 115     if (before) {
 116         if (0 == l || l == head) {
 117             prepend(item);
 118         } else {
 119             link<T> *n = new link<T>(item, l->prev, l);
 120             l->prev->next = n;
 121             l->prev = n;
 122         }
 123     } else {
 124         if (0 == l || l == tail) {
 125             append(item);
 126         } else {
 127             link<T> *n = new link<T>(item, l, l->next);
 128             l->next->prev = n;
 129             l->prev = n;
 130         }
 131     }
 132 }
 133
 134 template<class T>
 135 void
 136 List_DL<T>::remove(Pix& x, T& item)
 137 {
 138     link<T> *l = (link<T> *) x;
 139
 140     if (0 == l)
 141         return;
 142
 143     item = l->item;
 144     if (1 == count) {
 145         delete head;
 146         head = 0;
 147         tail = 0;
 148     } else {
 149         // more than one item in the list
 150         if (l == head) {
 151             link<T> *old = head;
 152             head = head->next;
 153             head->prev = 0;
 154             delete old;
 155         } else if (l == tail) {
 156             link<T> *old = tail;
 157             tail = tail->prev;
 158             tail->next = 0;
 159             delete old;
 160         } else {
 161             l->next->prev = l->prev;
 162             l->prev->next = l->next;
 163             delete l;
 164         }
 165     }
 166 }
 167
 168 template<class T>
 169 void
 170 List_DL<T>::clear()
 171 {
 172     link<T> *l, *succ;
 173     for (l=head; 0 != l; l=succ) {
 174         succ = l->next;
 175         delete l;
 176     }
 177     head = 0;
 178     tail = 0;
 179 }
 180
 181 template<class T>
 182 class List_DLS: public List_DL<T> {
 183 public:
 184     List_DLS(): List_DL<T>()
 185         { }
 186     List_DLS(const List_DLS& other): List_DL<T>(other)
 187         { }
 188
 189     bool contains(const T& item) const
 190         { return search(item) != 0 ? TRUE: FALSE; }
 191     Pix search(const T&) const;
 192 };
 193
 194 template<class T>
 195 Pix
 196 List_DLS<T>::search(const T& item) const
 197 {
 198     for (Pix x=this->first(); 0 != x; this->next(x)) {
 199         if (item == this->operator()(x)) // { dg-error "match" } const subversion
 200           // { dg-message "candidate" "candidate note" { target *-*-* } 199 }
 201             return x;
 202     }
 203     return 0;
 204 }
 205
 206 template<class T>
 207 class List_DLSp: public List_DL<T> {
 208 public:
 209     List_DLSp(): List_DL<T>()
 210         { }
 211     List_DLSp(const List_DLSp& other): List_DL<T>(other)
 212         { }
 213
 214     bool contains(const T& item) const
 215 #ifndef INTERNAL_ERROR
 216         ;
 217 #else
 218         { return search(item) != 0 ? TRUE: FALSE; }
 219 #endif
 220     Pix search(const T&) const;
 221 };
 222
 223 template<class T>
 224 bool
 225 List_DLSp<T>::contains(const T& item) const
 226 {
 227     for (Pix x=this->first(); 0 != x; this->next(x)) {
 228         if (*item == *(this->operator()(x)))
 229             return TRUE;
 230     }
 231     return FALSE;
 232 }
 233
 234 template<class T>
 235 class Set {
 236 public:
 237     Set();
 238     Set(const Set& other);
 239
 240     virtual void add(const T& item);
 241
 242     void remove(const T& item)
 243         { Pix x = search(item); remove(x); }
 244     void remove(Pix& x)
 245         { T tmp; remove(x, tmp); }
 246     virtual void remove(Pix& x, T& item);
 247
 248     virtual void clear();
 249
 250     virtual bool contains(const T&) const;
 251     virtual Pix search(const T&) const;
 252
 253     virtual unsigned length() const;
 254
 255     virtual Pix first() const;
 256     virtual void next(Pix& x) const;
 257     virtual T& operator()(Pix x) const;
 258 };
 259
 260 template<class T>
 261 Set<T>::Set()
 262 { }
 263
 264 template<class T>
 265 Set<T>::Set(const Set& other)
 266 { }
 267
 268
 269 template<class T>
 270 class Set_DL: public List_DLS<T> {
 271 public:
 272     Set_DL();
 273     Set_DL(const Set_DL& other);
 274
 275     void add(const T& item)
 276         { list.append(item); }
 277     void remove(Pix& x, T& item)
 278         { list.remove(x, item); }
 279
 280     void clear()
 281         { list.clear(); }
 282
 283     bool contains(const T& item) const
 284         { return list.contains(item); }
 285     Pix search(const T& item) const
 286         { return list.search(item); }
 287
 288     unsigned length() const
 289         { return list.length(); }
 290
 291     Pix first() const
 292         { return list.first(); }
 293     void next(Pix& x) const
 294         { list.next(x); }
 295     T& operator()(Pix x) const
 296         { return list(x); }
 297 private:
 298     List_DLS<T> list;
 299 };
 300
 301 template<class T>
 302 class Set_DLp: public List_DLSp<T> {
 303 public:
 304     Set_DLp();
 305     Set_DLp(const Set_DLp& other);
 306
 307     void add(const T& item)
 308         { list.append(item); }
 309     void remove(Pix& x, T& item)
 310         { list.remove(x, item); }
 311
 312     void clear()
 313         { list.clear(); }
 314
 315     bool contains(const T& item) const
 316         { return list.contains(item); }
 317     Pix search(const T& item) const
 318         { return list.search(item); }
 319
 320     unsigned length() const
 321         { return list.length(); }
 322
 323     Pix first() const
 324         { return list.first(); }
 325     void next(Pix& x) const
 326         { list.next(x); }
 327     T& operator()(Pix x) const
 328         { return list(x); }
 329 private:
 330     List_DLSp<T> list;
 331 };
 332
 333 template<class T>
 334 struct vertex {
 335     T item;
 336     List_DL<vertex<T> *> fanout;
 337
 338     vertex(): item(), fanout()  // { dg-bogus "" }
 339       { }
 340     vertex(const T& i): item(), fanout() // { dg-bogus "" }
 341       { }
 342 };
 343
 344 template<class T>
 345 class Graph {
 346 public:
 347     Graph();
 348     Graph(const Graph&);
 349     ~Graph();
 350
 351     void add(const T& from, const T& to);
 352     bool contains(const T& from, const T& to) const;
 353
 354     void clear()
 355         { vertices.clear(); }
 356
 357     unsigned lengthV() const
 358         { return vertices.length(); }
 359
 360     Pix firstV() const
 361         { return vertices.first(); }
 362     void nextV(Pix& x) const
 363         { vertices.next(x); }
 364     T& V(Pix x) const
 365         { return vertices(x).item; }
 366
 367     Pix firstV1(Pix vx) const;
 368     void nextV1(Pix vx, Pix& x) const;
 369     T& V1(Pix vx, Pix x) const;
 370 private:
 371     vertex<T> *lookup(const T& from) const;
 372     vertex<T> *lookup_new(const T& from);
 373
 374     List_DLS<vertex<T> > vertices;
 375 };
 376
 377 template<class T>
 378 Graph<T>::Graph():
 379 vertices()
 380 { }
 381
 382 template<class T>
 383 Graph<T>::Graph(const Graph& other):
 384 vertices()
 385 {
 386     for (Pix vx=firstV(); 0 != vx; nextV(vx)) {
 387         for (Pix vx1=firstV1(vx); 0 != vx1; nextV1(vx, vx1)) {
 388             add(V(vx), V1(vx, vx1));
 389         }
 390     }
 391 }
 392
 393 template<class T>
 394 Graph<T>::~Graph()
 395 {
 396     clear();
 397 }
 398
 399 template<class T>
 400 void
 401 Graph<T>::add(const T& from, const T& to)
 402 {
 403     vertex<T> *fromv = lookup_new(from);
 404     if (from == to)
 405         return;
 406     vertex<T> *tov = lookup_new(to);
 407     fromv->fanout.append(tov);
 408 }
 409
 410 template<class T>
 411 bool
 412 Graph<T>::contains(const T& from, const T& to) const
 413 {
 414     vertex<T> *fromv = lookup(from);
 415     if (0 == fromv)
 416         return FALSE;
 417
 418     for (Pix x=fromv->fanout.first(); 0 != x; fromv->fanout.next(x)) {
 419         if (fromv->fanout(x)->item == to)
 420             return TRUE;
 421     }
 422
 423     return FALSE;
 424 }
 425
 426 template<class T>
 427 vertex<T> *
 428 Graph<T>::lookup(const T& from) const
 429 {
 430     for (Pix x=vertices.first(); 0 != x; vertices.next(x)) {
 431         if (vertices(x).item == from)
 432             return &vertices(x);
 433     }
 434     return 0;
 435 }
 436
 437 template<class T>
 438 vertex<T> *
 439 Graph<T>::lookup_new(const T& from)
 440 {
 441     vertex<T> *v = lookup(from);
 442     if (0 == v) {
 443         vertices.append(from);
 444         return &vertices(vertices.last());
 445     }
 446     return v;
 447 }
 448
 449 template<class T>
 450 Pix
 451 Graph<T>::firstV1(Pix vx) const
 452 {
 453     vertex<T> *v = (vertex<T> *) vx;
 454     return v->fanout.first();
 455 }
 456
 457 template<class T>
 458 void
 459 Graph<T>::nextV1(Pix vx, Pix& x) const
 460 {
 461     vertex<T> *v = (vertex<T> *) vx;
 462     return v->fanout.next(x);
 463 }
 464
 465 template<class T>
 466 T&
 467 Graph<T>::V1(Pix vx, Pix x) const
 468 {
 469     vertex<T> *v = (vertex<T> *) vx;
 470     static T x1;
 471     return x1;
 472 }
 473
 474 class STRLIdentifier;
 475
 476 extern int x(List_DL<STRLIdentifier *>);
 477 extern int x(List_DLS<STRLIdentifier *>);
 478
 479 extern int x(Set<STRLIdentifier *>);
 480 extern int x(Set_DL<STRLIdentifier *>);
 481 extern int x(Set_DLp<STRLIdentifier *>);
 482
 483 extern int x(Graph<STRLIdentifier *>);
 484
 485 class STRLIdentifier {
 486     char buf[10];
 487 };
 488
 489 extern int operator==(vertex<STRLIdentifier*>&, vertex<STRLIdentifier*>&); // { dg-message "note" } const subversion
 490 extern int operator==(STRLIdentifier&, STRLIdentifier&); // { dg-message "note" } fn ref in err msg
 491
 492 extern int x(List_DLSp<STRLIdentifier *>);
 493
 494 template class Graph<STRLIdentifier *>;
 495 template class List_DLS<vertex<STRLIdentifier *> >;