Add key equality function option for hash_map

This will allow us to do deeper equality on things like
bluetooth addresses where the actual pointers are different
but the values of the bluetooth addresses are the same.

11 files changed, 38 insertions, 21 deletions

diff --git a/bta/sys/bta_sys_main.c b/bta/sys/bta_sys_main.c
index ee9e95391..32f9fdddb 100644
--- a/bta/sys/bta_sys_main.c
+++ b/bta/sys/bta_sys_main.c
@@ -179,7 +179,7 @@ void bta_sys_init(void)
     pthread_mutex_init(&bta_alarm_lock, NULL);
 
     bta_alarm_hash_map = hash_map_new(BTA_ALARM_HASH_MAP_SIZE,
-            hash_function_pointer, NULL, (data_free_fn)alarm_free);
+            hash_function_pointer, NULL, (data_free_fn)alarm_free, NULL);
     btu_bta_alarm_queue = fixed_queue_new(SIZE_MAX);
 
     fixed_queue_register_dequeue(btu_bta_alarm_queue,
diff --git a/btcore/src/counter.c b/btcore/src/counter.c
index d7bdc3cfd..0f980f61b 100644
--- a/btcore/src/counter.c
+++ b/btcore/src/counter.c
@@ -121,7 +121,7 @@ static future_t *counter_init(void) {
   assert(hash_map_counter_ == NULL);
   pthread_mutex_init(&hash_map_lock_, NULL);
   hash_map_counter_ = hash_map_new(COUNTER_NUM_BUCKETS, hash_function_string,
-      NULL, hash_element_free_);
+      NULL, hash_element_free_, NULL);
   if (hash_map_counter_ == NULL) {
     LOG_ERROR("%s unable to allocate resources", __func__);
     return future_new_immediate(FUTURE_FAIL);
diff --git a/btcore/src/module.c b/btcore/src/module.c
index 9b96bb2de..7e55a6133 100644
--- a/btcore/src/module.c
+++ b/btcore/src/module.c
@@ -49,7 +49,8 @@ void module_management_start(void) {
     number_of_metadata_buckets,
     hash_function_pointer,
     NULL,
-    osi_free
+    osi_free,
+    NULL
   );
 
   pthread_mutex_init(&metadata_lock, NULL);
diff --git a/hci/src/packet_fragmenter.c b/hci/src/packet_fragmenter.c
index 5840f01c3..67b4c7f5d 100644
--- a/hci/src/packet_fragmenter.c
+++ b/hci/src/packet_fragmenter.c
@@ -53,7 +53,7 @@ static hash_map_t *partial_packets;
 
 static void init(const packet_fragmenter_callbacks_t *result_callbacks) {
   callbacks = result_callbacks;
-  partial_packets = hash_map_new(NUMBER_OF_BUCKETS, hash_function_naive, NULL, NULL);
+  partial_packets = hash_map_new(NUMBER_OF_BUCKETS, hash_function_naive, NULL, NULL, NULL);
 }
 
 static void cleanup() {
diff --git a/osi/include/hash_map.h b/osi/include/hash_map.h
index bb0cb5e40..b0c4a5a38 100644
--- a/osi/include/hash_map.h
+++ b/osi/include/hash_map.h
@@ -36,6 +36,8 @@ typedef size_t hash_index_t;
 typedef hash_index_t (*hash_index_fn)(const void *key);
 typedef bool (*hash_map_iter_cb)(hash_map_entry_t *hash_entry, void *context);
 
+typedef bool (*key_equality_fn)(const void *x, const void *y);
+
 typedef void (*key_free_fn)(void *data);
 typedef void (*data_free_fn)(void *data);
 
@@ -44,7 +46,9 @@ hash_map_t *hash_map_new(
     size_t size,
     hash_index_fn hash_fn,
     key_free_fn key_fn,
-    data_free_fn);
+    data_free_fn data_fn,
+    key_equality_fn equality_fn);
+
 void hash_map_free(hash_map_t *hash_map);
 
 // Accessors.
diff --git a/osi/src/allocation_tracker.c b/osi/src/allocation_tracker.c
index 27768a4ce..082127620 100644
--- a/osi/src/allocation_tracker.c
+++ b/osi/src/allocation_tracker.c
@@ -43,6 +43,7 @@ hash_map_t *hash_map_new_internal(
     hash_index_fn hash_fn,
     key_free_fn key_fn,
     data_free_fn,
+    key_equality_fn equality_fn,
     const allocator_t *zeroed_allocator);
 
 static bool allocation_entry_freed_checker(hash_map_entry_t *entry, void *context);
@@ -71,6 +72,7 @@ void allocation_tracker_init(void) {
     hash_function_pointer,
     NULL,
     free,
+    NULL,
     &untracked_calloc_allocator);
 }
 
diff --git a/osi/src/data_dispatcher.c b/osi/src/data_dispatcher.c
index b52b4ac81..5d2b5065a 100644
--- a/osi/src/data_dispatcher.c
+++ b/osi/src/data_dispatcher.c
@@ -44,7 +44,7 @@ data_dispatcher_t *data_dispatcher_new(const char *name) {
     goto error;
   }
 
-  ret->dispatch_table = hash_map_new(DEFAULT_TABLE_BUCKETS, hash_function_naive, NULL, NULL);
+  ret->dispatch_table = hash_map_new(DEFAULT_TABLE_BUCKETS, hash_function_naive, NULL, NULL, NULL);
   if (!ret->dispatch_table) {
     LOG_ERROR("%s unable to create dispatch table.", __func__);
     goto error;
diff --git a/osi/src/hash_map.c b/osi/src/hash_map.c
index 83a567d64..fb4975271 100644
--- a/osi/src/hash_map.c
+++ b/osi/src/hash_map.c
@@ -36,22 +36,25 @@ typedef struct hash_map_t {
   key_free_fn key_fn;
   data_free_fn data_fn;
   const allocator_t *allocator;
+  key_equality_fn keys_are_equal;
 } hash_map_t;
 
 // Hidden constructor for list, only to be used by us.
 list_t *list_new_internal(list_free_cb callback, const allocator_t *zeroed_allocator);
 
 static void bucket_free_(void *data);
+static bool default_key_equality(const void *x, const void *y);
 static hash_map_entry_t *find_bucket_entry_(list_t *hash_bucket_list,
     const void *key);
 
 // Hidden constructor, only to be used by the allocation tracker. Behaves the same as
 // |hash_map_new|, except you get to specify the allocator.
-hash_map_t * hash_map_new_internal(
+hash_map_t *hash_map_new_internal(
     size_t num_bucket,
     hash_index_fn hash_fn,
     key_free_fn key_fn,
     data_free_fn data_fn,
+    key_equality_fn equality_fn,
     const allocator_t *zeroed_allocator) {
   assert(hash_fn != NULL);
   assert(num_bucket > 0);
@@ -65,6 +68,7 @@ hash_map_t * hash_map_new_internal(
   hash_map->key_fn = key_fn;
   hash_map->data_fn = data_fn;
   hash_map->allocator = zeroed_allocator;
+  hash_map->keys_are_equal = equality_fn ? equality_fn : default_key_equality;
 
   hash_map->num_bucket = num_bucket;
   hash_map->bucket = zeroed_allocator->alloc(sizeof(hash_map_bucket_t) * num_bucket);
@@ -82,13 +86,15 @@ hash_map_t * hash_map_new_internal(
 // The |key_fn| and |data_fn| are called whenever a hash_map element is removed from
 // the hash_map. They can be used to release resources held by the hash_map element,
 // e.g.  memory or file descriptor.  |key_fn| and |data_fn| may be NULL if no cleanup
-// is necessary on element removal.
-hash_map_t * hash_map_new(
+// is necessary on element removal. |equality_fn| is used to check for key equality.
+// If |equality_fn| is NULL, default pointer equality is used.
+hash_map_t *hash_map_new(
     size_t num_bucket,
     hash_index_fn hash_fn,
     key_free_fn key_fn,
-    data_free_fn data_fn) {
-  return hash_map_new_internal(num_bucket, hash_fn, key_fn, data_fn, &allocator_calloc);
+    data_free_fn data_fn,
+    key_equality_fn equality_fn) {
+  return hash_map_new_internal(num_bucket, hash_fn, key_fn, data_fn, equality_fn, &allocator_calloc);
 }
 
 // Frees the hash_map. This function accepts NULL as an argument, in which case it
@@ -265,9 +271,13 @@ static hash_map_entry_t * find_bucket_entry_(list_t *hash_bucket_list,
       iter != list_end(hash_bucket_list);
       iter = list_next(iter)) {
     hash_map_entry_t *hash_map_entry = (hash_map_entry_t *)list_node(iter);
-    if (hash_map_entry->key == key) {
+    if (hash_map_entry->hash_map->keys_are_equal(hash_map_entry->key, key)) {
       return hash_map_entry;
     }
   }
   return NULL;
 }
+
+static bool default_key_equality(const void *x, const void *y) {
+  return x == y;
+}
diff --git a/osi/test/hash_map_test.cpp b/osi/test/hash_map_test.cpp
index 264b6f344..086b414a6 100644
--- a/osi/test/hash_map_test.cpp
+++ b/osi/test/hash_map_test.cpp
@@ -43,13 +43,13 @@ void data_free_fn00(UNUSED_ATTR void *data) {
 }
 
 TEST_F(HashMapTest, test_new_free_simple) {
-  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL);
+  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL, NULL);
   ASSERT_TRUE(hash_map != NULL);
   hash_map_free(hash_map);
 }
 
 TEST_F(HashMapTest, test_insert_simple) {
-  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL);
+  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL, NULL);
   ASSERT_TRUE(hash_map != NULL);
 
   struct {
@@ -82,7 +82,7 @@ TEST_F(HashMapTest, test_insert_simple) {
 }
 
 TEST_F(HashMapTest, test_insert_same) {
-  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL);
+  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL, NULL);
   ASSERT_TRUE(hash_map != NULL);
 
   struct {
@@ -113,7 +113,7 @@ TEST_F(HashMapTest, test_insert_same) {
 }
 
 TEST_F(HashMapTest, test_functions) {
-  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, key_free_fn00, data_free_fn00);
+  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, key_free_fn00, data_free_fn00, NULL);
   ASSERT_TRUE(hash_map != NULL);
 
   struct {
@@ -183,7 +183,7 @@ bool hash_test_iter_ro_cb(hash_map_entry_t *hash_map_entry, void *context) {
 }
 
 TEST_F(HashMapTest, test_iter) {
-  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, key_free_fn00, data_free_fn00);
+  hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, key_free_fn00, data_free_fn00, NULL);
   ASSERT_TRUE(hash_map != NULL);
   g_data_free = 0;
   g_key_free = 0;
diff --git a/stack/btu/btu_init.c b/stack/btu/btu_init.c
index 204070f4a..a3b6176fa 100644
--- a/stack/btu/btu_init.c
+++ b/stack/btu/btu_init.c
@@ -154,7 +154,7 @@ void BTU_StartUp(void)
         goto error_exit;
 
     btu_general_alarm_hash_map = hash_map_new(BTU_GENERAL_ALARM_HASH_MAP_SIZE,
-            hash_function_pointer, NULL, (data_free_fn)alarm_free);
+            hash_function_pointer, NULL, (data_free_fn)alarm_free, NULL);
     if (btu_general_alarm_hash_map == NULL)
         goto error_exit;
 
@@ -166,7 +166,7 @@ void BTU_StartUp(void)
         goto error_exit;
 
     btu_oneshot_alarm_hash_map = hash_map_new(BTU_ONESHOT_ALARM_HASH_MAP_SIZE,
-            hash_function_pointer, NULL, (data_free_fn)alarm_free);
+            hash_function_pointer, NULL, (data_free_fn)alarm_free, NULL);
     if (btu_oneshot_alarm_hash_map == NULL)
         goto error_exit;
 
@@ -178,7 +178,7 @@ void BTU_StartUp(void)
         goto error_exit;
 
     btu_l2cap_alarm_hash_map = hash_map_new(BTU_L2CAP_ALARM_HASH_MAP_SIZE,
-            hash_function_pointer, NULL, (data_free_fn)alarm_free);
+            hash_function_pointer, NULL, (data_free_fn)alarm_free, NULL);
     if (btu_l2cap_alarm_hash_map == NULL)
         goto error_exit;
 
diff --git a/test/suite/support/hal.c b/test/suite/support/hal.c
index ecc4c29da..3ebcf743c 100644
--- a/test/suite/support/hal.c
+++ b/test/suite/support/hal.c
@@ -79,7 +79,7 @@ static bool set_wake_alarm(uint64_t delay_millis, bool should_wake, alarm_cb cb,
   static hash_map_t *timers;
 
   if (!timers) {
-    timers = hash_map_new(TIMER_BUCKET_COUNT, hash_function_pointer, NULL, NULL);
+    timers = hash_map_new(TIMER_BUCKET_COUNT, hash_function_pointer, NULL, NULL, NULL);
   }
 
   timer_t *timer = hash_map_get(timers, cb);