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
|
/*
* Binary Heap.
*
* Copyright (c) 2009 Marko Kreen, Skype Technologies OÜ
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
/** @file
* Binary heap.
*
* Binary heap is sort of binary tree held inside array,
* with following 2 properties:
* - heap property: each node is "better" than it's childs.
* - shape property: binary tree is complete, meaning all levels
* except the last one are fully filled.
*
* Instead of "min"- or "max"-heap, this is "best"-heap,
* as it operates with user-defined heap_is_better() functions,
* which is used to bubble elements on top.
*/
#ifndef _USUAL_HEAP_H_
#define _USUAL_HEAP_H_
#include <usual/cxalloc.h>
/**
* Object comparision function.
*
* Should return true if a needs to reach top before b,
* false if not or equal.
*/
typedef bool (*heap_is_better_f)(const void *a, const void *b);
/**
* Heap position storage.
*
* If user wants to delete elements from the middle of heap,
* this function should be used to keep track where the element
* is located.
*/
typedef void (*heap_save_pos_f)(void *a, unsigned pos);
/**
* Heap object.
*/
struct Heap;
/**
* Create new heap object.
*
* @param is_better_cb Callback to decide priority.
* @param save_pos_cb Callback to store current index.
* @param cx Allocation context.
*/
struct Heap *heap_create(
heap_is_better_f is_better_cb,
heap_save_pos_f save_pos_cb,
CxMem *cx);
/** Release memory allocated by heap */
void heap_destroy(struct Heap *h);
/** Put new object into heap */
bool heap_push(struct Heap *h, void *ptr);
/** Remove and return topmost object from heap */
void *heap_pop(struct Heap *h);
/** Return topmost object in heap */
void *heap_top(struct Heap *h);
/** Remove and return any object from heap by index */
void *heap_remove(struct Heap *h, unsigned pos);
/**
* Reserve room for more elements.
*
* Returns false if allocation failed.
*/
bool heap_reserve(struct Heap *h, unsigned extra);
/** Return number of objects in heap */
unsigned heap_size(struct Heap *h);
/* Return object by index, for testing */
void *heap_get_obj(struct Heap *h, unsigned pos);
#endif
|
