diff options
Diffstat (limited to 'sc4pd/headers/server/SC_List.h')
| -rw-r--r-- | sc4pd/headers/server/SC_List.h | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/sc4pd/headers/server/SC_List.h b/sc4pd/headers/server/SC_List.h new file mode 100644 index 0000000..d5bed41 --- /dev/null +++ b/sc4pd/headers/server/SC_List.h @@ -0,0 +1,229 @@ +/* + SuperCollider real time audio synthesis system + Copyright (c) 2002 James McCartney. All rights reserved. + http://www.audiosynth.com + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program 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 General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +/* + +A doubly linked list template. + +*/ + +#ifndef _SC_List_ +#define _SC_List_ + +#include <stdexcept> +#ifndef NDEBUG +# define NDEBUG +#endif +#include <assert.h> + + +// A Link can be a node in a list or a list itself. + +template <class T> +class Link +{ +public: + Link() : mNext(this), mPrev(this) {} + + T* Prev() { return static_cast<T*>(mPrev); } + T* Next() { return static_cast<T*>(mNext); } + + void RemoveLeaveDangling() + { + mPrev->mNext = mNext; + mNext->mPrev = mPrev; + } + + void Remove() + { + RemoveLeaveDangling(); + mNext = mPrev = this; + } + + void InsertAfter(T *inLink) + { + mPrev = inLink; + mNext = inLink->mNext; + mNext->mPrev = this; + mPrev->mNext = this; + } + + void InsertBefore(T *inLink) + { + mNext = inLink; + mPrev = inLink->mPrev; + mNext->mPrev = this; + mPrev->mNext = this; + } + + T* Head() { return static_cast<T*>(mNext); } + T* Tail() { return static_cast<T*>(mPrev); } + + T* PopHead(); + T* PopTail(); + void PushHead(T* inBuf); + void PushTail(T* inBuf); + + bool ContainsBuf(T* inBuf); + bool IsEmpty() { return mNext == this; } + void BeEmpty() { mNext = mPrev = this; } + + void Cat(T* inLink); + + bool SanityCheck(); + void DebugDump(); + +//private: +// Codewarrior refuses to inline Next() in some places.. + Link<T> *mNext, *mPrev; +}; + +template <class T, class Alloc> +void MakeListEmpty(Link<T> *inLink, Alloc* inAlloc) +{ + Link<T>* link = inLink->mNext; + while (link != inLink) { + Link<T>* nextlink = link->mNext; + // SC uses placement new extensively, so here we do a 'placement delete'. + // Using DestructSelf allows me to have either virtual + // or non virtual destructors in subclasses at the discretion of the subclass. + ((T*)(link))->DestructSelf(); + inAlloc->Free(static_cast<T*>(link)); + link = nextlink; + } + inLink->mNext = inLink->mPrev = inLink; +} + +template <class T> +void Link<T>::PushHead(T* inLink) +{ + assert(SanityCheck()); + + Link<T>* link = static_cast<Link<T>*>(inLink); + link->InsertAfter(static_cast<T*>(this)); + + assert(SanityCheck()); +} + +template <class T> +T* Link<T>::PopHead() +{ + assert(SanityCheck()); + if (IsEmpty()) return 0; + + Link<T>* link = mNext; + + link->Remove(); + + assert(SanityCheck()); + return static_cast<T*>(link); +} + +template <class T> +void Link<T>::PushTail(T* inLink) +{ + assert(SanityCheck()); + + Link<T>* link = static_cast<Link<T>*>(inLink); + link->InsertBefore(static_cast<T*>(this)); + + assert(SanityCheck()); +} + +template <class T> +T* Link<T>::PopTail() +{ + assert(SanityCheck()); + if (IsEmpty()) return 0; + + Link<T>* link = mPrev; + link->Remove(); + + assert(SanityCheck()); + return static_cast<T*>(link); +} + +template <class T> +void Link<T>::Cat(T* inLink) +{ + assert(SanityCheck()); + + Link<T>* link = static_cast<Link<T>*>(inLink); + + if (link->IsEmpty()) return; + if (IsEmpty()) { + mNext = link->mNext; + mPrev = link->mPrev; + link->mNext->mPrev = this; + link->mPrev->mNext = this; + } else { + link->mNext->mPrev = mPrev; + link->mPrev->mNext = this; + mPrev->mNext = link->mNext; + mPrev = link->mPrev; + } + link->mPrev = link; + link->mNext = link; + + assert(SanityCheck()); +} + +template <class T> +bool Link<T>::ContainsBuf(T* inLink) +{ + Link<T>* link = static_cast<Link<T>*>(inLink); + Link<T>* curLink = mNext; + while (curLink != this) { + if (curLink == link) return true; + curLink = curLink->mNext; + } + return false; +} + +template <class T> +void Link<T>::DebugDump() +{ + Link<T>* link = mNext; + while (link != this) { + //postbuf("Link-> %08X next %08X prev %08X\n", + // link, link->mNext, link->mPrev); + link = link->mNext; + } +} + +template <class T> +bool Link<T>::SanityCheck() +{ + Link<T>* link = mNext; + while (link != this) { + if (link->mPrev->mNext != link) { + throw std::runtime_error("Link: bad link <-,->"); + } + if (link->mNext->mPrev != link) { + throw std::runtime_error("Link: bad link ->,<-"); + } + link = link->mNext; + } + return true; +} + + + +#endif |