--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/SLList.cc	Fri Dec 06 05:39:13 1996 +0000
@@ -0,0 +1,256 @@
+// This may look like C code, but it is really -*- C++ -*-
+/* 
+Copyright (C) 1988, 1992 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+*/
+
+#if defined (__GNUG__)
+#pragma implementation
+#endif
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <limits.h>
+#include <stream.h>
+#include <builtin.h>
+#include "SLList.h"
+
+void BaseSLList::error(const char* msg) const
+{
+  (*lib_error_handler)("SLList", msg);
+}
+
+int BaseSLList::length() const
+{
+  int l = 0;
+  BaseSLNode* t = last;
+  if (t != 0) do { ++l; t = t->tl; } while (t != last);
+  return l;
+}
+
+void BaseSLList::clear()
+{
+  if (last == 0)
+    return;
+
+  BaseSLNode* p = last->tl;
+  last->tl = 0;
+  last = 0;
+
+  while (p != 0)
+  {
+    BaseSLNode* nxt = p->tl;
+    delete_node(p);
+    p = nxt;
+  }
+}
+
+
+// Note:  This is an internal method.  It does *not* free old contents!
+
+void BaseSLList::copy(const BaseSLList& a)
+{
+  if (a.last == 0)
+    last = 0;
+  else
+  {
+    BaseSLNode* p = a.last->tl;
+    BaseSLNode* h = copy_node(p->item());
+    last = h;
+    for (;;)
+    {
+      if (p == a.last)
+      {
+        last->tl = h;
+        return;
+      }
+      p = p->tl;
+      BaseSLNode* n = copy_node(p->item());
+      last->tl = n;
+      last = n;
+    }
+  }
+}
+
+BaseSLList& BaseSLList::operator = (const BaseSLList& a)
+{
+  if (last != a.last)
+  {
+    clear();
+    copy(a);
+  }
+  return *this;
+}
+
+Pix BaseSLList::prepend(const void *datum)
+{
+  return prepend(copy_node(datum));
+}
+
+
+Pix BaseSLList::prepend(BaseSLNode* t)
+{
+  if (t == 0) return 0;
+  if (last == 0)
+    t->tl = last = t;
+  else
+  {
+    t->tl = last->tl;
+    last->tl = t;
+  }
+  return Pix(t);
+}
+
+
+Pix BaseSLList::append(const void *datum)
+{
+  return append(copy_node(datum));
+}
+
+Pix BaseSLList::append(BaseSLNode* t)
+{
+  if (t == 0) return 0;
+  if (last == 0)
+    t->tl = last = t;
+  else
+  {
+    t->tl = last->tl;
+    last->tl = t;
+    last = t;
+  }
+  return Pix(t);
+}
+
+void BaseSLList::join(BaseSLList& b)
+{
+  BaseSLNode* t = b.last;
+  b.last = 0;
+  if (last == 0)
+    last = t;
+  else if (t != 0)
+  {
+    BaseSLNode* f = last->tl;
+    last->tl = t->tl;
+    t->tl = f;
+    last = t;
+  }
+}
+
+Pix BaseSLList::ins_after(Pix p, const void *datum)
+{
+  BaseSLNode* u = (BaseSLNode*)p;
+  BaseSLNode* t = copy_node(datum);
+  if (last == 0)
+    t->tl = last = t;
+  else if (u == 0) // ins_after 0 means prepend
+  {
+    t->tl = last->tl;
+    last->tl = t;
+  }
+  else
+  {
+    t->tl = u->tl;
+    u->tl = t;
+    if (u == last) 
+      last = t;
+  }
+  return Pix(t);
+}
+
+void BaseSLList::del_after(Pix p)
+{
+  BaseSLNode* u = (BaseSLNode*)p;
+  if (last == 0 || u == last) error("cannot del_after last");
+  if (u == 0) u = last; // del_after 0 means delete first
+  BaseSLNode* t = u->tl;
+  if (u == t)
+    last = 0;
+  else
+  {
+    u->tl = t->tl;
+    if (last == t)
+      last = u;
+  }
+  delete_node(t);
+}
+
+int BaseSLList::owns(Pix p) const
+{
+  BaseSLNode* t = last;
+  if (t != 0 && p != 0)
+  {
+    do
+    {
+      if (Pix(t) == p) return 1;
+      t = t->tl;
+    } while (t != last);
+  }
+  return 0;
+}
+
+int BaseSLList::remove_front(void *dst, int signal_error)
+{
+  if (last)
+  {
+    BaseSLNode* t = last->tl;
+    copy_item(dst, t->item());
+    if (t == last)
+      last = 0;
+    else
+      last->tl = t->tl;
+    delete_node(t);
+    return 1;
+  }
+  if (signal_error)
+    error("remove_front of empty list");
+  return 0;
+}
+
+void BaseSLList::del_front()
+{
+  if (last == 0) error("del_front of empty list");
+  BaseSLNode* t = last->tl;
+  if (t == last)
+    last = 0;
+  else
+    last->tl = t->tl;
+  delete_node(t);
+}
+
+int BaseSLList::OK() const
+{
+  int v = 1;
+  if (last != 0)
+  {
+    BaseSLNode* t = last;
+    long count = LONG_MAX;      // Lots of chances to find last!
+    do
+    {
+      count--;
+      t = t->tl;
+    } while (count > 0 && t != last);
+    v &= count > 0;
+  }
+  if (!v) error("invariant failure");
+  return v;
+}
+
+/*
+;;; Local Variables: ***
+;;; mode: C++ ***
+;;; End: ***
+*/

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/SLList.h	Fri Dec 06 05:39:13 1996 +0000
@@ -0,0 +1,136 @@
+// This may look like C code, but it is really -*- C++ -*-
+/* 
+Copyright (C) 1988, 1992 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+*/
+
+#ifndef _SLList_h
+#define _SLList_h 1
+
+#if defined (__GNUG__)
+#pragma interface
+#endif
+
+#undef OK
+
+#include <Pix.h>
+
+struct BaseSLNode
+{
+   union {
+     struct BaseSLNode *tl;
+     double dummy;  /* To force correct alignment */
+   };
+   void *item() {return (void*)(this+1);} // Return ((SLNode<T>*)this)->hd
+};
+
+template<class T>
+class SLNode : public BaseSLNode
+{
+  public:
+    T                    hd; // Data part of node
+                         SLNode() { }
+                         SLNode(const T& h, SLNode* t = 0)
+			     : hd(h) { tl = t; }
+                         ~SLNode() { }
+};
+
+extern int __SLListLength(BaseSLNode *ptr);
+
+class BaseSLList {
+  protected:
+    BaseSLNode *last;
+    virtual void delete_node(BaseSLNode*node) = 0;
+    virtual BaseSLNode* copy_node(const void* datum) = 0;
+    virtual void copy_item(void *dst, void *src) = 0;
+    virtual ~BaseSLList() { }
+    BaseSLList() { last = 0; }
+    void copy(const BaseSLList&);
+    BaseSLList& operator = (const BaseSLList& a);
+    Pix ins_after(Pix p, const void *datum);
+    Pix prepend(const void *datum);
+    Pix append(const void *datum);
+    int remove_front(void *dst, int signal_error = 0);
+    void join(BaseSLList&);
+  public:
+    int length() const;
+    int empty() const { return last == 0; }
+    void clear();
+    Pix                   prepend(BaseSLNode*);
+    Pix                   append(BaseSLNode*);
+    int                   OK() const;
+    void                  error(const char* msg) const;
+    void                  del_after(Pix p);
+    int                   owns(Pix p) const;
+    void                  del_front();
+};
+
+template <class T>
+class SLList : public BaseSLList
+{
+  private:
+    virtual void delete_node(BaseSLNode *node) { delete (SLNode<T>*)node; }
+    virtual BaseSLNode* copy_node(const void *datum)
+	{ return new SLNode<T>(*(const T*)datum); }
+    virtual void copy_item(void *dst, void *src) { *(T*)dst = *(T*)src; }
+
+public:
+    SLList() : BaseSLList() { }
+    SLList(const SLList<T>& a) : BaseSLList() { copy(a); }
+    SLList<T>&            operator = (const SLList<T>& a)
+	{ BaseSLList::operator=((const BaseSLList&) a); return *this; }
+    virtual ~SLList() { clear(); }
+
+    Pix prepend(const T& item) {return BaseSLList::prepend(&item);}
+    Pix append(const T& item) {return BaseSLList::append(&item);}
+    Pix prepend(SLNode<T>* node) {return BaseSLList::prepend(node);}
+    Pix append(SLNode<T>* node) {return BaseSLList::append(node);}
+
+    T& operator () (Pix p) {
+	if (p == 0) error("null Pix");
+	return ((SLNode<T>*)(p))->hd; }
+    const T& operator () (Pix p) const {
+	if (p == 0) error("null Pix");
+	return ((SLNode<T>*)(p))->hd; }
+    inline Pix first() const { return (last == 0) ? 0 : Pix(last->tl); }
+    void next(Pix& p) const
+	{ p = (p == 0 || p == last) ? 0 : Pix(((SLNode<T>*)(p))->tl); }
+    Pix ins_after(Pix p, const T& item)
+      { return BaseSLList::ins_after(p, &item); }
+    void join(SLList<T>& a) { BaseSLList::join(a); }
+    
+    T& front() {
+	if (last == 0) error("front: empty list");
+	return ((SLNode<T>*)last->tl)->hd; }
+    T& rear() {
+	if (last == 0) error("rear: empty list");
+	return ((SLNode<T>*)last)->hd; }
+    const T& front() const {
+	if (last == 0) error("front: empty list");
+	return ((SLNode<T>*)last->tl)->hd; }
+    const T& rear() const {
+	if (last == 0) error("rear: empty list");
+	return ((SLNode<T>*)last)->hd; }
+    int remove_front(T& x) { return BaseSLList::remove_front(&x); }
+    T remove_front() { T dst; BaseSLList::remove_front(&dst, 1); return dst; }
+};
+
+#endif
+
+/*
+;;; Local Variables: ***
+;;; mode: C++ ***
+;;; End: ***
+*/