lsquic_trechist.h revision fbc6cc04
1fbc6cc04SDmitri Tikhonov/* Copyright (c) 2017 - 2020 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