OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // This file contains the implementation of IdAllocator. | 5 // This file contains the implementation of IdAllocator. |
6 | 6 |
7 #include "gpu/command_buffer/common/id_allocator.h" | 7 #include "gpu/command_buffer/common/id_allocator.h" |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 | 10 |
(...skipping 30 matching lines...) Expand all Loading... |
41 id = LastUsedId() + 1; | 41 id = LastUsedId() + 1; |
42 if (!id) { | 42 if (!id) { |
43 // We wrapped around to 0. | 43 // We wrapped around to 0. |
44 id = FindFirstUnusedId(); | 44 id = FindFirstUnusedId(); |
45 } | 45 } |
46 } | 46 } |
47 MarkAsUsed(id); | 47 MarkAsUsed(id); |
48 return id; | 48 return id; |
49 } | 49 } |
50 | 50 |
| 51 ResourceId IdAllocator::AllocateIDRange(uint32_t range) { |
| 52 DCHECK(range > 0); |
| 53 if (range == 1) { |
| 54 return AllocateID(); |
| 55 } |
| 56 |
| 57 ResourceId first_id = kInvalidResource; |
| 58 |
| 59 { |
| 60 // Try to re-use ids from free_ids. |
| 61 ResourceIdSet::const_iterator iter = free_ids_.begin(); |
| 62 ResourceIdSet::const_iterator end = free_ids_.end(); |
| 63 const ResourceIdSet::size_type size = free_ids_.size(); |
| 64 if (iter != end && size >= range) { |
| 65 ResourceId first = *iter; |
| 66 ResourceIdSet::size_type needed_size = range; |
| 67 ResourceId prev = first; |
| 68 ++iter; |
| 69 for (; iter != end && size >= needed_size; ++iter) { |
| 70 if (prev + 1 == *iter) { |
| 71 if (first + range - 1 == *iter) { |
| 72 first_id = first; |
| 73 break; |
| 74 } |
| 75 } else { |
| 76 needed_size += prev - first + 1; |
| 77 first = *iter; |
| 78 } |
| 79 prev = *iter; |
| 80 } |
| 81 } |
| 82 } |
| 83 |
| 84 if (first_id == kInvalidResource) { |
| 85 // Allocate after the last id. |
| 86 ResourceId first = LastUsedId() + 1; |
| 87 if (first != 0) { |
| 88 ResourceId last = first + range - 1; |
| 89 if (first < last) { |
| 90 first_id = first; |
| 91 } |
| 92 } |
| 93 } |
| 94 |
| 95 if (first_id == kInvalidResource) { |
| 96 // Scan the gaps between used ids. |
| 97 ResourceId prev = 0; |
| 98 for (auto id : used_ids_) { |
| 99 if (id - prev > range) { |
| 100 first_id = prev + 1; |
| 101 break; |
| 102 } |
| 103 prev = id; |
| 104 } |
| 105 } |
| 106 |
| 107 if (first_id != kInvalidResource) { |
| 108 for (uint32 ii = 0; ii < range; ++ii) { |
| 109 MarkAsUsed(first_id + ii); |
| 110 } |
| 111 } |
| 112 |
| 113 return first_id; |
| 114 } |
| 115 |
51 bool IdAllocator::MarkAsUsed(ResourceId id) { | 116 bool IdAllocator::MarkAsUsed(ResourceId id) { |
52 DCHECK(id); | 117 DCHECK(id); |
53 free_ids_.erase(id); | 118 free_ids_.erase(id); |
54 std::pair<ResourceIdSet::iterator, bool> result = used_ids_.insert(id); | 119 std::pair<ResourceIdSet::iterator, bool> result = used_ids_.insert(id); |
55 return result.second; | 120 return result.second; |
56 } | 121 } |
57 | 122 |
58 void IdAllocator::FreeID(ResourceId id) { | 123 void IdAllocator::FreeID(ResourceId id) { |
59 if (id) { | 124 if (id) { |
60 used_ids_.erase(id); | 125 used_ids_.erase(id); |
61 free_ids_.insert(id); | 126 free_ids_.insert(id); |
62 } | 127 } |
63 } | 128 } |
64 | 129 |
| 130 void IdAllocator::FreeIDRange(ResourceId first_id, uint32 range) { |
| 131 for (uint32 ii = 0; ii < range; ++ii) { |
| 132 FreeID(first_id + ii); |
| 133 } |
| 134 } |
| 135 |
65 bool IdAllocator::InUse(ResourceId id) const { | 136 bool IdAllocator::InUse(ResourceId id) const { |
66 return id == kInvalidResource || used_ids_.find(id) != used_ids_.end(); | 137 return id == kInvalidResource || used_ids_.find(id) != used_ids_.end(); |
67 } | 138 } |
68 | 139 |
69 ResourceId IdAllocator::LastUsedId() const { | 140 ResourceId IdAllocator::LastUsedId() const { |
70 if (used_ids_.empty()) { | 141 if (used_ids_.empty()) { |
71 return 0u; | 142 return 0u; |
72 } else { | 143 } else { |
73 return *used_ids_.rbegin(); | 144 return *used_ids_.rbegin(); |
74 } | 145 } |
75 } | 146 } |
76 | 147 |
77 ResourceId IdAllocator::FindFirstUnusedId() const { | 148 ResourceId IdAllocator::FindFirstUnusedId() const { |
78 ResourceId id = 1; | 149 ResourceId id = 1; |
79 for (ResourceIdSet::const_iterator it = used_ids_.begin(); | 150 for (ResourceIdSet::const_iterator it = used_ids_.begin(); |
80 it != used_ids_.end(); ++it) { | 151 it != used_ids_.end(); ++it) { |
81 if ((*it) != id) { | 152 if ((*it) != id) { |
82 return id; | 153 return id; |
83 } | 154 } |
84 ++id; | 155 ++id; |
85 } | 156 } |
86 return id; | 157 return id; |
87 } | 158 } |
88 | 159 |
89 } // namespace gpu | 160 } // namespace gpu |
OLD | NEW |