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