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