lsquic_senhist.c revision bfc7bfd8 
1/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_senhist.c -- Sent history implementation
4 */
5
6#include <assert.h>
7#include <inttypes.h>
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11
12#include "lsquic_int_types.h"
13#include "lsquic_senhist.h"
14
15
16void
17lsquic_senhist_init (lsquic_senhist_t *hist)
18{
19    lsquic_packints_init(&hist->sh_pints);
20}
21
22
23void
24lsquic_senhist_cleanup (lsquic_senhist_t *hist)
25{
26    lsquic_packints_cleanup(&hist->sh_pints);
27}
28
29
30/* At the time of this writing, the only reason the sequence of sent
31 * packet numbers could contain a hole is elision of stream frames from
32 * scheduled, but delayed packets.  If such packet becomes empty after
33 * elision, it is dropped from the queue.
34 */
35
36
37/* The fast insert is used in the normal case, when packets are sent
38 * out in the same order in which they are scheduled: that is, their
39 * packet numbers are always increasing.
40 */
41static int
42senhist_add_fast (lsquic_senhist_t *hist, lsquic_packno_t packno)
43{
44    struct packet_interval *pi;
45
46    pi = TAILQ_FIRST(&hist->sh_pints.pk_intervals);
47    if (pi)
48    {
49        /* Check that packet numbers are always increasing */
50        assert(packno > pi->range.high);
51        if (packno == pi->range.high + 1)
52        {
53            ++pi->range.high;
54            return 0;
55        }
56    }
57
58    pi = malloc(sizeof(*pi));
59    if (!pi)
60        return -1;
61    pi->range.high = packno;
62    pi->range.low = packno;
63    TAILQ_INSERT_HEAD(&hist->sh_pints.pk_intervals, pi, next_pi);
64    return 0;
65}
66
67
68int
69lsquic_senhist_add (lsquic_senhist_t *hist, lsquic_packno_t packno)
70{
71        return senhist_add_fast(hist, packno);
72}
73
74
75int
76lsquic_senhist_sent_range (lsquic_senhist_t *hist, lsquic_packno_t low,
77                                                   lsquic_packno_t high)
78{
79    const struct lsquic_packno_range *range;
80    for (range = lsquic_packints_first(&hist->sh_pints); range;
81                            range = lsquic_packints_next(&hist->sh_pints))
82        if (range->low <= low && range->high >= high)
83            return 1;
84    return 0;
85}
86
87
88lsquic_packno_t
89lsquic_senhist_largest (lsquic_senhist_t *hist)
90{
91    const struct lsquic_packno_range *range;
92    range = lsquic_packints_first(&hist->sh_pints);
93    if (range)
94        return range->high;
95    else
96        return 0;
97}
98
99
100void
101lsquic_senhist_tostr (lsquic_senhist_t *hist, char *buf, size_t bufsz)
102{
103    const struct lsquic_packno_range *range;
104    size_t off;
105    int n;
106    for (off = 0, range = lsquic_packints_first(&hist->sh_pints);
107            range && off < bufsz;
108                off += n, range = lsquic_packints_next(&hist->sh_pints))
109    {
110        n = snprintf(buf + off, bufsz - off, "[%"PRIu64"-%"PRIu64"]",
111                                                    range->high, range->low);
112        if (n < 0 || (size_t) n >= bufsz - off)
113            break;
114    }
115    if (bufsz > 0)
116        buf[off] = '\0';
117}
118
119
120size_t
121lsquic_senhist_mem_used (const struct lsquic_senhist *hist)
122{
123    return sizeof(*hist)
124         - sizeof(hist->sh_pints)
125         + lsquic_packints_mem_used(&hist->sh_pints);
126}
127
128
129