command_buffer: Implement IdAllocator by recording ranges in an AVL tree

gpu/command_buffer/common/id_allocator.h

Index: gpu/command_buffer/common/id_allocator.h
diff --git a/gpu/command_buffer/common/id_allocator.h b/gpu/command_buffer/common/id_allocator.h
index 7f83a9c6691caefb911d15f4387c7619f127cd9a..a1a132d16ca289bb08b9a3c251fc2c1eff56b690 100644
--- a/gpu/command_buffer/common/id_allocator.h
+++ b/gpu/command_buffer/common/id_allocator.h
@@ -9,7 +9,7 @@
 
 #include <stdint.h>
 
-#include <set>
+#include <map>
 #include <utility>
 
 #include "base/compiler_specific.h"
@@ -54,17 +54,27 @@ class GPU_EXPORT IdAllocator {
   bool InUse(ResourceId id) const;
 
  private:
-  // TODO(gman): This would work much better with ranges or a hash table.
-  typedef std::set<ResourceId> ResourceIdSet;
-
-  // The highest ID on the used list.
-  ResourceId LastUsedId() const;
-
-  // Lowest ID that isn't on the used list. This is slow, use as a last resort.
-  ResourceId FindFirstUnusedId() const;
-
-  ResourceIdSet used_ids_;
-  ResourceIdSet free_ids_;
+  struct Node;
+  static int GetHeight(Node*);
+  static int GetBalance(Node*);
+  static void UpdateHeight(Node*);
+  static Node* RotateLeft(Node* node);
+  static Node* RotateRight(Node* node);
+  static Node* Balance(Node*);
+  static Node* ReplaceMax(Node* to_replace, Node* max_subtree);
+  static Node* Delete(Node*);
+  static Node* Insert(ResourceId min, ResourceId max, Node* pos);
+  static Node* AddRange(uint32_t range,
+                        ResourceId* first_id_out,
+                        ResourceId first_id_min,
+                        ResourceId first_id_max,
+                        Node* pos,
+                        Node* left_limit,
+                        Node* right_limit);
+  static Node* RemoveRange(ResourceId first_id, ResourceId last_id, Node* pos);
+  static void Destroy(Node* pos);
+
+  Node* root_;
 
   DISALLOW_COPY_AND_ASSIGN(IdAllocator);
 };