gpu/command_buffer/common/id_allocator.cc

   1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // This file contains the implementation of IdAllocator.
   6
   7 #include "gpu/command_buffer/common/id_allocator.h"
   8
   9 #include <limits>
  10 #include "base/logging.h"
  11
  12 namespace gpu {
  13
  14 IdAllocator::IdAllocator() {
  15   COMPILE_ASSERT(kInvalidResource == 0u, invalid_resource_is_not_zero);
  16   // Simplify the code by making sure that lower_bound(id) never
  17   // returns the beginning of the map, if id is valid (eg !=
  18   // kInvalidResource).
  19   used_ids_.insert(std::make_pair(0u, 0u));
  20 }
  21
  22 IdAllocator::~IdAllocator() {}
  23
  24 ResourceId IdAllocator::AllocateID() {
  25   return AllocateIDRange(1u);
  26 }
  27
  28 ResourceId IdAllocator::AllocateIDAtOrAbove(ResourceId desired_id) {
  29   if (desired_id == 0u || desired_id == 1u) {
  30     return AllocateIDRange(1u);
  31   }
  32
  33   ResourceIdRangeMap::iterator current = used_ids_.lower_bound(desired_id);
  34   ResourceIdRangeMap::iterator next = current;
  35   if (current == used_ids_.end() || current->first > desired_id) {
  36     current--;
  37   } else {
  38     next++;
  39   }
  40
  41   ResourceId first_id = current->first;
  42   ResourceId last_id = current->second;
  43
  44   DCHECK(desired_id >= first_id);
  45
  46   if (desired_id - 1u <= last_id) {
  47     // Append to current range.
  48     last_id++;
  49     if (last_id == 0) {
  50       // The increment overflowed.
  51       return AllocateIDRange(1u);
  52     }
  53
  54     current->second = last_id;
  55
  56     if (next != used_ids_.end() && next->first - 1u == last_id) {
  57       // Merge with next range.
  58       current->second = next->second;
  59       used_ids_.erase(next);
  60     }
  61     return last_id;
  62   } else if (next != used_ids_.end() && next->first - 1u == desired_id) {
  63     // Prepend to next range.
  64     ResourceId last_existing_id = next->second;
  65     used_ids_.erase(next);
  66     used_ids_.insert(std::make_pair(desired_id, last_existing_id));
  67     return desired_id;
  68   }
  69   used_ids_.insert(std::make_pair(desired_id, desired_id));
  70   return desired_id;
  71 }
  72
  73 ResourceId IdAllocator::AllocateIDRange(uint32_t range) {
  74   DCHECK(range > 0u);
  75
  76   ResourceIdRangeMap::iterator current = used_ids_.begin();
  77   ResourceIdRangeMap::iterator next = current;
  78
  79   while (++next != used_ids_.end()) {
  80     if (next->first - current->second > range) {
  81       break;
  82     }
  83     current = next;
  84   }
  85
  86   ResourceId first_id = current->second + 1u;
  87   ResourceId last_id = first_id + range - 1u;
  88
  89   if (first_id == 0u || last_id < first_id) {
  90     return kInvalidResource;
  91   }
  92
  93   current->second = last_id;
  94
  95   if (next != used_ids_.end() && next->first - 1u == last_id) {
  96     // Merge with next range.
  97     current->second = next->second;
  98     used_ids_.erase(next);
  99   }
 100
 101   return first_id;
 102 }
 103
 104 bool IdAllocator::MarkAsUsed(ResourceId id) {
 105   DCHECK(id);
 106   ResourceIdRangeMap::iterator current = used_ids_.lower_bound(id);
 107   if (current != used_ids_.end() && current->first == id) {
 108     return false;
 109   }
 110
 111   ResourceIdRangeMap::iterator next = current;
 112   --current;
 113
 114   if (current->second >= id) {
 115     return false;
 116   }
 117
 118   DCHECK(current->first < id && current->second < id);
 119
 120   if (current->second + 1u == id) {
 121     // Append to current range.
 122     current->second = id;
 123     if (next != used_ids_.end() && next->first - 1u == id) {
 124       // Merge with next range.
 125       current->second = next->second;
 126       used_ids_.erase(next);
 127     }
 128     return true;
 129   } else if (next != used_ids_.end() && next->first - 1u == id) {
 130     // Prepend to next range.
 131     ResourceId last_existing_id = next->second;
 132     used_ids_.erase(next);
 133     used_ids_.insert(std::make_pair(id, last_existing_id));
 134     return true;
 135   }
 136
 137   used_ids_.insert(std::make_pair(id, id));
 138   return true;
 139 }
 140
 141 void IdAllocator::FreeID(ResourceId id) {
 142   FreeIDRange(id, 1u);
 143 }
 144
 145 void IdAllocator::FreeIDRange(ResourceId first_id, uint32 range) {
 146   COMPILE_ASSERT(kInvalidResource == 0u, invalid_resource_is_not_zero);
 147
 148   if (range == 0u || (first_id == 0u && range == 1u)) {
 149     return;
 150   }
 151
 152   if (first_id == 0u) {
 153     first_id++;
 154     range--;
 155   }
 156
 157   ResourceId last_id = first_id + range - 1u;
 158   if (last_id < first_id) {
 159     last_id = std::numeric_limits<ResourceId>::max();
 160   }
 161
 162   while (true) {
 163     ResourceIdRangeMap::iterator current = used_ids_.lower_bound(last_id);
 164     if (current == used_ids_.end() || current->first > last_id) {
 165       --current;
 166     }
 167
 168     if (current->second < first_id) {
 169       return;
 170     }
 171
 172     if (current->first >= first_id) {
 173       ResourceId last_existing_id = current->second;
 174       used_ids_.erase(current);
 175       if (last_id < last_existing_id) {
 176         used_ids_.insert(std::make_pair(last_id + 1u, last_existing_id));
 177       }
 178     } else if (current->second <= last_id) {
 179       current->second = first_id - 1u;
 180     } else {
 181       DCHECK(current->first < first_id && current->second > last_id);
 182       ResourceId last_existing_id = current->second;
 183       current->second = first_id - 1u;
 184       used_ids_.insert(std::make_pair(last_id + 1u, last_existing_id));
 185     }
 186   }
 187 }
 188
 189 bool IdAllocator::InUse(ResourceId id) const {
 190   if (id == kInvalidResource) {
 191     return false;
 192   }
 193
 194   ResourceIdRangeMap::const_iterator current = used_ids_.lower_bound(id);
 195   if (current != used_ids_.end()) {
 196     if (current->first == id) {
 197       return true;
 198     }
 199   }
 200
 201   --current;
 202   return current->second >= id;
 203 }
 204
 205 }  // namespace gpu