Home | History | Annotate | Download | only in core 
      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 : 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 (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 (node) {
    130             this->removeNode(node);
    131         }
    132         this->validate();
    133     }
    134 
    135     void popTail() {
    136         this->validate();
    137         Node* node = fList.head();
    138         if (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(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 = kHead_IterStart) {
    202             INHERITED::init(list.fList, start);
    203         }
    204 
    205         T* init(const SkTLList& list, IterStart start = kHead_IterStart) {
    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 (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 (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(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(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
    404