command_buffer: Implement IdAllocator by recording ranges

gpu/command_buffer/common/id_allocator.cc

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..2c10a8b1cff94e602ec3fa38c3e0bb9284cb15da 100644
--- a/gpu/command_buffer/common/id_allocator.cc
+++ b/gpu/command_buffer/common/id_allocator.cc
@@ -6,84 +6,201 @@
 
 #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) {
+  DCHECK(desired_id > 0u);

[David Yen, 2015/02/04 22:57:16]

Nit: Even though 0 is a invalid ID, seems like it would be appropriate to
instead give them 1 or above if they desire 0.

[Kimmo Kinnunen, 2015/02/05 08:29:33]

Done.

+  if (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;
+  }
+
+  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;
 }
 
 void IdAllocator::FreeID(ResourceId id) {
   if (id) {

[David Yen, 2015/02/04 22:57:16]

Nit: This check no longer seems necessary.

[Kimmo Kinnunen, 2015/02/05 08:29:33]

Done.

-    used_ids_.erase(id);
-    free_ids_.insert(id);
+    FreeIDRange(id, 1u);
   }
 }
 
-bool IdAllocator::InUse(ResourceId id) const {
-  return id == kInvalidResource || used_ids_.find(id) != used_ids_.end();
-}
+void IdAllocator::FreeIDRange(ResourceId first_id, uint32 range) {
+  COMPILE_ASSERT(kInvalidResource == 0u, invalid_resource_is_not_zero);
 
-ResourceId IdAllocator::LastUsedId() const {
-  if (used_ids_.empty()) {
-    return 0u;
-  } else {
-    return *used_ids_.rbegin();
+  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 {
+  DCHECK(id);

[vmiura, 2015/02/04 07:32:56]

Should we return true if (id == kInvalidResource) instead to match the old
behavior?

[Kimmo Kinnunen, 2015/02/04 08:13:08]

Whichever way you want..

The suggestion breaks the implicit API, though. As far as implicit means "least
surprise" (no valid id is allocated when allocator is newly created, no valid id
is permanent)
 
Eg: 

for any id:
  Free(id);
  expect(InUse(id) == false)

I think originally I also thought of the case where the usage pattern is:

if (InUse(id)) {
  DoOperationWithId(id);
} else {
  error("id does not exist");
}

For this pattern, check the usage in:
 GLES2Implementation::BeginQueryEXT

(Though the case could perhaps be made that instead of error, one would
frequently want to do "MarkIdUsed"...)

I think currently there's only one call-site. This call-site checks for id == 0.

[Kimmo Kinnunen, 2015/02/05 08:29:33]

So I now changed the assert into if(). However, this changes the behavior,
InUse(0) returns always false. To me it seems a bit safer. Hope this is ok?

+
+  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