diff options
Diffstat (limited to 'src/core/lib/slice')
| -rw-r--r-- | src/core/lib/slice/slice.c | 2 | ||||
| -rw-r--r-- | src/core/lib/slice/slice_hash_table.c | 174 | ||||
| -rw-r--r-- | src/core/lib/slice/slice_hash_table.h | 93 | ||||
| -rw-r--r-- | src/core/lib/slice/slice_string_helpers.h | 3 | ||||
| -rw-r--r-- | src/core/lib/slice/slice_traits.h | 44 |
5 files changed, 315 insertions, 1 deletions
diff --git a/src/core/lib/slice/slice.c b/src/core/lib/slice/slice.c index a85a52b2c6..dc3e6fd93d 100644 --- a/src/core/lib/slice/slice.c +++ b/src/core/lib/slice/slice.c @@ -41,7 +41,7 @@ #include "src/core/lib/iomgr/exec_ctx.h" -grpc_slice gpr_empty_slice(void) { +grpc_slice grpc_empty_slice(void) { grpc_slice out; out.refcount = 0; out.data.inlined.length = 0; diff --git a/src/core/lib/slice/slice_hash_table.c b/src/core/lib/slice/slice_hash_table.c new file mode 100644 index 0000000000..7e6f705164 --- /dev/null +++ b/src/core/lib/slice/slice_hash_table.c @@ -0,0 +1,174 @@ +// +// Copyright 2016, Google Inc. +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// + +#include "src/core/lib/slice/slice_hash_table.h" + +#include <stdbool.h> +#include <string.h> + +#include <grpc/support/alloc.h> +#include <grpc/support/log.h> + +#include "src/core/lib/slice/slice_internal.h" +#include "src/core/lib/transport/metadata.h" + +static grpc_slice_refcount terminal_slice_refcount = {NULL, NULL}; +static const grpc_slice terminal_slice = {&terminal_slice_refcount, + .data.refcounted = {0, 0}}; + +struct grpc_slice_hash_table { + gpr_refcount refs; + size_t num_entries; + size_t size; + grpc_slice_hash_table_entry* entries; +}; + +static bool is_terminal(grpc_slice slice) { + return slice.refcount == &terminal_slice_refcount; +} + +// Helper function for insert and get operations that performs quadratic +// probing (https://en.wikipedia.org/wiki/Quadratic_probing). +static size_t grpc_slice_hash_table_find_index( + const grpc_slice_hash_table* table, const grpc_slice key, bool find_empty) { + size_t hash = grpc_slice_hash(key); + for (size_t i = 0; i < table->size; ++i) { + const size_t idx = (hash + i * i) % table->size; + if (is_terminal(table->entries[idx].key)) { + return find_empty ? idx : table->size; + } + if (grpc_slice_cmp(table->entries[idx].key, key) == 0) { + return idx; + } + } + return table->size; // Not found. +} + +static void grpc_slice_hash_table_add( + grpc_slice_hash_table* table, grpc_slice key, void* value, + const grpc_slice_hash_table_vtable* vtable) { + GPR_ASSERT(value != NULL); + const size_t idx = + grpc_slice_hash_table_find_index(table, key, true /* find_empty */); + GPR_ASSERT(idx != table->size); // Table should never be full. + grpc_slice_hash_table_entry* entry = &table->entries[idx]; + entry->key = grpc_slice_ref(key); + entry->value = vtable->copy_value(value); + entry->vtable = vtable; +} + +grpc_slice_hash_table* grpc_slice_hash_table_create( + size_t num_entries, grpc_slice_hash_table_entry* entries) { + grpc_slice_hash_table* table = gpr_malloc(sizeof(*table)); + memset(table, 0, sizeof(*table)); + gpr_ref_init(&table->refs, 1); + table->num_entries = num_entries; + // Quadratic probing gets best performance when the table is no more + // than half full. + table->size = num_entries * 2; + const size_t entry_size = sizeof(grpc_slice_hash_table_entry) * table->size; + table->entries = gpr_malloc(entry_size); + memset(table->entries, 0, entry_size); + for (size_t i = 0; i < num_entries; ++i) { + table->entries[i].key = terminal_slice; + } + for (size_t i = 0; i < num_entries; ++i) { + grpc_slice_hash_table_entry* entry = &entries[i]; + grpc_slice_hash_table_add(table, entry->key, entry->value, entry->vtable); + } + return table; +} + +grpc_slice_hash_table* grpc_slice_hash_table_ref(grpc_slice_hash_table* table) { + if (table != NULL) gpr_ref(&table->refs); + return table; +} + +int grpc_slice_hash_table_unref(grpc_exec_ctx* exec_ctx, + grpc_slice_hash_table* table) { + if (table != NULL && gpr_unref(&table->refs)) { + for (size_t i = 0; i < table->size; ++i) { + grpc_slice_hash_table_entry* entry = &table->entries[i]; + if (!is_terminal(entry->key)) { + grpc_slice_unref_internal(exec_ctx, entry->key); + entry->vtable->destroy_value(exec_ctx, entry->value); + } + } + gpr_free(table->entries); + gpr_free(table); + return 1; + } + return 0; +} + +size_t grpc_slice_hash_table_num_entries(const grpc_slice_hash_table* table) { + return table->num_entries; +} + +void* grpc_slice_hash_table_get(const grpc_slice_hash_table* table, + const grpc_slice key) { + const size_t idx = + grpc_slice_hash_table_find_index(table, key, false /* find_empty */); + if (idx == table->size) return NULL; // Not found. + return table->entries[idx].value; +} + +int grpc_slice_hash_table_cmp(const grpc_slice_hash_table* table1, + const grpc_slice_hash_table* table2) { + // Compare by num_entries. + if (table1->num_entries < table2->num_entries) return -1; + if (table1->num_entries > table2->num_entries) return 1; + for (size_t i = 0; i < table1->num_entries; ++i) { + grpc_slice_hash_table_entry* e1 = &table1->entries[i]; + grpc_slice_hash_table_entry* e2 = &table2->entries[i]; + // Compare keys by hash value. + int cmp = grpc_slice_cmp(e1->key, e2->key); + if (cmp != 0) return cmp; + // Compare by vtable (pointer equality). + if (e1->vtable < e2->vtable) return -1; + if (e1->vtable > e2->vtable) return 1; + // Compare values via vtable. + const int value_result = e1->vtable->compare_value(e1->value, e2->value); + if (value_result != 0) return value_result; + } + return 0; +} + +void grpc_slice_hash_table_iterate( + const grpc_slice_hash_table* table, + void (*func)(const grpc_slice_hash_table_entry* entry, void* user_data), + void* user_data) { + for (size_t i = 0; i < table->size; ++i) { + if (!is_terminal(table->entries[i].key)) { + func(&table->entries[i], user_data); + } + } +} diff --git a/src/core/lib/slice/slice_hash_table.h b/src/core/lib/slice/slice_hash_table.h new file mode 100644 index 0000000000..ac04950cc6 --- /dev/null +++ b/src/core/lib/slice/slice_hash_table.h @@ -0,0 +1,93 @@ +/* + * Copyright 2016, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef GRPC_CORE_LIB_TRANSPORT_MDSTR_HASH_TABLE_H +#define GRPC_CORE_LIB_TRANSPORT_MDSTR_HASH_TABLE_H + +#include "src/core/lib/transport/metadata.h" + +/** Hash table implementation. + * + * This implementation uses open addressing + * (https://en.wikipedia.org/wiki/Open_addressing) with quadratic + * probing (https://en.wikipedia.org/wiki/Quadratic_probing). + * + * The keys are \a grpc_slice objects. The values are arbitrary pointers + * with a common vtable. + * + * Hash tables are intentionally immutable, to avoid the need for locking. + */ + +typedef struct grpc_slice_hash_table grpc_slice_hash_table; + +typedef struct grpc_slice_hash_table_vtable { + void (*destroy_value)(grpc_exec_ctx *exec_ctx, void *value); + void *(*copy_value)(void *value); + int (*compare_value)(void *value1, void *value2); +} grpc_slice_hash_table_vtable; + +typedef struct grpc_slice_hash_table_entry { + grpc_slice key; + void *value; /* Must not be NULL. */ + const grpc_slice_hash_table_vtable *vtable; +} grpc_slice_hash_table_entry; + +/** Creates a new hash table of containing \a entries, which is an array + of length \a num_entries. + Creates its own copy of all keys and values from \a entries. */ +grpc_slice_hash_table *grpc_slice_hash_table_create( + size_t num_entries, grpc_slice_hash_table_entry *entries); + +grpc_slice_hash_table *grpc_slice_hash_table_ref(grpc_slice_hash_table *table); +/** Returns 1 when \a table is destroyed. */ +int grpc_slice_hash_table_unref(grpc_exec_ctx *exec_ctx, + grpc_slice_hash_table *table); + +/** Returns the number of entries in \a table. */ +size_t grpc_slice_hash_table_num_entries(const grpc_slice_hash_table *table); + +/** Returns the value from \a table associated with \a key. + Returns NULL if \a key is not found. */ +void *grpc_slice_hash_table_get(const grpc_slice_hash_table *table, + const grpc_slice key); + +/** Compares two hash tables. + The sort order is stable but undefined. */ +int grpc_slice_hash_table_cmp(const grpc_slice_hash_table *table1, + const grpc_slice_hash_table *table2); + +/** Iterates over the entries in \a table, calling \a func for each entry. */ +void grpc_slice_hash_table_iterate( + const grpc_slice_hash_table *table, + void (*func)(const grpc_slice_hash_table_entry *entry, void *user_data), + void *user_data); + +#endif /* GRPC_CORE_LIB_TRANSPORT_MDSTR_HASH_TABLE_H */ diff --git a/src/core/lib/slice/slice_string_helpers.h b/src/core/lib/slice/slice_string_helpers.h index c6f4e87c7f..4a4deec6e5 100644 --- a/src/core/lib/slice/slice_string_helpers.h +++ b/src/core/lib/slice/slice_string_helpers.h @@ -34,6 +34,7 @@ #ifndef GRPC_CORE_LIB_SLICE_SLICE_STRING_HELPERS_H #define GRPC_CORE_LIB_SLICE_SLICE_STRING_HELPERS_H +#include <stdbool.h> #include <stddef.h> #include <grpc/slice.h> @@ -53,6 +54,8 @@ char *grpc_dump_slice(grpc_slice slice, uint32_t flags); * should be a properly initialized instance. */ void grpc_slice_split(grpc_slice str, const char *sep, grpc_slice_buffer *dst); +bool grpc_parse_slice_to_uint32(grpc_slice str, uint32_t *result); + #ifdef __cplusplus } #endif diff --git a/src/core/lib/slice/slice_traits.h b/src/core/lib/slice/slice_traits.h new file mode 100644 index 0000000000..facbd0dd81 --- /dev/null +++ b/src/core/lib/slice/slice_traits.h @@ -0,0 +1,44 @@ +/* + * + * Copyright 2016, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + */ + +#ifndef SLICE_TRAITS_H +#define SLICE_TRAITS_H + +#include <grpc/slice.h> +#include <stdbool.h> + +bool grpc_slice_is_legal_header(grpc_slice s); +bool grpc_slice_is_legal_nonbin_header(grpc_slice s); +bool grpc_slice_is_bin_suffixed(grpc_slice s); + +#endif |