lsquic_trechist.h revision 06b2a236 
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
23struct trechist_elem
24{
25    uint32_t        te_low;
26    unsigned char   te_count;
27    unsigned char   te_next;    /* 0 means no next element */
28};
29
30#define TE_HIGH(te_) ((te_)->te_low + (te_)->te_count - 1)
31
32#define TRECHIST_SIZE (TRECHIST_MAX_RANGES * sizeof(struct trechist_elem))
33
34/* There are two parts to this: the array of trechist_elem's and the bitmask
35 * that tracks which elements are used.  The smallest range must always be at
36 * offset zero.
37 */
38typedef uint32_t trechist_mask_t;
39
40int
41lsquic_trechist_insert (trechist_mask_t *, struct trechist_elem *, uint32_t);
42
43struct trechist_iter {
44    struct lsquic_packno_range  range;
45    const struct trechist_elem *elems;
46    trechist_mask_t             mask;
47    unsigned char               next;
48};
49
50void
51lsquic_trechist_iter (struct trechist_iter *iter, trechist_mask_t mask,
52                                            const struct trechist_elem *);
53
54/* Don't modify history while iterating */
55const struct lsquic_packno_range *
56lsquic_trechist_first (void *iter);
57
58const struct lsquic_packno_range *
59lsquic_trechist_next (void *iter);
60
61int
62lsquic_trechist_copy_ranges (trechist_mask_t *mask /* This gets overwritten */,
63                    struct trechist_elem *elems, void *src_rechist,
64                    const struct lsquic_packno_range * (*first) (void *),
65                    const struct lsquic_packno_range * (*next) (void *));
66
67int
68lsquic_trechist_contains (trechist_mask_t mask,
69                        const struct trechist_elem *elems, uint32_t packno);
70
71uint32_t
72lsquic_trechist_max (trechist_mask_t mask, const struct trechist_elem *elems);
73
74#endif
75