include/common/SC_List.h

   1 /*
   2         SuperCollider real time audio synthesis system
   3     Copyright (c) 2002 James McCartney. All rights reserved.
   4         http://www.audiosynth.com
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  19 */
  20
  21 /*
  22
  23 A doubly linked list template.
  24
  25 */
  26
  27 #ifndef _SC_List_
  28 #define _SC_List_
  29
  30 #include <stdexcept>
  31 #include <assert.h>
  32
  33
  34 // A Link can be a node in a list or a list itself.
  35
  36 template <class T>
  37 class Link
  38 {
  39 public:
  40         Link() : mNext(this), mPrev(this) {}
  41
  42         T* Prev() { return static_cast<T*>(mPrev); }
  43         T* Next() { return static_cast<T*>(mNext); }
  44
  45         void RemoveLeaveDangling()
  46         {
  47                 mPrev->mNext = mNext;
  48                 mNext->mPrev = mPrev;
  49         }
  50
  51         void Remove()
  52         {
  53                 RemoveLeaveDangling();
  54                 mNext = mPrev = this;
  55         }
  56
  57         void InsertAfter(T *inLink)
  58         {
  59                 mPrev = inLink;
  60                 mNext = inLink->mNext;
  61                 mNext->mPrev = this;
  62                 mPrev->mNext = this;
  63         }
  64
  65         void InsertBefore(T *inLink)
  66         {
  67                 mNext = inLink;
  68                 mPrev = inLink->mPrev;
  69                 mNext->mPrev = this;
  70                 mPrev->mNext = this;
  71         }
  72
  73         T* Head() { return static_cast<T*>(mNext); }
  74         T* Tail() { return static_cast<T*>(mPrev); }
  75
  76         T* PopHead();
  77         T* PopTail();
  78         void PushHead(T* inBuf);
  79         void PushTail(T* inBuf);
  80
  81         bool ContainsBuf(T* inBuf);
  82         bool IsEmpty() { return mNext == this; }
  83         void BeEmpty() { mNext = mPrev = this; }
  84
  85         void Cat(T* inLink);
  86
  87         bool SanityCheck();
  88         void DebugDump();
  89
  90 //private:
  91 // Codewarrior refuses to inline Next() in some places..
  92         Link<T> *mNext, *mPrev;
  93 };
  94
  95 template <class T, class Alloc>
  96 void MakeListEmpty(Link<T> *inLink, Alloc* inAlloc)
  97 {
  98         Link<T>* link = inLink->mNext;
  99         while (link != inLink) {
 100                 Link<T>* nextlink = link->mNext;
 101                 // SC uses placement new extensively, so here we do a 'placement delete'.
 102                 // Using DestructSelf allows me to have either virtual
 103                 // or non virtual destructors in subclasses at the discretion of the subclass.
 104                 ((T*)(link))->DestructSelf();
 105                 inAlloc->Free(static_cast<T*>(link));
 106                 link = nextlink;
 107         }
 108         inLink->mNext = inLink->mPrev = inLink;
 109 }
 110
 111 template <class T>
 112 void Link<T>::PushHead(T* inLink)
 113 {
 114         assert(SanityCheck());
 115
 116         Link<T>* link = static_cast<Link<T>*>(inLink);
 117         link->InsertAfter(static_cast<T*>(this));
 118
 119         assert(SanityCheck());
 120 }
 121
 122 template <class T>
 123 T* Link<T>::PopHead()
 124 {
 125         assert(SanityCheck());
 126         if (IsEmpty()) return 0;
 127
 128         Link<T>* link = mNext;
 129
 130         link->Remove();
 131
 132         assert(SanityCheck());
 133         return static_cast<T*>(link);
 134 }
 135
 136 template <class T>
 137 void Link<T>::PushTail(T* inLink)
 138 {
 139         assert(SanityCheck());
 140
 141         Link<T>* link = static_cast<Link<T>*>(inLink);
 142         link->InsertBefore(static_cast<T*>(this));
 143
 144         assert(SanityCheck());
 145 }
 146
 147 template <class T>
 148 T* Link<T>::PopTail()
 149 {
 150         assert(SanityCheck());
 151         if (IsEmpty()) return 0;
 152
 153         Link<T>* link = mPrev;
 154         link->Remove();
 155
 156         assert(SanityCheck());
 157         return static_cast<T*>(link);
 158 }
 159
 160 template <class T>
 161 void Link<T>::Cat(T* inLink)
 162 {
 163         assert(SanityCheck());
 164
 165         Link<T>* link = static_cast<Link<T>*>(inLink);
 166
 167         if (link->IsEmpty()) return;
 168         if (IsEmpty()) {
 169                 mNext = link->mNext;
 170                 mPrev = link->mPrev;
 171                 link->mNext->mPrev = this;
 172                 link->mPrev->mNext = this;
 173         } else {
 174                 link->mNext->mPrev = mPrev;
 175                 link->mPrev->mNext = this;
 176                 mPrev->mNext = link->mNext;
 177                 mPrev = link->mPrev;
 178         }
 179         link->mPrev = link;
 180         link->mNext = link;
 181
 182         assert(SanityCheck());
 183 }
 184
 185 template <class T>
 186 bool Link<T>::ContainsBuf(T* inLink)
 187 {
 188         Link<T>* link = static_cast<Link<T>*>(inLink);
 189         Link<T>* curLink = mNext;
 190         while (curLink != this) {
 191                 if (curLink == link) return true;
 192                 curLink = curLink->mNext;
 193         }
 194         return false;
 195 }
 196
 197 template <class T>
 198 void Link<T>::DebugDump()
 199 {
 200         Link<T>* link = mNext;
 201         while (link != this) {
 202                 //post("Link-> %08X   next %08X   prev %08X\n",
 203                 //      link, link->mNext, link->mPrev);
 204                 link = link->mNext;
 205         }
 206 }
 207
 208 template <class T>
 209 bool Link<T>::SanityCheck()
 210 {
 211         Link<T>* link = mNext;
 212         while (link != this) {
 213                 if (link->mPrev->mNext != link) {
 214                         throw std::runtime_error("Link: bad link <-,->");
 215                 }
 216                 if (link->mNext->mPrev != link) {
 217                         throw std::runtime_error("Link: bad link ->,<-");
 218                 }
 219                 link = link->mNext;
 220         }
 221         return true;
 222 }
 223
 224
 225
 226 #endif