Home | History | Annotate | Download | only in transport 
      1 /*
      2  *
      3  * Copyright 2015 gRPC authors.
      4  *
      5  * Licensed under the Apache License, Version 2.0 (the "License");
      6  * you may not use this file except in compliance with the License.
      7  * You may obtain a copy of the License at
      8  *
      9  *     http://www.apache.org/licenses/LICENSE-2.0
     10  *
     11  * Unless required by applicable law or agreed to in writing, software
     12  * distributed under the License is distributed on an "AS IS" BASIS,
     13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14  * See the License for the specific language governing permissions and
     15  * limitations under the License.
     16  *
     17  */
     18 
     19 #include <grpc/support/port_platform.h>
     20 
     21 #include "src/core/ext/transport/chttp2/transport/stream_map.h"
     22 
     23 #include <string.h>
     24 
     25 #include <grpc/support/alloc.h>
     26 #include <grpc/support/log.h>
     27 
     28 void grpc_chttp2_stream_map_init(grpc_chttp2_stream_map* map,
     29                                  size_t initial_capacity) {
     30   GPR_ASSERT(initial_capacity > 1);
     31   map->keys =
     32       static_cast<uint32_t*>(gpr_malloc(sizeof(uint32_t) * initial_capacity));
     33   map->values =
     34       static_cast<void**>(gpr_malloc(sizeof(void*) * initial_capacity));
     35   map->count = 0;
     36   map->free = 0;
     37   map->capacity = initial_capacity;
     38 }
     39 
     40 void grpc_chttp2_stream_map_destroy(grpc_chttp2_stream_map* map) {
     41   gpr_free(map->keys);
     42   gpr_free(map->values);
     43 }
     44 
     45 static size_t compact(uint32_t* keys, void** values, size_t count) {
     46   size_t i, out;
     47 
     48   for (i = 0, out = 0; i < count; i++) {
     49     if (values[i]) {
     50       keys[out] = keys[i];
     51       values[out] = values[i];
     52       out++;
     53     }
     54   }
     55 
     56   return out;
     57 }
     58 
     59 void grpc_chttp2_stream_map_add(grpc_chttp2_stream_map* map, uint32_t key,
     60                                 void* value) {
     61   size_t count = map->count;
     62   size_t capacity = map->capacity;
     63   uint32_t* keys = map->keys;
     64   void** values = map->values;
     65 
     66   GPR_ASSERT(count == 0 || keys[count - 1] < key);
     67   GPR_ASSERT(value);
     68   GPR_ASSERT(grpc_chttp2_stream_map_find(map, key) == nullptr);
     69 
     70   if (count == capacity) {
     71     if (map->free > capacity / 4) {
     72       count = compact(keys, values, count);
     73       map->free = 0;
     74     } else {
     75       /* resize when less than 25% of the table is free, because compaction
     76          won't help much */
     77       map->capacity = capacity = 3 * capacity / 2;
     78       map->keys = keys = static_cast<uint32_t*>(
     79           gpr_realloc(keys, capacity * sizeof(uint32_t)));
     80       map->values = values =
     81           static_cast<void**>(gpr_realloc(values, capacity * sizeof(void*)));
     82     }
     83   }
     84 
     85   keys[count] = key;
     86   values[count] = value;
     87   map->count = count + 1;
     88 }
     89 
     90 static void** find(grpc_chttp2_stream_map* map, uint32_t key) {
     91   size_t min_idx = 0;
     92   size_t max_idx = map->count;
     93   size_t mid_idx;
     94   uint32_t* keys = map->keys;
     95   void** values = map->values;
     96   uint32_t mid_key;
     97 
     98   if (max_idx == 0) return nullptr;
     99 
    100   while (min_idx < max_idx) {
    101     /* find the midpoint, avoiding overflow */
    102     mid_idx = min_idx + ((max_idx - min_idx) / 2);
    103     mid_key = keys[mid_idx];
    104 
    105     if (mid_key < key) {
    106       min_idx = mid_idx + 1;
    107     } else if (mid_key > key) {
    108       max_idx = mid_idx;
    109     } else /* mid_key == key */
    110     {
    111       return &values[mid_idx];
    112     }
    113   }
    114 
    115   return nullptr;
    116 }
    117 
    118 void* grpc_chttp2_stream_map_delete(grpc_chttp2_stream_map* map, uint32_t key) {
    119   void** pvalue = find(map, key);
    120   void* out = nullptr;
    121   if (pvalue != nullptr) {
    122     out = *pvalue;
    123     *pvalue = nullptr;
    124     map->free += (out != nullptr);
    125     /* recognize complete emptyness and ensure we can skip
    126      * defragmentation later */
    127     if (map->free == map->count) {
    128       map->free = map->count = 0;
    129     }
    130     GPR_ASSERT(grpc_chttp2_stream_map_find(map, key) == nullptr);
    131   }
    132   return out;
    133 }
    134 
    135 void* grpc_chttp2_stream_map_find(grpc_chttp2_stream_map* map, uint32_t key) {
    136   void** pvalue = find(map, key);
    137   return pvalue != nullptr ? *pvalue : nullptr;
    138 }
    139 
    140 size_t grpc_chttp2_stream_map_size(grpc_chttp2_stream_map* map) {
    141   return map->count - map->free;
    142 }
    143 
    144 void* grpc_chttp2_stream_map_rand(grpc_chttp2_stream_map* map) {
    145   if (map->count == map->free) {
    146     return nullptr;
    147   }
    148   if (map->free != 0) {
    149     map->count = compact(map->keys, map->values, map->count);
    150     map->free = 0;
    151     GPR_ASSERT(map->count > 0);
    152   }
    153   return map->values[(static_cast<size_t>(rand())) % map->count];
    154 }
    155 
    156 void grpc_chttp2_stream_map_for_each(grpc_chttp2_stream_map* map,
    157                                      void (*f)(void* user_data, uint32_t key,
    158                                                void* value),
    159                                      void* user_data) {
    160   size_t i;
    161 
    162   for (i = 0; i < map->count; i++) {
    163     if (map->values[i]) {
    164       f(user_data, map->keys[i], map->values[i]);
    165     }
    166   }
    167 }
    168