src/type3_AndroidCloud/anbox-master/external/android-emugl/shared/emugl/common/unique_integer_map.h

   1 // Copyright (C) 2014 The Android Open Source Project
   2 //
   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
   6 //
   7 // http://www.apache.org/licenses/LICENSE-2.0
   8 //
   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.
  14
  15 #ifndef EMUGL_COMMON_UNIQUE_INTEGER_MAP_H
  16 #define EMUGL_COMMON_UNIQUE_INTEGER_MAP_H
  17
  18 #include "emugl/common/pod_vector.h"
  19
  20 #include <stdint.h>
  21
  22 namespace emugl {
  23
  24 // Helper template class that implements a bi-directional mapping between
  25 // two integer types |A| and |B|. More specifically:
  26 //
  27 // - The map allocates values of type |B| when a key of type |A| is entered
  28 //   in the map.
  29 //
  30 // - keys and values cannot be 0, which is reserved (i.e. means 'invalid').
  31 //
  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 {
  36 public:
  37     UniqueIntegerMap() : mForwardPairs(), mBackwardPairs() {}
  38     ~UniqueIntegerMap() {}
  39
  40     // Return true iff the map is empty.
  41     const bool empty() const { return mForwardPairs.empty(); }
  42
  43     // Return the number of (key,value) pairs in the map.
  44     size_t size() const { return mForwardPairs.size(); }
  45
  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;
  49
  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;
  53
  54     // Add |key| to the map and return an automatically-allocated
  55     // unique value for it. Return 0 if |key| is 0.
  56     B add(const A key);
  57
  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);
  61
  62 private:
  63     typedef struct {
  64         A first;
  65         B second;
  66     } ForwardPair;
  67
  68     typedef struct {
  69         B first;
  70         A second;
  71     } BackwardPair;
  72
  73     size_t findKeyIndexPlusOne(const A key) const;
  74     size_t findValueIndexPlusOne(const B value) const;
  75
  76     B allocValue();
  77     void freeValue(B value);
  78
  79     PodVector<ForwardPair> mForwardPairs;
  80     PodVector<BackwardPair> mBackwardPairs;
  81
  82     B mLastValue;
  83     PodVector<B> mFreeValues;
  84 };
  85
  86 template <typename A, typename B>
  87 B UniqueIntegerMap<A,B>::find(const A key) const {
  88     size_t keyIndex = findKeyIndexPlusOne(key);
  89     if (!keyIndex) {
  90         return 0;
  91     }
  92     return mForwardPairs[keyIndex - 1U].second;
  93 }
  94
  95 template <typename A, typename B>
  96 A UniqueIntegerMap<A,B>::findKeyFor(const B value) const {
  97     size_t valueIndex = findValueIndexPlusOne(value);
  98     if (!valueIndex) {
  99         return 0;
 100     }
 101     return mBackwardPairs[valueIndex - 1U].second;
 102 }
 103
 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.
 108     size_t min = 0;
 109     size_t max = mForwardPairs.size();
 110     while (min < max) {
 111         size_t mid = min + ((max - min) >> 1);
 112         A midKey = mForwardPairs[mid].first;
 113         if (midKey < key) {
 114             min = mid + 1U;
 115         } else if (midKey > key) {
 116             max = mid;
 117         } else {
 118             // Already in the set.
 119             return 0;
 120         }
 121     }
 122
 123     // Generate new unique value
 124     B value = allocValue();
 125
 126     ForwardPair* pair = mForwardPairs.emplace(min);
 127     pair->first = key;
 128     pair->second = value;
 129
 130     // Binary search to find proper insertion point for the value.
 131     min = 0;
 132     max = mBackwardPairs.size();
 133     while (min < max) {
 134         size_t mid = min + ((max - min) >> 1);
 135         B midValue = mBackwardPairs[mid].first;
 136         if (midValue < value) {
 137             min = mid + 1U;
 138         } else {
 139             max = mid;
 140         }
 141     }
 142
 143     BackwardPair* backPair = mBackwardPairs.emplace(min);
 144     backPair->first = value;
 145     backPair->second = key;
 146
 147     return value;
 148 }
 149
 150 template <typename A, typename B>
 151 void UniqueIntegerMap<A,B>::del(const A key) {
 152     size_t keyIndex = findKeyIndexPlusOne(key);
 153     if (!keyIndex) {
 154         return;
 155     }
 156     B value = mForwardPairs[keyIndex - 1U].second;
 157     size_t valueIndex = findValueIndexPlusOne(value);
 158     mForwardPairs.remove(keyIndex - 1U);
 159     mBackwardPairs.remove(valueIndex - 1U);
 160     freeValue(value);
 161 }
 162
 163 template <typename A, typename B>
 164 size_t UniqueIntegerMap<A,B>::findKeyIndexPlusOne(const A key) const {
 165     // Binary search in forward pair array.
 166     size_t min = 0;
 167     size_t max = mForwardPairs.size();
 168     while (min < max) {
 169         size_t mid = min + ((max - min) >> 1);
 170         A midKey = mForwardPairs[mid].first;
 171         if (midKey < key) {
 172             min = mid + 1U;
 173         } else if (midKey > key) {
 174             max = mid;
 175         } else {
 176             return mid + 1U;
 177         }
 178     }
 179     return 0U;
 180 }
 181
 182 template <typename A, typename B>
 183 size_t UniqueIntegerMap<A,B>::findValueIndexPlusOne(const B value) const {
 184     // Binary search in revere pair array.
 185     size_t min = 0;
 186     size_t max = mBackwardPairs.size();
 187     while (min < max) {
 188         size_t mid = min + ((max - min) >> 1);
 189         B midValue = mBackwardPairs[mid].first;
 190         if (midValue < value) {
 191             min = mid + 1U;
 192         } else if (midValue > value) {
 193             max = mid;
 194         } else {
 195             return mid + 1U;
 196         }
 197     }
 198     return 0U;
 199 }
 200
 201 template <typename A, typename B>
 202 B UniqueIntegerMap<A,B>::allocValue() {
 203     if (!mFreeValues.empty()) {
 204         B result = mFreeValues[0];
 205         mFreeValues.pop();
 206         return result;
 207     }
 208     return ++mLastValue;
 209 }
 210
 211 template <typename A, typename B>
 212 void UniqueIntegerMap<A,B>::freeValue(B value) {
 213     if (!value) {
 214         return;
 215     }
 216     if (value == mLastValue) {
 217         mLastValue--;
 218         return;
 219     }
 220     mFreeValues.append(value);
 221 }
 222
 223 }  // namespace emugl
 224
 225 #endif  // EMUGL_COMMON_INTEGER_MAP_H