hashmap.c 8.6 KB

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