lsquic_trechist.c revision 06b2a236
106b2a236SDmitri Tikhonov/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc. See LICENSE. */ 2fbc6cc04SDmitri Tikhonov#include <assert.h> 3fbc6cc04SDmitri Tikhonov#include <limits.h> 4fbc6cc04SDmitri Tikhonov#include <stddef.h> 5fbc6cc04SDmitri Tikhonov#include <stdint.h> 6fbc6cc04SDmitri Tikhonov 7fbc6cc04SDmitri Tikhonov#include "lsquic_int_types.h" 8fbc6cc04SDmitri Tikhonov#include "lsquic_trechist.h" 9fbc6cc04SDmitri Tikhonov 10fbc6cc04SDmitri Tikhonov 11fbc6cc04SDmitri Tikhonovstatic unsigned 12fbc6cc04SDmitri Tikhonovfind_free_slot (uint32_t slots) 13fbc6cc04SDmitri Tikhonov{ 14fbc6cc04SDmitri Tikhonov#if __GNUC__ 15fbc6cc04SDmitri Tikhonov return __builtin_ctz(~slots); 16fbc6cc04SDmitri Tikhonov#else 17fbc6cc04SDmitri Tikhonov unsigned n; 18fbc6cc04SDmitri Tikhonov 19fbc6cc04SDmitri Tikhonov slots =~ slots; 20fbc6cc04SDmitri Tikhonov n = 0; 21fbc6cc04SDmitri Tikhonov 22fbc6cc04SDmitri Tikhonov if (0 == (slots & ((1ULL << 16) - 1))) { n += 16; slots >>= 16; } 23fbc6cc04SDmitri Tikhonov if (0 == (slots & ((1ULL << 8) - 1))) { n += 8; slots >>= 8; } 24fbc6cc04SDmitri Tikhonov if (0 == (slots & ((1ULL << 4) - 1))) { n += 4; slots >>= 4; } 25fbc6cc04SDmitri Tikhonov if (0 == (slots & ((1ULL << 2) - 1))) { n += 2; slots >>= 2; } 26fbc6cc04SDmitri Tikhonov if (0 == (slots & ((1ULL << 1) - 1))) { n += 1; slots >>= 1; } 27fbc6cc04SDmitri Tikhonov return n; 28fbc6cc04SDmitri Tikhonov#endif 29fbc6cc04SDmitri Tikhonov} 30fbc6cc04SDmitri Tikhonov 31fbc6cc04SDmitri Tikhonov 32fbc6cc04SDmitri Tikhonov/* Returns 0 on success, 1 if dup, -1 if out of elements */ 33fbc6cc04SDmitri Tikhonovint 34fbc6cc04SDmitri Tikhonovlsquic_trechist_insert (trechist_mask_t *mask, struct trechist_elem *elems, 35fbc6cc04SDmitri Tikhonov uint32_t packno) 36fbc6cc04SDmitri Tikhonov{ 37fbc6cc04SDmitri Tikhonov struct trechist_elem *el, *prev; 38fbc6cc04SDmitri Tikhonov unsigned idx; 39fbc6cc04SDmitri Tikhonov 40fbc6cc04SDmitri Tikhonov if (*mask == 0) 41fbc6cc04SDmitri Tikhonov { 42fbc6cc04SDmitri Tikhonov elems[0].te_low = packno; 43fbc6cc04SDmitri Tikhonov elems[0].te_count = 1; 44fbc6cc04SDmitri Tikhonov elems[0].te_next = 0; 45fbc6cc04SDmitri Tikhonov *mask |= 1; 46fbc6cc04SDmitri Tikhonov return 0; 47fbc6cc04SDmitri Tikhonov } 48fbc6cc04SDmitri Tikhonov 49fbc6cc04SDmitri Tikhonov el = elems; 50fbc6cc04SDmitri Tikhonov prev = NULL; 51fbc6cc04SDmitri Tikhonov while (1) 52fbc6cc04SDmitri Tikhonov { 53fbc6cc04SDmitri Tikhonov if (packno > TE_HIGH(el) + 1) 54fbc6cc04SDmitri Tikhonov goto insert_before; 55fbc6cc04SDmitri Tikhonov if (packno == el->te_low - 1) 56fbc6cc04SDmitri Tikhonov { 57fbc6cc04SDmitri Tikhonov if (el->te_count == UCHAR_MAX) 58fbc6cc04SDmitri Tikhonov return -1; 59fbc6cc04SDmitri Tikhonov --el->te_low; 60fbc6cc04SDmitri Tikhonov ++el->te_count; 61fbc6cc04SDmitri Tikhonov if (el->te_next && el->te_low == TE_HIGH(&elems[el->te_next]) + 1) 62fbc6cc04SDmitri Tikhonov { 63fbc6cc04SDmitri Tikhonov *mask &= ~(1u << el->te_next); 64fbc6cc04SDmitri Tikhonov el->te_count += elems[el->te_next].te_count; 65fbc6cc04SDmitri Tikhonov el->te_low = elems[el->te_next].te_low; 66fbc6cc04SDmitri Tikhonov el->te_next = elems[el->te_next].te_next; 67fbc6cc04SDmitri Tikhonov } 68fbc6cc04SDmitri Tikhonov return 0; 69fbc6cc04SDmitri Tikhonov } 70fbc6cc04SDmitri Tikhonov if (packno == TE_HIGH(el) + 1) 71fbc6cc04SDmitri Tikhonov { 72fbc6cc04SDmitri Tikhonov if (el->te_count == UCHAR_MAX) 73fbc6cc04SDmitri Tikhonov return -1; 74fbc6cc04SDmitri Tikhonov ++el->te_count; 75fbc6cc04SDmitri Tikhonov return 0; 76fbc6cc04SDmitri Tikhonov } 77fbc6cc04SDmitri Tikhonov if (packno >= el->te_low && packno <= TE_HIGH(el)) 78fbc6cc04SDmitri Tikhonov return 1; /* Dup */ 79fbc6cc04SDmitri Tikhonov if (!el->te_next) 80fbc6cc04SDmitri Tikhonov break; /* insert tail */ 81fbc6cc04SDmitri Tikhonov prev = el; 82fbc6cc04SDmitri Tikhonov el = &elems[el->te_next]; 83fbc6cc04SDmitri Tikhonov } 84fbc6cc04SDmitri Tikhonov 85fbc6cc04SDmitri Tikhonov if (*mask == ((1u << TRECHIST_MAX_RANGES) - 1)) 86fbc6cc04SDmitri Tikhonov return -1; 87fbc6cc04SDmitri Tikhonov 88fbc6cc04SDmitri Tikhonov idx = find_free_slot(*mask); 89fbc6cc04SDmitri Tikhonov elems[idx].te_low = packno; 90fbc6cc04SDmitri Tikhonov elems[idx].te_count = 1; 91fbc6cc04SDmitri Tikhonov elems[idx].te_next = 0; 92fbc6cc04SDmitri Tikhonov *mask |= 1u << idx;; 93fbc6cc04SDmitri Tikhonov el->te_next = idx; 94fbc6cc04SDmitri Tikhonov return 0; 95fbc6cc04SDmitri Tikhonov 96fbc6cc04SDmitri Tikhonov insert_before: 97fbc6cc04SDmitri Tikhonov 98fbc6cc04SDmitri Tikhonov if (*mask == ((1u << TRECHIST_MAX_RANGES) - 1)) 99fbc6cc04SDmitri Tikhonov return -1; 100fbc6cc04SDmitri Tikhonov 101fbc6cc04SDmitri Tikhonov idx = find_free_slot(*mask); 102fbc6cc04SDmitri Tikhonov *mask |= 1u << idx;; 103fbc6cc04SDmitri Tikhonov if (el == elems) 104fbc6cc04SDmitri Tikhonov { 105fbc6cc04SDmitri Tikhonov elems[idx] = *el; 106fbc6cc04SDmitri Tikhonov elems[0].te_low = packno; 107fbc6cc04SDmitri Tikhonov elems[0].te_count = 1; 108fbc6cc04SDmitri Tikhonov elems[0].te_next = idx; 109fbc6cc04SDmitri Tikhonov } 110fbc6cc04SDmitri Tikhonov else 111fbc6cc04SDmitri Tikhonov { 112fbc6cc04SDmitri Tikhonov assert(prev); 113fbc6cc04SDmitri Tikhonov elems[idx].te_low = packno; 114fbc6cc04SDmitri Tikhonov elems[idx].te_count = 1; 115fbc6cc04SDmitri Tikhonov elems[idx].te_next = prev->te_next; 116fbc6cc04SDmitri Tikhonov prev->te_next = idx; 117fbc6cc04SDmitri Tikhonov } 118fbc6cc04SDmitri Tikhonov 119fbc6cc04SDmitri Tikhonov return 0; 120fbc6cc04SDmitri Tikhonov} 121fbc6cc04SDmitri Tikhonov 122fbc6cc04SDmitri Tikhonov 123fbc6cc04SDmitri Tikhonovvoid 124fbc6cc04SDmitri Tikhonovlsquic_trechist_iter (struct trechist_iter *iter, trechist_mask_t mask, 125fbc6cc04SDmitri Tikhonov const struct trechist_elem *elems) 126fbc6cc04SDmitri Tikhonov{ 127fbc6cc04SDmitri Tikhonov iter->mask = mask; 128fbc6cc04SDmitri Tikhonov iter->elems = elems; 129fbc6cc04SDmitri Tikhonov} 130fbc6cc04SDmitri Tikhonov 131fbc6cc04SDmitri Tikhonov 132fbc6cc04SDmitri Tikhonovconst struct lsquic_packno_range * 133fbc6cc04SDmitri Tikhonovlsquic_trechist_first (void *iter_p) 134fbc6cc04SDmitri Tikhonov{ 135fbc6cc04SDmitri Tikhonov struct trechist_iter *const iter = iter_p; 136fbc6cc04SDmitri Tikhonov 137fbc6cc04SDmitri Tikhonov if (iter->mask == 0) 138fbc6cc04SDmitri Tikhonov return NULL; 139fbc6cc04SDmitri Tikhonov 140fbc6cc04SDmitri Tikhonov iter->next = iter->elems[0].te_next; 141fbc6cc04SDmitri Tikhonov iter->range.low = iter->elems[0].te_low; 142fbc6cc04SDmitri Tikhonov iter->range.high = TE_HIGH(&iter->elems[0]); 143fbc6cc04SDmitri Tikhonov return &iter->range; 144fbc6cc04SDmitri Tikhonov} 145fbc6cc04SDmitri Tikhonov 146fbc6cc04SDmitri Tikhonov 147fbc6cc04SDmitri Tikhonovconst struct lsquic_packno_range * 148fbc6cc04SDmitri Tikhonovlsquic_trechist_next (void *iter_p) 149fbc6cc04SDmitri Tikhonov{ 150fbc6cc04SDmitri Tikhonov struct trechist_iter *const iter = iter_p; 151fbc6cc04SDmitri Tikhonov 152fbc6cc04SDmitri Tikhonov if (iter->next == 0) 153fbc6cc04SDmitri Tikhonov return NULL; 154fbc6cc04SDmitri Tikhonov 155fbc6cc04SDmitri Tikhonov iter->range.low = iter->elems[iter->next].te_low; 156fbc6cc04SDmitri Tikhonov iter->range.high = TE_HIGH(&iter->elems[iter->next]); 157fbc6cc04SDmitri Tikhonov iter->next = iter->elems[iter->next].te_next; 158fbc6cc04SDmitri Tikhonov return &iter->range; 159fbc6cc04SDmitri Tikhonov} 160fbc6cc04SDmitri Tikhonov 161fbc6cc04SDmitri Tikhonov 162fbc6cc04SDmitri Tikhonovint 163fbc6cc04SDmitri Tikhonovlsquic_trechist_copy_ranges (trechist_mask_t *mask, 164fbc6cc04SDmitri Tikhonov struct trechist_elem *elems, void *src_rechist, 165fbc6cc04SDmitri Tikhonov const struct lsquic_packno_range * (*first) (void *), 166fbc6cc04SDmitri Tikhonov const struct lsquic_packno_range * (*next) (void *)) 167fbc6cc04SDmitri Tikhonov{ 168fbc6cc04SDmitri Tikhonov const struct lsquic_packno_range *range; 169fbc6cc04SDmitri Tikhonov struct trechist_elem *el; 170fbc6cc04SDmitri Tikhonov unsigned i; 171fbc6cc04SDmitri Tikhonov 172fbc6cc04SDmitri Tikhonov for (el = NULL, i = 0, range = first(src_rechist); 173fbc6cc04SDmitri Tikhonov i < TRECHIST_MAX_RANGES && range; 174fbc6cc04SDmitri Tikhonov range = next(src_rechist), ++i) 175fbc6cc04SDmitri Tikhonov { 176fbc6cc04SDmitri Tikhonov /* This should never happen: */ 177fbc6cc04SDmitri Tikhonov assert(range->high - range->low + 1 <= UINT_MAX); 178fbc6cc04SDmitri Tikhonov 179fbc6cc04SDmitri Tikhonov el = &elems[i]; 180fbc6cc04SDmitri Tikhonov el->te_low = range->low; 181fbc6cc04SDmitri Tikhonov el->te_count = range->high - range->low + 1; 182fbc6cc04SDmitri Tikhonov el->te_next = i + 1; 183fbc6cc04SDmitri Tikhonov } 184fbc6cc04SDmitri Tikhonov 185fbc6cc04SDmitri Tikhonov if (!range && el) 186fbc6cc04SDmitri Tikhonov { 187fbc6cc04SDmitri Tikhonov el->te_next = 0; 188fbc6cc04SDmitri Tikhonov *mask = (1u << i) - 1; 189fbc6cc04SDmitri Tikhonov return 0; 190fbc6cc04SDmitri Tikhonov } 191fbc6cc04SDmitri Tikhonov else if (!el) 192fbc6cc04SDmitri Tikhonov { 193fbc6cc04SDmitri Tikhonov *mask = 0; 194fbc6cc04SDmitri Tikhonov return 0; /* Must have been an empty */ 195fbc6cc04SDmitri Tikhonov } 196fbc6cc04SDmitri Tikhonov else 197fbc6cc04SDmitri Tikhonov return -1; 198fbc6cc04SDmitri Tikhonov} 199fbc6cc04SDmitri Tikhonov 200fbc6cc04SDmitri Tikhonov 201fbc6cc04SDmitri Tikhonovint 202fbc6cc04SDmitri Tikhonovlsquic_trechist_contains (trechist_mask_t mask, 203fbc6cc04SDmitri Tikhonov const struct trechist_elem *elems, uint32_t packno) 204fbc6cc04SDmitri Tikhonov{ 205fbc6cc04SDmitri Tikhonov const struct trechist_elem *el; 206fbc6cc04SDmitri Tikhonov if (mask == 0) 207fbc6cc04SDmitri Tikhonov return 0; 208fbc6cc04SDmitri Tikhonov 209fbc6cc04SDmitri Tikhonov el = &elems[0]; 210fbc6cc04SDmitri Tikhonov while (1) 211fbc6cc04SDmitri Tikhonov { 212fbc6cc04SDmitri Tikhonov if (packno > TE_HIGH(el)) 213fbc6cc04SDmitri Tikhonov return 0; 214fbc6cc04SDmitri Tikhonov if (packno >= el->te_low) 215fbc6cc04SDmitri Tikhonov return 1; 216fbc6cc04SDmitri Tikhonov if (el->te_next) 217fbc6cc04SDmitri Tikhonov el = &elems[el->te_next]; 218fbc6cc04SDmitri Tikhonov else 219fbc6cc04SDmitri Tikhonov break; 220fbc6cc04SDmitri Tikhonov } 221fbc6cc04SDmitri Tikhonov 222fbc6cc04SDmitri Tikhonov return 0; 223fbc6cc04SDmitri Tikhonov} 224fbc6cc04SDmitri Tikhonov 225fbc6cc04SDmitri Tikhonov 226fbc6cc04SDmitri Tikhonovuint32_t 227fbc6cc04SDmitri Tikhonovlsquic_trechist_max (trechist_mask_t mask, const struct trechist_elem *elems) 228fbc6cc04SDmitri Tikhonov{ 229fbc6cc04SDmitri Tikhonov if (mask) 230fbc6cc04SDmitri Tikhonov { 231fbc6cc04SDmitri Tikhonov assert(mask & 1); 232fbc6cc04SDmitri Tikhonov return TE_HIGH(&elems[0]); 233fbc6cc04SDmitri Tikhonov } 234fbc6cc04SDmitri Tikhonov else 235fbc6cc04SDmitri Tikhonov return 0; 236fbc6cc04SDmitri Tikhonov} 237