Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 1 | // |
| 2 | // Copyright 2016, Google Inc. |
| 3 | // All rights reserved. |
| 4 | // |
| 5 | // Redistribution and use in source and binary forms, with or without |
| 6 | // modification, are permitted provided that the following conditions are |
| 7 | // met: |
| 8 | // |
| 9 | // * Redistributions of source code must retain the above copyright |
| 10 | // notice, this list of conditions and the following disclaimer. |
| 11 | // * Redistributions in binary form must reproduce the above |
| 12 | // copyright notice, this list of conditions and the following disclaimer |
| 13 | // in the documentation and/or other materials provided with the |
| 14 | // distribution. |
| 15 | // * Neither the name of Google Inc. nor the names of its |
| 16 | // contributors may be used to endorse or promote products derived from |
| 17 | // this software without specific prior written permission. |
| 18 | // |
| 19 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 20 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 21 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 22 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 23 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 24 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 25 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 26 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 27 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 28 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 29 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 30 | // |
| 31 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 32 | #include "src/core/lib/slice/slice_hash_table.h" |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 33 | |
| 34 | #include <stdbool.h> |
| 35 | #include <string.h> |
| 36 | |
| 37 | #include <grpc/support/alloc.h> |
| 38 | #include <grpc/support/log.h> |
| 39 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 40 | #include "src/core/lib/slice/slice_internal.h" |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 41 | #include "src/core/lib/transport/metadata.h" |
| 42 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 43 | struct grpc_slice_hash_table { |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 44 | gpr_refcount refs; |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 45 | size_t size; |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 46 | grpc_slice_hash_table_entry* entries; |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 47 | }; |
| 48 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 49 | static bool is_empty(grpc_slice_hash_table_entry* entry) { |
| 50 | return entry->vtable == NULL; |
| 51 | } |
| 52 | |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 53 | // Helper function for insert and get operations that performs quadratic |
| 54 | // probing (https://en.wikipedia.org/wiki/Quadratic_probing). |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 55 | static size_t grpc_slice_hash_table_find_index( |
| 56 | const grpc_slice_hash_table* table, const grpc_slice key, bool find_empty) { |
| 57 | size_t hash = grpc_slice_hash(key); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 58 | for (size_t i = 0; i < table->size; ++i) { |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 59 | const size_t idx = (hash + i * i) % table->size; |
| 60 | if (is_empty(&table->entries[idx])) { |
| 61 | return find_empty ? idx : table->size; |
| 62 | } |
| 63 | if (grpc_slice_eq(table->entries[idx].key, key)) { |
| 64 | return idx; |
| 65 | } |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 66 | } |
| 67 | return table->size; // Not found. |
| 68 | } |
| 69 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 70 | static void grpc_slice_hash_table_add( |
| 71 | grpc_slice_hash_table* table, grpc_slice key, void* value, |
| 72 | const grpc_slice_hash_table_vtable* vtable) { |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 73 | GPR_ASSERT(value != NULL); |
| 74 | const size_t idx = |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 75 | grpc_slice_hash_table_find_index(table, key, true /* find_empty */); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 76 | GPR_ASSERT(idx != table->size); // Table should never be full. |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 77 | grpc_slice_hash_table_entry* entry = &table->entries[idx]; |
| 78 | entry->key = grpc_slice_ref_internal(key); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 79 | entry->value = vtable->copy_value(value); |
| 80 | entry->vtable = vtable; |
| 81 | } |
| 82 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 83 | grpc_slice_hash_table* grpc_slice_hash_table_create( |
| 84 | size_t num_entries, grpc_slice_hash_table_entry* entries) { |
Craig Tiller | 6f41788 | 2017-02-16 14:09:39 -0800 | [diff] [blame] | 85 | grpc_slice_hash_table* table = gpr_zalloc(sizeof(*table)); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 86 | gpr_ref_init(&table->refs, 1); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 87 | // Quadratic probing gets best performance when the table is no more |
| 88 | // than half full. |
| 89 | table->size = num_entries * 2; |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 90 | const size_t entry_size = sizeof(grpc_slice_hash_table_entry) * table->size; |
Craig Tiller | 6f41788 | 2017-02-16 14:09:39 -0800 | [diff] [blame] | 91 | table->entries = gpr_zalloc(entry_size); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 92 | for (size_t i = 0; i < num_entries; ++i) { |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 93 | grpc_slice_hash_table_entry* entry = &entries[i]; |
| 94 | grpc_slice_hash_table_add(table, entry->key, entry->value, entry->vtable); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 95 | } |
| 96 | return table; |
| 97 | } |
| 98 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 99 | grpc_slice_hash_table* grpc_slice_hash_table_ref(grpc_slice_hash_table* table) { |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 100 | if (table != NULL) gpr_ref(&table->refs); |
| 101 | return table; |
| 102 | } |
| 103 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 104 | void grpc_slice_hash_table_unref(grpc_exec_ctx* exec_ctx, |
| 105 | grpc_slice_hash_table* table) { |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 106 | if (table != NULL && gpr_unref(&table->refs)) { |
| 107 | for (size_t i = 0; i < table->size; ++i) { |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 108 | grpc_slice_hash_table_entry* entry = &table->entries[i]; |
| 109 | if (!is_empty(entry)) { |
| 110 | grpc_slice_unref_internal(exec_ctx, entry->key); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 111 | entry->vtable->destroy_value(exec_ctx, entry->value); |
| 112 | } |
| 113 | } |
| 114 | gpr_free(table->entries); |
| 115 | gpr_free(table); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 116 | } |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 117 | } |
| 118 | |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 119 | void* grpc_slice_hash_table_get(const grpc_slice_hash_table* table, |
| 120 | const grpc_slice key) { |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 121 | const size_t idx = |
Craig Tiller | 7c70b6c | 2017-01-23 07:48:42 -0800 | [diff] [blame] | 122 | grpc_slice_hash_table_find_index(table, key, false /* find_empty */); |
Craig Tiller | 5ef31ab | 2016-11-10 16:27:48 -0800 | [diff] [blame] | 123 | if (idx == table->size) return NULL; // Not found. |
| 124 | return table->entries[idx].value; |
| 125 | } |