Line data    Source code

       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         713 :     bool    empty() const { return 0 == fCount; }
      37        1951 :     int     count() const { return fCount; }
      38             :     size_t  elemSize() const { return fElemSize; }
      39             : 
      40          87 :     const void* front() const { return fFront; }
      41        1308 :     const void* back() const  { return fBack; }
      42             : 
      43             :     void* front() {
      44             :         return (void*)((const SkDeque*)this)->front();
      45             :     }
      46             : 
      47        1308 :     void* back() {
      48        1308 :         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           0 :         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