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