Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2014 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 SkTInternalSList_DEFINED
      9 #define SkTInternalSList_DEFINED
     10 
     11 #include "SkTInternalLList.h" // for SkPtrWrapper
     12 
     13 /**
     14  * This macro creates the methods required by the SkTInternalSList class.
     15  * It should be instantiated in the private block of the class you want to put
     16  * into an SkTInternalSList.
     17  * For most use cases you should use SK_DECLARE_INTERNAL_SLIST_INTERFACE and not
     18  * this macro. If you care about the field name, or want to re-use an existing
     19  * field, then you can use this macro to declare the methods pointing to a
     20  * specific field.
     21  * Unlike SK_DECLARE_INTERNAL_SLIST_INTERFACE this does not declare the field
     22  * itself.
     23  * It also makes SkTInternalSList<ClassName> a friend to give it access to the
     24  * methods.
     25  */
     26 #define SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, field)     \
     27     ClassName* getSListNext() {                                 \
     28         return this->field;                                     \
     29     }                                                           \
     30     void setSListNext(ClassName* next) {                        \
     31         this->field = next;                                     \
     32     }                                                           \
     33     friend class SkTInternalSList<ClassName>
     34 
     35 /**
     36  * This macro declares an fSListNext that auto initializes to NULL and then
     37  * uses SK_DECLARE_INTERNAL_SLIST_ADAPTER to add the methods needed by
     38  * SkTInternalSList.
     39  * It should be instantiated in the private block of the class you want to put
     40  * into an SkTInternalSList.
     41  */
     42 #define SK_DECLARE_INTERNAL_SLIST_INTERFACE(ClassName)          \
     43     SK_DECLARE_INTERNAL_SLIST_ADAPTER(ClassName, fSListNext);   \
     44     SkPtrWrapper<ClassName> fSListNext
     45 
     46 /**
     47  * An implementation of an intrusive singly linked list.
     48  * The type T must have a methods getSListNext and setSListNext that are visible
     49  * to the list. The easiest way to do this is with
     50  * SK_DECLARE_INTERNAL_SLIST_INTERFACE.
     51  * The list does not maintain ownership of any of its elements, or ever delete
     52  * them.
     53  */
     54 template<typename T> class SkTInternalSList {
     55 public:
     56     SkTInternalSList() : fHead(NULL), fCount(0) {}
     57 
     58     /**
     59      * Push an item onto the head of the list.
     60      * This method is *not* thread safe.
     61      */
     62     void push(T* entry) {
     63         SkASSERT(entry->getSListNext() == NULL);
     64         entry->setSListNext(fHead);
     65         fHead = entry;
     66         ++fCount;
     67     }
     68 
     69     /**
     70      * Takes all the items from another list and pushes them into this list.
     71      * No ordering guarantees are made, the other list will be emptied.
     72      * This method is *not* thread safe.
     73      */
     74     void pushAll(SkTInternalSList<T>* other) {
     75         if (this->isEmpty()) {
     76             this->swap(other);
     77             return;
     78         }
     79         while (!other->isEmpty()) {
     80             this->push(other->pop());
     81         }
     82     }
     83 
     84     /**
     85      * Pop an item from the head of the list.
     86      * Returns NULL if the list is empty.
     87      * This method is *not* thread safe.
     88      */
     89     T* pop() {
     90         if (NULL == fHead) {
     91             return NULL;
     92         }
     93         T* result = fHead;
     94         fHead = result->getSListNext();
     95         result->setSListNext(NULL);
     96         --fCount;
     97         return result;
     98     }
     99 
    100     T* head() const {
    101         return fHead;
    102     }
    103 
    104     /**
    105      * Returns true if the list has no elements.
    106      */
    107     bool isEmpty() const {
    108         return NULL == fHead;
    109     }
    110 
    111     /**
    112      * Swaps the contents of this list with another one.
    113      * This method is *not* thread safe.
    114      */
    115     void swap(SkTInternalSList<T>* other) {
    116         SkTSwap(fHead, other->fHead);
    117         SkTSwap(fCount, other->fCount);
    118     }
    119 
    120     /**
    121      * Returns the count of elements in the list.
    122      */
    123     int getCount() const {
    124         return fCount;
    125     }
    126 private:
    127     T* fHead;
    128     int fCount;
    129 };
    130 
    131 
    132 #endif
    133