lsquic_attq.c revision 229fce07 
1/* Copyright (c) 2017 - 2019 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_attq.c -- Advisory Tick Time Queue
4 *
5 * This is a collection of connections kept in a binary heap, the top
6 * element having the minimum advsory time.  To speed up removal, each
7 * element has an index it has in the heap array.  The index is updated
8 * as elements are moved around in the array when heap is updated.
9 */
10
11#include <assert.h>
12#include <stdlib.h>
13#ifdef WIN32
14#include <vc_compat.h>
15#endif
16
17#include "lsquic.h"
18#include "lsquic_types.h"
19#include "lsquic_int_types.h"
20#include "lsquic_attq.h"
21#include "lsquic_malo.h"
22#include "lsquic_conn.h"
23
24
25struct attq
26{
27    struct malo        *aq_elem_malo;
28    struct attq_elem  **aq_heap;
29    unsigned            aq_nelem;
30    unsigned            aq_nalloc;
31};
32
33
34struct attq *
35attq_create (void)
36{
37    struct attq *q;
38    struct malo *malo;
39
40    malo = lsquic_malo_create(sizeof(struct attq_elem));
41    if (!malo)
42        return NULL;
43
44    q = calloc(1, sizeof(*q));
45    if (!q)
46    {
47        lsquic_malo_destroy(malo);
48        return NULL;
49    }
50
51    q->aq_elem_malo = malo;
52    return q;
53}
54
55
56void
57attq_destroy (struct attq *q)
58{
59    lsquic_malo_destroy(q->aq_elem_malo);
60    free(q->aq_heap);
61    free(q);
62}
63
64
65
66#define AE_PARENT(i) ((i - 1) / 2)
67#define AE_LCHILD(i) (2 * i + 1)
68#define AE_RCHILD(i) (2 * i + 2)
69
70
71#ifndef NDEBUG
72static void
73attq_verify (struct attq *q)
74{
75    unsigned i;
76
77    for (i = 0; i < q->aq_nelem; ++i)
78    {
79        assert(q->aq_heap[i]->ae_heap_idx == i);
80        if (AE_LCHILD(i) < q->aq_nelem)
81            assert(q->aq_heap[i]->ae_adv_time <=
82                        q->aq_heap[AE_LCHILD(i)]->ae_adv_time);
83        if (AE_RCHILD(i) < q->aq_nelem)
84            assert(q->aq_heap[i]->ae_adv_time <=
85                        q->aq_heap[AE_RCHILD(i)]->ae_adv_time);
86    }
87}
88#else
89#define attq_verify(q)
90#endif
91
92
93static void
94attq_swap (struct attq *q, unsigned a, unsigned b)
95{
96    struct attq_elem *el;
97
98    el = q->aq_heap[ a ];
99    q->aq_heap[ a ] = q->aq_heap[ b ];
100    q->aq_heap[ b ] = el;
101    q->aq_heap[ a ]->ae_heap_idx = a;
102    q->aq_heap[ b ]->ae_heap_idx = b;
103}
104
105
106int
107attq_add (struct attq *q, struct lsquic_conn *conn,
108                                            lsquic_time_t advisory_time)
109{
110    struct attq_elem *el, **heap;
111    unsigned n, i;
112
113    if (q->aq_nelem >= q->aq_nalloc)
114    {
115        if (q->aq_nalloc > 0)
116            n = q->aq_nalloc * 2;
117        else
118            n = 8;
119        heap = realloc(q->aq_heap, n * sizeof(q->aq_heap[0]));
120        if (!heap)
121            return -1;
122        q->aq_heap = heap;
123        q->aq_nalloc = n;
124    }
125
126    el = lsquic_malo_get(q->aq_elem_malo);
127    if (!el)
128        return -1;
129    el->ae_adv_time = advisory_time;
130
131    /* The only place linkage between conn and attq_elem occurs: */
132    el->ae_conn = conn;
133    conn->cn_attq_elem = el;
134
135    el->ae_heap_idx = q->aq_nelem;
136    q->aq_heap[ q->aq_nelem++ ] = el;
137
138    i = q->aq_nelem - 1;
139    while (i > 0 && q->aq_heap[ AE_PARENT(i) ]->ae_adv_time >=
140                                        q->aq_heap[ i ]->ae_adv_time)
141    {
142        attq_swap(q, i, AE_PARENT(i));
143        i = AE_PARENT(i);
144    }
145
146    attq_verify(q);
147
148    return 0;
149}
150
151
152struct lsquic_conn *
153attq_pop (struct attq *q, lsquic_time_t cutoff)
154{
155    struct lsquic_conn *conn;
156    struct attq_elem *el;
157
158    if (q->aq_nelem == 0)
159        return NULL;
160
161    el = q->aq_heap[0];
162    if (el->ae_adv_time >= cutoff)
163        return NULL;
164
165    conn = el->ae_conn;
166    attq_remove(q, conn);
167    return conn;
168}
169
170
171static void
172attq_heapify (struct attq *q, unsigned i)
173{
174    unsigned smallest;
175
176    assert(i < q->aq_nelem);
177
178    if (AE_LCHILD(i) < q->aq_nelem)
179    {
180        if (q->aq_heap[ AE_LCHILD(i) ]->ae_adv_time <
181                                    q->aq_heap[ i ]->ae_adv_time)
182            smallest = AE_LCHILD(i);
183        else
184            smallest = i;
185        if (AE_RCHILD(i) < q->aq_nelem &&
186            q->aq_heap[ AE_RCHILD(i) ]->ae_adv_time <
187                                    q->aq_heap[ smallest ]->ae_adv_time)
188            smallest = AE_RCHILD(i);
189    }
190    else
191        smallest = i;
192
193    if (smallest != i)
194    {
195        attq_swap(q, smallest, i);
196        attq_heapify(q, smallest);
197    }
198}
199
200
201void
202attq_remove (struct attq *q, struct lsquic_conn *conn)
203{
204    struct attq_elem *el;
205    unsigned idx;
206
207    el = conn->cn_attq_elem;
208    idx = el->ae_heap_idx;
209
210    assert(q->aq_nelem > 0);
211    assert(q->aq_heap[idx] == el);
212    assert(conn->cn_attq_elem == el);
213
214    conn->cn_attq_elem = NULL;
215    lsquic_malo_put(el);
216
217    q->aq_heap[ idx ] = q->aq_heap[ --q->aq_nelem ];
218    q->aq_heap[ idx ]->ae_heap_idx = idx;
219    if (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
220                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time)
221    {
222        do
223        {
224            attq_swap(q, idx, AE_PARENT(idx));
225            idx = AE_PARENT(idx);
226        }
227        while (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
228                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time);
229    }
230    else if (q->aq_nelem > 1 && idx < q->aq_nelem)
231        attq_heapify(q, idx);
232    attq_verify(q);
233}
234
235
236unsigned
237attq_count_before (struct attq *q, lsquic_time_t cutoff)
238{
239    unsigned level, total_count, level_count, i, level_max;
240
241    total_count = 0;
242    for (i = 0, level = 0;; ++level)
243    {
244        level_count = 0;
245        level_max = i + (1U << level);
246        for ( ; i < level_max && i < q->aq_nelem; ++i)
247            level_count += q->aq_heap[i]->ae_adv_time < cutoff;
248        total_count += level_count;
249        if (level_count < (1U << level))
250            return total_count;
251    }
252    assert(0);
253}
254
255
256const lsquic_time_t *
257attq_next_time (struct attq *q)
258{
259    if (q->aq_nelem > 0)
260        return &q->aq_heap[0]->ae_adv_time;
261    else
262        return NULL;
263}
264