src/third_party/skia/src/core/SkTLList.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 SkTLList_DEFINED
   9 #define SkTLList_DEFINED
  10
  11 #include "SkTInternalLList.h"
  12 #include "SkTemplates.h"
  13
  14 template <typename T> class SkTLList;
  15 template <typename T>
  16 inline void* operator new(size_t, SkTLList<T>* list,
  17                           typename SkTLList<T>::Placement placement,
  18                           const typename SkTLList<T>::Iter& location);
  19
  20 /** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the
  21     the list creates the objects and they are deleted upon removal. This class block-allocates
  22     space for entries based on a param passed to the constructor.
  23
  24     Elements of the list can be constructed in place using the following macros:
  25         SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args)
  26         SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args)
  27     where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded
  28     constructor arguments for type_name. These macros behave like addBefore() and addAfter().
  29 */
  30 template <typename T>
  31 class SkTLList : public SkNoncopyable {
  32 private:
  33     struct Block;
  34     struct Node {
  35         char fObj[sizeof(T)];
  36         SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node);
  37         Block* fBlock; // owning block.
  38     };
  39     typedef SkTInternalLList<Node> NodeList;
  40
  41 public:
  42
  43     class Iter;
  44
  45     /** allocCnt is the number of objects to allocate as a group. In the worst case fragmentation
  46         each object is using the space required for allocCnt unfragmented objects. */
  47     SkTLList(int allocCnt = 1) : fCount(0), fAllocCnt(allocCnt) {
  48         SkASSERT(allocCnt > 0);
  49         this->validate();
  50     }
  51
  52     ~SkTLList() {
  53         this->validate();
  54         typename NodeList::Iter iter;
  55         Node* node = iter.init(fList, Iter::kHead_IterStart);
  56         while (NULL != node) {
  57             SkTCast<T*>(node->fObj)->~T();
  58             Block* block = node->fBlock;
  59             node = iter.next();
  60             if (0 == --block->fNodesInUse) {
  61                 for (int i = 0; i < fAllocCnt; ++i) {
  62                     block->fNodes[i].~Node();
  63                 }
  64                 sk_free(block);
  65             }
  66         }
  67     }
  68
  69     T* addToHead(const T& t) {
  70         this->validate();
  71         Node* node = this->createNode();
  72         fList.addToHead(node);
  73         SkNEW_PLACEMENT_ARGS(node->fObj, T, (t));
  74         this->validate();
  75         return reinterpret_cast<T*>(node->fObj);
  76     }
  77
  78     T* addToHead() {
  79         this->validate();
  80         Node* node = this->createNode();
  81         fList.addToHead(node);
  82         SkNEW_PLACEMENT(node->fObj, T);
  83         this->validate();
  84         return reinterpret_cast<T*>(node->fObj);
  85     }
  86
  87     T* addToTail(const T& t) {
  88         this->validate();
  89         Node* node = this->createNode();
  90         fList.addToTail(node);
  91         SkNEW_PLACEMENT_ARGS(node->fObj, T, (t));
  92         this->validate();
  93         return reinterpret_cast<T*>(node->fObj);
  94     }
  95
  96     T* addToTail() {
  97         this->validate();
  98         Node* node = this->createNode();
  99         fList.addToTail(node);
 100         SkNEW_PLACEMENT(node->fObj, T);
 101         this->validate();
 102         return reinterpret_cast<T*>(node->fObj);
 103     }
 104
 105     /** Adds a new element to the list before the location indicated by the iterator. If the
 106         iterator refers to a NULL location then the new element is added at the tail */
 107     T* addBefore(const T& t, const Iter& location) {
 108         return SkNEW_PLACEMENT_ARGS(this->internalAddBefore(location), T, (t));
 109     }
 110
 111     /** Adds a new element to the list after the location indicated by the iterator. If the
 112         iterator refers to a NULL location then the new element is added at the head */
 113     T* addAfter(const T& t, const Iter& location) {
 114         return SkNEW_PLACEMENT_ARGS(this->internalAddAfter(location), T, (t));
 115     }
 116
 117     /** Convenience methods for getting an iterator initialized to the head/tail of the list. */
 118     Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
 119     Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
 120
 121     T* head() { return Iter(*this, Iter::kHead_IterStart).get(); }
 122     T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); }
 123     const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); }
 124     const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); }
 125
 126     void popHead() {
 127         this->validate();
 128         Node* node = fList.head();
 129         if (NULL != node) {
 130             this->removeNode(node);
 131         }
 132         this->validate();
 133     }
 134
 135     void popTail() {
 136         this->validate();
 137         Node* node = fList.head();
 138         if (NULL != node) {
 139             this->removeNode(node);
 140         }
 141         this->validate();
 142     }
 143
 144     void remove(T* t) {
 145         this->validate();
 146         Node* node = reinterpret_cast<Node*>(t);
 147         SkASSERT(reinterpret_cast<T*>(node->fObj) == t);
 148         this->removeNode(node);
 149         this->validate();
 150     }
 151
 152     void reset() {
 153         this->validate();
 154         Iter iter(*this, Iter::kHead_IterStart);
 155         while (iter.get()) {
 156             Iter next = iter;
 157             next.next();
 158             this->remove(iter.get());
 159             iter = next;
 160         }
 161         SkASSERT(0 == fCount);
 162         this->validate();
 163     }
 164
 165     int count() const { return fCount; }
 166     bool isEmpty() const { this->validate(); return 0 == fCount; }
 167
 168     bool operator== (const SkTLList& list) const {
 169         if (this == &list) {
 170             return true;
 171         }
 172         if (fCount != list.fCount) {
 173             return false;
 174         }
 175         for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart);
 176              a.get();
 177              a.next(), b.next()) {
 178             SkASSERT(NULL != b.get()); // already checked that counts match.
 179             if (!(*a.get() == *b.get())) {
 180                 return false;
 181             }
 182         }
 183         return true;
 184     }
 185     bool operator!= (const SkTLList& list) const { return !(*this == list); }
 186
 187     /** The iterator becomes invalid if the element it refers to is removed from the list. */
 188     class Iter : private NodeList::Iter {
 189     private:
 190         typedef typename NodeList::Iter INHERITED;
 191
 192     public:
 193         typedef typename INHERITED::IterStart IterStart;
 194         //!< Start the iterator at the head of the list.
 195         static const IterStart kHead_IterStart = INHERITED::kHead_IterStart;
 196         //!< Start the iterator at the tail of the list.
 197         static const IterStart kTail_IterStart = INHERITED::kTail_IterStart;
 198
 199         Iter() {}
 200
 201         Iter(const SkTLList& list, IterStart start) {
 202             INHERITED::init(list.fList, start);
 203         }
 204
 205         T* init(const SkTLList& list, IterStart start) {
 206             return this->nodeToObj(INHERITED::init(list.fList, start));
 207         }
 208
 209         T* get() { return this->nodeToObj(INHERITED::get()); }
 210
 211         T* next() { return this->nodeToObj(INHERITED::next()); }
 212
 213         T* prev() { return this->nodeToObj(INHERITED::prev()); }
 214
 215         Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
 216
 217     private:
 218         friend class SkTLList;
 219         Node* getNode() { return INHERITED::get(); }
 220
 221         T* nodeToObj(Node* node) {
 222             if (NULL != node) {
 223                 return reinterpret_cast<T*>(node->fObj);
 224             } else {
 225                 return NULL;
 226             }
 227         }
 228     };
 229
 230     // For use with operator new
 231     enum Placement {
 232         kBefore_Placement,
 233         kAfter_Placement,
 234     };
 235
 236 private:
 237     struct Block {
 238         int fNodesInUse;
 239         Node fNodes[1];
 240     };
 241
 242     size_t blockSize() const { return sizeof(Block) + sizeof(Node) * (fAllocCnt-1); }
 243
 244     Node* createNode() {
 245         Node* node = fFreeList.head();
 246         if (NULL != node) {
 247             fFreeList.remove(node);
 248             ++node->fBlock->fNodesInUse;
 249         } else {
 250             Block* block = reinterpret_cast<Block*>(sk_malloc_flags(this->blockSize(), 0));
 251             node = &block->fNodes[0];
 252             SkNEW_PLACEMENT(node, Node);
 253             node->fBlock = block;
 254             block->fNodesInUse = 1;
 255             for (int i = 1; i < fAllocCnt; ++i) {
 256                 SkNEW_PLACEMENT(block->fNodes + i, Node);
 257                 fFreeList.addToHead(block->fNodes + i);
 258                 block->fNodes[i].fBlock = block;
 259             }
 260         }
 261         ++fCount;
 262         return node;
 263     }
 264
 265     void removeNode(Node* node) {
 266         SkASSERT(NULL != node);
 267         fList.remove(node);
 268         SkTCast<T*>(node->fObj)->~T();
 269         if (0 == --node->fBlock->fNodesInUse) {
 270             Block* block = node->fBlock;
 271             for (int i = 0; i < fAllocCnt; ++i) {
 272                 if (block->fNodes + i != node) {
 273                     fFreeList.remove(block->fNodes + i);
 274                 }
 275                 block->fNodes[i].~Node();
 276             }
 277             sk_free(block);
 278         } else {
 279             fFreeList.addToHead(node);
 280         }
 281         --fCount;
 282         this->validate();
 283     }
 284
 285     void validate() const {
 286 #ifdef SK_DEBUG
 287         SkASSERT((0 == fCount) == fList.isEmpty());
 288         SkASSERT((0 != fCount) || fFreeList.isEmpty());
 289
 290         fList.validate();
 291         fFreeList.validate();
 292         typename NodeList::Iter iter;
 293         Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
 294         while (freeNode) {
 295             SkASSERT(fFreeList.isInList(freeNode));
 296             Block* block = freeNode->fBlock;
 297             SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse < fAllocCnt);
 298
 299             int activeCnt = 0;
 300             int freeCnt = 0;
 301             for (int i = 0; i < fAllocCnt; ++i) {
 302                 bool free = fFreeList.isInList(block->fNodes + i);
 303                 bool active = fList.isInList(block->fNodes + i);
 304                 SkASSERT(free != active);
 305                 activeCnt += active;
 306                 freeCnt += free;
 307             }
 308             SkASSERT(activeCnt == block->fNodesInUse);
 309             freeNode = iter.next();
 310         }
 311
 312         int count = 0;
 313         Node* activeNode = iter.init(fList, Iter::kHead_IterStart);
 314         while (activeNode) {
 315             ++count;
 316             SkASSERT(fList.isInList(activeNode));
 317             Block* block = activeNode->fBlock;
 318             SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse <= fAllocCnt);
 319
 320             int activeCnt = 0;
 321             int freeCnt = 0;
 322             for (int i = 0; i < fAllocCnt; ++i) {
 323                 bool free = fFreeList.isInList(block->fNodes + i);
 324                 bool active = fList.isInList(block->fNodes + i);
 325                 SkASSERT(free != active);
 326                 activeCnt += active;
 327                 freeCnt += free;
 328             }
 329             SkASSERT(activeCnt == block->fNodesInUse);
 330             activeNode = iter.next();
 331         }
 332         SkASSERT(count == fCount);
 333 #endif
 334     }
 335
 336     // Support in-place initializing of objects inserted into the list via operator new.
 337     friend void* operator new<T>(size_t,
 338                                  SkTLList* list,
 339                                  Placement placement,
 340                                  const Iter& location);
 341
 342
 343     // Helpers that insert the node and returns a pointer to where the new object should be init'ed.
 344     void* internalAddBefore(Iter location) {
 345         this->validate();
 346         Node* node = this->createNode();
 347         fList.addBefore(node, location.getNode());
 348         this->validate();
 349         return node->fObj;
 350     }
 351
 352     void* internalAddAfter(Iter location) {
 353         this->validate();
 354         Node* node = this->createNode();
 355         fList.addAfter(node, location.getNode());
 356         this->validate();
 357         return node->fObj;
 358     }
 359
 360     NodeList fList;
 361     NodeList fFreeList;
 362     int fCount;
 363     int fAllocCnt;
 364
 365 };
 366
 367 // Use the below macros rather than calling this directly
 368 template <typename T>
 369 void *operator new(size_t, SkTLList<T>* list,
 370                    typename SkTLList<T>::Placement placement,
 371                    const typename SkTLList<T>::Iter& location) {
 372     SkASSERT(NULL != list);
 373     if (SkTLList<T>::kBefore_Placement == placement) {
 374         return list->internalAddBefore(location);
 375     } else {
 376         return list->internalAddAfter(location);
 377     }
 378 }
 379
 380 // Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
 381 // to match the op new silences warnings about missing op delete when a constructor throws an
 382 // exception.
 383 template <typename T>
 384 void operator delete(void*,
 385                      SkTLList<T>*,
 386                      typename SkTLList<T>::Placement,
 387                      const typename SkTLList<T>::Iter&) {
 388     SK_CRASH();
 389 }
 390
 391 #define SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) \
 392     (new ((list), SkTLList< type_name >::kBefore_Placement, (location)) type_name args)
 393
 394 #define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \
 395     (new ((list), SkTLList< type_name >::kAfter_Placement, (location)) type_name args)
 396
 397 #define SkNEW_INSERT_AT_LLIST_HEAD(list, type_name, args) \
 398     SkNEW_INSERT_IN_LLIST_BEFORE((list), (list)->headIter(), type_name, args)
 399
 400 #define SkNEW_INSERT_AT_LLIST_TAIL(list, type_name, args) \
 401     SkNEW_INSERT_IN_LLIST_AFTER((list), (list)->tailIter(), type_name, args)
 402
 403 #endif