# HG changeset patch # User jwe # Date 849850753 0 # Node ID ed6532d8bf12be227dd1e88de935902e55c92a1f # Parent a3cd51f7e7aba2dd93d0f2994f3ec22139953971 [project @ 1996-12-06 05:39:13 by jwe] diff -r a3cd51f7e7ab -r ed6532d8bf12 src/SLList.cc --- /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 +#endif + +#include +#include +#include +#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: *** +*/ diff -r a3cd51f7e7ab -r ed6532d8bf12 src/SLList.h --- /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 + +struct BaseSLNode +{ + union { + struct BaseSLNode *tl; + double dummy; /* To force correct alignment */ + }; + void *item() {return (void*)(this+1);} // Return ((SLNode*)this)->hd +}; + +template +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 SLList : public BaseSLList +{ + private: + virtual void delete_node(BaseSLNode *node) { delete (SLNode*)node; } + virtual BaseSLNode* copy_node(const void *datum) + { return new SLNode(*(const T*)datum); } + virtual void copy_item(void *dst, void *src) { *(T*)dst = *(T*)src; } + +public: + SLList() : BaseSLList() { } + SLList(const SLList& a) : BaseSLList() { copy(a); } + SLList& operator = (const SLList& 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* node) {return BaseSLList::prepend(node);} + Pix append(SLNode* node) {return BaseSLList::append(node);} + + T& operator () (Pix p) { + if (p == 0) error("null Pix"); + return ((SLNode*)(p))->hd; } + const T& operator () (Pix p) const { + if (p == 0) error("null Pix"); + return ((SLNode*)(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*)(p))->tl); } + Pix ins_after(Pix p, const T& item) + { return BaseSLList::ins_after(p, &item); } + void join(SLList& a) { BaseSLList::join(a); } + + T& front() { + if (last == 0) error("front: empty list"); + return ((SLNode*)last->tl)->hd; } + T& rear() { + if (last == 0) error("rear: empty list"); + return ((SLNode*)last)->hd; } + const T& front() const { + if (last == 0) error("front: empty list"); + return ((SLNode*)last->tl)->hd; } + const T& rear() const { + if (last == 0) error("rear: empty list"); + return ((SLNode*)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: *** +*/