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 "base/logging.h"
10
11namespace gpu {
12
13IdAllocatorInterface::~IdAllocatorInterface() {
14}
15
16IdAllocator::IdAllocator() {}
17
18IdAllocator::~IdAllocator() {}
19
20ResourceId IdAllocator::AllocateID() {
21  ResourceId id;
22  ResourceIdSet::iterator iter = free_ids_.begin();
23  if (iter != free_ids_.end()) {
24    id = *iter;
25  } else {
26    id = LastUsedId() + 1;
27    if (!id) {
28      // We wrapped around to 0.
29      id = FindFirstUnusedId();
30    }
31  }
32  MarkAsUsed(id);
33  return id;
34}
35
36ResourceId IdAllocator::AllocateIDAtOrAbove(ResourceId desired_id) {
37  ResourceId id;
38  ResourceIdSet::iterator iter = free_ids_.lower_bound(desired_id);
39  if (iter != free_ids_.end()) {
40    id = *iter;
41  } else if (LastUsedId() < desired_id) {
42    id = desired_id;
43  } else {
44    id = LastUsedId() + 1;
45    if (!id) {
46      // We wrapped around to 0.
47      id = FindFirstUnusedId();
48    }
49  }
50  MarkAsUsed(id);
51  return id;
52}
53
54bool IdAllocator::MarkAsUsed(ResourceId id) {
55  DCHECK(id);
56  free_ids_.erase(id);
57  std::pair<ResourceIdSet::iterator, bool> result = used_ids_.insert(id);
58  return result.second;
59}
60
61void IdAllocator::FreeID(ResourceId id) {
62  if (id) {
63    used_ids_.erase(id);
64    free_ids_.insert(id);
65  }
66}
67
68bool IdAllocator::InUse(ResourceId id) const {
69  return id == kInvalidResource || used_ids_.find(id) != used_ids_.end();
70}
71
72ResourceId IdAllocator::LastUsedId() const {
73  if (used_ids_.empty()) {
74    return 0u;
75  } else {
76    return *used_ids_.rbegin();
77  }
78}
79
80ResourceId IdAllocator::FindFirstUnusedId() const {
81  ResourceId id = 1;
82  for (ResourceIdSet::const_iterator it = used_ids_.begin();
83       it != used_ids_.end(); ++it) {
84    if ((*it) != id) {
85      return id;
86    }
87    ++id;
88  }
89  return id;
90}
91
92NonReusedIdAllocator::NonReusedIdAllocator() : last_id_(0) {
93}
94
95NonReusedIdAllocator::~NonReusedIdAllocator() {
96}
97
98ResourceId NonReusedIdAllocator::AllocateID() {
99  return ++last_id_;
100}
101
102ResourceId NonReusedIdAllocator::AllocateIDAtOrAbove(ResourceId desired_id) {
103  if (desired_id > last_id_)
104    last_id_ = desired_id;
105
106  return ++last_id_;
107}
108
109bool NonReusedIdAllocator::MarkAsUsed(ResourceId id) {
110  NOTREACHED();
111  return false;
112}
113
114void NonReusedIdAllocator::FreeID(ResourceId id) {
115}
116
117bool NonReusedIdAllocator::InUse(ResourceId id) const {
118  NOTREACHED();
119  return false;
120}
121
122}  // namespace gpu
123