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
|
/* bheaps.h -- Binomial Heaps
*
* (c) 2008, 2009 Bjoern Brandenburg
*/
#ifndef BHEAP_H
#define BHEAP_H
#define NOT_IN_HEAP UINT_MAX
struct bheap_node {
struct bheap_node* parent;
struct bheap_node* next;
struct bheap_node* child;
unsigned int degree;
void* value;
struct bheap_node** ref;
};
struct bheap {
struct bheap_node* head;
/* We cache the minimum of the heap.
* This speeds up repeated peek operations.
*/
struct bheap_node* min;
};
typedef int (*bheap_prio_t)(struct bheap_node* a, struct bheap_node* b);
void bheap_init(struct bheap* heap);
void bheap_node_init(struct bheap_node** ref_to_bheap_node_ptr, void* value);
static inline int bheap_node_in_heap(struct bheap_node* h)
{
return h->degree != NOT_IN_HEAP;
}
static inline int bheap_empty(struct bheap* heap)
{
return heap->head == NULL && heap->min == NULL;
}
typedef void (*bheap_for_each_t)(struct bheap_node* node, void* args);
void bheap_for_each(struct bheap* heap, bheap_for_each_t fn, void* args);
/* insert (and reinitialize) a node into the heap */
void bheap_insert(bheap_prio_t higher_prio,
struct bheap* heap,
struct bheap_node* node);
/* merge addition into target */
void bheap_union(bheap_prio_t higher_prio,
struct bheap* target,
struct bheap* addition);
struct bheap_node* bheap_peek(bheap_prio_t higher_prio,
struct bheap* heap);
struct bheap_node* bheap_take(bheap_prio_t higher_prio,
struct bheap* heap);
void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap);
int bheap_decrease(bheap_prio_t higher_prio, struct bheap_node* node);
void bheap_delete(bheap_prio_t higher_prio,
struct bheap* heap,
struct bheap_node* node);
/* allocate from memcache */
struct bheap_node* bheap_node_alloc(int gfp_flags);
void bheap_node_free(struct bheap_node* hn);
/* allocate a heap node for value and insert into the heap */
int bheap_add(bheap_prio_t higher_prio, struct bheap* heap,
void* value, int gfp_flags);
void* bheap_take_del(bheap_prio_t higher_prio,
struct bheap* heap);
#endif
|
