Home | History | Annotate | Download | only in utils
      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 #ifndef ANDROID_BASIC_HASHTABLE_H
     18 #define ANDROID_BASIC_HASHTABLE_H
     19 
     20 #include <stdint.h>
     21 #include <sys/types.h>
     22 #include <utils/SharedBuffer.h>
     23 #include <utils/TypeHelpers.h>
     24 
     25 namespace android {
     26 
     27 /* Implementation type.  Nothing to see here. */
     28 class BasicHashtableImpl {
     29 protected:
     30     struct Bucket {
     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;
     35 
     36         // The present flag indicates that the bucket contains an initialized entry value.
     37         static const uint32_t PRESENT   = 0x40000000UL;
     38 
     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;
     43 
     44         // Combined value that stores the collision and present flags as well as
     45         // a 30 bit hash code.
     46         uint32_t cookie;
     47 
     48         // Storage for the entry begins here.
     49         char entry[0];
     50     };
     51 
     52     BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor,
     53             size_t minimumInitialCapacity, float loadFactor);
     54     BasicHashtableImpl(const BasicHashtableImpl& other);
     55 
     56     void dispose();
     57 
     58     inline void edit() {
     59         if (mBuckets && !SharedBuffer::bufferFromData(mBuckets)->onlyOwner()) {
     60             clone();
     61         }
     62     }
     63 
     64     void setTo(const BasicHashtableImpl& other);
     65     void clear();
     66 
     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);
     72 
     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
     81 
     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);
     85     }
     86 
     87     inline Bucket& bucketAt(void* __restrict__ buckets, size_t index) const {
     88         return *reinterpret_cast<Bucket*>(static_cast<uint8_t*>(buckets) + index * mBucketSize);
     89     }
     90 
     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;
     94 
     95 private:
     96     void clone();
     97 
     98     // Allocates a bucket array as a SharedBuffer.
     99     void* allocateBuckets(size_t count) const;
    100 
    101     // Releases a bucket array's associated SharedBuffer.
    102     void releaseBuckets(void* __restrict__ buckets, size_t count) const;
    103 
    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;
    107 
    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;
    112 
    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);
    117 
    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);
    121     }
    122 
    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.
    125     // (Primary hash)
    126     inline static size_t chainStart(hash_t hash, size_t count) {
    127         return hash % count;
    128     }
    129 
    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.
    132     // (Secondary hash)
    133     inline static size_t chainIncrement(hash_t hash, size_t count) {
    134         return ((hash >> 7) | (hash << 25)) % (count - 1) + 1;
    135     }
    136 
    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;
    141     }
    142 };
    143 
    144 /*
    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.
    148  *
    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.
    154  *
    155  * TKey: The key type.
    156  * TEntry: The entry type which is what is actually stored in the array.
    157  *
    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
    161  *
    162  * TEntry must support the following contract:
    163  *     const TKey& getKey() const;  // get the key from the entry
    164  *
    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.
    168  */
    169 template <typename TKey, typename TEntry>
    170 class BasicHashtable : private BasicHashtableImpl {
    171 public:
    172     /* Creates a hashtable with the specified minimum initial capacity.
    173      * The underlying array will be created when the first entry is added.
    174      *
    175      * minimumInitialCapacity: The minimum initial capacity for the hashtable.
    176      *     Default is 0.
    177      * loadFactor: The desired load factor for the hashtable, between 0 and 1.
    178      *     Default is 0.75.
    179      */
    180     BasicHashtable(size_t minimumInitialCapacity = 0, float loadFactor = 0.75f);
    181 
    182     /* Copies a hashtable.
    183      * The underlying storage is shared copy-on-write.
    184      */
    185     BasicHashtable(const BasicHashtable& other);
    186 
    187     /* Clears and destroys the hashtable.
    188      */
    189     virtual ~BasicHashtable();
    190 
    191     /* Making this hashtable a copy of the other hashtable.
    192      * The underlying storage is shared copy-on-write.
    193      *
    194      * other: The hashtable to copy.
    195      */
    196     inline BasicHashtable<TKey, TEntry>& operator =(const BasicHashtable<TKey, TEntry> & other) {
    197         setTo(other);
    198         return *this;
    199     }
    200 
    201     /* Returns the number of entries in the hashtable.
    202      */
    203     inline size_t size() const {
    204         return mSize;
    205     }
    206 
    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.
    209      */
    210     inline size_t capacity() const {
    211         return mCapacity;
    212     }
    213 
    214     /* Returns the number of buckets that the hashtable has, which is the size of its
    215      * underlying array.
    216      */
    217     inline size_t bucketCount() const {
    218         return mBucketCount;
    219     }
    220 
    221     /* Returns the load factor of the hashtable. */
    222     inline float loadFactor() const {
    223         return mLoadFactor;
    224     };
    225 
    226     /* Returns a const reference to the entry at the specified index.
    227      *
    228      * index:   The index of the entry to retrieve.  Must be a valid index within
    229      *          the bounds of the hashtable.
    230      */
    231     inline const TEntry& entryAt(size_t index) const {
    232         return entryFor(bucketAt(mBuckets, index));
    233     }
    234 
    235     /* Returns a non-const reference to the entry at the specified index.
    236      *
    237      * index: The index of the entry to edit.  Must be a valid index within
    238      *        the bounds of the hashtable.
    239      */
    240     inline TEntry& editEntryAt(size_t index) {
    241         edit();
    242         return entryFor(bucketAt(mBuckets, index));
    243     }
    244 
    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.
    249      */
    250     inline void clear() {
    251         BasicHashtableImpl::clear();
    252     }
    253 
    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.
    259      *
    260      * index:   The index of the previous entry that was iterated, or -1 to begin
    261      *          iteration at the beginning of the hashtable.
    262      */
    263     inline ssize_t next(ssize_t index) const {
    264         return BasicHashtableImpl::next(index);
    265     }
    266 
    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.
    273      *
    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.
    277      * key:     The key.
    278      */
    279     inline ssize_t find(ssize_t index, hash_t hash, const TKey& key) const {
    280         return BasicHashtableImpl::find(index, hash, &key);
    281     }
    282 
    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().
    288      *
    289      * hash:    The hashcode of the key.
    290      * entry:   The entry to add.
    291      */
    292     inline size_t add(hash_t hash, const TEntry& entry) {
    293         return BasicHashtableImpl::add(hash, &entry);
    294     }
    295 
    296     /* Removes the entry with the specified index from the hashtable.
    297      * The entry is destroyed immediately.
    298      * The index must be valid.
    299      *
    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().
    302      *
    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.
    305      */
    306     inline void removeAt(size_t index) {
    307         BasicHashtableImpl::removeAt(index);
    308     }
    309 
    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.
    313      *
    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.
    318      *
    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).
    323      *
    324      * minimumCapacity: The desired minimum capacity after rehashing.
    325      * loadFactor: The desired load factor after rehashing.
    326      */
    327     inline void rehash(size_t minimumCapacity, float loadFactor) {
    328         BasicHashtableImpl::rehash(minimumCapacity, loadFactor);
    329     }
    330 
    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.
    334      */
    335     inline bool hasMoreRoom() const {
    336         return mCapacity > mFilledBuckets;
    337     }
    338 
    339 protected:
    340     static inline const TEntry& entryFor(const Bucket& bucket) {
    341         return reinterpret_cast<const TEntry&>(bucket.entry);
    342     }
    343 
    344     static inline TEntry& entryFor(Bucket& bucket) {
    345         return reinterpret_cast<TEntry&>(bucket.entry);
    346     }
    347 
    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;
    351 
    352 private:
    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;
    357     }
    358 };
    359 
    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) {
    364 }
    365 
    366 template <typename TKey, typename TEntry>
    367 BasicHashtable<TKey, TEntry>::BasicHashtable(const BasicHashtable<TKey, TEntry>& other) :
    368         BasicHashtableImpl(other) {
    369 }
    370 
    371 template <typename TKey, typename TEntry>
    372 BasicHashtable<TKey, TEntry>::~BasicHashtable() {
    373     dispose();
    374 }
    375 
    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);
    380 }
    381 
    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)));
    387     } else {
    388         memcpy(&entryFor(bucket), entry, sizeof(TEntry));
    389     }
    390 }
    391 
    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();
    396     }
    397 }
    398 
    399 }; // namespace android
    400 
    401 #endif // ANDROID_BASIC_HASHTABLE_H
    402