← Back to branch summary

~ubuntu-branches/ubuntu/wily/grpc/wily

« back to all changes in this revision

Viewing changes to test/core/statistics/hash_table_test.c

  • Committer: Package Import Robot
  • Author(s): Andrew Pollock
  • Date: 2015-05-07 13:28:11 UTC
  • Revision ID: package-import@ubuntu.com-20150507132811-ybm4hfq73tnvvd2e
Tags: upstream-0.10.0
Import upstream version 0.10.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
test/core/statistics/hash_table_test.c
 
1
/*
 
2
 *
 
3
 * Copyright 2015, Google Inc.
 
4
 * All rights reserved.
 
5
 *
 
6
 * Redistribution and use in source and binary forms, with or without
 
7
 * modification, are permitted provided that the following conditions are
 
8
 * met:
 
9
 *
 
10
 *     * Redistributions of source code must retain the above copyright
 
11
 * notice, this list of conditions and the following disclaimer.
 
12
 *     * Redistributions in binary form must reproduce the above
 
13
 * copyright notice, this list of conditions and the following disclaimer
 
14
 * in the documentation and/or other materials provided with the
 
15
 * distribution.
 
16
 *     * Neither the name of Google Inc. nor the names of its
 
17
 * contributors may be used to endorse or promote products derived from
 
18
 * this software without specific prior written permission.
 
19
 *
 
20
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 
21
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 
22
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 
23
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 
24
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 
25
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 
26
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
27
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
28
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
29
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 
30
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
31
 *
 
32
 */
 
33
 
 
34
#include <stdio.h>
 
35
#include <stdlib.h>
 
36
#include <string.h>
 
37
 
 
38
#include "src/core/statistics/hash_table.h"
 
39
 
 
40
#include "src/core/support/murmur_hash.h"
 
41
#include "src/core/support/string.h"
 
42
#include <grpc/support/alloc.h>
 
43
#include <grpc/support/log.h>
 
44
#include <grpc/support/time.h>
 
45
#include "test/core/util/test_config.h"
 
46
 
 
47
static gpr_uint64 hash64(const void* k) {
 
48
  size_t len = strlen(k);
 
49
  gpr_uint64 higher = gpr_murmur_hash3((const char*)k, len / 2, 0);
 
50
  return higher << 32 |
 
51
         gpr_murmur_hash3((const char*)(k) + len / 2, len - len / 2, 0);
 
52
}
 
53
 
 
54
static int cmp_str_keys(const void* k1, const void* k2) {
 
55
  return strcmp((const char*)k1, (const char*)k2);
 
56
}
 
57
 
 
58
static gpr_uint64 force_collision(const void* k) {
 
59
  return (1997 + hash64(k) % 3);
 
60
}
 
61
 
 
62
static void free_data(void* data) { gpr_free(data); }
 
63
 
 
64
/* Basic tests that empty hash table can be created and destroyed. */
 
65
static void test_create_table(void) {
 
66
  /* Create table with uint64 key type */
 
67
  census_ht* ht = NULL;
 
68
  census_ht_option ht_options = {CENSUS_HT_UINT64, 1999, NULL,
 
69
                                 NULL,             NULL, NULL};
 
70
  ht = census_ht_create(&ht_options);
 
71
  GPR_ASSERT(ht != NULL);
 
72
  GPR_ASSERT(census_ht_get_size(ht) == 0);
 
73
  census_ht_destroy(ht);
 
74
  /* Create table with pointer key type */
 
75
  ht = NULL;
 
76
  ht_options.key_type = CENSUS_HT_POINTER;
 
77
  ht_options.hash = &hash64;
 
78
  ht_options.compare_keys = &cmp_str_keys;
 
79
  ht = census_ht_create(&ht_options);
 
80
  GPR_ASSERT(ht != NULL);
 
81
  GPR_ASSERT(census_ht_get_size(ht) == 0);
 
82
  census_ht_destroy(ht);
 
83
}
 
84
 
 
85
static void test_table_with_int_key(void) {
 
86
  census_ht_option opt = {CENSUS_HT_UINT64, 7, NULL, NULL, NULL, NULL};
 
87
  census_ht* ht = census_ht_create(&opt);
 
88
  gpr_uint64 i = 0;
 
89
  gpr_uint64 sum_of_keys = 0;
 
90
  size_t num_elements;
 
91
  census_ht_kv* elements = NULL;
 
92
  GPR_ASSERT(ht != NULL);
 
93
  GPR_ASSERT(census_ht_get_size(ht) == 0);
 
94
  elements = census_ht_get_all_elements(ht, &num_elements);
 
95
  GPR_ASSERT(num_elements == 0);
 
96
  GPR_ASSERT(elements == NULL);
 
97
  for (i = 0; i < 20; ++i) {
 
98
    census_ht_key key;
 
99
    key.val = i;
 
100
    census_ht_insert(ht, key, (void*)(gpr_intptr) i);
 
101
    GPR_ASSERT(census_ht_get_size(ht) == i + 1);
 
102
  }
 
103
  for (i = 0; i < 20; i++) {
 
104
    gpr_uint64* val = NULL;
 
105
    census_ht_key key;
 
106
    key.val = i;
 
107
    val = census_ht_find(ht, key);
 
108
    GPR_ASSERT(val == (void*)(gpr_intptr) i);
 
109
  }
 
110
  elements = census_ht_get_all_elements(ht, &num_elements);
 
111
  GPR_ASSERT(elements != NULL);
 
112
  GPR_ASSERT(num_elements == 20);
 
113
  for (i = 0; i < num_elements; i++) {
 
114
    sum_of_keys += elements[i].k.val;
 
115
  }
 
116
  GPR_ASSERT(sum_of_keys == 190);
 
117
  gpr_free(elements);
 
118
  census_ht_destroy(ht);
 
119
}
 
120
 
 
121
/* Test that there is no memory leak when keys and values are owned by table. */
 
122
static void test_value_and_key_deleter(void) {
 
123
  census_ht_option opt = {CENSUS_HT_POINTER, 7,          &hash64,
 
124
                          &cmp_str_keys,     &free_data, &free_data};
 
125
  census_ht* ht = census_ht_create(&opt);
 
126
  census_ht_key key;
 
127
  char* val = NULL;
 
128
  char* val2 = NULL;
 
129
  key.ptr = gpr_malloc(100);
 
130
  val = gpr_malloc(10);
 
131
  strcpy(val, "value");
 
132
  strcpy(key.ptr, "some string as a key");
 
133
  GPR_ASSERT(ht != NULL);
 
134
  GPR_ASSERT(census_ht_get_size(ht) == 0);
 
135
  census_ht_insert(ht, key, val);
 
136
  GPR_ASSERT(census_ht_get_size(ht) == 1);
 
137
  val = census_ht_find(ht, key);
 
138
  GPR_ASSERT(val != NULL);
 
139
  GPR_ASSERT(strcmp(val, "value") == 0);
 
140
  /* Insert same key different value, old value is overwritten. */
 
141
  val2 = gpr_malloc(10);
 
142
  strcpy(val2, "v2");
 
143
  census_ht_insert(ht, key, val2);
 
144
  GPR_ASSERT(census_ht_get_size(ht) == 1);
 
145
  val2 = census_ht_find(ht, key);
 
146
  GPR_ASSERT(val2 != NULL);
 
147
  GPR_ASSERT(strcmp(val2, "v2") == 0);
 
148
  census_ht_destroy(ht);
 
149
}
 
150
 
 
151
/* Test simple insert and erase operations. */
 
152
static void test_simple_add_and_erase(void) {
 
153
  census_ht_option opt = {CENSUS_HT_UINT64, 7, NULL, NULL, NULL, NULL};
 
154
  census_ht* ht = census_ht_create(&opt);
 
155
  GPR_ASSERT(ht != NULL);
 
156
  GPR_ASSERT(census_ht_get_size(ht) == 0);
 
157
  {
 
158
    census_ht_key key;
 
159
    int val = 3;
 
160
    key.val = 2;
 
161
    census_ht_insert(ht, key, (void*)&val);
 
162
    GPR_ASSERT(census_ht_get_size(ht) == 1);
 
163
    census_ht_erase(ht, key);
 
164
    GPR_ASSERT(census_ht_get_size(ht) == 0);
 
165
    /* Erasing a key from an empty table should be noop. */
 
166
    census_ht_erase(ht, key);
 
167
    GPR_ASSERT(census_ht_get_size(ht) == 0);
 
168
    /* Erasing a non-existant key from a table should be noop. */
 
169
    census_ht_insert(ht, key, (void*)&val);
 
170
    key.val = 3;
 
171
    census_ht_insert(ht, key, (void*)&val);
 
172
    key.val = 9;
 
173
    census_ht_insert(ht, key, (void*)&val);
 
174
    GPR_ASSERT(census_ht_get_size(ht) == 3);
 
175
    key.val = 1;
 
176
    census_ht_erase(ht, key);
 
177
    /* size unchanged after deleting non-existant key. */
 
178
    GPR_ASSERT(census_ht_get_size(ht) == 3);
 
179
    /* size decrease by 1 after deleting an existant key. */
 
180
    key.val = 2;
 
181
    census_ht_erase(ht, key);
 
182
    GPR_ASSERT(census_ht_get_size(ht) == 2);
 
183
  }
 
184
  census_ht_destroy(ht);
 
185
}
 
186
 
 
187
static void test_insertion_and_deletion_with_high_collision_rate(void) {
 
188
  census_ht_option opt = {CENSUS_HT_POINTER, 13,   &force_collision,
 
189
                          &cmp_str_keys,     NULL, NULL};
 
190
  census_ht* ht = census_ht_create(&opt);
 
191
  char key_str[1000][GPR_LTOA_MIN_BUFSIZE];
 
192
  gpr_uint64 val = 0;
 
193
  unsigned i = 0;
 
194
  for (i = 0; i < 1000; i++) {
 
195
    census_ht_key key;
 
196
    key.ptr = key_str[i];
 
197
    gpr_ltoa(i, key_str[i]);
 
198
    census_ht_insert(ht, key, (void*)(&val));
 
199
    gpr_log(GPR_INFO, "%d\n", i);
 
200
    GPR_ASSERT(census_ht_get_size(ht) == (i + 1));
 
201
  }
 
202
  for (i = 0; i < 1000; i++) {
 
203
    census_ht_key key;
 
204
    key.ptr = key_str[i];
 
205
    census_ht_erase(ht, key);
 
206
    GPR_ASSERT(census_ht_get_size(ht) == (999 - i));
 
207
  }
 
208
  census_ht_destroy(ht);
 
209
}
 
210
 
 
211
static void test_table_with_string_key(void) {
 
212
  census_ht_option opt = {CENSUS_HT_POINTER, 7,    &hash64,
 
213
                          &cmp_str_keys,     NULL, NULL};
 
214
  census_ht* ht = census_ht_create(&opt);
 
215
  const char* keys[] = {"k1",    "a",                              "000",
 
216
                        "apple", "banana_a_long_long_long_banana", "%$",
 
217
                        "111",   "foo",                            "b"};
 
218
  const int vals[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
 
219
  int i = 0;
 
220
  GPR_ASSERT(ht != NULL);
 
221
  GPR_ASSERT(census_ht_get_size(ht) == 0);
 
222
  for (i = 0; i < 9; i++) {
 
223
    census_ht_key key;
 
224
    key.ptr = (void*)(keys[i]);
 
225
    census_ht_insert(ht, key, (void*)(vals + i));
 
226
  }
 
227
  GPR_ASSERT(census_ht_get_size(ht) == 9);
 
228
  for (i = 0; i < 9; i++) {
 
229
    census_ht_key key;
 
230
    int* val_ptr;
 
231
    key.ptr = (void*)(keys[i]);
 
232
    val_ptr = census_ht_find(ht, key);
 
233
    GPR_ASSERT(*val_ptr == vals[i]);
 
234
  }
 
235
  {
 
236
    /* inserts duplicate keys */
 
237
    census_ht_key key;
 
238
    int* val_ptr = NULL;
 
239
    key.ptr = (void*)(keys[2]);
 
240
    census_ht_insert(ht, key, (void*)(vals + 8));
 
241
    /* expect value to be over written by new insertion */
 
242
    GPR_ASSERT(census_ht_get_size(ht) == 9);
 
243
    val_ptr = census_ht_find(ht, key);
 
244
    GPR_ASSERT(*val_ptr == vals[8]);
 
245
  }
 
246
  for (i = 0; i < 9; i++) {
 
247
    census_ht_key key;
 
248
    int* val_ptr;
 
249
    gpr_uint32 expected_tbl_sz = 9 - i;
 
250
    GPR_ASSERT(census_ht_get_size(ht) == expected_tbl_sz);
 
251
    key.ptr = (void*)(keys[i]);
 
252
    val_ptr = census_ht_find(ht, key);
 
253
    GPR_ASSERT(val_ptr != NULL);
 
254
    census_ht_erase(ht, key);
 
255
    GPR_ASSERT(census_ht_get_size(ht) == expected_tbl_sz - 1);
 
256
    val_ptr = census_ht_find(ht, key);
 
257
    GPR_ASSERT(val_ptr == NULL);
 
258
  }
 
259
  census_ht_destroy(ht);
 
260
}
 
261
 
 
262
static void test_insertion_with_same_key(void) {
 
263
  census_ht_option opt = {CENSUS_HT_UINT64, 11, NULL, NULL, NULL, NULL};
 
264
  census_ht* ht = census_ht_create(&opt);
 
265
  census_ht_key key;
 
266
  const char vals[] = {'a', 'b', 'c'};
 
267
  char* val_ptr;
 
268
  key.val = 3;
 
269
  census_ht_insert(ht, key, (void*)&(vals[0]));
 
270
  GPR_ASSERT(census_ht_get_size(ht) == 1);
 
271
  val_ptr = (char*)census_ht_find(ht, key);
 
272
  GPR_ASSERT(val_ptr != NULL);
 
273
  GPR_ASSERT(*val_ptr == 'a');
 
274
  key.val = 4;
 
275
  val_ptr = (char*)census_ht_find(ht, key);
 
276
  GPR_ASSERT(val_ptr == NULL);
 
277
  key.val = 3;
 
278
  census_ht_insert(ht, key, (void*)&(vals[1]));
 
279
  GPR_ASSERT(census_ht_get_size(ht) == 1);
 
280
  val_ptr = (char*)census_ht_find(ht, key);
 
281
  GPR_ASSERT(val_ptr != NULL);
 
282
  GPR_ASSERT(*val_ptr == 'b');
 
283
  census_ht_insert(ht, key, (void*)&(vals[2]));
 
284
  GPR_ASSERT(census_ht_get_size(ht) == 1);
 
285
  val_ptr = (char*)census_ht_find(ht, key);
 
286
  GPR_ASSERT(val_ptr != NULL);
 
287
  GPR_ASSERT(*val_ptr == 'c');
 
288
  census_ht_destroy(ht);
 
289
}
 
290
 
 
291
int main(int argc, char** argv) {
 
292
  grpc_test_init(argc, argv);
 
293
  test_create_table();
 
294
  test_simple_add_and_erase();
 
295
  test_table_with_int_key();
 
296
  test_table_with_string_key();
 
297
  test_value_and_key_deleter();
 
298
  test_insertion_with_same_key();
 
299
  test_insertion_and_deletion_with_high_collision_rate();
 
300
  return 0;
 
301
}