Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(163)

Unified Diff: gpu/command_buffer/common/id_allocator.cc

Issue 988693005: Chromium roll (https://codereview.chromium.org/976353002) (Closed) Base URL: https://github.com/domokit/mojo.git@master
Patch Set: fixed bad android build patch Created 5 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « gpu/command_buffer/common/id_allocator.h ('k') | gpu/command_buffer/common/id_allocator_test.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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
« no previous file with comments | « gpu/command_buffer/common/id_allocator.h ('k') | gpu/command_buffer/common/id_allocator_test.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698