configure: re-enable '-Wunused-parameter'
[babeltrace.git] / src / lib / prio-heap / prio-heap.h
CommitLineData
1eb0c69c 1/*
0235b0db 2 * SPDX-License-Identifier: MIT
1eb0c69c 3 *
0235b0db 4 * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
1eb0c69c 5 *
0235b0db
MJ
6 * Static-sized priority heap containing pointers. Based on CLRS,
7 * chapter 6.
1eb0c69c
MD
8 */
9
0235b0db
MJ
10#ifndef _BABELTRACE_PRIO_HEAP_H
11#define _BABELTRACE_PRIO_HEAP_H
12
1eb0c69c 13#include <unistd.h>
91d81473 14#include "common/macros.h"
1eb0c69c
MD
15
16struct ptr_heap {
17 size_t len, alloc_len;
18 void **ptrs;
19 int (*gt)(void *a, void *b);
20};
21
eacd552c
MD
22#ifdef DEBUG_HEAP
23void check_heap(const struct ptr_heap *heap);
24#else
25static inline
ecd7492f 26void check_heap(const struct ptr_heap *heap __attribute__((unused)))
eacd552c
MD
27{
28}
29#endif
30
1eb0c69c 31/**
dd06413f 32 * bt_heap_maximum - return the largest element in the heap
1eb0c69c
MD
33 * @heap: the heap to be operated on
34 *
35 * Returns the largest element in the heap, without performing any modification
36 * to the heap structure. Returns NULL if the heap is empty.
37 */
dd06413f 38static inline void *bt_heap_maximum(const struct ptr_heap *heap)
1eb0c69c 39{
eacd552c 40 check_heap(heap);
91d81473 41 return G_LIKELY(heap->len) ? heap->ptrs[0] : NULL;
1eb0c69c
MD
42}
43
44/**
dd06413f 45 * bt_heap_init - initialize the heap
1eb0c69c
MD
46 * @heap: the heap to initialize
47 * @alloc_len: number of elements initially allocated
48 * @gt: function to compare the elements
49 *
50 * Returns -ENOMEM if out of memory.
51 */
dd06413f 52extern int bt_heap_init(struct ptr_heap *heap,
1eb0c69c
MD
53 size_t alloc_len,
54 int gt(void *a, void *b));
55
56/**
dd06413f 57 * bt_heap_free - free the heap
1eb0c69c
MD
58 * @heap: the heap to free
59 */
dd06413f 60extern void bt_heap_free(struct ptr_heap *heap);
1eb0c69c
MD
61
62/**
dd06413f 63 * bt_heap_insert - insert an element into the heap
1eb0c69c
MD
64 * @heap: the heap to be operated on
65 * @p: the element to add
66 *
67 * Insert an element into the heap.
68 *
69 * Returns -ENOMEM if out of memory.
70 */
dd06413f 71extern int bt_heap_insert(struct ptr_heap *heap, void *p);
1eb0c69c
MD
72
73/**
dd06413f 74 * bt_heap_remove - remove the largest element from the heap
1eb0c69c
MD
75 * @heap: the heap to be operated on
76 *
77 * Returns the largest element in the heap. It removes this element from the
78 * heap. Returns NULL if the heap is empty.
79 */
dd06413f 80extern void *bt_heap_remove(struct ptr_heap *heap);
1eb0c69c
MD
81
82/**
dd06413f 83 * bt_heap_cherrypick - remove a given element from the heap
1eb0c69c
MD
84 * @heap: the heap to be operated on
85 * @p: the element
86 *
87 * Remove the given element from the heap. Return the element if present, else
88 * return NULL. This algorithm has a complexity of O(n), which is higher than
89 * O(log(n)) provided by the rest of this API.
90 */
dd06413f 91extern void *bt_heap_cherrypick(struct ptr_heap *heap, void *p);
1eb0c69c
MD
92
93/**
dd06413f 94 * bt_heap_replace_max - replace the the largest element from the heap
1eb0c69c
MD
95 * @heap: the heap to be operated on
96 * @p: the pointer to be inserted as topmost element replacement
97 *
98 * Returns the largest element in the heap. It removes this element from the
99 * heap. The heap is rebalanced only once after the insertion. Returns NULL if
100 * the heap is empty.
101 *
dd06413f 102 * This is the equivalent of calling bt_heap_remove() and then bt_heap_insert(), but
1eb0c69c
MD
103 * it only rebalances the heap once. It never allocates memory.
104 */
dd06413f 105extern void *bt_heap_replace_max(struct ptr_heap *heap, void *p);
1eb0c69c 106
23a151f0 107/**
dd06413f 108 * bt_heap_copy - copy a heap
23a151f0
JD
109 * @dst: the destination heap (must be allocated)
110 * @src: the source heap
111 *
112 * Returns -ENOMEM if out of memory.
113 */
dd06413f 114extern int bt_heap_copy(struct ptr_heap *dst, struct ptr_heap *src);
23a151f0 115
1eb0c69c 116#endif /* _BABELTRACE_PRIO_HEAP_H */
This page took 0.109215 seconds and 4 git commands to generate.