| // Copyright (C) 2014 The Android Open Source Project |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "emugl/common/id_to_object_map.h" |
| |
| #include <stdlib.h> |
| |
| namespace emugl { |
| |
| namespace { |
| |
| typedef IdToObjectMapBase::KeyType KeyType; |
| |
| enum { |
| kMinShift = 3, |
| kMaxShift = 31, |
| kMinCapacity = (1 << kMinShift), |
| kLoadScale = 1024, |
| kMinLoad = kLoadScale/4, // 25% minimum load. |
| kMaxLoad = kLoadScale*3/4, // 75% maximum load. |
| |
| kInvalidKey = IdToObjectMapBase::kMaxId + 1U, |
| kTombstone = IdToObjectMapBase::kMaxId + 2U, |
| }; |
| |
| // Return a number that indicates if the current |capacity| is appropriate |
| // to hold |size| items in our map. |
| // -1 -> the capacity is too small and needs to be increased. |
| // 0 -> the capacity is ok. |
| // +1 -> the capacity is too large and needs to be decreased. |
| int capacityCompare(size_t shift, size_t size) { |
| size_t capacity = 1U << shift; |
| // Essentially, one can rewrite: |
| // load < minLoad |
| // as: |
| // size / capacity < minLoad |
| // capacity * minLoad > size |
| if (capacity * kMinLoad > size * kLoadScale) |
| return +1; |
| |
| // Similarly, one can rewrite: |
| // load > maxLoad |
| // as: |
| // size / capacity > maxLoad |
| // capacity * maxLoad < size |
| if (capacity * kMaxLoad < size * kLoadScale) |
| return -1; |
| |
| return 0; |
| } |
| |
| size_t probeKeys(const KeyType* keys, size_t shift, KeyType key) { |
| static const int kPrimes[] = { |
| 1, /* For 1 << 0 */ |
| 2, |
| 3, |
| 7, |
| 13, |
| 31, |
| 61, |
| 127, |
| 251, |
| 509, |
| 1021, |
| 2039, |
| 4093, |
| 8191, |
| 16381, |
| 32749, |
| 65521, /* For 1 << 16 */ |
| 131071, |
| 262139, |
| 524287, |
| 1048573, |
| 2097143, |
| 4194301, |
| 8388593, |
| 16777213, |
| 33554393, |
| 67108859, |
| 134217689, |
| 268435399, |
| 536870909, |
| 1073741789, |
| 2147483647 /* For 1 << 31 */ |
| }; |
| |
| size_t slot = key % kPrimes[shift]; |
| size_t step = 0; |
| for (;;) { |
| KeyType k = keys[slot]; |
| if (k == kInvalidKey || k == kTombstone || k == key) |
| return slot; |
| |
| step += 1; |
| slot = (slot + step) & (1U << shift); |
| } |
| } |
| |
| } // namespace |
| |
| IdToObjectMapBase::IdToObjectMapBase() : |
| mCount(0), mShift(kMinShift) { |
| size_t capacity = 1U << mShift; |
| mKeys = static_cast<KeyType*>(::calloc(sizeof(mKeys[0]), capacity)); |
| mValues = static_cast<void**>(::calloc(sizeof(mValues[0]), capacity)); |
| for (size_t n = 0; n < capacity; ++n) { |
| mKeys[n] = kInvalidKey; |
| } |
| } |
| |
| IdToObjectMapBase::~IdToObjectMapBase() { |
| mShift = 0; |
| mCount = 0; |
| ::free(mKeys); |
| ::free(mValues); |
| } |
| |
| bool IdToObjectMapBase::contains(KeyType key) const { |
| size_t slot = probeKeys(mKeys, mShift, key); |
| switch (mKeys[slot]) { |
| case kInvalidKey: |
| case kTombstone: |
| return false; |
| default: |
| ; |
| } |
| return true; |
| } |
| |
| bool IdToObjectMapBase::find(KeyType key, void** value) const { |
| size_t slot = probeKeys(mKeys, mShift, key); |
| if (!isValidKey(mKeys[slot])) { |
| *value = NULL; |
| return false; |
| } |
| *value = mValues[slot]; |
| return true; |
| } |
| |
| void* IdToObjectMapBase::set(KeyType key, void* value) { |
| if (!value) |
| return remove(key); |
| |
| size_t slot = probeKeys(mKeys, mShift, key); |
| void* result; |
| if (isValidKey(mKeys[slot])) { |
| result = mValues[slot]; |
| mValues[slot] = value; |
| } else { |
| mKeys[slot] = key; |
| mValues[slot] = value; |
| result = NULL; |
| mCount++; |
| resize(mCount); |
| } |
| return result; |
| } |
| |
| void* IdToObjectMapBase::remove(KeyType key) { |
| size_t slot = probeKeys(mKeys, mShift, key); |
| if (!isValidKey(mKeys[slot])) |
| return NULL; |
| |
| void* result = mValues[slot]; |
| mValues[slot] = NULL; |
| mKeys[slot] = kTombstone; |
| mCount--; |
| return result; |
| } |
| |
| void IdToObjectMapBase::resize(size_t newSize) { |
| int ret = capacityCompare(mShift, newSize); |
| if (!ret) |
| return; |
| |
| size_t oldCapacity = 1U << mShift; |
| size_t newShift = mShift; |
| |
| if (ret < 0) { |
| // Capacity is too small and must be increased. |
| do { |
| if (newShift == kMaxShift) |
| break; |
| ++newShift; |
| } while (capacityCompare(newShift, newSize) < 0); |
| } else { |
| // Capacity is too large and must be decreased. |
| do { |
| if (newShift == kMinShift) |
| break; |
| newShift--; |
| } while (capacityCompare(newShift, newSize) > 0); |
| } |
| if (newShift == mShift) |
| return; |
| |
| // Allocate new arrays. |
| size_t newCapacity = 1U << newShift; |
| KeyType* newKeys = static_cast<KeyType*>( |
| ::calloc(sizeof(newKeys[0]), newCapacity)); |
| void** newValues = static_cast<void**>( |
| ::calloc(sizeof(newValues[0]), newCapacity)); |
| for (size_t n = 0; n < newCapacity; ++n) |
| newKeys[n] = kInvalidKey; |
| |
| // Copy old entries into new arrays. |
| for (size_t n = 0; n < oldCapacity; ++n) { |
| KeyType key = mKeys[n]; |
| if (isValidKey(key)) { |
| size_t newSlot = probeKeys(newKeys, newShift, key); |
| newKeys[newSlot] = key; |
| newValues[newSlot] = mValues[n]; |
| } |
| } |
| |
| // Swap arrays, and get rid of old ones. |
| ::free(mKeys); |
| ::free(mValues); |
| mKeys = newKeys; |
| mValues = newValues; |
| mShift = newShift; |
| } |
| |
| } // namespace emugl |