lsquic_attq.c revision 10c492f0 
1/* Copyright (c) 2017 - 2018 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    lsquic_time_t       aq_min;
30    unsigned            aq_nelem;
31    unsigned            aq_nalloc;
32};
33
34
35struct attq *
36attq_create (void)
37{
38    struct attq *q;
39    struct malo *malo;
40
41    malo = lsquic_malo_create(sizeof(struct attq_elem));
42    if (!malo)
43        return NULL;
44
45    q = calloc(1, sizeof(*q));
46    if (!q)
47    {
48        lsquic_malo_destroy(malo);
49        return NULL;
50    }
51
52    q->aq_elem_malo = malo;
53    return q;
54}
55
56
57void
58attq_destroy (struct attq *q)
59{
60    lsquic_malo_destroy(q->aq_elem_malo);
61    free(q->aq_heap);
62    free(q);
63}
64
65
66
67#define AE_PARENT(i) ((i - 1) / 2)
68#define AE_LCHILD(i) (2 * i + 1)
69#define AE_RCHILD(i) (2 * i + 2)
70
71
72#ifndef NDEBUG
73static void
74attq_verify (struct attq *q)
75{
76    unsigned i;
77
78    for (i = 0; i < q->aq_nelem; ++i)
79    {
80        assert(q->aq_heap[i]->ae_heap_idx == i);
81        if (AE_LCHILD(i) < q->aq_nelem)
82            assert(q->aq_heap[i]->ae_adv_time <=
83                        q->aq_heap[AE_LCHILD(i)]->ae_adv_time);
84        if (AE_RCHILD(i) < q->aq_nelem)
85            assert(q->aq_heap[i]->ae_adv_time <=
86                        q->aq_heap[AE_RCHILD(i)]->ae_adv_time);
87    }
88}
89#else
90#define attq_verify(q)
91#endif
92
93
94int
95attq_maybe_add (struct attq *q, struct lsquic_conn *conn,
96                                            lsquic_time_t advisory_time)
97{
98    if (advisory_time < q->aq_min)
99        return 1;
100    else
101        return attq_add(q, conn, advisory_time);
102}
103
104
105static void
106attq_swap (struct attq *q, unsigned a, unsigned b)
107{
108    struct attq_elem *el;
109
110    el = q->aq_heap[ a ];
111    q->aq_heap[ a ] = q->aq_heap[ b ];
112    q->aq_heap[ b ] = el;
113    q->aq_heap[ a ]->ae_heap_idx = a;
114    q->aq_heap[ b ]->ae_heap_idx = b;
115}
116
117
118int
119attq_add (struct attq *q, struct lsquic_conn *conn,
120                                            lsquic_time_t advisory_time)
121{
122    struct attq_elem *el, **heap;
123    unsigned n, i;
124
125    if (q->aq_nelem >= q->aq_nalloc)
126    {
127        if (q->aq_nalloc > 0)
128            n = q->aq_nalloc * 2;
129        else
130            n = 8;
131        heap = realloc(q->aq_heap, n * sizeof(q->aq_heap[0]));
132        if (!heap)
133            return -1;
134        q->aq_heap = heap;
135        q->aq_nalloc = n;
136    }
137
138    el = lsquic_malo_get(q->aq_elem_malo);
139    if (!el)
140        return -1;
141    el->ae_adv_time = advisory_time;
142
143    /* The only place linkage between conn and attq_elem occurs: */
144    el->ae_conn = conn;
145    conn->cn_attq_elem = el;
146
147    el->ae_heap_idx = q->aq_nelem;
148    q->aq_heap[ q->aq_nelem++ ] = el;
149
150    i = q->aq_nelem - 1;
151    while (i > 0 && q->aq_heap[ AE_PARENT(i) ]->ae_adv_time >=
152                                        q->aq_heap[ i ]->ae_adv_time)
153    {
154        attq_swap(q, i, AE_PARENT(i));
155        i = AE_PARENT(i);
156    }
157
158    attq_verify(q);
159
160    return 0;
161}
162
163
164struct lsquic_conn *
165attq_pop (struct attq *q, lsquic_time_t cutoff)
166{
167    struct lsquic_conn *conn;
168    struct attq_elem *el;
169
170    if (q->aq_nelem == 0)
171        return NULL;
172
173    el = q->aq_heap[0];
174    if (el->ae_adv_time >= cutoff)
175        return NULL;
176
177    conn = el->ae_conn;
178    attq_remove(q, conn);
179    return conn;
180}
181
182
183static void
184attq_heapify (struct attq *q, unsigned i)
185{
186    unsigned smallest;
187
188    assert(i < q->aq_nelem);
189
190    if (AE_LCHILD(i) < q->aq_nelem)
191    {
192        if (q->aq_heap[ AE_LCHILD(i) ]->ae_adv_time <
193                                    q->aq_heap[ i ]->ae_adv_time)
194            smallest = AE_LCHILD(i);
195        else
196            smallest = i;
197        if (AE_RCHILD(i) < q->aq_nelem &&
198            q->aq_heap[ AE_RCHILD(i) ]->ae_adv_time <
199                                    q->aq_heap[ smallest ]->ae_adv_time)
200            smallest = AE_RCHILD(i);
201    }
202    else
203        smallest = i;
204
205    if (smallest != i)
206    {
207        attq_swap(q, smallest, i);
208        attq_heapify(q, smallest);
209    }
210}
211
212
213void
214attq_remove (struct attq *q, struct lsquic_conn *conn)
215{
216    struct attq_elem *el;
217    unsigned idx;
218
219    el = conn->cn_attq_elem;
220    idx = el->ae_heap_idx;
221
222    assert(q->aq_nelem > 0);
223    assert(q->aq_heap[idx] == el);
224    assert(conn->cn_attq_elem == el);
225
226    conn->cn_attq_elem = NULL;
227    lsquic_malo_put(el);
228
229    q->aq_heap[ idx ] = q->aq_heap[ --q->aq_nelem ];
230    q->aq_heap[ idx ]->ae_heap_idx = idx;
231    if (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
232                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time)
233    {
234        do
235        {
236            attq_swap(q, idx, AE_PARENT(idx));
237            idx = AE_PARENT(idx);
238        }
239        while (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
240                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time);
241    }
242    else if (q->aq_nelem > 1 && idx < q->aq_nelem)
243        attq_heapify(q, idx);
244    attq_verify(q);
245}
246
247
248unsigned
249attq_count_before (struct attq *q, lsquic_time_t cutoff)
250{
251    unsigned level, total_count, level_count, i, level_max;
252
253    total_count = 0;
254    for (i = 0, level = 0;; ++level)
255    {
256        level_count = 0;
257        level_max = i + (1U << level);
258        for ( ; i < level_max && i < q->aq_nelem; ++i)
259            level_count += q->aq_heap[i]->ae_adv_time < cutoff;
260        total_count += level_count;
261        if (level_count < (1U << level))
262            return total_count;
263    }
264    assert(0);
265}
266
267
268const lsquic_time_t *
269attq_next_time (struct attq *q)
270{
271    if (q->aq_nelem > 0)
272        return &q->aq_heap[0]->ae_adv_time;
273    else
274        return NULL;
275}
276
277
278lsquic_time_t
279attq_set_min (struct attq *q, lsquic_time_t new_min)
280{
281    lsquic_time_t prev_value;
282    prev_value = q->aq_min;
283    q->aq_min = new_min;
284    return prev_value;
285}
286