1 // Copyright (C) 2014 The Android Open Source Project
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
7 // http://www.apache.org/licenses/LICENSE-2.0
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
15 #ifndef EMUGL_COMMON_UNIQUE_INTEGER_MAP_H
16 #define EMUGL_COMMON_UNIQUE_INTEGER_MAP_H
18 #include "emugl/common/pod_vector.h"
24 // Helper template class that implements a bi-directional mapping between
25 // two integer types |A| and |B|. More specifically:
27 // - The map allocates values of type |B| when a key of type |A| is entered
30 // - keys and values cannot be 0, which is reserved (i.e. means 'invalid').
32 // This is used in EmuGL to map liberal 'void*' values (e.g. EGLimages ones)
33 // to unique 32-bit IDs that can be written to / read from the wire protocol.
34 template <typename A, typename B>
35 class UniqueIntegerMap {
37 UniqueIntegerMap() : mForwardPairs(), mBackwardPairs() {}
38 ~UniqueIntegerMap() {}
40 // Return true iff the map is empty.
41 const bool empty() const { return mForwardPairs.empty(); }
43 // Return the number of (key,value) pairs in the map.
44 size_t size() const { return mForwardPairs.size(); }
46 // Find the value associated with |key| in the map.
47 // Returns 0 in case of failure, or if |key| is 0.
48 B find(const A key) const;
50 // Find the key associated with a given |value| in the map.
51 // Returns 0 if |value| is 0, or in case of failure.
52 A findKeyFor(const B value) const;
54 // Add |key| to the map and return an automatically-allocated
55 // unique value for it. Return 0 if |key| is 0.
58 // Delete the entry associated with a given |key|. The
59 // corresponding value may be recycled by future calls to add().
60 void del(const A key);
73 size_t findKeyIndexPlusOne(const A key) const;
74 size_t findValueIndexPlusOne(const B value) const;
77 void freeValue(B value);
79 PodVector<ForwardPair> mForwardPairs;
80 PodVector<BackwardPair> mBackwardPairs;
83 PodVector<B> mFreeValues;
86 template <typename A, typename B>
87 B UniqueIntegerMap<A,B>::find(const A key) const {
88 size_t keyIndex = findKeyIndexPlusOne(key);
92 return mForwardPairs[keyIndex - 1U].second;
95 template <typename A, typename B>
96 A UniqueIntegerMap<A,B>::findKeyFor(const B value) const {
97 size_t valueIndex = findValueIndexPlusOne(value);
101 return mBackwardPairs[valueIndex - 1U].second;
104 template <typename A, typename B>
105 B UniqueIntegerMap<A,B>::add(const A key) {
106 // Binary search to find the proper insertion point for the key.
107 // Also checks that the key isn't already in the set.
109 size_t max = mForwardPairs.size();
111 size_t mid = min + ((max - min) >> 1);
112 A midKey = mForwardPairs[mid].first;
115 } else if (midKey > key) {
118 // Already in the set.
123 // Generate new unique value
124 B value = allocValue();
126 ForwardPair* pair = mForwardPairs.emplace(min);
128 pair->second = value;
130 // Binary search to find proper insertion point for the value.
132 max = mBackwardPairs.size();
134 size_t mid = min + ((max - min) >> 1);
135 B midValue = mBackwardPairs[mid].first;
136 if (midValue < value) {
143 BackwardPair* backPair = mBackwardPairs.emplace(min);
144 backPair->first = value;
145 backPair->second = key;
150 template <typename A, typename B>
151 void UniqueIntegerMap<A,B>::del(const A key) {
152 size_t keyIndex = findKeyIndexPlusOne(key);
156 B value = mForwardPairs[keyIndex - 1U].second;
157 size_t valueIndex = findValueIndexPlusOne(value);
158 mForwardPairs.remove(keyIndex - 1U);
159 mBackwardPairs.remove(valueIndex - 1U);
163 template <typename A, typename B>
164 size_t UniqueIntegerMap<A,B>::findKeyIndexPlusOne(const A key) const {
165 // Binary search in forward pair array.
167 size_t max = mForwardPairs.size();
169 size_t mid = min + ((max - min) >> 1);
170 A midKey = mForwardPairs[mid].first;
173 } else if (midKey > key) {
182 template <typename A, typename B>
183 size_t UniqueIntegerMap<A,B>::findValueIndexPlusOne(const B value) const {
184 // Binary search in revere pair array.
186 size_t max = mBackwardPairs.size();
188 size_t mid = min + ((max - min) >> 1);
189 B midValue = mBackwardPairs[mid].first;
190 if (midValue < value) {
192 } else if (midValue > value) {
201 template <typename A, typename B>
202 B UniqueIntegerMap<A,B>::allocValue() {
203 if (!mFreeValues.empty()) {
204 B result = mFreeValues[0];
211 template <typename A, typename B>
212 void UniqueIntegerMap<A,B>::freeValue(B value) {
216 if (value == mLastValue) {
220 mFreeValues.append(value);
225 #endif // EMUGL_COMMON_INTEGER_MAP_H