2 * Copyright (C) 2011 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef ANDROID_BASIC_HASHTABLE_H
18 #define ANDROID_BASIC_HASHTABLE_H
21 #include <sys/types.h>
22 #include <utils/SharedBuffer.h>
23 #include <utils/TypeHelpers.h>
27 /* Implementation type. Nothing to see here. */
28 class BasicHashtableImpl {
31 // The collision flag indicates that the bucket is part of a collision chain
32 // such that at least two entries both hash to this bucket. When true, we
33 // may need to seek further along the chain to find the entry.
34 static const uint32_t COLLISION = 0x80000000UL;
36 // The present flag indicates that the bucket contains an initialized entry value.
37 static const uint32_t PRESENT = 0x40000000UL;
39 // Mask for 30 bits worth of the hash code that are stored within the bucket to
40 // speed up lookups and rehashing by eliminating the need to recalculate the
41 // hash code of the entry's key.
42 static const uint32_t HASH_MASK = 0x3fffffffUL;
44 // Combined value that stores the collision and present flags as well as
45 // a 30 bit hash code.
48 // Storage for the entry begins here.
52 BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor,
53 size_t minimumInitialCapacity, float loadFactor);
54 BasicHashtableImpl(const BasicHashtableImpl& other);
59 if (mBuckets && !SharedBuffer::bufferFromData(mBuckets)->onlyOwner()) {
64 void setTo(const BasicHashtableImpl& other);
67 ssize_t next(ssize_t index) const;
68 ssize_t find(ssize_t index, hash_t hash, const void* __restrict__ key) const;
69 size_t add(hash_t hash, const void* __restrict__ entry);
70 void removeAt(size_t index);
71 void rehash(size_t minimumCapacity, float loadFactor);
73 const size_t mBucketSize; // number of bytes per bucket including the entry
74 const bool mHasTrivialDestructor; // true if the entry type does not require destruction
75 size_t mCapacity; // number of buckets that can be filled before exceeding load factor
76 float mLoadFactor; // load factor
77 size_t mSize; // number of elements actually in the table
78 size_t mFilledBuckets; // number of buckets for which collision or present is true
79 size_t mBucketCount; // number of slots in the mBuckets array
80 void* mBuckets; // array of buckets, as a SharedBuffer
82 inline const Bucket& bucketAt(const void* __restrict__ buckets, size_t index) const {
83 return *reinterpret_cast<const Bucket*>(
84 static_cast<const uint8_t*>(buckets) + index * mBucketSize);
87 inline Bucket& bucketAt(void* __restrict__ buckets, size_t index) const {
88 return *reinterpret_cast<Bucket*>(static_cast<uint8_t*>(buckets) + index * mBucketSize);
91 virtual bool compareBucketKey(const Bucket& bucket, const void* __restrict__ key) const = 0;
92 virtual void initializeBucketEntry(Bucket& bucket, const void* __restrict__ entry) const = 0;
93 virtual void destroyBucketEntry(Bucket& bucket) const = 0;
98 // Allocates a bucket array as a SharedBuffer.
99 void* allocateBuckets(size_t count) const;
101 // Releases a bucket array's associated SharedBuffer.
102 void releaseBuckets(void* __restrict__ buckets, size_t count) const;
104 // Destroys the contents of buckets (invokes destroyBucketEntry for each
105 // populated bucket if needed).
106 void destroyBuckets(void* __restrict__ buckets, size_t count) const;
108 // Copies the content of buckets (copies the cookie and invokes copyBucketEntry
109 // for each populated bucket if needed).
110 void copyBuckets(const void* __restrict__ fromBuckets,
111 void* __restrict__ toBuckets, size_t count) const;
113 // Determines the appropriate size of a bucket array to store a certain minimum
114 // number of entries and returns its effective capacity.
115 static void determineCapacity(size_t minimumCapacity, float loadFactor,
116 size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity);
118 // Trim a hash code to 30 bits to match what we store in the bucket's cookie.
119 inline static hash_t trimHash(hash_t hash) {
120 return (hash & Bucket::HASH_MASK) ^ (hash >> 30);
123 // Returns the index of the first bucket that is in the collision chain
124 // for the specified hash code, given the total number of buckets.
126 inline static size_t chainStart(hash_t hash, size_t count) {
130 // Returns the increment to add to a bucket index to seek to the next bucket
131 // in the collision chain for the specified hash code, given the total number of buckets.
133 inline static size_t chainIncrement(hash_t hash, size_t count) {
134 return ((hash >> 7) | (hash << 25)) % (count - 1) + 1;
137 // Returns the index of the next bucket that is in the collision chain
138 // that is defined by the specified increment, given the total number of buckets.
139 inline static size_t chainSeek(size_t index, size_t increment, size_t count) {
140 return (index + increment) % count;
145 * A BasicHashtable stores entries that are indexed by hash code in place
146 * within an array. The basic operations are finding entries by key,
147 * adding new entries and removing existing entries.
149 * This class provides a very limited set of operations with simple semantics.
150 * It is intended to be used as a building block to construct more complex
151 * and interesting data structures such as HashMap. Think very hard before
152 * adding anything extra to BasicHashtable, it probably belongs at a
153 * higher level of abstraction.
155 * TKey: The key type.
156 * TEntry: The entry type which is what is actually stored in the array.
158 * TKey must support the following contract:
159 * bool operator==(const TKey& other) const; // return true if equal
160 * bool operator!=(const TKey& other) const; // return true if unequal
162 * TEntry must support the following contract:
163 * const TKey& getKey() const; // get the key from the entry
165 * This class supports storing entries with duplicate keys. Of course, it can't
166 * tell them apart during removal so only the first entry will be removed.
167 * We do this because it means that operations like add() can't fail.
169 template <typename TKey, typename TEntry>
170 class BasicHashtable : private BasicHashtableImpl {
172 /* Creates a hashtable with the specified minimum initial capacity.
173 * The underlying array will be created when the first entry is added.
175 * minimumInitialCapacity: The minimum initial capacity for the hashtable.
177 * loadFactor: The desired load factor for the hashtable, between 0 and 1.
180 BasicHashtable(size_t minimumInitialCapacity = 0, float loadFactor = 0.75f);
182 /* Copies a hashtable.
183 * The underlying storage is shared copy-on-write.
185 BasicHashtable(const BasicHashtable& other);
187 /* Clears and destroys the hashtable.
189 virtual ~BasicHashtable();
191 /* Making this hashtable a copy of the other hashtable.
192 * The underlying storage is shared copy-on-write.
194 * other: The hashtable to copy.
196 inline BasicHashtable<TKey, TEntry>& operator =(const BasicHashtable<TKey, TEntry> & other) {
201 /* Returns the number of entries in the hashtable.
203 inline size_t size() const {
207 /* Returns the capacity of the hashtable, which is the number of elements that can
208 * added to the hashtable without requiring it to be grown.
210 inline size_t capacity() const {
214 /* Returns the number of buckets that the hashtable has, which is the size of its
217 inline size_t bucketCount() const {
221 /* Returns the load factor of the hashtable. */
222 inline float loadFactor() const {
226 /* Returns a const reference to the entry at the specified index.
228 * index: The index of the entry to retrieve. Must be a valid index within
229 * the bounds of the hashtable.
231 inline const TEntry& entryAt(size_t index) const {
232 return entryFor(bucketAt(mBuckets, index));
235 /* Returns a non-const reference to the entry at the specified index.
237 * index: The index of the entry to edit. Must be a valid index within
238 * the bounds of the hashtable.
240 inline TEntry& editEntryAt(size_t index) {
242 return entryFor(bucketAt(mBuckets, index));
245 /* Clears the hashtable.
246 * All entries in the hashtable are destroyed immediately.
247 * If you need to do something special with the entries in the hashtable then iterate
248 * over them and do what you need before clearing the hashtable.
250 inline void clear() {
251 BasicHashtableImpl::clear();
254 /* Returns the index of the next entry in the hashtable given the index of a previous entry.
255 * If the given index is -1, then returns the index of the first entry in the hashtable,
256 * if there is one, or -1 otherwise.
257 * If the given index is not -1, then returns the index of the next entry in the hashtable,
258 * in strictly increasing order, or -1 if there are none left.
260 * index: The index of the previous entry that was iterated, or -1 to begin
261 * iteration at the beginning of the hashtable.
263 inline ssize_t next(ssize_t index) const {
264 return BasicHashtableImpl::next(index);
267 /* Finds the index of an entry with the specified key.
268 * If the given index is -1, then returns the index of the first matching entry,
269 * otherwise returns the index of the next matching entry.
270 * If the hashtable contains multiple entries with keys that match the requested
271 * key, then the sequence of entries returned is arbitrary.
272 * Returns -1 if no entry was found.
274 * index: The index of the previous entry with the specified key, or -1 to
275 * find the first matching entry.
276 * hash: The hashcode of the key.
279 inline ssize_t find(ssize_t index, hash_t hash, const TKey& key) const {
280 return BasicHashtableImpl::find(index, hash, &key);
283 /* Adds the entry to the hashtable.
284 * Returns the index of the newly added entry.
285 * If an entry with the same key already exists, then a duplicate entry is added.
286 * If the entry will not fit, then the hashtable's capacity is increased and
287 * its contents are rehashed. See rehash().
289 * hash: The hashcode of the key.
290 * entry: The entry to add.
292 inline size_t add(hash_t hash, const TEntry& entry) {
293 return BasicHashtableImpl::add(hash, &entry);
296 /* Removes the entry with the specified index from the hashtable.
297 * The entry is destroyed immediately.
298 * The index must be valid.
300 * The hashtable is not compacted after an item is removed, so it is legal
301 * to continue iterating over the hashtable using next() or find().
303 * index: The index of the entry to remove. Must be a valid index within the
304 * bounds of the hashtable, and it must refer to an existing entry.
306 inline void removeAt(size_t index) {
307 BasicHashtableImpl::removeAt(index);
310 /* Rehashes the contents of the hashtable.
311 * Grows the hashtable to at least the specified minimum capacity or the
312 * current number of elements, whichever is larger.
314 * Rehashing causes all entries to be copied and the entry indices may change.
315 * Although the hash codes are cached by the hashtable, rehashing can be an
316 * expensive operation and should be avoided unless the hashtable's size
317 * needs to be changed.
319 * Rehashing is the only way to change the capacity or load factor of the
320 * hashtable once it has been created. It can be used to compact the
321 * hashtable by choosing a minimum capacity that is smaller than the current
322 * capacity (such as 0).
324 * minimumCapacity: The desired minimum capacity after rehashing.
325 * loadFactor: The desired load factor after rehashing.
327 inline void rehash(size_t minimumCapacity, float loadFactor) {
328 BasicHashtableImpl::rehash(minimumCapacity, loadFactor);
331 /* Determines whether there is room to add another entry without rehashing.
332 * When this returns true, a subsequent add() operation is guaranteed to
333 * complete without performing a rehash.
335 inline bool hasMoreRoom() const {
336 return mCapacity > mFilledBuckets;
340 static inline const TEntry& entryFor(const Bucket& bucket) {
341 return reinterpret_cast<const TEntry&>(bucket.entry);
344 static inline TEntry& entryFor(Bucket& bucket) {
345 return reinterpret_cast<TEntry&>(bucket.entry);
348 virtual bool compareBucketKey(const Bucket& bucket, const void* __restrict__ key) const;
349 virtual void initializeBucketEntry(Bucket& bucket, const void* __restrict__ entry) const;
350 virtual void destroyBucketEntry(Bucket& bucket) const;
353 // For dumping the raw contents of a hashtable during testing.
354 friend class BasicHashtableTest;
355 inline uint32_t cookieAt(size_t index) const {
356 return bucketAt(mBuckets, index).cookie;
360 template <typename TKey, typename TEntry>
361 BasicHashtable<TKey, TEntry>::BasicHashtable(size_t minimumInitialCapacity, float loadFactor) :
362 BasicHashtableImpl(sizeof(TEntry), traits<TEntry>::has_trivial_dtor,
363 minimumInitialCapacity, loadFactor) {
366 template <typename TKey, typename TEntry>
367 BasicHashtable<TKey, TEntry>::BasicHashtable(const BasicHashtable<TKey, TEntry>& other) :
368 BasicHashtableImpl(other) {
371 template <typename TKey, typename TEntry>
372 BasicHashtable<TKey, TEntry>::~BasicHashtable() {
376 template <typename TKey, typename TEntry>
377 bool BasicHashtable<TKey, TEntry>::compareBucketKey(const Bucket& bucket,
378 const void* __restrict__ key) const {
379 return entryFor(bucket).getKey() == *static_cast<const TKey*>(key);
382 template <typename TKey, typename TEntry>
383 void BasicHashtable<TKey, TEntry>::initializeBucketEntry(Bucket& bucket,
384 const void* __restrict__ entry) const {
385 if (!traits<TEntry>::has_trivial_copy) {
386 new (&entryFor(bucket)) TEntry(*(static_cast<const TEntry*>(entry)));
388 memcpy(&entryFor(bucket), entry, sizeof(TEntry));
392 template <typename TKey, typename TEntry>
393 void BasicHashtable<TKey, TEntry>::destroyBucketEntry(Bucket& bucket) const {
394 if (!traits<TEntry>::has_trivial_dtor) {
395 entryFor(bucket).~TEntry();
399 }; // namespace android
401 #endif // ANDROID_BASIC_HASHTABLE_H