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 : 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* addToTail(const T& t) {
     79         this->validate();
     80         Node* node = this->createNode();
     81         fList.addToTail(node);
     82         SkNEW_PLACEMENT_ARGS(node->fObj, T, (t));
     83         this->validate();
     84         return reinterpret_cast<T*>(node->fObj);
     85     }
     86 
     87     /** Adds a new element to the list before the location indicated by the iterator. If the
     88         iterator refers to a NULL location then the new element is added at the tail */
     89     T* addBefore(const T& t, const Iter& location) {
     90         return SkNEW_PLACEMENT_ARGS(this->internalAddBefore(location), T, (t));
     91     }
     92 
     93     /** Adds a new element to the list after the location indicated by the iterator. If the
     94         iterator refers to a NULL location then the new element is added at the head */
     95     T* addAfter(const T& t, const Iter& location) {
     96         return SkNEW_PLACEMENT_ARGS(this->internalAddAfter(location), T, (t));
     97     }
     98 
     99     /** Convenience methods for getting an iterator initialized to the head/tail of the list. */
    100     Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
    101     Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
    102 
    103     T* head() { return Iter(*this, Iter::kHead_IterStart).get(); }
    104     T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); }
    105     const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); }
    106     const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); }
    107 
    108     void popHead() {
    109         this->validate();
    110         Node* node = fList.head();
    111         if (NULL != node) {
    112             this->removeNode(node);
    113         }
    114         this->validate();
    115     }
    116 
    117     void popTail() {
    118         this->validate();
    119         Node* node = fList.head();
    120         if (NULL != node) {
    121             this->removeNode(node);
    122         }
    123         this->validate();
    124     }
    125 
    126     void remove(T* t) {
    127         this->validate();
    128         Node* node = reinterpret_cast<Node*>(t);
    129         SkASSERT(reinterpret_cast<T*>(node->fObj) == t);
    130         this->removeNode(node);
    131         this->validate();
    132     }
    133 
    134     void reset() {
    135         this->validate();
    136         Iter iter(*this, Iter::kHead_IterStart);
    137         while (iter.get()) {
    138             Iter next = iter;
    139             next.next();
    140             this->remove(iter.get());
    141             iter = next;
    142         }
    143         SkASSERT(0 == fCount);
    144         this->validate();
    145     }
    146 
    147     int count() const { return fCount; }
    148     bool isEmpty() const { this->validate(); return 0 == fCount; }
    149 
    150     bool operator== (const SkTLList& list) const {
    151         if (this == &list) {
    152             return true;
    153         }
    154         if (fCount != list.fCount) {
    155             return false;
    156         }
    157         for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart);
    158              a.get();
    159              a.next(), b.next()) {
    160             SkASSERT(NULL != b.get()); // already checked that counts match.
    161             if (!(*a.get() == *b.get())) {
    162                 return false;
    163             }
    164         }
    165         return true;
    166     }
    167     bool operator!= (const SkTLList& list) const { return !(*this == list); }
    168 
    169     /** The iterator becomes invalid if the element it refers to is removed from the list. */
    170     class Iter : private NodeList::Iter {
    171     private:
    172         typedef typename NodeList::Iter INHERITED;
    173 
    174     public:
    175         typedef typename INHERITED::IterStart IterStart;
    176         //!< Start the iterator at the head of the list.
    177         static const IterStart kHead_IterStart = INHERITED::kHead_IterStart;
    178         //!< Start the iterator at the tail of the list.
    179         static const IterStart kTail_IterStart = INHERITED::kTail_IterStart;
    180 
    181         Iter() {}
    182 
    183         Iter(const SkTLList& list, IterStart start) {
    184             INHERITED::init(list.fList, start);
    185         }
    186 
    187         T* init(const SkTLList& list, IterStart start) {
    188             return this->nodeToObj(INHERITED::init(list.fList, start));
    189         }
    190 
    191         T* get() { return this->nodeToObj(INHERITED::get()); }
    192 
    193         T* next() { return this->nodeToObj(INHERITED::next()); }
    194 
    195         T* prev() { return this->nodeToObj(INHERITED::prev()); }
    196 
    197         Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
    198 
    199     private:
    200         friend class SkTLList;
    201         Node* getNode() { return INHERITED::get(); }
    202 
    203         T* nodeToObj(Node* node) {
    204             if (NULL != node) {
    205                 return reinterpret_cast<T*>(node->fObj);
    206             } else {
    207                 return NULL;
    208             }
    209         }
    210     };
    211 
    212     // For use with operator new
    213     enum Placement {
    214         kBefore_Placement,
    215         kAfter_Placement,
    216     };
    217 
    218 private:
    219     struct Block {
    220         int fNodesInUse;
    221         Node fNodes[1];
    222     };
    223 
    224     size_t blockSize() const { return sizeof(Block) + sizeof(Node) * (fAllocCnt-1); }
    225 
    226     Node* createNode() {
    227         Node* node = fFreeList.head();
    228         if (NULL != node) {
    229             fFreeList.remove(node);
    230             ++node->fBlock->fNodesInUse;
    231         } else {
    232             Block* block = reinterpret_cast<Block*>(sk_malloc_flags(this->blockSize(), 0));
    233             node = &block->fNodes[0];
    234             SkNEW_PLACEMENT(node, Node);
    235             node->fBlock = block;
    236             block->fNodesInUse = 1;
    237             for (int i = 1; i < fAllocCnt; ++i) {
    238                 SkNEW_PLACEMENT(block->fNodes + i, Node);
    239                 fFreeList.addToHead(block->fNodes + i);
    240                 block->fNodes[i].fBlock = block;
    241             }
    242         }
    243         ++fCount;
    244         return node;
    245     }
    246 
    247     void removeNode(Node* node) {
    248         SkASSERT(NULL != node);
    249         fList.remove(node);
    250         SkTCast<T*>(node->fObj)->~T();
    251         if (0 == --node->fBlock->fNodesInUse) {
    252             Block* block = node->fBlock;
    253             for (int i = 0; i < fAllocCnt; ++i) {
    254                 if (block->fNodes + i != node) {
    255                     fFreeList.remove(block->fNodes + i);
    256                 }
    257                 block->fNodes[i].~Node();
    258             }
    259             sk_free(block);
    260         } else {
    261             fFreeList.addToHead(node);
    262         }
    263         --fCount;
    264         this->validate();
    265     }
    266 
    267     void validate() const {
    268 #ifdef SK_DEBUG
    269         SkASSERT((0 == fCount) == fList.isEmpty());
    270         SkASSERT((0 != fCount) || fFreeList.isEmpty());
    271 
    272         fList.validate();
    273         fFreeList.validate();
    274         typename NodeList::Iter iter;
    275         Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
    276         while (freeNode) {
    277             SkASSERT(fFreeList.isInList(freeNode));
    278             Block* block = freeNode->fBlock;
    279             SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse < fAllocCnt);
    280 
    281             int activeCnt = 0;
    282             int freeCnt = 0;
    283             for (int i = 0; i < fAllocCnt; ++i) {
    284                 bool free = fFreeList.isInList(block->fNodes + i);
    285                 bool active = fList.isInList(block->fNodes + i);
    286                 SkASSERT(free != active);
    287                 activeCnt += active;
    288                 freeCnt += free;
    289             }
    290             SkASSERT(activeCnt == block->fNodesInUse);
    291             freeNode = iter.next();
    292         }
    293 
    294         int count = 0;
    295         Node* activeNode = iter.init(fList, Iter::kHead_IterStart);
    296         while (activeNode) {
    297             ++count;
    298             SkASSERT(fList.isInList(activeNode));
    299             Block* block = activeNode->fBlock;
    300             SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse <= fAllocCnt);
    301 
    302             int activeCnt = 0;
    303             int freeCnt = 0;
    304             for (int i = 0; i < fAllocCnt; ++i) {
    305                 bool free = fFreeList.isInList(block->fNodes + i);
    306                 bool active = fList.isInList(block->fNodes + i);
    307                 SkASSERT(free != active);
    308                 activeCnt += active;
    309                 freeCnt += free;
    310             }
    311             SkASSERT(activeCnt == block->fNodesInUse);
    312             activeNode = iter.next();
    313         }
    314         SkASSERT(count == fCount);
    315 #endif
    316     }
    317 
    318     // Support in-place initializing of objects inserted into the list via operator new.
    319     friend void* operator new<T>(size_t,
    320                                  SkTLList* list,
    321                                  Placement placement,
    322                                  const Iter& location);
    323 
    324 
    325     // Helpers that insert the node and returns a pointer to where the new object should be init'ed.
    326     void* internalAddBefore(Iter location) {
    327         this->validate();
    328         Node* node = this->createNode();
    329         fList.addBefore(node, location.getNode());
    330         this->validate();
    331         return node->fObj;
    332     }
    333 
    334     void* internalAddAfter(Iter location) {
    335         this->validate();
    336         Node* node = this->createNode();
    337         fList.addAfter(node, location.getNode());
    338         this->validate();
    339         return node->fObj;
    340     }
    341 
    342     NodeList fList;
    343     NodeList fFreeList;
    344     int fCount;
    345     int fAllocCnt;
    346 
    347 };
    348 
    349 // Use the below macros rather than calling this directly
    350 template <typename T>
    351 void *operator new(size_t, SkTLList<T>* list,
    352                    typename SkTLList<T>::Placement placement,
    353                    const typename SkTLList<T>::Iter& location) {
    354     SkASSERT(NULL != list);
    355     if (SkTLList<T>::kBefore_Placement == placement) {
    356         return list->internalAddBefore(location);
    357     } else {
    358         return list->internalAddAfter(location);
    359     }
    360 }
    361 
    362 // Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
    363 // to match the op new silences warnings about missing op delete when a constructor throws an
    364 // exception.
    365 template <typename T>
    366 void operator delete(void*,
    367                      SkTLList<T>*,
    368                      typename SkTLList<T>::Placement,
    369                      const typename SkTLList<T>::Iter&) {
    370     SK_CRASH();
    371 }
    372 
    373 #define SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) \
    374     (new ((list), SkTLList< type_name >::kBefore_Placement, (location)) type_name args)
    375 
    376 #define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \
    377     (new ((list), SkTLList< type_name >::kAfter_Placement, (location)) type_name args)
    378 
    379 #define SkNEW_INSERT_AT_LLIST_HEAD(list, type_name, args) \
    380     SkNEW_INSERT_IN_LLIST_BEFORE((list), (list)->headIter(), type_name, args)
    381 
    382 #define SkNEW_INSERT_AT_LLIST_TAIL(list, type_name, args) \
    383     SkNEW_INSERT_IN_LLIST_AFTER((list), (list)->tailIter(), type_name, args)
    384 
    385 #endif
    386