src/type3_AndroidCloud/anbox-master/external/android-emugl/shared/emugl/common/id_to_object_map.cpp

   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 #include "emugl/common/id_to_object_map.h"
  16
  17 #include <stdlib.h>
  18
  19 namespace emugl {
  20
  21 namespace {
  22
  23 typedef IdToObjectMapBase::KeyType KeyType;
  24
  25 enum {
  26     kMinShift = 3,
  27     kMaxShift = 31,
  28     kMinCapacity = (1 << kMinShift),
  29     kLoadScale = 1024,
  30     kMinLoad = kLoadScale/4,    // 25% minimum load.
  31     kMaxLoad = kLoadScale*3/4,  // 75% maximum load.
  32
  33     kInvalidKey = IdToObjectMapBase::kMaxId + 1U,
  34     kTombstone = IdToObjectMapBase::kMaxId + 2U,
  35 };
  36
  37 // Return a number that indicates if the current |capacity| is appropriate
  38 // to hold |size| items in our map.
  39 // -1 -> the capacity is too small and needs to be increased.
  40 //  0 -> the capacity is ok.
  41 // +1 -> the capacity is too large and needs to be decreased.
  42 int capacityCompare(size_t shift, size_t size) {
  43     size_t capacity = 1U << shift;
  44     // Essentially, one can rewrite:
  45     //   load < minLoad
  46     // as:
  47     //   size / capacity < minLoad
  48     //   capacity * minLoad > size
  49     if (capacity * kMinLoad  > size * kLoadScale)
  50         return +1;
  51
  52     // Similarly, one can rewrite:
  53     //   load > maxLoad
  54     // as:
  55     //   size / capacity > maxLoad
  56     //   capacity * maxLoad < size
  57     if (capacity * kMaxLoad < size * kLoadScale)
  58         return -1;
  59
  60     return 0;
  61 }
  62
  63 size_t probeKeys(const KeyType* keys, size_t shift, KeyType key) {
  64     static const int kPrimes[] = {
  65     1,          /* For 1 << 0 */
  66     2,
  67     3,
  68     7,
  69     13,
  70     31,
  71     61,
  72     127,
  73     251,
  74     509,
  75     1021,
  76     2039,
  77     4093,
  78     8191,
  79     16381,
  80     32749,
  81     65521,      /* For 1 << 16 */
  82     131071,
  83     262139,
  84     524287,
  85     1048573,
  86     2097143,
  87     4194301,
  88     8388593,
  89     16777213,
  90     33554393,
  91     67108859,
  92     134217689,
  93     268435399,
  94     536870909,
  95     1073741789,
  96     2147483647  /* For 1 << 31 */
  97     };
  98
  99     size_t slot = key % kPrimes[shift];
 100     size_t step = 0;
 101     for (;;) {
 102         KeyType k = keys[slot];
 103         if (k == kInvalidKey || k == kTombstone || k == key)
 104             return slot;
 105
 106         step += 1;
 107         slot = (slot + step) & (1U << shift);
 108     }
 109 }
 110
 111 }  // namespace
 112
 113 IdToObjectMapBase::IdToObjectMapBase() :
 114         mCount(0), mShift(kMinShift) {
 115     size_t capacity = 1U << mShift;
 116     mKeys = static_cast<KeyType*>(::calloc(sizeof(mKeys[0]), capacity));
 117     mValues = static_cast<void**>(::calloc(sizeof(mValues[0]), capacity));
 118     for (size_t n = 0; n < capacity; ++n) {
 119         mKeys[n] = kInvalidKey;
 120     }
 121 }
 122
 123 IdToObjectMapBase::~IdToObjectMapBase() {
 124     mShift = 0;
 125     mCount = 0;
 126     ::free(mKeys);
 127     ::free(mValues);
 128 }
 129
 130 bool IdToObjectMapBase::contains(KeyType key) const {
 131     size_t slot = probeKeys(mKeys, mShift, key);
 132     switch (mKeys[slot]) {
 133         case kInvalidKey:
 134         case kTombstone:
 135             return false;
 136         default:
 137             ;
 138     }
 139     return true;
 140 }
 141
 142 bool IdToObjectMapBase::find(KeyType key, void** value) const {
 143     size_t slot = probeKeys(mKeys, mShift, key);
 144     if (!isValidKey(mKeys[slot])) {
 145         *value = NULL;
 146         return false;
 147     }
 148     *value = mValues[slot];
 149     return true;
 150 }
 151
 152 void* IdToObjectMapBase::set(KeyType key, void* value) {
 153     if (!value)
 154         return remove(key);
 155
 156     size_t slot = probeKeys(mKeys, mShift, key);
 157     void* result;
 158     if (isValidKey(mKeys[slot])) {
 159         result = mValues[slot];
 160         mValues[slot] = value;
 161     } else {
 162         mKeys[slot] = key;
 163         mValues[slot] = value;
 164         result = NULL;
 165         mCount++;
 166         resize(mCount);
 167     }
 168     return result;
 169 }
 170
 171 void* IdToObjectMapBase::remove(KeyType key) {
 172     size_t slot = probeKeys(mKeys, mShift, key);
 173     if (!isValidKey(mKeys[slot]))
 174         return NULL;
 175
 176     void* result = mValues[slot];
 177     mValues[slot] = NULL;
 178     mKeys[slot] = kTombstone;
 179     mCount--;
 180     return result;
 181 }
 182
 183 void IdToObjectMapBase::resize(size_t newSize) {
 184     int ret = capacityCompare(mShift, newSize);
 185     if (!ret)
 186         return;
 187
 188     size_t oldCapacity = 1U << mShift;
 189     size_t newShift = mShift;
 190
 191     if (ret < 0) {
 192         // Capacity is too small and must be increased.
 193         do {
 194             if (newShift == kMaxShift)
 195                 break;
 196             ++newShift;
 197         } while (capacityCompare(newShift, newSize) < 0);
 198     } else {
 199         // Capacity is too large and must be decreased.
 200         do {
 201             if (newShift == kMinShift)
 202                 break;
 203             newShift--;
 204         } while (capacityCompare(newShift, newSize) > 0);
 205     }
 206     if (newShift == mShift)
 207         return;
 208
 209     // Allocate new arrays.
 210     size_t newCapacity = 1U << newShift;
 211     KeyType* newKeys = static_cast<KeyType*>(
 212             ::calloc(sizeof(newKeys[0]), newCapacity));
 213     void** newValues = static_cast<void**>(
 214             ::calloc(sizeof(newValues[0]), newCapacity));
 215     for (size_t n = 0; n < newCapacity; ++n)
 216         newKeys[n] = kInvalidKey;
 217
 218     // Copy old entries into new arrays.
 219     for (size_t n = 0; n < oldCapacity; ++n) {
 220         KeyType key = mKeys[n];
 221         if (isValidKey(key)) {
 222             size_t newSlot = probeKeys(newKeys, newShift, key);
 223             newKeys[newSlot] = key;
 224             newValues[newSlot] = mValues[n];
 225         }
 226     }
 227
 228     // Swap arrays, and get rid of old ones.
 229     ::free(mKeys);
 230     ::free(mValues);
 231     mKeys = newKeys;
 232     mValues = newValues;
 233     mShift = newShift;
 234 }
 235
 236 }  // namespace emugl