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