• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  
BasicHashtableImpl(size_t entrySize,bool hasTrivialDestructor,size_t minimumInitialCapacity,float loadFactor)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  
BasicHashtableImpl(const BasicHashtableImpl & other)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  
~BasicHashtableImpl()45  BasicHashtableImpl::~BasicHashtableImpl()
46  {
47  }
48  
dispose()49  void BasicHashtableImpl::dispose() {
50      if (mBuckets) {
51          releaseBuckets(mBuckets, mBucketCount);
52      }
53  }
54  
clone()55  void BasicHashtableImpl::clone() {
56      if (mBuckets) {
57          void* newBuckets = allocateBuckets(mBucketCount);
58          copyBuckets(mBuckets, newBuckets, mBucketCount);
59          releaseBuckets(mBuckets, mBucketCount);
60          mBuckets = newBuckets;
61      }
62  }
63  
setTo(const BasicHashtableImpl & other)64  void BasicHashtableImpl::setTo(const BasicHashtableImpl& other) {
65      if (mBuckets) {
66          releaseBuckets(mBuckets, mBucketCount);
67      }
68  
69      mCapacity = other.mCapacity;
70      mLoadFactor = other.mLoadFactor;
71      mSize = other.mSize;
72      mFilledBuckets = other.mFilledBuckets;
73      mBucketCount = other.mBucketCount;
74      mBuckets = other.mBuckets;
75  
76      if (mBuckets) {
77          SharedBuffer::bufferFromData(mBuckets)->acquire();
78      }
79  }
80  
clear()81  void BasicHashtableImpl::clear() {
82      if (mBuckets) {
83          if (mFilledBuckets) {
84              SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets);
85              if (sb->onlyOwner()) {
86                  destroyBuckets(mBuckets, mBucketCount);
87                  for (size_t i = 0; i < mBucketCount; i++) {
88                      Bucket& bucket = bucketAt(mBuckets, i);
89                      bucket.cookie = 0;
90                  }
91              } else {
92                  releaseBuckets(mBuckets, mBucketCount);
93                  mBuckets = NULL;
94              }
95              mFilledBuckets = 0;
96          }
97          mSize = 0;
98      }
99  }
100  
next(ssize_t index) const101  ssize_t BasicHashtableImpl::next(ssize_t index) const {
102      if (mSize) {
103          while (size_t(++index) < mBucketCount) {
104              const Bucket& bucket = bucketAt(mBuckets, index);
105              if (bucket.cookie & Bucket::PRESENT) {
106                  return index;
107              }
108          }
109      }
110      return -1;
111  }
112  
find(ssize_t index,hash_t hash,const void * __restrict__ key) const113  ssize_t BasicHashtableImpl::find(ssize_t index, hash_t hash,
114          const void* __restrict__ key) const {
115      if (!mSize) {
116          return -1;
117      }
118  
119      hash = trimHash(hash);
120      if (index < 0) {
121          index = chainStart(hash, mBucketCount);
122  
123          const Bucket& bucket = bucketAt(mBuckets, size_t(index));
124          if (bucket.cookie & Bucket::PRESENT) {
125              if (compareBucketKey(bucket, key)) {
126                  return index;
127              }
128          } else {
129              if (!(bucket.cookie & Bucket::COLLISION)) {
130                  return -1;
131              }
132          }
133      }
134  
135      size_t inc = chainIncrement(hash, mBucketCount);
136      for (;;) {
137          index = chainSeek(index, inc, mBucketCount);
138  
139          const Bucket& bucket = bucketAt(mBuckets, size_t(index));
140          if (bucket.cookie & Bucket::PRESENT) {
141              if ((bucket.cookie & Bucket::HASH_MASK) == hash
142                      && compareBucketKey(bucket, key)) {
143                  return index;
144              }
145          }
146          if (!(bucket.cookie & Bucket::COLLISION)) {
147              return -1;
148          }
149      }
150  }
151  
add(hash_t hash,const void * entry)152  size_t BasicHashtableImpl::add(hash_t hash, const void* entry) {
153      if (!mBuckets) {
154          mBuckets = allocateBuckets(mBucketCount);
155      } else {
156          edit();
157      }
158  
159      hash = trimHash(hash);
160      for (;;) {
161          size_t index = chainStart(hash, mBucketCount);
162          Bucket* bucket = &bucketAt(mBuckets, size_t(index));
163          if (bucket->cookie & Bucket::PRESENT) {
164              size_t inc = chainIncrement(hash, mBucketCount);
165              do {
166                  bucket->cookie |= Bucket::COLLISION;
167                  index = chainSeek(index, inc, mBucketCount);
168                  bucket = &bucketAt(mBuckets, size_t(index));
169              } while (bucket->cookie & Bucket::PRESENT);
170          }
171  
172          uint32_t collision = bucket->cookie & Bucket::COLLISION;
173          if (!collision) {
174              if (mFilledBuckets >= mCapacity) {
175                  rehash(mCapacity * 2, mLoadFactor);
176                  continue;
177              }
178              mFilledBuckets += 1;
179          }
180  
181          bucket->cookie = collision | Bucket::PRESENT | hash;
182          mSize += 1;
183          initializeBucketEntry(*bucket, entry);
184          return index;
185      }
186  }
187  
removeAt(size_t index)188  void BasicHashtableImpl::removeAt(size_t index) {
189      edit();
190  
191      Bucket& bucket = bucketAt(mBuckets, index);
192      bucket.cookie &= ~Bucket::PRESENT;
193      if (!(bucket.cookie & Bucket::COLLISION)) {
194          mFilledBuckets -= 1;
195      }
196      mSize -= 1;
197      if (!mHasTrivialDestructor) {
198          destroyBucketEntry(bucket);
199      }
200  }
201  
rehash(size_t minimumCapacity,float loadFactor)202  void BasicHashtableImpl::rehash(size_t minimumCapacity, float loadFactor) {
203      if (minimumCapacity < mSize) {
204          minimumCapacity = mSize;
205      }
206      size_t newBucketCount, newCapacity;
207      determineCapacity(minimumCapacity, loadFactor, &newBucketCount, &newCapacity);
208  
209      if (newBucketCount != mBucketCount || newCapacity != mCapacity) {
210          if (mBuckets) {
211              void* newBuckets;
212              if (mSize) {
213                  newBuckets = allocateBuckets(newBucketCount);
214                  for (size_t i = 0; i < mBucketCount; i++) {
215                      const Bucket& fromBucket = bucketAt(mBuckets, i);
216                      if (fromBucket.cookie & Bucket::PRESENT) {
217                          hash_t hash = fromBucket.cookie & Bucket::HASH_MASK;
218                          size_t index = chainStart(hash, newBucketCount);
219                          Bucket* toBucket = &bucketAt(newBuckets, size_t(index));
220                          if (toBucket->cookie & Bucket::PRESENT) {
221                              size_t inc = chainIncrement(hash, newBucketCount);
222                              do {
223                                  toBucket->cookie |= Bucket::COLLISION;
224                                  index = chainSeek(index, inc, newBucketCount);
225                                  toBucket = &bucketAt(newBuckets, size_t(index));
226                              } while (toBucket->cookie & Bucket::PRESENT);
227                          }
228                          toBucket->cookie = Bucket::PRESENT | hash;
229                          initializeBucketEntry(*toBucket, fromBucket.entry);
230                      }
231                  }
232              } else {
233                  newBuckets = NULL;
234              }
235              releaseBuckets(mBuckets, mBucketCount);
236              mBuckets = newBuckets;
237              mFilledBuckets = mSize;
238          }
239          mBucketCount = newBucketCount;
240          mCapacity = newCapacity;
241      }
242      mLoadFactor = loadFactor;
243  }
244  
allocateBuckets(size_t count) const245  void* BasicHashtableImpl::allocateBuckets(size_t count) const {
246      size_t bytes = count * mBucketSize;
247      SharedBuffer* sb = SharedBuffer::alloc(bytes);
248      LOG_ALWAYS_FATAL_IF(!sb, "Could not allocate %u bytes for hashtable with %u buckets.",
249              uint32_t(bytes), uint32_t(count));
250      void* buckets = sb->data();
251      for (size_t i = 0; i < count; i++) {
252          Bucket& bucket = bucketAt(buckets, i);
253          bucket.cookie = 0;
254      }
255      return buckets;
256  }
257  
releaseBuckets(void * __restrict__ buckets,size_t count) const258  void BasicHashtableImpl::releaseBuckets(void* __restrict__ buckets, size_t count) const {
259      SharedBuffer* sb = SharedBuffer::bufferFromData(buckets);
260      if (sb->release(SharedBuffer::eKeepStorage) == 1) {
261          destroyBuckets(buckets, count);
262          SharedBuffer::dealloc(sb);
263      }
264  }
265  
destroyBuckets(void * __restrict__ buckets,size_t count) const266  void BasicHashtableImpl::destroyBuckets(void* __restrict__ buckets, size_t count) const {
267      if (!mHasTrivialDestructor) {
268          for (size_t i = 0; i < count; i++) {
269              Bucket& bucket = bucketAt(buckets, i);
270              if (bucket.cookie & Bucket::PRESENT) {
271                  destroyBucketEntry(bucket);
272              }
273          }
274      }
275  }
276  
copyBuckets(const void * __restrict__ fromBuckets,void * __restrict__ toBuckets,size_t count) const277  void BasicHashtableImpl::copyBuckets(const void* __restrict__ fromBuckets,
278          void* __restrict__ toBuckets, size_t count) const {
279      for (size_t i = 0; i < count; i++) {
280          const Bucket& fromBucket = bucketAt(fromBuckets, i);
281          Bucket& toBucket = bucketAt(toBuckets, i);
282          toBucket.cookie = fromBucket.cookie;
283          if (fromBucket.cookie & Bucket::PRESENT) {
284              initializeBucketEntry(toBucket, fromBucket.entry);
285          }
286      }
287  }
288  
289  // Table of 31-bit primes where each prime is no less than twice as large
290  // as the previous one.  Generated by "primes.py".
291  static size_t PRIMES[] = {
292      5,
293      11,
294      23,
295      47,
296      97,
297      197,
298      397,
299      797,
300      1597,
301      3203,
302      6421,
303      12853,
304      25717,
305      51437,
306      102877,
307      205759,
308      411527,
309      823117,
310      1646237,
311      3292489,
312      6584983,
313      13169977,
314      26339969,
315      52679969,
316      105359939,
317      210719881,
318      421439783,
319      842879579,
320      1685759167,
321      0,
322  };
323  
determineCapacity(size_t minimumCapacity,float loadFactor,size_t * __restrict__ outBucketCount,size_t * __restrict__ outCapacity)324  void BasicHashtableImpl::determineCapacity(size_t minimumCapacity, float loadFactor,
325          size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity) {
326      LOG_ALWAYS_FATAL_IF(loadFactor <= 0.0f || loadFactor > 1.0f,
327              "Invalid load factor %0.3f.  Must be in the range (0, 1].", loadFactor);
328  
329      size_t count = ceilf(minimumCapacity / loadFactor) + 1;
330      size_t i = 0;
331      while (count > PRIMES[i] && i < NELEM(PRIMES)) {
332          i++;
333      }
334      count = PRIMES[i];
335      LOG_ALWAYS_FATAL_IF(!count, "Could not determine required number of buckets for "
336              "hashtable with minimum capacity %u and load factor %0.3f.",
337              uint32_t(minimumCapacity), loadFactor);
338      *outBucketCount = count;
339      *outCapacity = ceilf((count - 1) * loadFactor);
340  }
341  
342  }; // namespace android
343