// This may look like C code, but it is really -*- C++ -*-
Copyright (C) 1988 Free Software Foundation
written by Doug Lea (dl@rocky.oswego.edu)
This file is part of the GNU C++ Library. This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version. This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
<T>ListNode Nil<T>ListNode;
class init_Nil<T>ListNode
Nil<T>ListNode.tl = &Nil<T>ListNode;
static init_Nil<T>ListNode Nil<T>ListNode_initializer;
<T>List& <T>List::operator = (<T>List& a)
<T>ListNode* tail = P->tl;
void <T>List::set_tail(<T>List& a)
<T>List <T>List::nth(int n)
for (<T>ListNode* p = P; n-- > 0; p = p->tl);
if (p != &Nil<T>ListNode) while (p->tl != &Nil<T>ListNode) p = p->tl;
void <T>List::append(<T>List& l)
if (p != &Nil<T>ListNode)
while (p->tl != &Nil<T>ListNode) p = p->tl;
for (<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl) ++l;
<T>& <T>List::operator [] (int n)
for (<T>ListNode* p = P; n-- > 0; p = p->tl);
int operator == (<T>List& x, <T>List& y)
if (a == &Nil<T>ListNode)
return b == &Nil<T>ListNode;
else if (b == &Nil<T>ListNode)
else if (<T>EQ(a->hd, b->hd))
void <T>List::apply(<T>Procedure f)
for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
void <T>List::subst(<T&> old, <T&> repl)
for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
<T> <T>List::reduce(<T>Combiner f, <T&> base)
for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
int <T>List::position(<T&> targ)
if (p == &Nil<T>ListNode)
else if (<T>EQ(p->hd, targ))
int <T>List::contains(<T&> targ)
if (p == &Nil<T>ListNode)
else if (<T>EQ(p->hd, targ))
<T>List <T>List::find(<T&> targ)
while (p != &Nil<T>ListNode && !<T>EQ(p->hd, targ))
Pix <T>List::seek(<T&> targ)
if (p == &Nil<T>ListNode)
else if (<T>EQ(p->hd, targ))
if (p == &Nil<T>ListNode)
<T>List <T>List::find(<T>List& target)
<T>ListNode* targ = target.P;
if (targ == &Nil<T>ListNode)
while (p != &Nil<T>ListNode)
if (<T>EQ(p->hd, targ->hd))
<T>ListNode* t = targ->tl;
if (t == &Nil<T>ListNode)
else if (a == &Nil<T>ListNode || !<T>EQ(a->hd, t->hd))
return <T>List(&Nil<T>ListNode);
int <T>List::contains(<T>List& target)
<T>ListNode* targ = target.P;
if (targ == &Nil<T>ListNode)
while (p != &Nil<T>ListNode)
if (<T>EQ(p->hd, targ->hd))
<T>ListNode* t = targ->tl;
if (t == &Nil<T>ListNode)
else if (a == &Nil<T>ListNode || !<T>EQ(a->hd, t->hd))
void <T>List::del(<T&> targ)
if (h == &Nil<T>ListNode)
else if (<T>EQ(h->hd, targ))
<T>ListNode* nxt = h->tl;
while (p != &Nil<T>ListNode)
<T>ListNode* nxt = p->tl;
void <T>List::del(<T>Predicate f)
if (h == &Nil<T>ListNode)
<T>ListNode* nxt = h->tl;
while (p != &Nil<T>ListNode)
<T>ListNode* nxt = p->tl;
void <T>List::select(<T>Predicate f)
if (h == &Nil<T>ListNode)
<T>ListNode* nxt = h->tl;
while (p != &Nil<T>ListNode)
<T>ListNode* nxt = p->tl;
<T>ListNode* l = &Nil<T>ListNode;
while (p != &Nil<T>ListNode)
<T>ListNode* nxt = p->tl;
if (a == &Nil<T>ListNode)
<T>ListNode* h = new<T>ListNode(a->hd);
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode(a->hd);
trail->tl = &Nil<T>ListNode;
<T>List subst(<T&> old, <T&> repl, <T>List& x)
if (a == &Nil<T>ListNode)
<T>ListNode* h = new <T>ListNode;
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new <T>ListNode;
trail->tl = &Nil<T>ListNode;
<T>List combine(<T>Combiner f, <T>List& x, <T>List& y)
if (a == &Nil<T>ListNode || b == &Nil<T>ListNode)
return <T>List(&Nil<T>ListNode);
<T>ListNode* h = new<T>ListNode((*f)(a->hd, b->hd));
while (a != &Nil<T>ListNode && b != &Nil<T>ListNode)
<T>ListNode* n = new<T>ListNode((*f)(a->hd, b->hd));
trail->tl = &Nil<T>ListNode;
<T>List reverse(<T>List& x)
if (a == &Nil<T>ListNode)
<T>ListNode* l = new<T>ListNode(a->hd);
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode(a->hd);
<T>List append(<T>List& x, <T>List& y)
if (a != &Nil<T>ListNode)
<T>ListNode* h = new<T>ListNode(a->hd);
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode(a->hd);
void <T>List::prepend(<T>List& y)
if (b != &Nil<T>ListNode)
<T>ListNode* h = new<T>ListNode(b->hd);
for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
<T>ListNode* n = new<T>ListNode(b->hd);
<T>List concat(<T>List& x, <T>List& y)
if (a != &Nil<T>ListNode)
<T>ListNode* h = new<T>ListNode(a->hd);
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode(a->hd);
for(;b != &Nil<T>ListNode; b = b->tl)
<T>ListNode* n = new<T>ListNode(b->hd);
trail->tl = &Nil<T>ListNode;
else if (b != &Nil<T>ListNode)
<T>ListNode* h = new<T>ListNode(b->hd);
for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
<T>ListNode* n = new<T>ListNode(b->hd);
trail->tl = &Nil<T>ListNode;
return <T>List(&Nil<T>ListNode);
<T>List select(<T>Predicate f, <T>List& x)
<T>ListNode* h = &Nil<T>ListNode;
while (a != &Nil<T>ListNode)
h = new<T>ListNode(a->hd);
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode(a->hd);
trail->tl = &Nil<T>ListNode;
<T>List remove(<T>Predicate f, <T>List& x)
<T>ListNode* h = &Nil<T>ListNode;
while (a != &Nil<T>ListNode)
h = new<T>ListNode(a->hd);
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode(a->hd);
trail->tl = &Nil<T>ListNode;
<T>List remove(<T&> targ, <T>List& x)
<T>ListNode* h = &Nil<T>ListNode;
while (a != &Nil<T>ListNode)
if (!(<T>EQ(a->hd, targ)))
h = new<T>ListNode(a->hd);
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode(a->hd);
trail->tl = &Nil<T>ListNode;
<T>List map(<T>Mapper f, <T>List& x)
<T>ListNode* h = &Nil<T>ListNode;
if (a != &Nil<T>ListNode)
h = new<T>ListNode((*f)(a->hd));
for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
<T>ListNode* n = new<T>ListNode((*f)(a->hd));
trail->tl = &Nil<T>ListNode;
<T>List merge(<T>List& x, <T>List& y, <T>Comparator f)
if (a == &Nil<T>ListNode)
if (b == &Nil<T>ListNode)
return <T>List(&Nil<T>ListNode);
else if (b == &Nil<T>ListNode)
<T>ListNode* h = new <T>ListNode;
if ((*f)(a->hd, b->hd) <= 0)
if (a == &Nil<T>ListNode)
while (b != &Nil<T>ListNode)
<T>ListNode* n = new <T>ListNode;
else if (b == &Nil<T>ListNode)
while (a != &Nil<T>ListNode)
<T>ListNode* n = new <T>ListNode;
else if ((*f)(a->hd, b->hd) <= 0)
<T>ListNode* n = new <T>ListNode;
<T>ListNode* n = new <T>ListNode;
void <T>List::sort(<T>Comparator f)
// strategy: place runs in queue, merge runs until done
// This is often very fast
if (P == &Nil<T>ListNode || P->tl == &Nil<T>ListNode)
int qlen = 250; // guess a good queue size, realloc if necessary
<T>ListNode** queue = (<T>ListNode**)malloc(qlen * sizeof(<T>ListNode*));
while (b != &Nil<T>ListNode)
if ((*f)(a->hd, b->hd) > 0)
if (h == a) // minor optimization: ensure runlen >= 2
queue = (<T>ListNode**)realloc(queue, qlen * sizeof(<T>ListNode*));
if (++qin >= qlen) qin = 0;
if (++qout >= qlen) qout = 0;
if (++qout >= qlen) qout = 0;
if ((*f)(a->hd, b->hd) <= 0)
if (++qin >= qlen) qin = 0;
if (a == &Nil<T>ListNode)
else if (b == &Nil<T>ListNode)
else if ((*f)(a->hd, b->hd) <= 0)
int <T>List::list_length()
if (fast == &Nil<T>ListNode)
<T>ListNode* slow = fast->tl;
if (slow == &Nil<T>ListNode)
if (fast == &Nil<T>ListNode)
else if (fast->tl == &Nil<T>ListNode)
void <T>List::error(const char* msg)
(*lib_error_handler)("List", msg);
int v = P != 0; // have a node
// check that all nodes OK, even if circular:
if (fast != &Nil<T>ListNode)
<T>ListNode* slow = fast->tl;
if (v && slow != &Nil<T>ListNode)
if (fast == &Nil<T>ListNode)
else if (fast->tl == &Nil<T>ListNode)
v &= fast->ref != 0 && slow->ref != 0;
if (!v) error ("invariant failure");