summaryrefslogtreecommitdiff
path: root/cesar/lib/heap.h
blob: 6505f0f001f933524e188b3292642f568902e5e6 (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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#ifndef lib_heap_h
#define lib_heap_h
/* Cesar project {{{
 *
 * Copyright (C) 2007 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \file    lib/heap.h
 * \brief   Heap (the data structure) service.
 * \ingroup lib
 *
 * An heap is a tree data structure which satisfies the following property: if B
 * is a child of A, then B.key >= A.key.
 *
 * It defines the following set of operations efficiently:
 *  - insert,
 *  - find root (the minimum value),
 *  - remove root (the minimum value).
 *
 * Some heap algorithms also define the following efficient operations:
 *  - remove a arbitrary node,
 *  - merge two heaps.
 *
 * Its common use is to implement priority queue.
 */
#include "config/heap.h"

/* Forward declaration. */
typedef struct heap_node_t heap_node_t;

/**
 * Heap node comparison function pointer.
 * \param  left  left hand node
 * \param  right  right hand node
 * \return  true iff left is lesser than right
 */
typedef bool
(*heap_node_less_t) (heap_node_t *left, heap_node_t *right);

/** Heap structure. */
struct heap_t
{
    /** Heap root node. */
    heap_node_t *root;
    /** Heap "is lesser than" comparison function. */
    heap_node_less_t less;
};
typedef struct heap_t heap_t;

#if CONFIG_HEAP_SKEW
#  include "lib/skewheap.h"
#elif CONFIG_HEAP_LEFTIST
#  include "lib/leftheap.h"
#endif

/** Heap node with an u32 key. */
struct heap_node_u32_t
{
    heap_node_t node;
    u32 key;
};
typedef struct heap_node_u32_t heap_node_u32_t;

BEGIN_DECLS

/**
 * Initialise a new heap.
 * \param  heap  the heap
 * \param  less  the "is lesser than" comparison function
 */
void
heap_init (heap_t *heap, heap_node_less_t less);

/**
 * Adjust position of a given node after a key change.
 * \param  heap  the heap
 * \param  node  the node to adjust.
 *
 * Actually, if the node is at a good position, nothing is done.  In other
 * cases, it is removed, then inserted.
 */
void
heap_adjust (heap_t *heap, heap_node_t *node);

/**
 * Get heap root.
 * \param  heap  the heap
 * \return  the root or NULL if the heap is empty
 */
extern inline heap_node_t *
heap_get_root (heap_t *heap)
{
    return heap->root;
}

/**
 * Return whether the heap is empty.
 * \param  heap  the heap
 * \return  true if empty
 */
extern inline bool
heap_empty (heap_t *heap)
{
    return !heap->root;
}

/**
 * Merge two heaps, result in the first one.
 * \param  heap_to  heap receiving the result
 * \param  heap_from  heap to be merge with the first one
 */
void
heap_merge (heap_t *heap_to, heap_t *heap_from);

/** Heap comparison function for an u32 node using modulo 2^32. */
bool
heap_node_u32_less_mod2p32 (heap_node_t *left, heap_node_t *right);

END_DECLS

#endif /* lib_heap_h */