1 /* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #define LOG_TAG "BasicHashtable" 18 19 #include <math.h> 20 21 #include <utils/Log.h> 22 #include <utils/BasicHashtable.h> 23 #include <utils/misc.h> 24 25 namespace android { 26 27 BasicHashtableImpl::BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor, 28 size_t minimumInitialCapacity, float loadFactor) : 29 mBucketSize(entrySize + sizeof(Bucket)), mHasTrivialDestructor(hasTrivialDestructor), 30 mLoadFactor(loadFactor), mSize(0), 31 mFilledBuckets(0), mBuckets(NULL) { 32 determineCapacity(minimumInitialCapacity, mLoadFactor, &mBucketCount, &mCapacity); 33 } 34 35 BasicHashtableImpl::BasicHashtableImpl(const BasicHashtableImpl& other) : 36 mBucketSize(other.mBucketSize), mHasTrivialDestructor(other.mHasTrivialDestructor), 37 mCapacity(other.mCapacity), mLoadFactor(other.mLoadFactor), 38 mSize(other.mSize), mFilledBuckets(other.mFilledBuckets), 39 mBucketCount(other.mBucketCount), mBuckets(other.mBuckets) { 40 if (mBuckets) { 41 SharedBuffer::bufferFromData(mBuckets)->acquire(); 42 } 43 } 44 45 void BasicHashtableImpl::dispose() { 46 if (mBuckets) { 47 releaseBuckets(mBuckets, mBucketCount); 48 } 49 } 50 51 void BasicHashtableImpl::clone() { 52 if (mBuckets) { 53 void* newBuckets = allocateBuckets(mBucketCount); 54 copyBuckets(mBuckets, newBuckets, mBucketCount); 55 releaseBuckets(mBuckets, mBucketCount); 56 mBuckets = newBuckets; 57 } 58 } 59 60 void BasicHashtableImpl::setTo(const BasicHashtableImpl& other) { 61 if (mBuckets) { 62 releaseBuckets(mBuckets, mBucketCount); 63 } 64 65 mCapacity = other.mCapacity; 66 mLoadFactor = other.mLoadFactor; 67 mSize = other.mSize; 68 mFilledBuckets = other.mFilledBuckets; 69 mBucketCount = other.mBucketCount; 70 mBuckets = other.mBuckets; 71 72 if (mBuckets) { 73 SharedBuffer::bufferFromData(mBuckets)->acquire(); 74 } 75 } 76 77 void BasicHashtableImpl::clear() { 78 if (mBuckets) { 79 if (mFilledBuckets) { 80 SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets); 81 if (sb->onlyOwner()) { 82 destroyBuckets(mBuckets, mBucketCount); 83 for (size_t i = 0; i < mSize; i++) { 84 Bucket& bucket = bucketAt(mBuckets, i); 85 bucket.cookie = 0; 86 } 87 } else { 88 releaseBuckets(mBuckets, mBucketCount); 89 mBuckets = NULL; 90 } 91 mFilledBuckets = 0; 92 } 93 mSize = 0; 94 } 95 } 96 97 ssize_t BasicHashtableImpl::next(ssize_t index) const { 98 if (mSize) { 99 while (size_t(++index) < mBucketCount) { 100 const Bucket& bucket = bucketAt(mBuckets, index); 101 if (bucket.cookie & Bucket::PRESENT) { 102 return index; 103 } 104 } 105 } 106 return -1; 107 } 108 109 ssize_t BasicHashtableImpl::find(ssize_t index, hash_t hash, 110 const void* __restrict__ key) const { 111 if (!mSize) { 112 return -1; 113 } 114 115 hash = trimHash(hash); 116 if (index < 0) { 117 index = chainStart(hash, mBucketCount); 118 119 const Bucket& bucket = bucketAt(mBuckets, size_t(index)); 120 if (bucket.cookie & Bucket::PRESENT) { 121 if (compareBucketKey(bucket, key)) { 122 return index; 123 } 124 } else { 125 if (!(bucket.cookie & Bucket::COLLISION)) { 126 return -1; 127 } 128 } 129 } 130 131 size_t inc = chainIncrement(hash, mBucketCount); 132 for (;;) { 133 index = chainSeek(index, inc, mBucketCount); 134 135 const Bucket& bucket = bucketAt(mBuckets, size_t(index)); 136 if (bucket.cookie & Bucket::PRESENT) { 137 if ((bucket.cookie & Bucket::HASH_MASK) == hash 138 && compareBucketKey(bucket, key)) { 139 return index; 140 } 141 } 142 if (!(bucket.cookie & Bucket::COLLISION)) { 143 return -1; 144 } 145 } 146 } 147 148 size_t BasicHashtableImpl::add(hash_t hash, const void* entry) { 149 if (!mBuckets) { 150 mBuckets = allocateBuckets(mBucketCount); 151 } else { 152 edit(); 153 } 154 155 hash = trimHash(hash); 156 for (;;) { 157 size_t index = chainStart(hash, mBucketCount); 158 Bucket* bucket = &bucketAt(mBuckets, size_t(index)); 159 if (bucket->cookie & Bucket::PRESENT) { 160 size_t inc = chainIncrement(hash, mBucketCount); 161 do { 162 bucket->cookie |= Bucket::COLLISION; 163 index = chainSeek(index, inc, mBucketCount); 164 bucket = &bucketAt(mBuckets, size_t(index)); 165 } while (bucket->cookie & Bucket::PRESENT); 166 } 167 168 uint32_t collision = bucket->cookie & Bucket::COLLISION; 169 if (!collision) { 170 if (mFilledBuckets >= mCapacity) { 171 rehash(mCapacity * 2, mLoadFactor); 172 continue; 173 } 174 mFilledBuckets += 1; 175 } 176 177 bucket->cookie = collision | Bucket::PRESENT | hash; 178 mSize += 1; 179 initializeBucketEntry(*bucket, entry); 180 return index; 181 } 182 } 183 184 void BasicHashtableImpl::removeAt(size_t index) { 185 edit(); 186 187 Bucket& bucket = bucketAt(mBuckets, index); 188 bucket.cookie &= ~Bucket::PRESENT; 189 if (!(bucket.cookie & Bucket::COLLISION)) { 190 mFilledBuckets -= 1; 191 } 192 mSize -= 1; 193 if (!mHasTrivialDestructor) { 194 destroyBucketEntry(bucket); 195 } 196 } 197 198 void BasicHashtableImpl::rehash(size_t minimumCapacity, float loadFactor) { 199 if (minimumCapacity < mSize) { 200 minimumCapacity = mSize; 201 } 202 size_t newBucketCount, newCapacity; 203 determineCapacity(minimumCapacity, loadFactor, &newBucketCount, &newCapacity); 204 205 if (newBucketCount != mBucketCount || newCapacity != mCapacity) { 206 if (mBuckets) { 207 void* newBuckets; 208 if (mSize) { 209 newBuckets = allocateBuckets(newBucketCount); 210 for (size_t i = 0; i < mBucketCount; i++) { 211 const Bucket& fromBucket = bucketAt(mBuckets, i); 212 if (fromBucket.cookie & Bucket::PRESENT) { 213 hash_t hash = fromBucket.cookie & Bucket::HASH_MASK; 214 size_t index = chainStart(hash, newBucketCount); 215 Bucket* toBucket = &bucketAt(newBuckets, size_t(index)); 216 if (toBucket->cookie & Bucket::PRESENT) { 217 size_t inc = chainIncrement(hash, newBucketCount); 218 do { 219 toBucket->cookie |= Bucket::COLLISION; 220 index = chainSeek(index, inc, newBucketCount); 221 toBucket = &bucketAt(newBuckets, size_t(index)); 222 } while (toBucket->cookie & Bucket::PRESENT); 223 } 224 toBucket->cookie = Bucket::PRESENT | hash; 225 initializeBucketEntry(*toBucket, fromBucket.entry); 226 } 227 } 228 } else { 229 newBuckets = NULL; 230 } 231 releaseBuckets(mBuckets, mBucketCount); 232 mBuckets = newBuckets; 233 mFilledBuckets = mSize; 234 } 235 mBucketCount = newBucketCount; 236 mCapacity = newCapacity; 237 } 238 mLoadFactor = loadFactor; 239 } 240 241 void* BasicHashtableImpl::allocateBuckets(size_t count) const { 242 size_t bytes = count * mBucketSize; 243 SharedBuffer* sb = SharedBuffer::alloc(bytes); 244 LOG_ALWAYS_FATAL_IF(!sb, "Could not allocate %u bytes for hashtable with %u buckets.", 245 uint32_t(bytes), uint32_t(count)); 246 void* buckets = sb->data(); 247 for (size_t i = 0; i < count; i++) { 248 Bucket& bucket = bucketAt(buckets, i); 249 bucket.cookie = 0; 250 } 251 return buckets; 252 } 253 254 void BasicHashtableImpl::releaseBuckets(void* __restrict__ buckets, size_t count) const { 255 SharedBuffer* sb = SharedBuffer::bufferFromData(buckets); 256 if (sb->release(SharedBuffer::eKeepStorage) == 1) { 257 destroyBuckets(buckets, count); 258 SharedBuffer::dealloc(sb); 259 } 260 } 261 262 void BasicHashtableImpl::destroyBuckets(void* __restrict__ buckets, size_t count) const { 263 if (!mHasTrivialDestructor) { 264 for (size_t i = 0; i < count; i++) { 265 Bucket& bucket = bucketAt(buckets, i); 266 if (bucket.cookie & Bucket::PRESENT) { 267 destroyBucketEntry(bucket); 268 } 269 } 270 } 271 } 272 273 void BasicHashtableImpl::copyBuckets(const void* __restrict__ fromBuckets, 274 void* __restrict__ toBuckets, size_t count) const { 275 for (size_t i = 0; i < count; i++) { 276 const Bucket& fromBucket = bucketAt(fromBuckets, i); 277 Bucket& toBucket = bucketAt(toBuckets, i); 278 toBucket.cookie = fromBucket.cookie; 279 if (fromBucket.cookie & Bucket::PRESENT) { 280 initializeBucketEntry(toBucket, fromBucket.entry); 281 } 282 } 283 } 284 285 // Table of 31-bit primes where each prime is no less than twice as large 286 // as the previous one. Generated by "primes.py". 287 static size_t PRIMES[] = { 288 5, 289 11, 290 23, 291 47, 292 97, 293 197, 294 397, 295 797, 296 1597, 297 3203, 298 6421, 299 12853, 300 25717, 301 51437, 302 102877, 303 205759, 304 411527, 305 823117, 306 1646237, 307 3292489, 308 6584983, 309 13169977, 310 26339969, 311 52679969, 312 105359939, 313 210719881, 314 421439783, 315 842879579, 316 1685759167, 317 0, 318 }; 319 320 void BasicHashtableImpl::determineCapacity(size_t minimumCapacity, float loadFactor, 321 size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity) { 322 LOG_ALWAYS_FATAL_IF(loadFactor <= 0.0f || loadFactor > 1.0f, 323 "Invalid load factor %0.3f. Must be in the range (0, 1].", loadFactor); 324 325 size_t count = ceilf(minimumCapacity / loadFactor) + 1; 326 size_t i = 0; 327 while (count > PRIMES[i] && i < NELEM(PRIMES)) { 328 i++; 329 } 330 count = PRIMES[i]; 331 LOG_ALWAYS_FATAL_IF(!count, "Could not determine required number of buckets for " 332 "hashtable with minimum capacity %u and load factor %0.3f.", 333 uint32_t(minimumCapacity), loadFactor); 334 *outBucketCount = count; 335 *outCapacity = ceilf((count - 1) * loadFactor); 336 } 337 338 }; // namespace android 339