summaryrefslogtreecommitdiff
path: root/cesar/lib/src/heap.c
blob: af8c83f2ca1f7ca1efe44f8ef51cd5cde22112c5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/* Cesar project {{{
 *
 * Copyright (C) 2007 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \file    lib/src/heap.c
 * \brief   Heap common functions.
 * \ingroup lib
 *
 * Provide common utilities functions for heaps.
 */
#include "common/std.h"

#include "lib/heap.h"

void
heap_init (heap_t *heap, heap_node_less_t less)
{
    dbg_assert (heap);
    heap->root = NULL;
    heap->less = less;
}

void
heap_adjust (heap_t *heap, heap_node_t *node)
{
    dbg_assert (heap);
    dbg_assert (node);
    /* If position should actually change. */
    if ((node->left && heap->less (node->left, node))
        || (node->right && heap->less (node->right, node))
        || (node->father && heap->less (node, node->father)))
    {
        heap_remove (heap, node);
        heap_insert (heap, node);
    }
}

void
heap_merge (heap_t *heap_to, heap_t *heap_from)
{
    dbg_assert (heap_to && heap_to->less);
    dbg_assert (heap_from && heap_from->less);
    dbg_assert_print (heap_to->less == heap_from->less, "incompatible heaps");
    heap_to->root = heap_node_merge (heap_to->root, heap_from->root,
                                     heap_to->less);
    heap_from->root = NULL;
}

bool
heap_node_u32_less_mod2p32 (heap_node_t *left, heap_node_t *right)
{
    dbg_assert (left);
    dbg_assert (right);
    heap_node_u32_t *l = PARENT_OF (heap_node_u32_t, node, left);
    heap_node_u32_t *r = PARENT_OF (heap_node_u32_t, node, right);
    return less_mod2p32 (l->key, r->key);
}