src/third_party/skia/include/core/SkTInternalLList.h

   1 /*
   2  * Copyright 2012 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #ifndef SkTInternalLList_DEFINED
   9 #define SkTInternalLList_DEFINED
  10
  11 #include "SkTypes.h"
  12
  13 /**
  14  * Helper class to automatically initialize the doubly linked list created pointers.
  15  */
  16 template <typename T> class SkPtrWrapper {
  17   public:
  18       SkPtrWrapper() : fPtr(NULL) {}
  19       SkPtrWrapper& operator =(T* ptr) { fPtr = ptr; return *this; }
  20       operator T*() const { return fPtr; }
  21       T* operator->() { return fPtr; }
  22   private:
  23       T* fPtr;
  24 };
  25
  26
  27 /**
  28  * This macro creates the member variables required by the SkTInternalLList class. It should be
  29  * placed in the private section of any class that will be stored in a double linked list.
  30  */
  31 #define SK_DECLARE_INTERNAL_LLIST_INTERFACE(ClassName)              \
  32     friend class SkTInternalLList<ClassName>;                       \
  33     /* back pointer to the owning list - for debugging */           \
  34     SkDEBUGCODE(SkPtrWrapper<SkTInternalLList<ClassName> > fList;)  \
  35     SkPtrWrapper<ClassName> fPrev;                                  \
  36     SkPtrWrapper<ClassName> fNext
  37
  38 /**
  39  * This class implements a templated internal doubly linked list data structure.
  40  */
  41 template <class T> class SkTInternalLList : SkNoncopyable {
  42 public:
  43     SkTInternalLList()
  44         : fHead(NULL)
  45         , fTail(NULL) {
  46     }
  47
  48     void remove(T* entry) {
  49         SkASSERT(NULL != fHead && NULL != fTail);
  50         SkASSERT(this->isInList(entry));
  51
  52         T* prev = entry->fPrev;
  53         T* next = entry->fNext;
  54
  55         if (NULL != prev) {
  56             prev->fNext = next;
  57         } else {
  58             fHead = next;
  59         }
  60         if (NULL != next) {
  61             next->fPrev = prev;
  62         } else {
  63             fTail = prev;
  64         }
  65
  66         entry->fPrev = NULL;
  67         entry->fNext = NULL;
  68
  69 #ifdef SK_DEBUG
  70         entry->fList = NULL;
  71 #endif
  72     }
  73
  74     void addToHead(T* entry) {
  75         SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
  76         SkASSERT(NULL == entry->fList);
  77
  78         entry->fPrev = NULL;
  79         entry->fNext = fHead;
  80         if (NULL != fHead) {
  81             fHead->fPrev = entry;
  82         }
  83         fHead = entry;
  84         if (NULL == fTail) {
  85             fTail = entry;
  86         }
  87
  88 #ifdef SK_DEBUG
  89         entry->fList = this;
  90 #endif
  91     }
  92
  93     void addToTail(T* entry) {
  94         SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
  95         SkASSERT(NULL == entry->fList);
  96
  97         entry->fPrev = fTail;
  98         entry->fNext = NULL;
  99         if (NULL != fTail) {
 100             fTail->fNext = entry;
 101         }
 102         fTail = entry;
 103         if (NULL == fHead) {
 104             fHead = entry;
 105         }
 106
 107 #ifdef SK_DEBUG
 108         entry->fList = this;
 109 #endif
 110     }
 111
 112     /**
 113      * Inserts a new list entry before an existing list entry. The new entry must not already be
 114      * a member of this or any other list. If existingEntry is NULL then the new entry is added
 115      * at the tail.
 116      */
 117     void addBefore(T* newEntry, T* existingEntry) {
 118         SkASSERT(NULL != newEntry);
 119
 120         if (NULL == existingEntry) {
 121             this->addToTail(newEntry);
 122             return;
 123         }
 124
 125         SkASSERT(this->isInList(existingEntry));
 126         newEntry->fNext = existingEntry;
 127         T* prev = existingEntry->fPrev;
 128         existingEntry->fPrev = newEntry;
 129         newEntry->fPrev = prev;
 130         if (NULL == prev) {
 131             SkASSERT(fHead == existingEntry);
 132             fHead = newEntry;
 133         } else {
 134             prev->fNext = newEntry;
 135         }
 136 #ifdef SK_DEBUG
 137         newEntry->fList = this;
 138 #endif
 139     }
 140
 141     /**
 142      * Inserts a new list entry after an existing list entry. The new entry must not already be
 143      * a member of this or any other list. If existingEntry is NULL then the new entry is added
 144      * at the head.
 145      */
 146     void addAfter(T* newEntry, T* existingEntry) {
 147         SkASSERT(NULL != newEntry);
 148
 149         if (NULL == existingEntry) {
 150             this->addToHead(newEntry);
 151             return;
 152         }
 153
 154         SkASSERT(this->isInList(existingEntry));
 155         newEntry->fPrev = existingEntry;
 156         T* next = existingEntry->fNext;
 157         existingEntry->fNext = newEntry;
 158         newEntry->fNext = next;
 159         if (NULL == next) {
 160             SkASSERT(fTail == existingEntry);
 161             fTail = newEntry;
 162         } else {
 163             next->fPrev = newEntry;
 164         }
 165 #ifdef SK_DEBUG
 166         newEntry->fList = this;
 167 #endif
 168     }
 169
 170     bool isEmpty() const {
 171         return NULL == fHead && NULL == fTail;
 172     }
 173
 174     T* head() { return fHead; }
 175     T* tail() { return fTail; }
 176
 177     class Iter {
 178     public:
 179         enum IterStart {
 180             kHead_IterStart,
 181             kTail_IterStart
 182         };
 183
 184         Iter() : fCurr(NULL) {}
 185         Iter(const Iter& iter) : fCurr(iter.fCurr) {}
 186         Iter& operator= (const Iter& iter) { fCurr = iter.fCurr; return *this; }
 187
 188         T* init(const SkTInternalLList& list, IterStart startLoc) {
 189             if (kHead_IterStart == startLoc) {
 190                 fCurr = list.fHead;
 191             } else {
 192                 SkASSERT(kTail_IterStart == startLoc);
 193                 fCurr = list.fTail;
 194             }
 195
 196             return fCurr;
 197         }
 198
 199         T* get() { return fCurr; }
 200
 201         /**
 202          * Return the next/previous element in the list or NULL if at the end.
 203          */
 204         T* next() {
 205             if (NULL == fCurr) {
 206                 return NULL;
 207             }
 208
 209             fCurr = fCurr->fNext;
 210             return fCurr;
 211         }
 212
 213         T* prev() {
 214             if (NULL == fCurr) {
 215                 return NULL;
 216             }
 217
 218             fCurr = fCurr->fPrev;
 219             return fCurr;
 220         }
 221
 222     private:
 223         T* fCurr;
 224     };
 225
 226 #ifdef SK_DEBUG
 227     void validate() const {
 228         SkASSERT(!fHead == !fTail);
 229         Iter iter;
 230         for (T* item = iter.init(*this, Iter::kHead_IterStart); NULL != item; item = iter.next()) {
 231             SkASSERT(this->isInList(item));
 232             if (NULL == item->fPrev) {
 233                 SkASSERT(fHead == item);
 234             } else {
 235                 SkASSERT(item->fPrev->fNext == item);
 236             }
 237             if (NULL == item->fNext) {
 238                 SkASSERT(fTail == item);
 239             } else {
 240                 SkASSERT(item->fNext->fPrev == item);
 241             }
 242         }
 243     }
 244
 245     /**
 246      * Debugging-only method that uses the list back pointer to check if 'entry' is indeed in 'this'
 247      * list.
 248      */
 249     bool isInList(const T* entry) const {
 250         return entry->fList == this;
 251     }
 252
 253     /**
 254      * Debugging-only method that laboriously counts the list entries.
 255      */
 256     int countEntries() const {
 257         int count = 0;
 258         for (T* entry = fHead; NULL != entry; entry = entry->fNext) {
 259             ++count;
 260         }
 261         return count;
 262     }
 263 #endif // SK_DEBUG
 264
 265 private:
 266     T* fHead;
 267     T* fTail;
 268
 269     typedef SkNoncopyable INHERITED;
 270 };
 271
 272 #endif