lsquic_trechist.h revision 06b2a236
106b2a236SDmitri Tikhonov/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc. See LICENSE. */ 2fbc6cc04SDmitri Tikhonov/* 3fbc6cc04SDmitri Tikhonov * Tiny receive history. It is used in IETF mini connection, where we want 4fbc6cc04SDmitri Tikhonov * to use as little memory as possible. This data structure is an array of 5fbc6cc04SDmitri Tikhonov * packet ranges. Each packet range is six bytes. This is possible because 6fbc6cc04SDmitri Tikhonov * initial packets must not be wider than four bytes. 7fbc6cc04SDmitri Tikhonov * 8fbc6cc04SDmitri Tikhonov * Another limitation of this history is that it never shrinks. (Although 9fbc6cc04SDmitri Tikhonov * technically is is possible to implement. 10fbc6cc04SDmitri Tikhonov */ 11fbc6cc04SDmitri Tikhonov 12fbc6cc04SDmitri Tikhonov#ifndef LSQUIC_TRECHIST 13fbc6cc04SDmitri Tikhonov#define LSQUIC_TRECHIST 1 14fbc6cc04SDmitri Tikhonov 15fbc6cc04SDmitri Tikhonovstruct lsquic_packno_range; 16fbc6cc04SDmitri Tikhonov 17fbc6cc04SDmitri Tikhonov/* This value could be as large as 32, which is how many bits wide 18fbc6cc04SDmitri Tikhonov * trechist_mask_t is. The other limit on the number of ranges is 19fbc6cc04SDmitri Tikhonov * UCHAR_MAX, which is how many different values can fit into te_next. 20fbc6cc04SDmitri Tikhonov */ 21fbc6cc04SDmitri Tikhonov#define TRECHIST_MAX_RANGES 16 22fbc6cc04SDmitri Tikhonov 23fbc6cc04SDmitri Tikhonovstruct trechist_elem 24fbc6cc04SDmitri Tikhonov{ 25fbc6cc04SDmitri Tikhonov uint32_t te_low; 26fbc6cc04SDmitri Tikhonov unsigned char te_count; 27fbc6cc04SDmitri Tikhonov unsigned char te_next; /* 0 means no next element */ 28fbc6cc04SDmitri Tikhonov}; 29fbc6cc04SDmitri Tikhonov 30fbc6cc04SDmitri Tikhonov#define TE_HIGH(te_) ((te_)->te_low + (te_)->te_count - 1) 31fbc6cc04SDmitri Tikhonov 32fbc6cc04SDmitri Tikhonov#define TRECHIST_SIZE (TRECHIST_MAX_RANGES * sizeof(struct trechist_elem)) 33fbc6cc04SDmitri Tikhonov 34fbc6cc04SDmitri Tikhonov/* There are two parts to this: the array of trechist_elem's and the bitmask 35fbc6cc04SDmitri Tikhonov * that tracks which elements are used. The smallest range must always be at 36fbc6cc04SDmitri Tikhonov * offset zero. 37fbc6cc04SDmitri Tikhonov */ 38fbc6cc04SDmitri Tikhonovtypedef uint32_t trechist_mask_t; 39fbc6cc04SDmitri Tikhonov 40fbc6cc04SDmitri Tikhonovint 41fbc6cc04SDmitri Tikhonovlsquic_trechist_insert (trechist_mask_t *, struct trechist_elem *, uint32_t); 42fbc6cc04SDmitri Tikhonov 43fbc6cc04SDmitri Tikhonovstruct trechist_iter { 44fbc6cc04SDmitri Tikhonov struct lsquic_packno_range range; 45fbc6cc04SDmitri Tikhonov const struct trechist_elem *elems; 46fbc6cc04SDmitri Tikhonov trechist_mask_t mask; 47fbc6cc04SDmitri Tikhonov unsigned char next; 48fbc6cc04SDmitri Tikhonov}; 49fbc6cc04SDmitri Tikhonov 50fbc6cc04SDmitri Tikhonovvoid 51fbc6cc04SDmitri Tikhonovlsquic_trechist_iter (struct trechist_iter *iter, trechist_mask_t mask, 52fbc6cc04SDmitri Tikhonov const struct trechist_elem *); 53fbc6cc04SDmitri Tikhonov 54fbc6cc04SDmitri Tikhonov/* Don't modify history while iterating */ 55fbc6cc04SDmitri Tikhonovconst struct lsquic_packno_range * 56fbc6cc04SDmitri Tikhonovlsquic_trechist_first (void *iter); 57fbc6cc04SDmitri Tikhonov 58fbc6cc04SDmitri Tikhonovconst struct lsquic_packno_range * 59fbc6cc04SDmitri Tikhonovlsquic_trechist_next (void *iter); 60fbc6cc04SDmitri Tikhonov 61fbc6cc04SDmitri Tikhonovint 62fbc6cc04SDmitri Tikhonovlsquic_trechist_copy_ranges (trechist_mask_t *mask /* This gets overwritten */, 63fbc6cc04SDmitri Tikhonov struct trechist_elem *elems, void *src_rechist, 64fbc6cc04SDmitri Tikhonov const struct lsquic_packno_range * (*first) (void *), 65fbc6cc04SDmitri Tikhonov const struct lsquic_packno_range * (*next) (void *)); 66fbc6cc04SDmitri Tikhonov 67fbc6cc04SDmitri Tikhonovint 68fbc6cc04SDmitri Tikhonovlsquic_trechist_contains (trechist_mask_t mask, 69fbc6cc04SDmitri Tikhonov const struct trechist_elem *elems, uint32_t packno); 70fbc6cc04SDmitri Tikhonov 71fbc6cc04SDmitri Tikhonovuint32_t 72fbc6cc04SDmitri Tikhonovlsquic_trechist_max (trechist_mask_t mask, const struct trechist_elem *elems); 73fbc6cc04SDmitri Tikhonov 74fbc6cc04SDmitri Tikhonov#endif 75