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