Index: gpu/command_buffer/common/id_allocator.cc |
diff --git a/gpu/command_buffer/common/id_allocator.cc b/gpu/command_buffer/common/id_allocator.cc |
index 507b14e9af19bfdd298f5b93362dc099f428c5f2..eccb4681df72bced7aa00d1ac01d59931b0429d1 100644 |
--- a/gpu/command_buffer/common/id_allocator.cc |
+++ b/gpu/command_buffer/common/id_allocator.cc |
@@ -6,84 +6,200 @@ |
#include "gpu/command_buffer/common/id_allocator.h" |
+#include <limits> |
#include "base/logging.h" |
namespace gpu { |
-IdAllocator::IdAllocator() {} |
+IdAllocator::IdAllocator() { |
+ COMPILE_ASSERT(kInvalidResource == 0u, invalid_resource_is_not_zero); |
+ // Simplify the code by making sure that lower_bound(id) never |
+ // returns the beginning of the map, if id is valid (eg != |
+ // kInvalidResource). |
+ used_ids_.insert(std::make_pair(0u, 0u)); |
+} |
IdAllocator::~IdAllocator() {} |
ResourceId IdAllocator::AllocateID() { |
- ResourceId id; |
- ResourceIdSet::iterator iter = free_ids_.begin(); |
- if (iter != free_ids_.end()) { |
- id = *iter; |
+ return AllocateIDRange(1u); |
+} |
+ |
+ResourceId IdAllocator::AllocateIDAtOrAbove(ResourceId desired_id) { |
+ if (desired_id == 0u || desired_id == 1u) { |
+ return AllocateIDRange(1u); |
+ } |
+ |
+ ResourceIdRangeMap::iterator current = used_ids_.lower_bound(desired_id); |
+ ResourceIdRangeMap::iterator next = current; |
+ if (current == used_ids_.end() || current->first > desired_id) { |
+ current--; |
} else { |
- id = LastUsedId() + 1; |
- if (!id) { |
- // We wrapped around to 0. |
- id = FindFirstUnusedId(); |
+ next++; |
+ } |
+ |
+ ResourceId first_id = current->first; |
+ ResourceId last_id = current->second; |
+ |
+ DCHECK(desired_id >= first_id); |
+ |
+ if (desired_id - 1u <= last_id) { |
+ // Append to current range. |
+ last_id++; |
+ if (last_id == 0) { |
+ // The increment overflowed. |
+ return AllocateIDRange(1u); |
+ } |
+ |
+ current->second = last_id; |
+ |
+ if (next != used_ids_.end() && next->first - 1u == last_id) { |
+ // Merge with next range. |
+ current->second = next->second; |
+ used_ids_.erase(next); |
} |
+ return last_id; |
+ } else if (next != used_ids_.end() && next->first - 1u == desired_id) { |
+ // Prepend to next range. |
+ ResourceId last_existing_id = next->second; |
+ used_ids_.erase(next); |
+ used_ids_.insert(std::make_pair(desired_id, last_existing_id)); |
+ return desired_id; |
} |
- MarkAsUsed(id); |
- return id; |
+ used_ids_.insert(std::make_pair(desired_id, desired_id)); |
+ return desired_id; |
} |
-ResourceId IdAllocator::AllocateIDAtOrAbove(ResourceId desired_id) { |
- ResourceId id; |
- ResourceIdSet::iterator iter = free_ids_.lower_bound(desired_id); |
- if (iter != free_ids_.end()) { |
- id = *iter; |
- } else if (LastUsedId() < desired_id) { |
- id = desired_id; |
- } else { |
- id = LastUsedId() + 1; |
- if (!id) { |
- // We wrapped around to 0. |
- id = FindFirstUnusedId(); |
+ResourceId IdAllocator::AllocateIDRange(uint32_t range) { |
+ DCHECK(range > 0u); |
+ |
+ ResourceIdRangeMap::iterator current = used_ids_.begin(); |
+ ResourceIdRangeMap::iterator next = current; |
+ |
+ while (++next != used_ids_.end()) { |
+ if (next->first - current->second > range) { |
+ break; |
} |
+ current = next; |
+ } |
+ |
+ ResourceId first_id = current->second + 1u; |
+ ResourceId last_id = first_id + range - 1u; |
+ |
+ if (first_id == 0u || last_id < first_id) { |
+ return kInvalidResource; |
} |
- MarkAsUsed(id); |
- return id; |
+ |
+ current->second = last_id; |
+ |
+ if (next != used_ids_.end() && next->first - 1u == last_id) { |
+ // Merge with next range. |
+ current->second = next->second; |
+ used_ids_.erase(next); |
+ } |
+ |
+ 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; |
-} |
+ ResourceIdRangeMap::iterator current = used_ids_.lower_bound(id); |
+ if (current != used_ids_.end() && current->first == id) { |
+ return false; |
+ } |
-void IdAllocator::FreeID(ResourceId id) { |
- if (id) { |
- used_ids_.erase(id); |
- free_ids_.insert(id); |
+ ResourceIdRangeMap::iterator next = current; |
+ --current; |
+ |
+ if (current->second >= id) { |
+ return false; |
} |
+ |
+ DCHECK(current->first < id && current->second < id); |
+ |
+ if (current->second + 1u == id) { |
+ // Append to current range. |
+ current->second = id; |
+ if (next != used_ids_.end() && next->first - 1u == id) { |
+ // Merge with next range. |
+ current->second = next->second; |
+ used_ids_.erase(next); |
+ } |
+ return true; |
+ } else if (next != used_ids_.end() && next->first - 1u == id) { |
+ // Prepend to next range. |
+ ResourceId last_existing_id = next->second; |
+ used_ids_.erase(next); |
+ used_ids_.insert(std::make_pair(id, last_existing_id)); |
+ return true; |
+ } |
+ |
+ used_ids_.insert(std::make_pair(id, id)); |
+ return true; |
} |
-bool IdAllocator::InUse(ResourceId id) const { |
- return id == kInvalidResource || used_ids_.find(id) != used_ids_.end(); |
+void IdAllocator::FreeID(ResourceId id) { |
+ FreeIDRange(id, 1u); |
} |
-ResourceId IdAllocator::LastUsedId() const { |
- if (used_ids_.empty()) { |
- return 0u; |
- } else { |
- return *used_ids_.rbegin(); |
+void IdAllocator::FreeIDRange(ResourceId first_id, uint32 range) { |
+ COMPILE_ASSERT(kInvalidResource == 0u, invalid_resource_is_not_zero); |
+ |
+ if (range == 0u || (first_id == 0u && range == 1u)) { |
+ return; |
+ } |
+ |
+ if (first_id == 0u) { |
+ first_id++; |
+ range--; |
+ } |
+ |
+ ResourceId last_id = first_id + range - 1u; |
+ if (last_id < first_id) { |
+ last_id = std::numeric_limits<ResourceId>::max(); |
+ } |
+ |
+ while (true) { |
+ ResourceIdRangeMap::iterator current = used_ids_.lower_bound(last_id); |
+ if (current == used_ids_.end() || current->first > last_id) { |
+ --current; |
+ } |
+ |
+ if (current->second < first_id) { |
+ return; |
+ } |
+ |
+ if (current->first >= first_id) { |
+ ResourceId last_existing_id = current->second; |
+ used_ids_.erase(current); |
+ if (last_id < last_existing_id) { |
+ used_ids_.insert(std::make_pair(last_id + 1u, last_existing_id)); |
+ } |
+ } else if (current->second <= last_id) { |
+ current->second = first_id - 1u; |
+ } else { |
+ DCHECK(current->first < first_id && current->second > last_id); |
+ ResourceId last_existing_id = current->second; |
+ current->second = first_id - 1u; |
+ used_ids_.insert(std::make_pair(last_id + 1u, last_existing_id)); |
+ } |
} |
} |
-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; |
+bool IdAllocator::InUse(ResourceId id) const { |
+ if (id == kInvalidResource) { |
+ return false; |
+ } |
+ |
+ ResourceIdRangeMap::const_iterator current = used_ids_.lower_bound(id); |
+ if (current != used_ids_.end()) { |
+ if (current->first == id) { |
+ return true; |
} |
- ++id; |
} |
- return id; |
+ |
+ --current; |
+ return current->second >= id; |
} |
} // namespace gpu |