SkDeque.h 3.7 KB

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