X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/b5422865f473faf3977f31b96a635c4c8c4ede09..9dae56ea45a0f5f8136a5c93d6f3a7f99399ca73:/bytecompiler/SegmentedVector.h

diff --git a/bytecompiler/SegmentedVector.h b/bytecompiler/SegmentedVector.h
new file mode 100644
index 0000000..bbab04f
--- /dev/null
+++ b/bytecompiler/SegmentedVector.h
@@ -0,0 +1,170 @@
+/*
+ * Copyright (C) 2008 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
+ *     its contributors may be used to endorse or promote products derived
+ *     from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef SegmentedVector_h
+#define SegmentedVector_h
+
+#include <wtf/Vector.h>
+
+namespace JSC {
+
+    // SegmentedVector is just like Vector, but it doesn't move the values
+    // stored in its buffer when it grows. Therefore, it is safe to keep
+    // pointers into a SegmentedVector.
+    template <typename T, size_t SegmentSize> class SegmentedVector {
+    public:
+        SegmentedVector()
+            : m_size(0)
+        {
+            m_segments.append(&m_inlineSegment);
+        }
+
+        ~SegmentedVector()
+        {
+            deleteAllSegments();
+        }
+
+        size_t size() const { return m_size; }
+
+        T& at(size_t index)
+        {
+            if (index < SegmentSize)
+                return m_inlineSegment[index];
+            return segmentFor(index)->at(subscriptFor(index));
+        }
+
+        T& operator[](size_t index)
+        {
+            return at(index);
+        }
+
+        T& last()
+        {
+            return at(size() - 1);
+        }
+
+        template <typename U> void append(const U& value)
+        {
+            ++m_size;
+
+            if (m_size <= SegmentSize) {
+                m_inlineSegment.uncheckedAppend(value);
+                return;
+            }
+
+            if (!segmentExistsFor(m_size - 1))
+                m_segments.append(new Segment);
+            segmentFor(m_size - 1)->uncheckedAppend(value);
+        }
+
+        void removeLast()
+        {
+            if (m_size <= SegmentSize)
+                m_inlineSegment.removeLast();
+            else
+                segmentFor(m_size - 1)->removeLast();
+            --m_size;
+        }
+
+        void grow(size_t size)
+        {
+            ASSERT(size > m_size);
+            ensureSegmentsFor(size);
+            m_size = size;
+        }
+
+        void clear()
+        {
+            deleteAllSegments();
+            m_segments.resize(1);
+            m_inlineSegment.clear();
+            m_size = 0;
+        }
+
+    private:
+        typedef Vector<T, SegmentSize> Segment;
+        
+        void deleteAllSegments()
+        {
+            // Skip the first segment, because it's our inline segment, which was
+            // not created by new.
+            for (size_t i = 1; i < m_segments.size(); i++)
+                delete m_segments[i];
+        }
+        
+        bool segmentExistsFor(size_t index)
+        {
+            return index / SegmentSize < m_segments.size();
+        }
+        
+        Segment* segmentFor(size_t index)
+        {
+            return m_segments[index / SegmentSize];
+        }
+        
+        size_t subscriptFor(size_t index)
+        {
+            return index % SegmentSize;
+        }
+        
+        void ensureSegmentsFor(size_t size)
+        {
+            size_t segmentCount = m_size / SegmentSize;
+            if (m_size % SegmentSize)
+                ++segmentCount;
+            segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
+
+            size_t neededSegmentCount = size / SegmentSize;
+            if (size % SegmentSize)
+                ++neededSegmentCount;
+
+            // Fill up to N - 1 segments.
+            size_t end = neededSegmentCount - 1;
+            for (size_t i = segmentCount - 1; i < end; ++i)
+                ensureSegment(i, SegmentSize);
+            
+            // Grow segment N to accomodate the remainder.
+            ensureSegment(end, subscriptFor(size - 1) + 1);
+        }
+
+        void ensureSegment(size_t segmentIndex, size_t size)
+        {
+            ASSERT(segmentIndex <= m_segments.size());
+            if (segmentIndex == m_segments.size())
+                m_segments.append(new Segment);
+            m_segments[segmentIndex]->grow(size);
+        }
+
+        size_t m_size;
+        Segment m_inlineSegment;
+        Vector<Segment*, 32> m_segments;
+    };
+
+} // namespace JSC
+
+#endif // SegmentedVector_h