diff options
author | Craig Tiller <ctiller@google.com> | 2016-03-25 17:07:29 -0700 |
---|---|---|
committer | Craig Tiller <ctiller@google.com> | 2016-03-25 17:07:29 -0700 |
commit | f23078cbd302d32649537eedda1769c5685228d8 (patch) | |
tree | b0bb46845658e5b8256868d102076226aa10215e /src/core/transport/chttp2/stream_map.c | |
parent | f3d76384351039266e250aacf97c90d5b0c07dca (diff) |
Stage #1 of core breakup: move everything under lib
Diffstat (limited to 'src/core/transport/chttp2/stream_map.c')
-rw-r--r-- | src/core/transport/chttp2/stream_map.c | 197 |
1 files changed, 0 insertions, 197 deletions
diff --git a/src/core/transport/chttp2/stream_map.c b/src/core/transport/chttp2/stream_map.c deleted file mode 100644 index 555a16fb72..0000000000 --- a/src/core/transport/chttp2/stream_map.c +++ /dev/null @@ -1,197 +0,0 @@ -/* - * - * Copyright 2015, 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/transport/chttp2/stream_map.h" - -#include <string.h> - -#include <grpc/support/alloc.h> -#include <grpc/support/log.h> -#include <grpc/support/useful.h> - -void grpc_chttp2_stream_map_init(grpc_chttp2_stream_map *map, - size_t initial_capacity) { - GPR_ASSERT(initial_capacity > 1); - map->keys = gpr_malloc(sizeof(uint32_t) * initial_capacity); - map->values = gpr_malloc(sizeof(void *) * initial_capacity); - map->count = 0; - map->free = 0; - map->capacity = initial_capacity; -} - -void grpc_chttp2_stream_map_destroy(grpc_chttp2_stream_map *map) { - gpr_free(map->keys); - gpr_free(map->values); -} - -static size_t compact(uint32_t *keys, void **values, size_t count) { - size_t i, out; - - for (i = 0, out = 0; i < count; i++) { - if (values[i]) { - keys[out] = keys[i]; - values[out] = values[i]; - out++; - } - } - - return out; -} - -void grpc_chttp2_stream_map_add(grpc_chttp2_stream_map *map, uint32_t key, - void *value) { - size_t count = map->count; - size_t capacity = map->capacity; - uint32_t *keys = map->keys; - void **values = map->values; - - GPR_ASSERT(count == 0 || keys[count - 1] < key); - GPR_ASSERT(value); - - if (count == capacity) { - if (map->free > capacity / 4) { - count = compact(keys, values, count); - map->free = 0; - } else { - /* resize when less than 25% of the table is free, because compaction - won't help much */ - map->capacity = capacity = 3 * capacity / 2; - map->keys = keys = gpr_realloc(keys, capacity * sizeof(uint32_t)); - map->values = values = gpr_realloc(values, capacity * sizeof(void *)); - } - } - - keys[count] = key; - values[count] = value; - map->count = count + 1; -} - -void grpc_chttp2_stream_map_move_into(grpc_chttp2_stream_map *src, - grpc_chttp2_stream_map *dst) { - /* if src is empty we dont need to do anything */ - if (src->count == src->free) { - return; - } - /* if dst is empty we simply need to swap */ - if (dst->count == dst->free) { - GPR_SWAP(grpc_chttp2_stream_map, *src, *dst); - return; - } - /* the first element of src must be greater than the last of dst... - * however the maps may need compacting for this property to hold */ - if (src->keys[0] <= dst->keys[dst->count - 1]) { - src->count = compact(src->keys, src->values, src->count); - src->free = 0; - dst->count = compact(dst->keys, dst->values, dst->count); - dst->free = 0; - } - GPR_ASSERT(src->keys[0] > dst->keys[dst->count - 1]); - /* if dst doesn't have capacity, resize */ - if (dst->count + src->count > dst->capacity) { - dst->capacity = GPR_MAX(dst->capacity * 3 / 2, dst->count + src->count); - dst->keys = gpr_realloc(dst->keys, dst->capacity * sizeof(uint32_t)); - dst->values = gpr_realloc(dst->values, dst->capacity * sizeof(void *)); - } - memcpy(dst->keys + dst->count, src->keys, src->count * sizeof(uint32_t)); - memcpy(dst->values + dst->count, src->values, src->count * sizeof(void *)); - dst->count += src->count; - dst->free += src->free; - src->count = 0; - src->free = 0; -} - -static void **find(grpc_chttp2_stream_map *map, uint32_t key) { - size_t min_idx = 0; - size_t max_idx = map->count; - size_t mid_idx; - uint32_t *keys = map->keys; - void **values = map->values; - uint32_t mid_key; - - if (max_idx == 0) return NULL; - - while (min_idx < max_idx) { - /* find the midpoint, avoiding overflow */ - mid_idx = min_idx + ((max_idx - min_idx) / 2); - mid_key = keys[mid_idx]; - - if (mid_key < key) { - min_idx = mid_idx + 1; - } else if (mid_key > key) { - max_idx = mid_idx; - } else /* mid_key == key */ - { - return &values[mid_idx]; - } - } - - return NULL; -} - -void *grpc_chttp2_stream_map_delete(grpc_chttp2_stream_map *map, uint32_t key) { - void **pvalue = find(map, key); - void *out = NULL; - if (pvalue != NULL) { - out = *pvalue; - *pvalue = NULL; - map->free += (out != NULL); - /* recognize complete emptyness and ensure we can skip - * defragmentation later */ - if (map->free == map->count) { - map->free = map->count = 0; - } - } - return out; -} - -void *grpc_chttp2_stream_map_find(grpc_chttp2_stream_map *map, uint32_t key) { - void **pvalue = find(map, key); - return pvalue != NULL ? *pvalue : NULL; -} - -size_t grpc_chttp2_stream_map_size(grpc_chttp2_stream_map *map) { - return map->count - map->free; -} - -void grpc_chttp2_stream_map_for_each(grpc_chttp2_stream_map *map, - void (*f)(void *user_data, uint32_t key, - void *value), - void *user_data) { - size_t i; - - for (i = 0; i < map->count; i++) { - if (map->values[i]) { - f(user_data, map->keys[i], map->values[i]); - } - } -} |