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
|
/* heaps.h -- Binomial Heaps
*
* (c) 2008, 2009 Bjoern Brandenburg
*/
#ifndef HEAP_H
#define HEAP_H
#define NOT_IN_HEAP UINT_MAX
struct heap_node {
struct heap_node* parent;
struct heap_node* next;
struct heap_node* child;
unsigned int degree;
void* value;
struct heap_node** ref;
};
struct heap {
struct heap_node* head;
/* We cache the minimum of the heap.
* This speeds up repeated peek operations.
*/
struct heap_node* min;
};
typedef int (*heap_prio_t)(struct heap_node* a, struct heap_node* b);
void heap_init(struct heap* heap);
void heap_node_init(struct heap_node** ref_to_heap_node_ptr, void* value);
static inline int heap_node_in_heap(struct heap_node* h)
{
return h->degree != NOT_IN_HEAP;
}
static inline int heap_empty(struct heap* heap)
{
return heap->head == NULL && heap->min == NULL;
}
/* insert (and reinitialize) a node into the heap */
void heap_insert(heap_prio_t higher_prio,
struct heap* heap,
struct heap_node* node);
/* merge addition into target */
void heap_union(heap_prio_t higher_prio,
struct heap* target,
struct heap* addition);
struct heap_node* heap_peek(heap_prio_t higher_prio,
struct heap* heap);
struct heap_node* heap_take(heap_prio_t higher_prio,
struct heap* heap);
void heap_uncache_min(heap_prio_t higher_prio, struct heap* heap);
int heap_decrease(heap_prio_t higher_prio, struct heap_node* node);
void heap_delete(heap_prio_t higher_prio,
struct heap* heap,
struct heap_node* node);
/* allocate from memcache */
struct heap_node* heap_node_alloc(int gfp_flags);
void heap_node_free(struct heap_node* hn);
/* allocate a heap node for value and insert into the heap */
int heap_add(heap_prio_t higher_prio, struct heap* heap,
void* value, int gfp_flags);
void* heap_take_del(heap_prio_t higher_prio,
struct heap* heap);
#endif
|
