Home | History | Annotate | Download | only in libcutils
      1 /*
      2  * Copyright (C) 2007 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 #include <cutils/hashmap.h>
     18 #include <assert.h>
     19 #include <errno.h>
     20 #include <cutils/threads.h>
     21 #include <stdlib.h>
     22 #include <string.h>
     23 #include <stdbool.h>
     24 #include <sys/types.h>
     25 
     26 typedef struct Entry Entry;
     27 struct Entry {
     28     void* key;
     29     int hash;
     30     void* value;
     31     Entry* next;
     32 };
     33 
     34 struct Hashmap {
     35     Entry** buckets;
     36     size_t bucketCount;
     37     int (*hash)(void* key);
     38     bool (*equals)(void* keyA, void* keyB);
     39     mutex_t lock;
     40     size_t size;
     41 };
     42 
     43 Hashmap* hashmapCreate(size_t initialCapacity,
     44         int (*hash)(void* key), bool (*equals)(void* keyA, void* keyB)) {
     45     assert(hash != NULL);
     46     assert(equals != NULL);
     47 
     48     Hashmap* map = malloc(sizeof(Hashmap));
     49     if (map == NULL) {
     50         return NULL;
     51     }
     52 
     53     // 0.75 load factor.
     54     size_t minimumBucketCount = initialCapacity * 4 / 3;
     55     map->bucketCount = 1;
     56     while (map->bucketCount <= minimumBucketCount) {
     57         // Bucket count must be power of 2.
     58         map->bucketCount <<= 1;
     59     }
     60 
     61     map->buckets = calloc(map->bucketCount, sizeof(Entry*));
     62     if (map->buckets == NULL) {
     63         free(map);
     64         return NULL;
     65     }
     66 
     67     map->size = 0;
     68 
     69     map->hash = hash;
     70     map->equals = equals;
     71 
     72     mutex_init(&map->lock);
     73 
     74     return map;
     75 }
     76 
     77 /**
     78  * Hashes the given key.
     79  */
     80 static inline int hashKey(Hashmap* map, void* key) {
     81     int h = map->hash(key);
     82 
     83     // We apply this secondary hashing discovered by Doug Lea to defend
     84     // against bad hashes.
     85     h += ~(h << 9);
     86     h ^= (((unsigned int) h) >> 14);
     87     h += (h << 4);
     88     h ^= (((unsigned int) h) >> 10);
     89 
     90     return h;
     91 }
     92 
     93 size_t hashmapSize(Hashmap* map) {
     94     return map->size;
     95 }
     96 
     97 static inline size_t calculateIndex(size_t bucketCount, int hash) {
     98     return ((size_t) hash) & (bucketCount - 1);
     99 }
    100 
    101 static void expandIfNecessary(Hashmap* map) {
    102     // If the load factor exceeds 0.75...
    103     if (map->size > (map->bucketCount * 3 / 4)) {
    104         // Start off with a 0.33 load factor.
    105         size_t newBucketCount = map->bucketCount << 1;
    106         Entry** newBuckets = calloc(newBucketCount, sizeof(Entry*));
    107         if (newBuckets == NULL) {
    108             // Abort expansion.
    109             return;
    110         }
    111 
    112         // Move over existing entries.
    113         size_t i;
    114         for (i = 0; i < map->bucketCount; i++) {
    115             Entry* entry = map->buckets[i];
    116             while (entry != NULL) {
    117                 Entry* next = entry->next;
    118                 size_t index = calculateIndex(newBucketCount, entry->hash);
    119                 entry->next = newBuckets[index];
    120                 newBuckets[index] = entry;
    121                 entry = next;
    122             }
    123         }
    124 
    125         // Copy over internals.
    126         free(map->buckets);
    127         map->buckets = newBuckets;
    128         map->bucketCount = newBucketCount;
    129     }
    130 }
    131 
    132 void hashmapLock(Hashmap* map) {
    133     mutex_lock(&map->lock);
    134 }
    135 
    136 void hashmapUnlock(Hashmap* map) {
    137     mutex_unlock(&map->lock);
    138 }
    139 
    140 void hashmapFree(Hashmap* map) {
    141     size_t i;
    142     for (i = 0; i < map->bucketCount; i++) {
    143         Entry* entry = map->buckets[i];
    144         while (entry != NULL) {
    145             Entry* next = entry->next;
    146             free(entry);
    147             entry = next;
    148         }
    149     }
    150     free(map->buckets);
    151     mutex_destroy(&map->lock);
    152     free(map);
    153 }
    154 
    155 int hashmapHash(void* key, size_t keySize) {
    156     int h = keySize;
    157     char* data = (char*) key;
    158     size_t i;
    159     for (i = 0; i < keySize; i++) {
    160         h = h * 31 + *data;
    161         data++;
    162     }
    163     return h;
    164 }
    165 
    166 static Entry* createEntry(void* key, int hash, void* value) {
    167     Entry* entry = malloc(sizeof(Entry));
    168     if (entry == NULL) {
    169         return NULL;
    170     }
    171     entry->key = key;
    172     entry->hash = hash;
    173     entry->value = value;
    174     entry->next = NULL;
    175     return entry;
    176 }
    177 
    178 static inline bool equalKeys(void* keyA, int hashA, void* keyB, int hashB,
    179         bool (*equals)(void*, void*)) {
    180     if (keyA == keyB) {
    181         return true;
    182     }
    183     if (hashA != hashB) {
    184         return false;
    185     }
    186     return equals(keyA, keyB);
    187 }
    188 
    189 void* hashmapPut(Hashmap* map, void* key, void* value) {
    190     int hash = hashKey(map, key);
    191     size_t index = calculateIndex(map->bucketCount, hash);
    192 
    193     Entry** p = &(map->buckets[index]);
    194     while (true) {
    195         Entry* current = *p;
    196 
    197         // Add a new entry.
    198         if (current == NULL) {
    199             *p = createEntry(key, hash, value);
    200             if (*p == NULL) {
    201                 errno = ENOMEM;
    202                 return NULL;
    203             }
    204             map->size++;
    205             expandIfNecessary(map);
    206             return NULL;
    207         }
    208 
    209         // Replace existing entry.
    210         if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
    211             void* oldValue = current->value;
    212             current->value = value;
    213             return oldValue;
    214         }
    215 
    216         // Move to next entry.
    217         p = &current->next;
    218     }
    219 }
    220 
    221 void* hashmapGet(Hashmap* map, void* key) {
    222     int hash = hashKey(map, key);
    223     size_t index = calculateIndex(map->bucketCount, hash);
    224 
    225     Entry* entry = map->buckets[index];
    226     while (entry != NULL) {
    227         if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
    228             return entry->value;
    229         }
    230         entry = entry->next;
    231     }
    232 
    233     return NULL;
    234 }
    235 
    236 bool hashmapContainsKey(Hashmap* map, void* key) {
    237     int hash = hashKey(map, key);
    238     size_t index = calculateIndex(map->bucketCount, hash);
    239 
    240     Entry* entry = map->buckets[index];
    241     while (entry != NULL) {
    242         if (equalKeys(entry->key, entry->hash, key, hash, map->equals)) {
    243             return true;
    244         }
    245         entry = entry->next;
    246     }
    247 
    248     return false;
    249 }
    250 
    251 void* hashmapMemoize(Hashmap* map, void* key,
    252         void* (*initialValue)(void* key, void* context), void* context) {
    253     int hash = hashKey(map, key);
    254     size_t index = calculateIndex(map->bucketCount, hash);
    255 
    256     Entry** p = &(map->buckets[index]);
    257     while (true) {
    258         Entry* current = *p;
    259 
    260         // Add a new entry.
    261         if (current == NULL) {
    262             *p = createEntry(key, hash, NULL);
    263             if (*p == NULL) {
    264                 errno = ENOMEM;
    265                 return NULL;
    266             }
    267             void* value = initialValue(key, context);
    268             (*p)->value = value;
    269             map->size++;
    270             expandIfNecessary(map);
    271             return value;
    272         }
    273 
    274         // Return existing value.
    275         if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
    276             return current->value;
    277         }
    278 
    279         // Move to next entry.
    280         p = &current->next;
    281     }
    282 }
    283 
    284 void* hashmapRemove(Hashmap* map, void* key) {
    285     int hash = hashKey(map, key);
    286     size_t index = calculateIndex(map->bucketCount, hash);
    287 
    288     // Pointer to the current entry.
    289     Entry** p = &(map->buckets[index]);
    290     Entry* current;
    291     while ((current = *p) != NULL) {
    292         if (equalKeys(current->key, current->hash, key, hash, map->equals)) {
    293             void* value = current->value;
    294             *p = current->next;
    295             free(current);
    296             map->size--;
    297             return value;
    298         }
    299 
    300         p = &current->next;
    301     }
    302 
    303     return NULL;
    304 }
    305 
    306 void hashmapForEach(Hashmap* map,
    307         bool (*callback)(void* key, void* value, void* context),
    308         void* context) {
    309     size_t i;
    310     for (i = 0; i < map->bucketCount; i++) {
    311         Entry* entry = map->buckets[i];
    312         while (entry != NULL) {
    313             if (!callback(entry->key, entry->value, context)) {
    314                 return;
    315             }
    316             entry = entry->next;
    317         }
    318     }
    319 }
    320 
    321 size_t hashmapCurrentCapacity(Hashmap* map) {
    322     size_t bucketCount = map->bucketCount;
    323     return bucketCount * 3 / 4;
    324 }
    325 
    326 size_t hashmapCountCollisions(Hashmap* map) {
    327     size_t collisions = 0;
    328     size_t i;
    329     for (i = 0; i < map->bucketCount; i++) {
    330         Entry* entry = map->buckets[i];
    331         while (entry != NULL) {
    332             if (entry->next != NULL) {
    333                 collisions++;
    334             }
    335             entry = entry->next;
    336         }
    337     }
    338     return collisions;
    339 }
    340 
    341 int hashmapIntHash(void* key) {
    342     // Return the key value itself.
    343     return *((int*) key);
    344 }
    345 
    346 bool hashmapIntEquals(void* keyA, void* keyB) {
    347     int a = *((int*) keyA);
    348     int b = *((int*) keyB);
    349     return a == b;
    350 }
    351