lsquic_trechist.c revision a74702c6 
1/* Copyright (c) 2017 - 2022 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/* When capacity is reached, smallest element is removed.  When the number
33 * of elements in a single range cannot be represented by te_count, an
34 * error is returned.  This is the only error this function returns.
35 */
36int
37lsquic_trechist_insert (trechist_mask_t *mask, struct trechist_elem *elems,
38                                                            uint32_t packno)
39{
40    struct trechist_elem *el, *prev, *cur, *next;
41    unsigned idx;
42
43    if (*mask == 0)
44    {
45        elems[0].te_low   = packno;
46        elems[0].te_count = 1;
47        elems[0].te_next  = 0;
48        *mask |= 1;
49        return 0;
50    }
51
52    el = elems;
53    prev = NULL;
54    while (1)
55    {
56        if (packno > TE_HIGH(el) + 1)
57            goto insert_before;
58        if (packno == el->te_low - 1)
59        {
60            if (el->te_next && el->te_low == TE_HIGH(&elems[el->te_next]) + 2)
61            {
62                if (el->te_count + elems[el->te_next].te_count - 1 > UCHAR_MAX)
63                    return -1;
64                *mask &= ~(1u << el->te_next);
65                el->te_count += elems[el->te_next].te_count + 1;
66                el->te_low    = elems[el->te_next].te_low;
67                el->te_next   = elems[el->te_next].te_next;
68            }
69            else
70            {
71                if (el->te_count == UCHAR_MAX)
72                    return -1;
73                --el->te_low;
74                ++el->te_count;
75            }
76            return 0;
77        }
78        if (packno == TE_HIGH(el) + 1)
79        {
80            if (el->te_count == UCHAR_MAX)
81                return -1;
82            ++el->te_count;
83            return 0;
84        }
85        if (packno >= el->te_low && packno <= TE_HIGH(el))
86            return 0;   /* Dup */
87        if (!el->te_next)
88            break;  /* insert tail */
89        prev = el;
90        el = &elems[el->te_next];
91    }
92
93    if (*mask == TRECHIST_MAX_RANGES_MASK)
94        /* No need to insert element smaller than the smallest element
95         * already in our list.  The new element "overflows".
96         */
97        return 0;
98
99    idx = find_free_slot(*mask);
100    elems[idx].te_low   = packno;
101    elems[idx].te_count = 1;
102    elems[idx].te_next  = 0;
103    *mask |= 1u << idx;;
104    el->te_next = idx;
105    return 0;
106
107  insert_before:
108
109    if (*mask != TRECHIST_MAX_RANGES_MASK)
110        idx = find_free_slot(*mask);
111    else
112    {   /* Drop last element and reuse its slot */
113        for (next = &elems[el->te_next], cur = el; next->te_next;
114                                cur = next, next = &elems[cur->te_next])
115            ;
116        idx = cur->te_next;
117        cur->te_next = 0;
118    }
119
120    *mask |= 1u << idx;;
121    if (el == elems)
122    {
123        elems[idx] = *el;
124        elems[0].te_low   = packno;
125        elems[0].te_count = 1;
126        elems[0].te_next  = idx;
127    }
128    else
129    {
130        assert(prev);
131        elems[idx].te_low   = packno;
132        elems[idx].te_count = 1;
133        elems[idx].te_next  = prev->te_next;
134        prev->te_next = idx;
135    }
136
137    return 0;
138}
139
140
141void
142lsquic_trechist_iter (struct trechist_iter *iter, trechist_mask_t mask,
143                                            const struct trechist_elem *elems)
144{
145    iter->mask = mask;
146    iter->elems = elems;
147}
148
149
150const struct lsquic_packno_range *
151lsquic_trechist_first (void *iter_p)
152{
153    struct trechist_iter *const iter = iter_p;
154
155    if (iter->mask == 0)
156        return NULL;
157
158    iter->next = iter->elems[0].te_next;
159    iter->range.low = iter->elems[0].te_low;
160    iter->range.high = TE_HIGH(&iter->elems[0]);
161    return &iter->range;
162}
163
164
165const struct lsquic_packno_range *
166lsquic_trechist_next (void *iter_p)
167{
168    struct trechist_iter *const iter = iter_p;
169
170    if (iter->next == 0)
171        return NULL;
172
173    iter->range.low = iter->elems[iter->next].te_low;
174    iter->range.high = TE_HIGH(&iter->elems[iter->next]);
175    iter->next = iter->elems[iter->next].te_next;
176    return &iter->range;
177}
178
179
180/* First TRECHIST_MAX_RANGES ranges are copied */
181void
182lsquic_trechist_copy_ranges (trechist_mask_t *mask,
183                    struct trechist_elem *elems, void *src_rechist,
184                    const struct lsquic_packno_range * (*first) (void *),
185                    const struct lsquic_packno_range * (*next) (void *))
186{
187    const struct lsquic_packno_range *range;
188    struct trechist_elem *el;
189    unsigned i;
190
191    for (el = NULL, i = 0, range = first(src_rechist);
192            i < TRECHIST_MAX_RANGES && range;
193                range = next(src_rechist), ++i)
194    {
195        /* This should never happen: */
196        assert(range->high - range->low + 1 <= UINT_MAX);
197
198        el = &elems[i];
199        el->te_low = range->low;
200        el->te_count = range->high - range->low + 1;
201        el->te_next = i + 1;
202    }
203
204    if (el)
205        el->te_next = 0;
206
207    if (i < 32)
208        *mask = (1u << i) - 1;
209    else
210        *mask = UINT32_MAX;
211}
212
213
214int
215lsquic_trechist_contains (trechist_mask_t mask,
216                    const struct trechist_elem *elems, uint32_t packno)
217{
218    const struct trechist_elem *el;
219    if (mask == 0)
220        return 0;
221
222    el = &elems[0];
223    while (1)
224    {
225        if (packno > TE_HIGH(el))
226            return 0;
227        if (packno >= el->te_low)
228            return 1;
229        if (el->te_next)
230            el = &elems[el->te_next];
231        else
232            break;
233    }
234
235    return 0;
236}
237
238
239uint32_t
240lsquic_trechist_max (trechist_mask_t mask, const struct trechist_elem *elems)
241{
242    if (mask)
243    {
244        assert(mask & 1);
245        return TE_HIGH(&elems[0]);
246    }
247    else
248        return 0;
249}
250