osi/src/hash_map.c

   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 #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 }