command_buffer: Implement IdAllocator by recording ranges

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 <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();
-    }
-  }
-  MarkAsUsed(id);
-  return 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();
-    }
-  }
-  MarkAsUsed(id);
-  return id;
+    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;
+  }
+  used_ids_.insert(std::make_pair(desired_id, desired_id));
+  return desired_id;
+}
+
+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;
+  }
+
+  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);
+  }
+}
+
+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));
+    }
   }
 }
 
 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;
+  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;
+    }
+  }
+
+  --current;
+  return current->second >= id;
 }
 
 }  // namespace gpu