1 files changed, 141 insertions, 0 deletions
diff --git a/src/deps/skia/include/private/SkDeque.h b/src/deps/skia/include/private/SkDeque.h
new file mode 100644
index 000000000..8adc39c1c
--- /dev/null
+++ b/src/deps/skia/include/private/SkDeque.h
@@ -0,0 +1,141 @@
+
+/*
+ * Copyright 2006 The Android Open Source Project
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+
+#ifndef SkDeque_DEFINED
+#define SkDeque_DEFINED
+
+#include "include/core/SkTypes.h"
+
+/*
+ * The deque class works by blindly creating memory space of a specified element
+ * size. It manages the memory as a doubly linked list of blocks each of which
+ * can contain multiple elements. Pushes and pops add/remove blocks from the
+ * beginning/end of the list as necessary while each block tracks the used
+ * portion of its memory.
+ * One behavior to be aware of is that the pops do not immediately remove an
+ * empty block from the beginning/end of the list (Presumably so push/pop pairs
+ * on the block boundaries don't cause thrashing). This can result in the first/
+ * last element not residing in the first/last block.
+ */
+class SK_API SkDeque {
+public:
+    /**
+     * elemSize specifies the size of each individual element in the deque
+     * allocCount specifies how many elements are to be allocated as a block
+     */
+    explicit SkDeque(size_t elemSize, int allocCount = 1);
+    SkDeque(size_t elemSize, void* storage, size_t storageSize, int allocCount = 1);
+    ~SkDeque();
+
+    bool    empty() const { return 0 == fCount; }
+    int     count() const { return fCount; }
+    size_t  elemSize() const { return fElemSize; }
+
+    const void* front() const { return fFront; }
+    const void* back() const  { return fBack; }
+
+    void* front() {
+        return (void*)((const SkDeque*)this)->front();
+    }
+
+    void* back() {
+        return (void*)((const SkDeque*)this)->back();
+    }
+
+    /**
+     * push_front and push_back return a pointer to the memory space
+     * for the new element
+     */
+    void* push_front();
+    void* push_back();
+
+    void pop_front();
+    void pop_back();
+
+private:
+    struct Block;
+
+public:
+    class Iter {
+    public:
+        enum IterStart {
+            kFront_IterStart,
+            kBack_IterStart,
+        };
+
+        /**
+         * Creates an uninitialized iterator. Must be reset()
+         */
+        Iter();
+
+        Iter(const SkDeque& d, IterStart startLoc);
+        void* next();
+        void* prev();
+
+        void reset(const SkDeque& d, IterStart startLoc);
+
+    private:
+        SkDeque::Block* fCurBlock;
+        char*           fPos;
+        size_t          fElemSize;
+    };
+
+    // Inherit privately from Iter to prevent access to reverse iteration
+    class F2BIter : private Iter {
+    public:
+        F2BIter() {}
+
+        /**
+         * Wrap Iter's 2 parameter ctor to force initialization to the
+         * beginning of the deque
+         */
+        F2BIter(const SkDeque& d) : INHERITED(d, kFront_IterStart) {}
+
+        using Iter::next;
+
+        /**
+         * Wrap Iter::reset to force initialization to the beginning of the
+         * deque
+         */
+        void reset(const SkDeque& d) {
+            this->INHERITED::reset(d, kFront_IterStart);
+        }
+
+    private:
+        using INHERITED = Iter;
+    };
+
+private:
+    // allow unit test to call numBlocksAllocated
+    friend class DequeUnitTestHelper;
+
+    void*   fFront;
+    void*   fBack;
+
+    Block*  fFrontBlock;
+    Block*  fBackBlock;
+    size_t  fElemSize;
+    void*   fInitialStorage;
+    int     fCount;             // number of elements in the deque
+    int     fAllocCount;        // number of elements to allocate per block
+
+    Block*  allocateBlock(int allocCount);
+    void    freeBlock(Block* block);
+
+    /**
+     * This returns the number of chunk blocks allocated by the deque. It
+     * can be used to gauge the effectiveness of the selected allocCount.
+     */
+    int  numBlocksAllocated() const;
+
+    SkDeque(const SkDeque&) = delete;
+    SkDeque& operator=(const SkDeque&) = delete;
+};
+
+#endif