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.
capacityCompare(size_t shift,size_t size)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
probeKeys(const KeyType * keys,size_t shift,KeyType key)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
IdToObjectMapBase()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
~IdToObjectMapBase()123 IdToObjectMapBase::~IdToObjectMapBase() {
124 mShift = 0;
125 mCount = 0;
126 ::free(mKeys);
127 ::free(mValues);
128 }
129
contains(KeyType key) const130 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
find(KeyType key,void ** value) const142 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
set(KeyType key,void * value)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
remove(KeyType key)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
resize(size_t newSize)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
237