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