Subversion Repositories openrisc

// { dg-do assemble  }
// prms-id: 1989

#define TRUE true
#define FALSE false
typedef void *Pix;

template<class T>
struct link {
    T item;
    link *next;
    link *prev;

    link(const T& t): item(t), prev(0), next(0)
        { }
    link(const T& t, link<T> *p, link<T> *n): item(t), prev(p), next(n)
        { }
};

template<class T>
class List_DL {
public:
    List_DL();
    List_DL(const List_DL&);
    ~List_DL();

    void append(const T& item);
    void prepend(const T& item);
    void insert(const T& item, Pix x, bool before);

    void remove(Pix& x)
        { T tmp; remove(x, tmp); }
    void remove(Pix& x, T& item);

    void clear();

    unsigned length() const
        { return count; }

private:

    unsigned count;
    link<T> *head;
    link<T> *tail;

public:
    Pix first() const
        { return Pix(head); }
    Pix last() const
        { return Pix(tail); }
    void next(Pix& x) const
        { if (0 != x) x = ((link<T> *) x)->next; }
    void prev(Pix& x) const
        { if (0 != x) x = ((link<T> *) x)->prev; }
    T& operator()(Pix x) const
        { return ((link<T> *) x)->item; }
};

template<class T>
List_DL<T>::List_DL():
count(0),
head(0)
{ }

template<class T>
List_DL<T>::List_DL(const List_DL& other):
count(0),
head(0)
{
    for (Pix x=other.first(); 0 != x; other.next(x))
        append(other(x));
}

template<class T>
List_DL<T>::~List_DL()
{
    clear();
}

template<class T>
void
List_DL<T>::append(const T& item)
{
    count++;
    if (0 == head) {
        head = new link<T>(item);
        tail = head;
    } else {
        tail->next = new link<T>(item, tail, 0);
        tail = tail->next;
    }
}

template<class T>
void
List_DL<T>::prepend(const T& item)
{
    count++;
    if (0 == head) {
        head = new link<T>(item);
        tail = head;
    } else {
        head = new link<T>(item, 0, head);
        if (tail == head)
            tail = tail->next;
    }
}

template<class T>
void
List_DL<T>::insert(const T& item, Pix x, bool before = TRUE)
{
    link<T> *l = (link<T> *) x;

    if (before) {
        if (0 == l || l == head) {
            prepend(item);
        } else {
            link<T> *n = new link<T>(item, l->prev, l);
            l->prev->next = n;
            l->prev = n;
        }
    } else {
        if (0 == l || l == tail) {
            append(item);
        } else {
            link<T> *n = new link<T>(item, l, l->next);
            l->next->prev = n;
            l->prev = n;
        }
    }
}

template<class T>
void
List_DL<T>::remove(Pix& x, T& item)
{
    link<T> *l = (link<T> *) x;

    if (0 == l)
        return;

    item = l->item;
    if (1 == count) {
        delete head;
        head = 0;
        tail = 0;
    } else {
        // more than one item in the list
        if (l == head) {
            link<T> *old = head;
            head = head->next;
            head->prev = 0;
            delete old;
        } else if (l == tail) {
            link<T> *old = tail;
            tail = tail->prev;
            tail->next = 0;
            delete old;
        } else {
            l->next->prev = l->prev;
            l->prev->next = l->next;
            delete l;
        }
    }
}

template<class T>
void
List_DL<T>::clear()
{
    link<T> *l, *succ;
    for (l=head; 0 != l; l=succ) {
        succ = l->next;
        delete l;
    }
    head = 0;
    tail = 0;
}

template<class T>
class List_DLS: public List_DL<T> {
public:
    List_DLS(): List_DL<T>()
        { }
    List_DLS(const List_DLS& other): List_DL<T>(other)
        { }

    bool contains(const T& item) const
        { return search(item) != 0 ? TRUE: FALSE; }
    Pix search(const T&) const;
};

template<class T>
Pix
List_DLS<T>::search(const T& item) const
{
    for (Pix x=this->first(); 0 != x; this->next(x)) {
        if (item == this->operator()(x)) // { dg-error "match" } const subversion
          // { dg-message "candidate" "candidate note" { target *-*-* } 199 }
            return x;
    }
    return 0;
}

template<class T>
class List_DLSp: public List_DL<T> {
public:
    List_DLSp(): List_DL<T>()
        { }
    List_DLSp(const List_DLSp& other): List_DL<T>(other)
        { }

    bool contains(const T& item) const
#ifndef INTERNAL_ERROR
        ;
#else
        { return search(item) != 0 ? TRUE: FALSE; }
#endif
    Pix search(const T&) const;
};

template<class T>
bool
List_DLSp<T>::contains(const T& item) const
{
    for (Pix x=this->first(); 0 != x; this->next(x)) {
        if (*item == *(this->operator()(x)))
            return TRUE;
    }
    return FALSE;
}

template<class T>
class Set {
public:
    Set();
    Set(const Set& other);

    virtual void add(const T& item);

    void remove(const T& item)
        { Pix x = search(item); remove(x); }
    void remove(Pix& x)
        { T tmp; remove(x, tmp); }
    virtual void remove(Pix& x, T& item);

    virtual void clear();

    virtual bool contains(const T&) const;
    virtual Pix search(const T&) const;

    virtual unsigned length() const;

    virtual Pix first() const;
    virtual void next(Pix& x) const;
    virtual T& operator()(Pix x) const;
};

template<class T>
Set<T>::Set()
{ }

template<class T>
Set<T>::Set(const Set& other)
{ }


template<class T>
class Set_DL: public List_DLS<T> {
public:
    Set_DL();
    Set_DL(const Set_DL& other);

    void add(const T& item)
        { list.append(item); }
    void remove(Pix& x, T& item)
        { list.remove(x, item); }

    void clear()
        { list.clear(); }

    bool contains(const T& item) const
        { return list.contains(item); }
    Pix search(const T& item) const
        { return list.search(item); }

    unsigned length() const
        { return list.length(); }

    Pix first() const
        { return list.first(); }
    void next(Pix& x) const
        { list.next(x); }
    T& operator()(Pix x) const
        { return list(x); }
private:
    List_DLS<T> list;
};

template<class T>
class Set_DLp: public List_DLSp<T> {
public:
    Set_DLp();
    Set_DLp(const Set_DLp& other);

    void add(const T& item)
        { list.append(item); }
    void remove(Pix& x, T& item)
        { list.remove(x, item); }

    void clear()
        { list.clear(); }

    bool contains(const T& item) const
        { return list.contains(item); }
    Pix search(const T& item) const
        { return list.search(item); }

    unsigned length() const
        { return list.length(); }

    Pix first() const
        { return list.first(); }
    void next(Pix& x) const
        { list.next(x); }
    T& operator()(Pix x) const
        { return list(x); }
private:
    List_DLSp<T> list;
};

template<class T>
struct vertex {
    T item;
    List_DL<vertex<T> *> fanout;

    vertex(): item(), fanout()  // { dg-bogus "" } 
      { }
    vertex(const T& i): item(), fanout() // { dg-bogus "" } 
      { }
};

template<class T>
class Graph {
public:
    Graph();
    Graph(const Graph&);
    ~Graph();

    void add(const T& from, const T& to);
    bool contains(const T& from, const T& to) const;

    void clear()
        { vertices.clear(); }

    unsigned lengthV() const
        { return vertices.length(); }

    Pix firstV() const
        { return vertices.first(); }
    void nextV(Pix& x) const
        { vertices.next(x); }
    T& V(Pix x) const
        { return vertices(x).item; }

    Pix firstV1(Pix vx) const;
    void nextV1(Pix vx, Pix& x) const;
    T& V1(Pix vx, Pix x) const;
private:
    vertex<T> *lookup(const T& from) const;
    vertex<T> *lookup_new(const T& from);

    List_DLS<vertex<T> > vertices;
};

template<class T>
Graph<T>::Graph():
vertices()
{ }

template<class T>
Graph<T>::Graph(const Graph& other):
vertices()
{
    for (Pix vx=firstV(); 0 != vx; nextV(vx)) {
        for (Pix vx1=firstV1(vx); 0 != vx1; nextV1(vx, vx1)) {
            add(V(vx), V1(vx, vx1));
        }
    }
}

template<class T>
Graph<T>::~Graph()
{
    clear();
}

template<class T>
void
Graph<T>::add(const T& from, const T& to)
{
    vertex<T> *fromv = lookup_new(from);
    if (from == to)
        return;
    vertex<T> *tov = lookup_new(to);
    fromv->fanout.append(tov);
}

template<class T>
bool
Graph<T>::contains(const T& from, const T& to) const
{
    vertex<T> *fromv = lookup(from);
    if (0 == fromv)
        return FALSE;

    for (Pix x=fromv->fanout.first(); 0 != x; fromv->fanout.next(x)) {
        if (fromv->fanout(x)->item == to)
            return TRUE;
    }

    return FALSE;
}

template<class T>
vertex<T> *
Graph<T>::lookup(const T& from) const
{
    for (Pix x=vertices.first(); 0 != x; vertices.next(x)) {
        if (vertices(x).item == from)
            return &vertices(x);
    }
    return 0;
}

template<class T>
vertex<T> *
Graph<T>::lookup_new(const T& from)
{
    vertex<T> *v = lookup(from);
    if (0 == v) {
        vertices.append(from);
        return &vertices(vertices.last());
    }
    return v;
}

template<class T>
Pix
Graph<T>::firstV1(Pix vx) const
{
    vertex<T> *v = (vertex<T> *) vx;
    return v->fanout.first();
}

template<class T>
void
Graph<T>::nextV1(Pix vx, Pix& x) const
{
    vertex<T> *v = (vertex<T> *) vx;
    return v->fanout.next(x);
}

template<class T>
T&
Graph<T>::V1(Pix vx, Pix x) const
{
    vertex<T> *v = (vertex<T> *) vx;
    static T x1;
    return x1;
}

class STRLIdentifier;

extern int x(List_DL<STRLIdentifier *>);
extern int x(List_DLS<STRLIdentifier *>);

extern int x(Set<STRLIdentifier *>);
extern int x(Set_DL<STRLIdentifier *>);
extern int x(Set_DLp<STRLIdentifier *>);

extern int x(Graph<STRLIdentifier *>);

class STRLIdentifier {
    char buf[10];
};

extern int operator==(vertex<STRLIdentifier*>&, vertex<STRLIdentifier*>&); // { dg-message "note" } const subversion
extern int operator==(STRLIdentifier&, STRLIdentifier&); // { dg-message "note" } fn ref in err msg

extern int x(List_DLSp<STRLIdentifier *>);

template class Graph<STRLIdentifier *>;
template class List_DLS<vertex<STRLIdentifier *> >;