1 /****************************************************************************** 2 * 3 * Copyright (C) 2014 Google, Inc. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at: 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 ******************************************************************************/ 18 19 #include <assert.h> 20 #include <list.h> 21 #include <hash_map.h> 22 23 #include "osi/include/allocator.h" 24 25 struct hash_map_t; 26 27 typedef struct hash_map_bucket_t { 28 list_t *list; 29 } hash_map_bucket_t; 30 31 typedef struct hash_map_t { 32 hash_map_bucket_t *bucket; 33 size_t num_bucket; 34 size_t hash_size; 35 hash_index_fn hash_fn; 36 key_free_fn key_fn; 37 data_free_fn data_fn; 38 const allocator_t *allocator; 39 key_equality_fn keys_are_equal; 40 } hash_map_t; 41 42 // Hidden constructor for list, only to be used by us. 43 list_t *list_new_internal(list_free_cb callback, const allocator_t *zeroed_allocator); 44 45 static void bucket_free_(void *data); 46 static bool default_key_equality(const void *x, const void *y); 47 static hash_map_entry_t *find_bucket_entry_(list_t *hash_bucket_list, 48 const void *key); 49 50 // Hidden constructor, only to be used by the allocation tracker. Behaves the same as 51 // |hash_map_new|, except you get to specify the allocator. 52 hash_map_t *hash_map_new_internal( 53 size_t num_bucket, 54 hash_index_fn hash_fn, 55 key_free_fn key_fn, 56 data_free_fn data_fn, 57 key_equality_fn equality_fn, 58 const allocator_t *zeroed_allocator) { 59 assert(hash_fn != NULL); 60 assert(num_bucket > 0); 61 assert(zeroed_allocator != NULL); 62 63 hash_map_t *hash_map = zeroed_allocator->alloc(sizeof(hash_map_t)); 64 if (hash_map == NULL) 65 return NULL; 66 67 hash_map->hash_fn = hash_fn; 68 hash_map->key_fn = key_fn; 69 hash_map->data_fn = data_fn; 70 hash_map->allocator = zeroed_allocator; 71 hash_map->keys_are_equal = equality_fn ? equality_fn : default_key_equality; 72 73 hash_map->num_bucket = num_bucket; 74 hash_map->bucket = zeroed_allocator->alloc(sizeof(hash_map_bucket_t) * num_bucket); 75 if (hash_map->bucket == NULL) { 76 zeroed_allocator->free(hash_map); 77 return NULL; 78 } 79 return hash_map; 80 } 81 82 hash_map_t *hash_map_new( 83 size_t num_bucket, 84 hash_index_fn hash_fn, 85 key_free_fn key_fn, 86 data_free_fn data_fn, 87 key_equality_fn equality_fn) { 88 return hash_map_new_internal(num_bucket, hash_fn, key_fn, data_fn, equality_fn, &allocator_calloc); 89 } 90 91 void hash_map_free(hash_map_t *hash_map) { 92 if (hash_map == NULL) 93 return; 94 hash_map_clear(hash_map); 95 hash_map->allocator->free(hash_map->bucket); 96 hash_map->allocator->free(hash_map); 97 } 98 99 bool hash_map_is_empty(const hash_map_t *hash_map) { 100 assert(hash_map != NULL); 101 return (hash_map->hash_size == 0); 102 } 103 104 size_t hash_map_size(const hash_map_t *hash_map) { 105 assert(hash_map != NULL); 106 return hash_map->hash_size; 107 } 108 109 size_t hash_map_num_buckets(const hash_map_t *hash_map) { 110 assert(hash_map != NULL); 111 return hash_map->num_bucket; 112 } 113 114 bool hash_map_has_key(const hash_map_t *hash_map, const void *key) { 115 assert(hash_map != NULL); 116 117 hash_index_t hash_key = hash_map->hash_fn(key) % hash_map->num_bucket; 118 list_t *hash_bucket_list = hash_map->bucket[hash_key].list; 119 120 hash_map_entry_t *hash_map_entry = find_bucket_entry_(hash_bucket_list, key); 121 return (hash_map_entry != NULL); 122 } 123 124 bool hash_map_set(hash_map_t *hash_map, const void *key, void *data) { 125 assert(hash_map != NULL); 126 assert(data != NULL); 127 128 hash_index_t hash_key = hash_map->hash_fn(key) % hash_map->num_bucket; 129 130 if (hash_map->bucket[hash_key].list == NULL) { 131 hash_map->bucket[hash_key].list = list_new_internal(bucket_free_, hash_map->allocator); 132 if (hash_map->bucket[hash_key].list == NULL) 133 return false; 134 } 135 list_t *hash_bucket_list = hash_map->bucket[hash_key].list; 136 137 hash_map_entry_t *hash_map_entry = find_bucket_entry_(hash_bucket_list, key); 138 139 if (hash_map_entry) { 140 // Calls hash_map callback to delete the hash_map_entry. 141 bool rc = list_remove(hash_bucket_list, hash_map_entry); 142 assert(rc == true); 143 } else { 144 hash_map->hash_size++; 145 } 146 hash_map_entry = hash_map->allocator->alloc(sizeof(hash_map_entry_t)); 147 if (hash_map_entry == NULL) 148 return false; 149 150 hash_map_entry->key = key; 151 hash_map_entry->data = data; 152 hash_map_entry->hash_map = hash_map; 153 154 return list_append(hash_bucket_list, hash_map_entry); 155 } 156 157 bool hash_map_erase(hash_map_t *hash_map, const void *key) { 158 assert(hash_map != NULL); 159 160 hash_index_t hash_key = hash_map->hash_fn(key) % hash_map->num_bucket; 161 list_t *hash_bucket_list = hash_map->bucket[hash_key].list; 162 163 hash_map_entry_t *hash_map_entry = find_bucket_entry_(hash_bucket_list, key); 164 if (hash_map_entry == NULL) { 165 return false; 166 } 167 168 hash_map->hash_size--; 169 170 return list_remove(hash_bucket_list, hash_map_entry); 171 } 172 173 void *hash_map_get(const hash_map_t *hash_map, const void *key) { 174 assert(hash_map != NULL); 175 176 hash_index_t hash_key = hash_map->hash_fn(key) % hash_map->num_bucket; 177 list_t *hash_bucket_list = hash_map->bucket[hash_key].list; 178 179 hash_map_entry_t *hash_map_entry = find_bucket_entry_(hash_bucket_list, key); 180 if (hash_map_entry != NULL) 181 return hash_map_entry->data; 182 183 return NULL; 184 } 185 186 void hash_map_clear(hash_map_t *hash_map) { 187 assert(hash_map != NULL); 188 189 for (hash_index_t i = 0; i < hash_map->num_bucket; i++){ 190 if (hash_map->bucket[i].list == NULL) 191 continue; 192 list_free(hash_map->bucket[i].list); 193 hash_map->bucket[i].list = NULL; 194 } 195 } 196 197 void hash_map_foreach(hash_map_t *hash_map, hash_map_iter_cb callback, void *context) { 198 assert(hash_map != NULL); 199 assert(callback != NULL); 200 201 for (hash_index_t i = 0; i < hash_map->num_bucket; ++i){ 202 if (hash_map->bucket[i].list == NULL) 203 continue; 204 for (const list_node_t *iter = list_begin(hash_map->bucket[i].list); 205 iter != list_end(hash_map->bucket[i].list); 206 iter = list_next(iter)) { 207 hash_map_entry_t *hash_map_entry = (hash_map_entry_t *)list_node(iter); 208 if (!callback(hash_map_entry, context)) 209 return; 210 } 211 } 212 } 213 214 static void bucket_free_(void *data) { 215 assert(data != NULL); 216 hash_map_entry_t *hash_map_entry = (hash_map_entry_t *)data; 217 const hash_map_t *hash_map = hash_map_entry->hash_map; 218 219 if (hash_map->key_fn) 220 hash_map->key_fn((void *)hash_map_entry->key); 221 if (hash_map->data_fn) 222 hash_map->data_fn(hash_map_entry->data); 223 hash_map->allocator->free(hash_map_entry); 224 } 225 226 static hash_map_entry_t * find_bucket_entry_(list_t *hash_bucket_list, 227 const void *key) { 228 229 if (hash_bucket_list == NULL) 230 return NULL; 231 232 for (const list_node_t *iter = list_begin(hash_bucket_list); 233 iter != list_end(hash_bucket_list); 234 iter = list_next(iter)) { 235 hash_map_entry_t *hash_map_entry = (hash_map_entry_t *)list_node(iter); 236 if (hash_map_entry->hash_map->keys_are_equal(hash_map_entry->key, key)) { 237 return hash_map_entry; 238 } 239 } 240 return NULL; 241 } 242 243 static bool default_key_equality(const void *x, const void *y) { 244 return x == y; 245 } 246
