Home | History | Annotate | Download | only in core 
      1 
      2 /*
      3  * Copyright 2006 The Android Open Source Project
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 
     10 #ifndef SkDeque_DEFINED
     11 #define SkDeque_DEFINED
     12 
     13 #include "../private/SkNoncopyable.h"
     14 #include "SkTypes.h"
     15 
     16 /*
     17  * The deque class works by blindly creating memory space of a specified element
     18  * size. It manages the memory as a doubly linked list of blocks each of which
     19  * can contain multiple elements. Pushes and pops add/remove blocks from the
     20  * beginning/end of the list as necessary while each block tracks the used
     21  * portion of its memory.
     22  * One behavior to be aware of is that the pops do not immediately remove an
     23  * empty block from the beginning/end of the list (Presumably so push/pop pairs
     24  * on the block boundaries don't cause thrashing). This can result in the first/
     25  * last element not residing in the first/last block.
     26  */
     27 class SK_API SkDeque : SkNoncopyable {
     28 public:
     29     /**
     30      * elemSize specifies the size of each individual element in the deque
     31      * allocCount specifies how many elements are to be allocated as a block
     32      */
     33     explicit SkDeque(size_t elemSize, int allocCount = 1);
     34     SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1);
     35     ~SkDeque();
     36 
     37     bool    empty() const { return 0 == fCount; }
     38     int     count() const { return fCount; }
     39     size_t  elemSize() const { return fElemSize; }
     40 
     41     const void* front() const { return fFront; }
     42     const void* back() const  { return fBack; }
     43 
     44     void* front() {
     45         return (void*)((const SkDeque*)this)->front();
     46     }
     47 
     48     void* back() {
     49         return (void*)((const SkDeque*)this)->back();
     50     }
     51 
     52     /**
     53      * push_front and push_back return a pointer to the memory space
     54      * for the new element
     55      */
     56     void* push_front();
     57     void* push_back();
     58 
     59     void pop_front();
     60     void pop_back();
     61 
     62 private:
     63     struct Block;
     64 
     65 public:
     66     class Iter {
     67     public:
     68         enum IterStart {
     69             kFront_IterStart,
     70             kBack_IterStart,
     71         };
     72 
     73         /**
     74          * Creates an uninitialized iterator. Must be reset()
     75          */
     76         Iter();
     77 
     78         Iter(const SkDeque& d, IterStart startLoc);
     79         void* next();
     80         void* prev();
     81 
     82         void reset(const SkDeque& d, IterStart startLoc);
     83 
     84     private:
     85         SkDeque::Block* fCurBlock;
     86         char*           fPos;
     87         size_t          fElemSize;
     88     };
     89 
     90     // Inherit privately from Iter to prevent access to reverse iteration
     91     class F2BIter : private Iter {
     92     public:
     93         F2BIter() {}
     94 
     95         /**
     96          * Wrap Iter's 2 parameter ctor to force initialization to the
     97          * beginning of the deque
     98          */
     99         F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {}
    100 
    101         using Iter::next;
    102 
    103         /**
    104          * Wrap Iter::reset to force initialization to the beginning of the
    105          * deque
    106          */
    107         void reset(const SkDeque& d) {
    108             this->INHERITED::reset(d, kFront_IterStart);
    109         }
    110 
    111     private:
    112         typedef Iter INHERITED;
    113     };
    114 
    115 private:
    116     // allow unit test to call numBlocksAllocated
    117     friend class DequeUnitTestHelper;
    118 
    119     void*   fFront;
    120     void*   fBack;
    121 
    122     Block*  fFrontBlock;
    123     Block*  fBackBlock;
    124     size_t  fElemSize;
    125     void*   fInitialStorage;
    126     int     fCount;             // number of elements in the deque
    127     int     fAllocCount;        // number of elements to allocate per block
    128 
    129     Block*  allocateBlock(int allocCount);
    130     void    freeBlock(Block* block);
    131 
    132     /**
    133      * This returns the number of chunk blocks allocated by the deque. It
    134      * can be used to gauge the effectiveness of the selected allocCount.
    135      */
    136     int  numBlocksAllocated() const;
    137 };
    138 
    139 #endif
    140