1 files changed, 225 insertions, 0 deletions

diff --git a/gfx/angle/src/libANGLE/HandleRangeAllocator.cpp b/gfx/angle/src/libANGLE/HandleRangeAllocator.cpp
new file mode 100755
index 000000000..500a79629
--- /dev/null
+++ b/gfx/angle/src/libANGLE/HandleRangeAllocator.cpp
@@ -0,0 +1,225 @@
+//
+// Copyright (c) 2016 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+
+// HandleRangeAllocator.cpp : Implementation for HandleRangeAllocator.h
+
+#include "libANGLE/HandleRangeAllocator.h"
+
+#include <algorithm>
+#include <limits>
+#include <utility>
+
+#include "common/angleutils.h"
+#include "common/debug.h"
+
+namespace gl
+{
+
+const GLuint HandleRangeAllocator::kInvalidHandle = 0;
+
+HandleRangeAllocator::HandleRangeAllocator()
+{
+    // Simplify the code by making sure that lower_bound(id) never
+    // returns the beginning of the map, if id is valid (eg != kInvalidHandle).
+    mUsed.insert(std::make_pair(0u, 0u));
+}
+
+GLuint HandleRangeAllocator::allocate()
+{
+    return allocateRange(1u);
+}
+
+GLuint HandleRangeAllocator::allocateAtOrAbove(GLuint wanted)
+{
+    if (wanted == 0u || wanted == 1u)
+        return allocateRange(1u);
+
+    auto current = mUsed.lower_bound(wanted);
+    auto next = current;
+    if (current == mUsed.end() || current->first > wanted)
+    {
+        current--;
+    }
+    else
+    {
+        next++;
+    }
+
+    GLuint firstId = current->first;
+    GLuint lastId = current->second;
+    ASSERT(wanted >= firstId);
+
+    if (wanted - 1u <= lastId)
+    {
+        // Append to current range.
+        lastId++;
+        if (lastId == 0)
+        {
+            // The increment overflowed.
+            return allocateRange(1u);
+        }
+
+        current->second = lastId;
+
+        if (next != mUsed.end() && next->first - 1u == lastId)
+        {
+            // Merge with next range.
+            current->second = next->second;
+            mUsed.erase(next);
+        }
+        return lastId;
+    }
+    else if (next != mUsed.end() && next->first - 1u == wanted)
+    {
+        // Prepend to next range.
+        GLuint lastExisting = next->second;
+        mUsed.erase(next);
+        mUsed.insert(std::make_pair(wanted, lastExisting));
+        return wanted;
+    }
+    mUsed.insert(std::make_pair(wanted, wanted));
+    return wanted;
+}
+
+GLuint HandleRangeAllocator::allocateRange(GLuint range)
+{
+    ASSERT(range != 0);
+
+    auto current = mUsed.begin();
+    auto next    = current;
+
+    while (++next != mUsed.end())
+    {
+        if (next->first - current->second > range)
+            break;
+        current = next;
+    }
+    const GLuint firstId = current->second + 1u;
+    const GLuint lastId  = firstId + range - 1u;
+
+    // deal with wraparound
+    if (firstId == 0u || lastId < firstId)
+        return kInvalidHandle;
+
+    current->second = lastId;
+
+    if (next != mUsed.end() && next->first - 1u == lastId)
+    {
+        // merge with next range
+        current->second = next->second;
+        mUsed.erase(next);
+    }
+    return firstId;
+}
+
+bool HandleRangeAllocator::markAsUsed(GLuint handle)
+{
+    ASSERT(handle);
+    auto current = mUsed.lower_bound(handle);
+    if (current != mUsed.end() && current->first == handle)
+        return false;
+
+    auto next = current;
+    --current;
+
+    if (current->second >= handle)
+        return false;
+
+    ASSERT(current->first < handle && current->second < handle);
+
+    if (current->second + 1u == handle)
+    {
+        // Append to current range.
+        current->second = handle;
+        if (next != mUsed.end() && next->first - 1u == handle)
+        {
+            // Merge with next range.
+            current->second = next->second;
+            mUsed.erase(next);
+        }
+        return true;
+    }
+    else if (next != mUsed.end() && next->first - 1u == handle)
+    {
+        // Prepend to next range.
+        GLuint lastExisting = next->second;
+        mUsed.erase(next);
+        mUsed.insert(std::make_pair(handle, lastExisting));
+        return true;
+    }
+
+    mUsed.insert(std::make_pair(handle, handle));
+    return true;
+}
+
+void HandleRangeAllocator::release(GLuint handle)
+{
+    releaseRange(handle, 1u);
+}
+
+void HandleRangeAllocator::releaseRange(GLuint first, GLuint range)
+{
+    if (range == 0u || (first == 0u && range == 1u))
+        return;
+
+    if (first == 0u)
+    {
+        first++;
+        range--;
+    }
+
+    GLuint last = first + range - 1u;
+    if (last < first)
+        last = std::numeric_limits<GLuint>::max();
+
+    while (true)
+    {
+        auto current = mUsed.lower_bound(last);
+        if (current == mUsed.end() || current->first > last)
+            --current;
+
+        if (current->second < first)
+            return;
+
+        if (current->first >= first)
+        {
+            const GLuint lastExisting = current->second;
+            mUsed.erase(current);
+            if (last < lastExisting)
+            {
+                mUsed.insert(std::make_pair(last + 1u, lastExisting));
+            }
+        }
+        else if (current->second <= last)
+        {
+            current->second = first - 1u;
+        }
+        else
+        {
+            ASSERT(current->first < first && current->second > last);
+            const GLuint lastExisting = current->second;
+            current->second = first - 1u;
+            mUsed.insert(std::make_pair(last + 1u, lastExisting));
+        }
+    }
+}
+
+bool HandleRangeAllocator::isUsed(GLuint handle) const
+{
+    if (handle == kInvalidHandle)
+        return false;
+
+    auto current = mUsed.lower_bound(handle);
+    if (current != mUsed.end())
+    {
+        if (current->first == handle)
+            return true;
+    }
+    --current;
+    return current->second >= handle;
+}
+
+}  // namespace gl
\ No newline at end of file