Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 1 | /* |
| 2 | * |
Craig Tiller | 2e19036 | 2016-03-25 14:33:26 -0700 | [diff] [blame] | 3 | * Copyright 2015-2016, Google Inc. |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 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 "src/core/statistics/hash_table.h" |
| 35 | |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 36 | #include <stddef.h> |
Craig Tiller | f40df23 | 2016-03-25 13:38:14 -0700 | [diff] [blame] | 37 | #include <stdio.h> |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 38 | |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 39 | #include <grpc/support/alloc.h> |
Craig Tiller | f40df23 | 2016-03-25 13:38:14 -0700 | [diff] [blame] | 40 | #include <grpc/support/log.h> |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 41 | #include <grpc/support/port_platform.h> |
| 42 | |
| 43 | #define CENSUS_HT_NUM_BUCKETS 1999 |
| 44 | |
| 45 | /* A single hash table data entry */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 46 | typedef struct ht_entry { |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 47 | census_ht_key key; |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 48 | void *data; |
| 49 | struct ht_entry *next; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 50 | } ht_entry; |
| 51 | |
| 52 | /* hash table bucket */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 53 | typedef struct bucket { |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 54 | /* NULL if bucket is empty */ |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 55 | ht_entry *next; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 56 | /* -1 if all buckets are empty. */ |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 57 | int32_t prev_non_empty_bucket; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 58 | /* -1 if all buckets are empty. */ |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 59 | int32_t next_non_empty_bucket; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 60 | } bucket; |
| 61 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 62 | struct unresizable_hash_table { |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 63 | /* Number of entries in the table */ |
| 64 | size_t size; |
| 65 | /* Number of buckets */ |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 66 | uint32_t num_buckets; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 67 | /* Array of buckets initialized at creation time. Memory consumption is |
| 68 | 16 bytes per bucket on a 64-bit platform. */ |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 69 | bucket *buckets; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 70 | /* Index of the first non-empty bucket. -1 iff size == 0. */ |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 71 | int32_t first_non_empty_bucket; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 72 | /* Index of the last non_empty bucket. -1 iff size == 0. */ |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 73 | int32_t last_non_empty_bucket; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 74 | /* Immutable options of this hash table, initialized at creation time. */ |
| 75 | census_ht_option options; |
| 76 | }; |
| 77 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 78 | typedef struct entry_locator { |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 79 | int32_t bucket_idx; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 80 | int is_first_in_chain; |
| 81 | int found; |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 82 | ht_entry *prev_entry; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 83 | } entry_locator; |
| 84 | |
| 85 | /* Asserts if option is not valid. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 86 | void check_options(const census_ht_option *option) { |
| 87 | GPR_ASSERT(option != NULL); |
| 88 | GPR_ASSERT(option->num_buckets > 0); |
| 89 | GPR_ASSERT(option->key_type == CENSUS_HT_UINT64 || |
| 90 | option->key_type == CENSUS_HT_POINTER); |
| 91 | if (option->key_type == CENSUS_HT_UINT64) { |
| 92 | GPR_ASSERT(option->hash == NULL); |
| 93 | } else if (option->key_type == CENSUS_HT_POINTER) { |
| 94 | GPR_ASSERT(option->hash != NULL); |
| 95 | GPR_ASSERT(option->compare_keys != NULL); |
| 96 | } |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 97 | } |
| 98 | |
| 99 | #define REMOVE_NEXT(options, ptr) \ |
| 100 | do { \ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 101 | ht_entry *tmp = (ptr)->next; \ |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 102 | (ptr)->next = tmp->next; \ |
| 103 | delete_entry(options, tmp); \ |
| 104 | } while (0) |
| 105 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 106 | static void delete_entry(const census_ht_option *opt, ht_entry *p) { |
| 107 | if (opt->delete_data != NULL) { |
| 108 | opt->delete_data(p->data); |
| 109 | } |
| 110 | if (opt->delete_key != NULL) { |
| 111 | opt->delete_key(p->key.ptr); |
| 112 | } |
| 113 | gpr_free(p); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 114 | } |
| 115 | |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 116 | static uint64_t hash(const census_ht_option *opt, census_ht_key key) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 117 | return opt->key_type == CENSUS_HT_UINT64 ? key.val : opt->hash(key.ptr); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 118 | } |
| 119 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 120 | census_ht *census_ht_create(const census_ht_option *option) { |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 121 | int i; |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 122 | census_ht *ret = NULL; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 123 | check_options(option); |
| 124 | ret = (census_ht *)gpr_malloc(sizeof(census_ht)); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 125 | ret->size = 0; |
| 126 | ret->num_buckets = option->num_buckets; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 127 | ret->buckets = (bucket *)gpr_malloc(sizeof(bucket) * ret->num_buckets); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 128 | ret->options = *option; |
| 129 | /* initialize each bucket */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 130 | for (i = 0; i < ret->options.num_buckets; i++) { |
| 131 | ret->buckets[i].prev_non_empty_bucket = -1; |
| 132 | ret->buckets[i].next_non_empty_bucket = -1; |
| 133 | ret->buckets[i].next = NULL; |
| 134 | } |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 135 | return ret; |
| 136 | } |
| 137 | |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 138 | static int32_t find_bucket_idx(const census_ht *ht, census_ht_key key) { |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 139 | return hash(&ht->options, key) % ht->num_buckets; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 140 | } |
| 141 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 142 | static int keys_match(const census_ht_option *opt, const ht_entry *p, |
| 143 | const census_ht_key key) { |
| 144 | GPR_ASSERT(opt->key_type == CENSUS_HT_UINT64 || |
| 145 | opt->key_type == CENSUS_HT_POINTER); |
| 146 | if (opt->key_type == CENSUS_HT_UINT64) return p->key.val == key.val; |
| 147 | return !opt->compare_keys((p->key).ptr, key.ptr); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 148 | } |
| 149 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 150 | static entry_locator ht_find(const census_ht *ht, census_ht_key key) { |
| 151 | entry_locator loc = {0, 0, 0, NULL}; |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 152 | int32_t idx = 0; |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 153 | ht_entry *ptr = NULL; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 154 | GPR_ASSERT(ht != NULL); |
| 155 | idx = find_bucket_idx(ht, key); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 156 | ptr = ht->buckets[idx].next; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 157 | if (ptr == NULL) { |
| 158 | /* bucket is empty */ |
| 159 | return loc; |
| 160 | } |
| 161 | if (keys_match(&ht->options, ptr, key)) { |
| 162 | loc.bucket_idx = idx; |
| 163 | loc.is_first_in_chain = 1; |
| 164 | loc.found = 1; |
| 165 | return loc; |
| 166 | } else { |
| 167 | for (; ptr->next != NULL; ptr = ptr->next) { |
| 168 | if (keys_match(&ht->options, ptr->next, key)) { |
| 169 | loc.bucket_idx = idx; |
| 170 | loc.is_first_in_chain = 0; |
| 171 | loc.found = 1; |
| 172 | loc.prev_entry = ptr; |
| 173 | return loc; |
| 174 | } |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 175 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 176 | } |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 177 | /* Could not find the key */ |
| 178 | return loc; |
| 179 | } |
| 180 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 181 | void *census_ht_find(const census_ht *ht, census_ht_key key) { |
| 182 | entry_locator loc = ht_find(ht, key); |
| 183 | if (loc.found == 0) { |
| 184 | return NULL; |
| 185 | } |
| 186 | return loc.is_first_in_chain ? ht->buckets[loc.bucket_idx].next->data |
| 187 | : loc.prev_entry->next->data; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 188 | } |
| 189 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 190 | void census_ht_insert(census_ht *ht, census_ht_key key, void *data) { |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 191 | int32_t idx = find_bucket_idx(ht, key); |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 192 | ht_entry *ptr = NULL; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 193 | entry_locator loc = ht_find(ht, key); |
| 194 | if (loc.found) { |
| 195 | /* Replace old value with new value. */ |
| 196 | ptr = loc.is_first_in_chain ? ht->buckets[loc.bucket_idx].next |
| 197 | : loc.prev_entry->next; |
| 198 | if (ht->options.delete_data != NULL) { |
| 199 | ht->options.delete_data(ptr->data); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 200 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 201 | ptr->data = data; |
| 202 | return; |
| 203 | } |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 204 | |
| 205 | /* first entry in the table. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 206 | if (ht->size == 0) { |
| 207 | ht->buckets[idx].next_non_empty_bucket = -1; |
| 208 | ht->buckets[idx].prev_non_empty_bucket = -1; |
| 209 | ht->first_non_empty_bucket = idx; |
| 210 | ht->last_non_empty_bucket = idx; |
| 211 | } else if (ht->buckets[idx].next == NULL) { |
| 212 | /* first entry in the bucket. */ |
| 213 | ht->buckets[ht->last_non_empty_bucket].next_non_empty_bucket = idx; |
| 214 | ht->buckets[idx].prev_non_empty_bucket = ht->last_non_empty_bucket; |
| 215 | ht->buckets[idx].next_non_empty_bucket = -1; |
| 216 | ht->last_non_empty_bucket = idx; |
| 217 | } |
| 218 | ptr = (ht_entry *)gpr_malloc(sizeof(ht_entry)); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 219 | ptr->key = key; |
| 220 | ptr->data = data; |
| 221 | ptr->next = ht->buckets[idx].next; |
| 222 | ht->buckets[idx].next = ptr; |
| 223 | ht->size++; |
| 224 | } |
| 225 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 226 | void census_ht_erase(census_ht *ht, census_ht_key key) { |
| 227 | entry_locator loc = ht_find(ht, key); |
| 228 | if (loc.found == 0) { |
| 229 | /* noop if not found */ |
| 230 | return; |
| 231 | } |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 232 | ht->size--; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 233 | if (loc.is_first_in_chain) { |
| 234 | bucket *b = &ht->buckets[loc.bucket_idx]; |
| 235 | GPR_ASSERT(b->next != NULL); |
| 236 | /* The only entry in the bucket */ |
| 237 | if (b->next->next == NULL) { |
| 238 | int prev = b->prev_non_empty_bucket; |
| 239 | int next = b->next_non_empty_bucket; |
| 240 | if (prev != -1) { |
| 241 | ht->buckets[prev].next_non_empty_bucket = next; |
| 242 | } else { |
| 243 | ht->first_non_empty_bucket = next; |
| 244 | } |
| 245 | if (next != -1) { |
| 246 | ht->buckets[next].prev_non_empty_bucket = prev; |
| 247 | } else { |
| 248 | ht->last_non_empty_bucket = prev; |
| 249 | } |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 250 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 251 | REMOVE_NEXT(&ht->options, b); |
| 252 | } else { |
| 253 | GPR_ASSERT(loc.prev_entry->next != NULL); |
| 254 | REMOVE_NEXT(&ht->options, loc.prev_entry); |
| 255 | } |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 256 | } |
| 257 | |
| 258 | /* Returns NULL if input table is empty. */ |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 259 | census_ht_kv *census_ht_get_all_elements(const census_ht *ht, size_t *num) { |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 260 | census_ht_kv *ret = NULL; |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 261 | int i = 0; |
Craig Tiller | 7536af0 | 2015-12-22 13:49:30 -0800 | [diff] [blame] | 262 | int32_t idx = -1; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 263 | GPR_ASSERT(ht != NULL && num != NULL); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 264 | *num = ht->size; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 265 | if (*num == 0) { |
| 266 | return NULL; |
| 267 | } |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 268 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 269 | ret = (census_ht_kv *)gpr_malloc(sizeof(census_ht_kv) * ht->size); |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 270 | idx = ht->first_non_empty_bucket; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 271 | while (idx >= 0) { |
| 272 | ht_entry *ptr = ht->buckets[idx].next; |
| 273 | for (; ptr != NULL; ptr = ptr->next) { |
| 274 | ret[i].k = ptr->key; |
| 275 | ret[i].v = ptr->data; |
| 276 | i++; |
Craig Tiller | 45724b3 | 2015-09-22 10:42:19 -0700 | [diff] [blame] | 277 | } |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 278 | idx = ht->buckets[idx].next_non_empty_bucket; |
| 279 | } |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 280 | return ret; |
| 281 | } |
| 282 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 283 | static void ht_delete_entry_chain(const census_ht_option *options, |
| 284 | ht_entry *first) { |
| 285 | if (first == NULL) { |
| 286 | return; |
| 287 | } |
| 288 | if (first->next != NULL) { |
| 289 | ht_delete_entry_chain(options, first->next); |
| 290 | } |
| 291 | delete_entry(options, first); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 292 | } |
| 293 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 294 | void census_ht_destroy(census_ht *ht) { |
Nicolas "Pixel" Noble | 213ed91 | 2015-01-30 02:11:35 +0100 | [diff] [blame] | 295 | unsigned i; |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 296 | for (i = 0; i < ht->num_buckets; ++i) { |
| 297 | ht_delete_entry_chain(&ht->options, ht->buckets[i].next); |
| 298 | } |
| 299 | gpr_free(ht->buckets); |
| 300 | gpr_free(ht); |
Nicolas Noble | b7ebd3b | 2014-11-26 16:33:03 -0800 | [diff] [blame] | 301 | } |
| 302 | |
Craig Tiller | a82950e | 2015-09-22 12:33:20 -0700 | [diff] [blame] | 303 | size_t census_ht_get_size(const census_ht *ht) { return ht->size; } |