command_buffer: Implement path rendering functions for CHROMIUM_path_rendering

gpu/command_buffer/common/id_allocator.cc

 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // This file contains the implementation of IdAllocator.
 
 #include "gpu/command_buffer/common/id_allocator.h"
 
 #include "base/logging.h"
 
@@ skipping 30 matching lines @@
     id = LastUsedId() + 1;
     if (!id) {
       // We wrapped around to 0.
       id = FindFirstUnusedId();
     }
   }
   MarkAsUsed(id);
   return id;
 }
 
+ResourceId IdAllocator::AllocateIDRange(uint32_t range) {
+  DCHECK(range > 0);
+  if (range == 1) {
+    return AllocateID();
+  }
+
+  ResourceId first_id = kInvalidResource;
+
+  {
+    // Try to re-use ids from free_ids.
+    ResourceIdSet::const_iterator iter = free_ids_.begin();
+    ResourceIdSet::const_iterator end = free_ids_.end();
+    const ResourceIdSet::size_type size = free_ids_.size();
+    if (iter != end && size >= range) {
+      ResourceId first = *iter;
+      ResourceIdSet::size_type needed_size = range;
+      ResourceId prev = first;
+      ++iter;
+      for (; iter != end && size >= needed_size; ++iter) {
+        if (prev + 1 == *iter) {
+          if (first + range - 1 == *iter) {
+            first_id = first;
+            break;
+          }
+        } else {
+          needed_size += prev - first + 1;
+          first = *iter;
+        }
+        prev = *iter;
+      }
+    }
+  }
+
+  if (first_id == kInvalidResource) {
+    // Allocate after the last id.
+    ResourceId first = LastUsedId() + 1;
+    if (first != 0) {
+      ResourceId last = first + range - 1;
+      if (first < last) {
+        first_id = first;
+      }
+    }
+  }
+
+  if (first_id == kInvalidResource) {
+    // Scan the gaps between used ids.
+    ResourceId prev = 0;
+    for (auto id : used_ids_) {
+      if (id - prev > range) {
+        first_id = prev + 1;
+        break;
+      }
+      prev = id;
+    }
+  }
+
+  if (first_id != kInvalidResource) {
+    for (uint32 ii = 0; ii < range; ++ii) {
+      MarkAsUsed(first_id + ii);
+    }
+  }
+
+  return first_id;
+}
+
 bool IdAllocator::MarkAsUsed(ResourceId id) {
   DCHECK(id);
   free_ids_.erase(id);
   std::pair<ResourceIdSet::iterator, bool> result = used_ids_.insert(id);
   return result.second;
 }
 
 void IdAllocator::FreeID(ResourceId id) {
   if (id) {
     used_ids_.erase(id);
     free_ids_.insert(id);
   }
 }
 
+void IdAllocator::FreeIDRange(ResourceId first_id, uint32 range) {
+  for (uint32 ii = 0; ii < range; ++ii) {
+    FreeID(first_id + ii);
+  }
+}
+
 bool IdAllocator::InUse(ResourceId id) const {
   return id == kInvalidResource || used_ids_.find(id) != used_ids_.end();
 }
 
 ResourceId IdAllocator::LastUsedId() const {
   if (used_ids_.empty()) {
     return 0u;
   } else {
     return *used_ids_.rbegin();
   }
 }
 
 ResourceId IdAllocator::FindFirstUnusedId() const {
   ResourceId id = 1;
   for (ResourceIdSet::const_iterator it = used_ids_.begin();
        it != used_ids_.end(); ++it) {
     if ((*it) != id) {
       return id;
     }
     ++id;
   }
   return id;
 }
 
 }  // namespace gpu