command_buffer: Implement IdAllocator by recording ranges in an AVL tree

gpu/command_buffer/common/id_allocator.h

 // Copyright (c) 2012 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 definition of the IdAllocator class.
 
 #ifndef GPU_COMMAND_BUFFER_CLIENT_ID_ALLOCATOR_H_
 #define GPU_COMMAND_BUFFER_CLIENT_ID_ALLOCATOR_H_
 
 #include <stdint.h>
 
-#include <set>
+#include <map>
 #include <utility>
 
 #include "base/compiler_specific.h"
 #include "base/macros.h"
 #include "gpu/gpu_export.h"
 
 namespace gpu {
 
 // A resource ID, key to the resource maps.
 typedef uint32_t ResourceId;
@@ skipping 24 matching lines @@
   // Frees a resource ID.
   void FreeID(ResourceId id);
 
   // Frees a |range| amount of contiguous ids, starting from |first_id|.
   void FreeIDRange(ResourceId first_id, uint32_t range);
 
   // Checks whether or not a resource ID is in use.
   bool InUse(ResourceId id) const;
 
  private:
-  // TODO(gman): This would work much better with ranges or a hash table.
-  typedef std::set<ResourceId> ResourceIdSet;
+  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);
 
-  // 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_;
+  Node* root_;
 
   DISALLOW_COPY_AND_ASSIGN(IdAllocator);
 };
 
 }  // namespace gpu
 
 #endif  // GPU_COMMAND_BUFFER_CLIENT_ID_ALLOCATOR_H_