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