command_buffer: Implement IdAllocator by recording ranges in an AVL tree

gpu/command_buffer/common/id_allocator_test.cc

Index: gpu/command_buffer/common/id_allocator_test.cc
diff --git a/gpu/command_buffer/common/id_allocator_test.cc b/gpu/command_buffer/common/id_allocator_test.cc
index e4c2140782535cca890488ac3a8a989616961c7c..2b38042d1d98091c4d425898c4a3196ebdd8a9eb 100644
--- a/gpu/command_buffer/common/id_allocator_test.cc
+++ b/gpu/command_buffer/common/id_allocator_test.cc
@@ -165,12 +165,12 @@ TEST_F(IdAllocatorTest, AllocateIDRange) {
   EXPECT_EQ(101u, id12);
 
   ResourceId id13 = allocator->AllocateIDAtOrAbove(kMaxPossibleOffset - 2u);
-  EXPECT_EQ(kMaxPossibleOffset, id13);
+  EXPECT_EQ(kMaxPossibleOffset - 2u, id13);
   ResourceId id14 = allocator->AllocateIDRange(3);
   EXPECT_EQ(201u, id14);
 }
 
-TEST_F(IdAllocatorTest, AllocateIDRangeNoWrapInRange) {
+TEST_F(IdAllocatorTest, AllocateIDRangeEndNoEffect) {
   const ResourceId kMaxPossibleOffset = ~static_cast<ResourceId>(0);
 
   IdAllocator* allocator = id_allocator();
@@ -179,7 +179,55 @@ TEST_F(IdAllocatorTest, AllocateIDRangeNoWrapInRange) {
   ResourceId id3 = allocator->AllocateIDRange(3);
   EXPECT_EQ(1u, id3);
   ResourceId id2 = allocator->AllocateIDRange(2);
-  EXPECT_EQ(kMaxPossibleOffset - 1, id2);
+  EXPECT_EQ(4u, id2);
+}
+
+TEST_F(IdAllocatorTest, AllocateFullIDRange) {
+  const uint32_t kMaxPossibleRange = ~static_cast<uint32_t>(0u);
+  const ResourceId kFreedId = 555u;
+  IdAllocator* allocator = id_allocator();
+
+  ResourceId id1 = allocator->AllocateIDRange(kMaxPossibleRange);
+  EXPECT_EQ(1u, id1);
+  ResourceId id2 = allocator->AllocateID();
+  EXPECT_EQ(0u, id2);
+  allocator->FreeID(kFreedId);
+  ResourceId id3 = allocator->AllocateID();
+  EXPECT_EQ(kFreedId, id3);
+  ResourceId id4 = allocator->AllocateID();
+  EXPECT_EQ(0u, id4);
+  allocator->FreeID(kFreedId + 1u);
+  allocator->FreeID(kFreedId + 3u);
+  allocator->FreeID(kFreedId + 2u);
+  allocator->FreeID(kFreedId + 5u);
+  allocator->FreeID(kFreedId + 4u);
+  ResourceId id5 = allocator->AllocateIDRange(5);
+  EXPECT_EQ(kFreedId + 1u, id5);
+}
+
+TEST_F(IdAllocatorTest, AllocateIDRangeNoWrapInRange) {
+  const uint32_t kMaxPossibleRange = ~static_cast<uint32_t>(0u);
+  const ResourceId kAllocId = 10u;
+  IdAllocator* allocator = id_allocator();
+
+  ResourceId id1 = allocator->AllocateIDAtOrAbove(kAllocId);
+  EXPECT_EQ(kAllocId, id1);
+  ResourceId id2 = allocator->AllocateIDRange(kMaxPossibleRange - 5u);
+  EXPECT_EQ(0u, id2);
+}
+TEST_F(IdAllocatorTest, AllocateIdMax) {
+  IdAllocator* allocator = id_allocator();
+  ResourceId id =
+      allocator->AllocateIDRange(std::numeric_limits<uint32_t>::max());
+  EXPECT_EQ(1u, id);
+  allocator->FreeIDRange(id, std::numeric_limits<uint32_t>::max() - 1u);
+  ResourceId id2 =
+      allocator->AllocateIDRange(std::numeric_limits<uint32_t>::max());
+  EXPECT_EQ(0u, id2);
+  allocator->FreeIDRange(id, std::numeric_limits<uint32_t>::max());
+  ResourceId id3 =
+      allocator->AllocateIDRange(std::numeric_limits<uint32_t>::max());
+  EXPECT_EQ(1u, id3);
 }
 
 }  // namespace gpu