1// { dg-do assemble } 2// prms-id: 1989 3 4#define TRUE true 5#define FALSE false 6typedef void *Pix; 7 8template<class T> 9struct 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 20template<class T> 21class List_DL { 22public: 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 40private: 41 42 unsigned count; 43 link<T> *head; 44 link<T> *tail; 45 46public: 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 59template<class T> 60List_DL<T>::List_DL(): 61count(0), 62head(0) 63{ } 64 65template<class T> 66List_DL<T>::List_DL(const List_DL& other): 67count(0), 68head(0) 69{ 70 for (Pix x=other.first(); 0 != x; other.next(x)) 71 append(other(x)); 72} 73 74template<class T> 75List_DL<T>::~List_DL() 76{ 77 clear(); 78} 79 80template<class T> 81void 82List_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 94template<class T> 95void 96List_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 109template<class T> 110void 111List_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 134template<class T> 135void 136List_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 168template<class T> 169void 170List_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 181template<class T> 182class List_DLS: public List_DL<T> { 183public: 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 194template<class T> 195Pix 196List_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 return x; 201 } 202 return 0; 203} 204 205template<class T> 206class List_DLSp: public List_DL<T> { 207public: 208 List_DLSp(): List_DL<T>() 209 { } 210 List_DLSp(const List_DLSp& other): List_DL<T>(other) 211 { } 212 213 bool contains(const T& item) const 214#ifndef INTERNAL_ERROR 215 ; 216#else 217 { return search(item) != 0 ? TRUE: FALSE; } 218#endif 219 Pix search(const T&) const; 220}; 221 222template<class T> 223bool 224List_DLSp<T>::contains(const T& item) const 225{ 226 for (Pix x=this->first(); 0 != x; this->next(x)) { 227 if (*item == *(this->operator()(x))) 228 return TRUE; 229 } 230 return FALSE; 231} 232 233template<class T> 234class Set { 235public: 236 Set(); 237 Set(const Set& other); 238 239 virtual void add(const T& item); 240 241 void remove(const T& item) 242 { Pix x = search(item); remove(x); } 243 void remove(Pix& x) 244 { T tmp; remove(x, tmp); } 245 virtual void remove(Pix& x, T& item); 246 247 virtual void clear(); 248 249 virtual bool contains(const T&) const; 250 virtual Pix search(const T&) const; 251 252 virtual unsigned length() const; 253 254 virtual Pix first() const; 255 virtual void next(Pix& x) const; 256 virtual T& operator()(Pix x) const; 257}; 258 259template<class T> 260Set<T>::Set() 261{ } 262 263template<class T> 264Set<T>::Set(const Set& other) 265{ } 266 267 268template<class T> 269class Set_DL: public List_DLS<T> { 270public: 271 Set_DL(); 272 Set_DL(const Set_DL& other); 273 274 void add(const T& item) 275 { list.append(item); } 276 void remove(Pix& x, T& item) 277 { list.remove(x, item); } 278 279 void clear() 280 { list.clear(); } 281 282 bool contains(const T& item) const 283 { return list.contains(item); } 284 Pix search(const T& item) const 285 { return list.search(item); } 286 287 unsigned length() const 288 { return list.length(); } 289 290 Pix first() const 291 { return list.first(); } 292 void next(Pix& x) const 293 { list.next(x); } 294 T& operator()(Pix x) const 295 { return list(x); } 296private: 297 List_DLS<T> list; 298}; 299 300template<class T> 301class Set_DLp: public List_DLSp<T> { 302public: 303 Set_DLp(); 304 Set_DLp(const Set_DLp& other); 305 306 void add(const T& item) 307 { list.append(item); } 308 void remove(Pix& x, T& item) 309 { list.remove(x, item); } 310 311 void clear() 312 { list.clear(); } 313 314 bool contains(const T& item) const 315 { return list.contains(item); } 316 Pix search(const T& item) const 317 { return list.search(item); } 318 319 unsigned length() const 320 { return list.length(); } 321 322 Pix first() const 323 { return list.first(); } 324 void next(Pix& x) const 325 { list.next(x); } 326 T& operator()(Pix x) const 327 { return list(x); } 328private: 329 List_DLSp<T> list; 330}; 331 332template<class T> 333struct vertex { 334 T item; 335 List_DL<vertex<T> *> fanout; 336 337 vertex(): item(), fanout() // { dg-bogus "" } 338 { } 339 vertex(const T& i): item(), fanout() // { dg-bogus "" } 340 { } 341}; 342 343template<class T> 344class Graph { 345public: 346 Graph(); 347 Graph(const Graph&); 348 ~Graph(); 349 350 void add(const T& from, const T& to); 351 bool contains(const T& from, const T& to) const; 352 353 void clear() 354 { vertices.clear(); } 355 356 unsigned lengthV() const 357 { return vertices.length(); } 358 359 Pix firstV() const 360 { return vertices.first(); } 361 void nextV(Pix& x) const 362 { vertices.next(x); } 363 T& V(Pix x) const 364 { return vertices(x).item; } 365 366 Pix firstV1(Pix vx) const; 367 void nextV1(Pix vx, Pix& x) const; 368 T& V1(Pix vx, Pix x) const; 369private: 370 vertex<T> *lookup(const T& from) const; 371 vertex<T> *lookup_new(const T& from); 372 373 List_DLS<vertex<T> > vertices; 374}; 375 376template<class T> 377Graph<T>::Graph(): 378vertices() 379{ } 380 381template<class T> 382Graph<T>::Graph(const Graph& other): 383vertices() 384{ 385 for (Pix vx=firstV(); 0 != vx; nextV(vx)) { 386 for (Pix vx1=firstV1(vx); 0 != vx1; nextV1(vx, vx1)) { 387 add(V(vx), V1(vx, vx1)); 388 } 389 } 390} 391 392template<class T> 393Graph<T>::~Graph() 394{ 395 clear(); 396} 397 398template<class T> 399void 400Graph<T>::add(const T& from, const T& to) 401{ 402 vertex<T> *fromv = lookup_new(from); 403 if (from == to) 404 return; 405 vertex<T> *tov = lookup_new(to); 406 fromv->fanout.append(tov); 407} 408 409template<class T> 410bool 411Graph<T>::contains(const T& from, const T& to) const 412{ 413 vertex<T> *fromv = lookup(from); 414 if (0 == fromv) 415 return FALSE; 416 417 for (Pix x=fromv->fanout.first(); 0 != x; fromv->fanout.next(x)) { 418 if (fromv->fanout(x)->item == to) 419 return TRUE; 420 } 421 422 return FALSE; 423} 424 425template<class T> 426vertex<T> * 427Graph<T>::lookup(const T& from) const 428{ 429 for (Pix x=vertices.first(); 0 != x; vertices.next(x)) { 430 if (vertices(x).item == from) 431 return &vertices(x); 432 } 433 return 0; 434} 435 436template<class T> 437vertex<T> * 438Graph<T>::lookup_new(const T& from) 439{ 440 vertex<T> *v = lookup(from); 441 if (0 == v) { 442 vertices.append(from); 443 return &vertices(vertices.last()); 444 } 445 return v; 446} 447 448template<class T> 449Pix 450Graph<T>::firstV1(Pix vx) const 451{ 452 vertex<T> *v = (vertex<T> *) vx; 453 return v->fanout.first(); 454} 455 456template<class T> 457void 458Graph<T>::nextV1(Pix vx, Pix& x) const 459{ 460 vertex<T> *v = (vertex<T> *) vx; 461 return v->fanout.next(x); 462} 463 464template<class T> 465T& 466Graph<T>::V1(Pix vx, Pix x) const 467{ 468 vertex<T> *v = (vertex<T> *) vx; 469 static T x1; 470 return x1; 471} 472 473class STRLIdentifier; 474 475extern int x(List_DL<STRLIdentifier *>); 476extern int x(List_DLS<STRLIdentifier *>); 477 478extern int x(Set<STRLIdentifier *>); 479extern int x(Set_DL<STRLIdentifier *>); 480extern int x(Set_DLp<STRLIdentifier *>); 481 482extern int x(Graph<STRLIdentifier *>); 483 484class STRLIdentifier { 485 char buf[10]; 486}; 487 488extern int operator==(vertex<STRLIdentifier*>&, vertex<STRLIdentifier*>&); // { dg-message "candidates" } const subversion 489extern int operator==(STRLIdentifier&, STRLIdentifier&); // { dg-message "note" } fn ref in err msg 490 491extern int x(List_DLSp<STRLIdentifier *>); 492 493template class Graph<STRLIdentifier *>; 494template class List_DLS<vertex<STRLIdentifier *> >; 495