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