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 <gtest/gtest.h>
20 
21 #include "AllocationTestHarness.h"
22 
23 extern "C" {
24 #include "hash_map.h"
25 #include "osi.h"
26 }
27 
28 class HashMapTest : public AllocationTestHarness {};
29 
hash_map_fn00(const void * key)30 hash_index_t hash_map_fn00(const void *key) {
31   hash_index_t hash_key = (hash_index_t)key;
32   return hash_key;
33 }
34 
35 static size_t g_key_free;
key_free_fn00(UNUSED_ATTR void * data)36 void key_free_fn00(UNUSED_ATTR void *data) {
37   g_key_free++;
38 }
39 
40 static size_t g_data_free;
data_free_fn00(UNUSED_ATTR void * data)41 void data_free_fn00(UNUSED_ATTR void *data) {
42   g_data_free++;
43 }
44 
TEST_F(HashMapTest,test_new_free_simple)45 TEST_F(HashMapTest, test_new_free_simple) {
46   hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL, NULL);
47   ASSERT_TRUE(hash_map != NULL);
48   hash_map_free(hash_map);
49 }
50 
TEST_F(HashMapTest,test_insert_simple)51 TEST_F(HashMapTest, test_insert_simple) {
52   hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL, NULL);
53   ASSERT_TRUE(hash_map != NULL);
54 
55   struct {
56     const char *key;
57     const char *data;
58   } data[] = {
59     { "0", "zero" },
60     { "1", "one" },
61     { "2", "two" },
62     { "3", "three" },
63   };
64 
65   size_t data_sz = sizeof(data)/sizeof(data[0]);
66 
67   for (size_t i = 0; i < data_sz; i++) {
68     EXPECT_EQ(i, hash_map_size(hash_map));
69     hash_map_set(hash_map, data[i].key, (void*)data[i].data);
70     EXPECT_EQ(i + 1, hash_map_size(hash_map));
71   }
72 
73   EXPECT_EQ(data_sz, hash_map_size(hash_map));
74 
75   for (size_t i = 0; i < data_sz; i++) {
76     char *val = (char *)hash_map_get(hash_map, data[i].key);
77     EXPECT_STREQ(data[i].data, val);
78   }
79   EXPECT_EQ(data_sz, hash_map_size(hash_map));
80 
81   hash_map_free(hash_map);
82 }
83 
TEST_F(HashMapTest,test_insert_same)84 TEST_F(HashMapTest, test_insert_same) {
85   hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, NULL, NULL, NULL);
86   ASSERT_TRUE(hash_map != NULL);
87 
88   struct {
89     const char *key;
90     const char *data;
91   } data[] = {
92     { "0", "zero" },
93     { "0", "one" },
94     { "0", "two" },
95     { "0", "three" },
96   };
97 
98   size_t data_sz = sizeof(data)/sizeof(data[0]);
99 
100   for (size_t i = 0; i < data_sz; i++) {
101     hash_map_set(hash_map, data[i].key, (void*)data[i].data);
102     EXPECT_EQ(1U, hash_map_size(hash_map));
103   }
104 
105   EXPECT_EQ(1U, hash_map_size(hash_map));
106 
107   for (size_t i = 0; i < data_sz; i++) {
108     char *val = (char *)hash_map_get(hash_map, data[i].key);
109     EXPECT_STREQ(data[data_sz - 1].data, val);
110   }
111 
112   hash_map_free(hash_map);
113 }
114 
TEST_F(HashMapTest,test_functions)115 TEST_F(HashMapTest, test_functions) {
116   hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, key_free_fn00, data_free_fn00, NULL);
117   ASSERT_TRUE(hash_map != NULL);
118 
119   struct {
120     const char *key;
121     const char *data;
122   } data[] = {
123     { "0", "zero" },
124     { "1", "one" },
125     { "2", "two" },
126     { "3", "three" },
127   };
128 
129   g_data_free = 0;
130   g_key_free = 0;
131 
132   size_t data_sz = sizeof(data)/sizeof(data[0]);
133 
134   for (size_t i = 0; i < data_sz; i++) {
135     EXPECT_EQ(hash_map_size(hash_map), i);
136     hash_map_set(hash_map, data[i].key, (void*)data[i].data);
137   }
138 
139   EXPECT_EQ(data_sz, hash_map_size(hash_map));
140   EXPECT_EQ((size_t)0, g_data_free);
141   EXPECT_EQ((size_t)0, g_key_free);
142 
143   for (size_t i = 0; i < data_sz; i++) {
144     char *val = (char *)hash_map_get(hash_map, data[i].key);
145     EXPECT_TRUE(val != NULL);
146     EXPECT_STREQ(data[i].data, val);
147     hash_map_erase(hash_map, (void*)data[i].key);
148     EXPECT_EQ(i + 1, g_data_free);
149     EXPECT_EQ(i + 1, g_key_free);
150   }
151 
152   hash_map_free(hash_map);
153 }
154 
155 struct hash_test_iter_data_s {
156   const char *key;
157   const char *data;
158 } hash_test_iter_data[] = {
159   { "0", "zero" },
160   { "1", "one" },
161   { "2", "two" },
162   { "3", "three" },
163   { "elephant", "big" },
164   { "fox", "medium" },
165   { "gerbil", "small" },
166 };
167 
hash_test_iter_ro_cb(hash_map_entry_t * hash_map_entry,void * context)168 bool hash_test_iter_ro_cb(hash_map_entry_t *hash_map_entry, void *context) {
169   const char *key = (const char *)hash_map_entry->key;
170   char *data = (char *)hash_map_entry->data;
171   EXPECT_TRUE(data != NULL);
172 
173   size_t hash_test_iter_data_sz = sizeof(hash_test_iter_data)/sizeof(hash_test_iter_data[0]);
174   size_t i;
175   for (i = 0; i < hash_test_iter_data_sz; i++) {
176     if (!strcmp(hash_test_iter_data[i].key, key))
177       break;
178   }
179   EXPECT_NE(hash_test_iter_data_sz, i);
180   EXPECT_EQ(NULL, context);
181   EXPECT_STREQ(hash_test_iter_data[i].data, data);
182   return true;
183 }
184 
TEST_F(HashMapTest,test_iter)185 TEST_F(HashMapTest, test_iter) {
186   hash_map_t *hash_map = hash_map_new(5, hash_map_fn00, key_free_fn00, data_free_fn00, NULL);
187   ASSERT_TRUE(hash_map != NULL);
188   g_data_free = 0;
189   g_key_free = 0;
190 
191   size_t hash_test_iter_data_sz = sizeof(hash_test_iter_data)/sizeof(hash_test_iter_data[0]);
192 
193   for (size_t i = 0; i < hash_test_iter_data_sz; i++) {
194     EXPECT_EQ(hash_map_size(hash_map), i);
195     hash_map_set(hash_map, hash_test_iter_data[i].key, (void*)hash_test_iter_data[i].data);
196   }
197 
198   void *context = NULL;
199   hash_map_foreach(hash_map, hash_test_iter_ro_cb, context);
200 
201   hash_map_free(hash_map);
202 }
203