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 19namespace emugl { 20 21namespace { 22 23typedef IdToObjectMapBase::KeyType KeyType; 24 25enum { 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. 42int 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 63size_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 113IdToObjectMapBase::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 123IdToObjectMapBase::~IdToObjectMapBase() { 124 mShift = 0; 125 mCount = 0; 126 ::free(mKeys); 127 ::free(mValues); 128} 129 130bool 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 142bool 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 152void* 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 171void* 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 183void 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 237