| 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) // { dg-error "default arguments" } |
| 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 "qualifiers" } const subversion |
| 200 |
return x; |
| 201 |
} |
| 202 |
return 0; |
| 203 |
} |
| 204 |
|
| 205 |
template<class T> |
| 206 |
class List_DLSp: public List_DL<T> { |
| 207 |
public: |
| 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 |
|
| 222 |
template<class T> |
| 223 |
bool |
| 224 |
List_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 |
|
| 233 |
template<class T> |
| 234 |
class Set { |
| 235 |
public: |
| 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 |
|
| 259 |
template<class T> |
| 260 |
Set<T>::Set() |
| 261 |
{ } |
| 262 |
|
| 263 |
template<class T> |
| 264 |
Set<T>::Set(const Set& other) |
| 265 |
{ } |
| 266 |
|
| 267 |
|
| 268 |
template<class T> |
| 269 |
class Set_DL: public List_DLS<T> { |
| 270 |
public: |
| 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); } |
| 296 |
private: |
| 297 |
List_DLS<T> list; |
| 298 |
}; |
| 299 |
|
| 300 |
template<class T> |
| 301 |
class Set_DLp: public List_DLSp<T> { |
| 302 |
public: |
| 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); } |
| 328 |
private: |
| 329 |
List_DLSp<T> list; |
| 330 |
}; |
| 331 |
|
| 332 |
template<class T> |
| 333 |
struct 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 |
|
| 343 |
template<class T> |
| 344 |
class Graph { |
| 345 |
public: |
| 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; |
| 369 |
private: |
| 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 |
|
| 376 |
template<class T> |
| 377 |
Graph<T>::Graph(): |
| 378 |
vertices() |
| 379 |
{ } |
| 380 |
|
| 381 |
template<class T> |
| 382 |
Graph<T>::Graph(const Graph& other): |
| 383 |
vertices() |
| 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 |
|
| 392 |
template<class T> |
| 393 |
Graph<T>::~Graph() |
| 394 |
{ |
| 395 |
clear(); |
| 396 |
} |
| 397 |
|
| 398 |
template<class T> |
| 399 |
void |
| 400 |
Graph<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 |
|
| 409 |
template<class T> |
| 410 |
bool |
| 411 |
Graph<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 |
|
| 425 |
template<class T> |
| 426 |
vertex<T> * |
| 427 |
Graph<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 |
|
| 436 |
template<class T> |
| 437 |
vertex<T> * |
| 438 |
Graph<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 |
|
| 448 |
template<class T> |
| 449 |
Pix |
| 450 |
Graph<T>::firstV1(Pix vx) const |
| 451 |
{ |
| 452 |
vertex<T> *v = (vertex<T> *) vx; |
| 453 |
return v->fanout.first(); |
| 454 |
} |
| 455 |
|
| 456 |
template<class T> |
| 457 |
void |
| 458 |
Graph<T>::nextV1(Pix vx, Pix& x) const |
| 459 |
{ |
| 460 |
vertex<T> *v = (vertex<T> *) vx; |
| 461 |
return v->fanout.next(x); |
| 462 |
} |
| 463 |
|
| 464 |
template<class T> |
| 465 |
T& |
| 466 |
Graph<T>::V1(Pix vx, Pix x) const |
| 467 |
{ |
| 468 |
vertex<T> *v = (vertex<T> *) vx; |
| 469 |
static T x1; |
| 470 |
return x1; |
| 471 |
} |
| 472 |
|
| 473 |
class STRLIdentifier; |
| 474 |
|
| 475 |
extern int x(List_DL<STRLIdentifier *>); |
| 476 |
extern int x(List_DLS<STRLIdentifier *>); |
| 477 |
|
| 478 |
extern int x(Set<STRLIdentifier *>); |
| 479 |
extern int x(Set_DL<STRLIdentifier *>); |
| 480 |
extern int x(Set_DLp<STRLIdentifier *>); |
| 481 |
|
| 482 |
extern int x(Graph<STRLIdentifier *>); |
| 483 |
|
| 484 |
class STRLIdentifier { |
| 485 |
char buf[10]; |
| 486 |
}; |
| 487 |
|
| 488 |
extern int operator==(vertex<STRLIdentifier*>&, vertex<STRLIdentifier*>&); // { dg-message "argument 1" } const subversion |
| 489 |
extern int operator==(STRLIdentifier&, STRLIdentifier&); |
| 490 |
|
| 491 |
extern int x(List_DLSp<STRLIdentifier *>); |
| 492 |
|
| 493 |
template class Graph<STRLIdentifier *>; |
| 494 |
template class List_DLS<vertex<STRLIdentifier *> >; |