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