lsquic_min_heap.c revision 5392f7a3 
1/* Copyright (c) 2017 - 2019 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_min_heap.c
4 */
5
6#include <assert.h>
7#include <stdint.h>
8
9#include "lsquic_min_heap.h"
10#define LSQUIC_LOGGER_MODULE LSQLM_MIN_HEAP
11#include "lsquic_types.h"
12#include "lsquic_logger.h"
13
14#define MHE_PARENT(i) ((i - 1) / 2)
15#define MHE_LCHILD(i) (2 * i + 1)
16#define MHE_RCHILD(i) (2 * i + 2)
17
18
19static void
20heapify_min_heap (struct min_heap *heap, unsigned i)
21{
22    struct min_heap_elem el;
23    unsigned smallest;
24
25    assert(i < heap->mh_nelem);
26
27    if (MHE_LCHILD(i) < heap->mh_nelem)
28    {
29        if (heap->mh_elems[ MHE_LCHILD(i) ].mhe_val <
30                                    heap->mh_elems[ i ].mhe_val)
31            smallest = MHE_LCHILD(i);
32        else
33            smallest = i;
34        if (MHE_RCHILD(i) < heap->mh_nelem &&
35            heap->mh_elems[ MHE_RCHILD(i) ].mhe_val <
36                                    heap->mh_elems[ smallest ].mhe_val)
37            smallest = MHE_RCHILD(i);
38    }
39    else
40        smallest = i;
41
42    if (smallest != i)
43    {
44        el = heap->mh_elems[ smallest ];
45        heap->mh_elems[ smallest ] = heap->mh_elems[ i ];
46        heap->mh_elems[ i ] = el;
47        heapify_min_heap(heap, smallest);
48    }
49}
50
51
52void
53lsquic_mh_insert (struct min_heap *heap, struct lsquic_conn *conn, uint64_t val)
54{
55    struct min_heap_elem el;
56    unsigned i;
57
58    assert(heap->mh_nelem < heap->mh_nalloc);
59
60    heap->mh_elems[ heap->mh_nelem ].mhe_conn = conn;
61    heap->mh_elems[ heap->mh_nelem ].mhe_val  = val;
62    ++heap->mh_nelem;
63
64    i = heap->mh_nelem - 1;
65    while (i > 0 && heap->mh_elems[ MHE_PARENT(i) ].mhe_val >
66                                    heap->mh_elems[ i ].mhe_val)
67    {
68        el = heap->mh_elems[ MHE_PARENT(i) ];
69        heap->mh_elems[ MHE_PARENT(i) ] = heap->mh_elems[ i ];
70        heap->mh_elems[ i ] = el;
71        i = MHE_PARENT(i);
72    }
73}
74
75
76struct lsquic_conn *
77lsquic_mh_pop (struct min_heap *heap)
78{
79    struct lsquic_conn *conn;
80
81    if (heap->mh_nelem == 0)
82        return NULL;
83
84    conn = heap->mh_elems[0].mhe_conn;
85    --heap->mh_nelem;
86    if (heap->mh_nelem > 0)
87    {
88        heap->mh_elems[0] = heap->mh_elems[ heap->mh_nelem ];
89        heapify_min_heap(heap, 0);
90    }
91
92    return conn;
93}
94