blob: 6ae650725fdcec58e0594ce73062c364fb964313 (
plain) (
blame)
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
|
/* SPDX-License-Identifier: GPL-3.0-or-later */
#pragma once
#include <stddef.h>
#include <stdint.h>
//
// This module implements a binary heap, specifically a min-heap. Each node contains a 64-bit
// value and a pointer to user data (user data is reused when nodes are extracted). All memory
// is a single contiguous chunk.
//
// In a min-heap, the root node always has the smallest value. The root node can be
// acquired with heap_next_extract() and extracted (removed) with heap_extract().
// The runtime of heap_extract() is O(log n).
//
// Prior to insertion, the node that will be inserted can already be obtained with
// heap_next_insert(), which MUST be succeeded by heap_insert() to actually insert the node.
// The runtime of heap_insert() is O(log n).
//
typedef struct {
uint64_t value;
void* user;
} heap_node_t; //!< Node in a heap
typedef struct {
heap_node_t* nodes;
size_t capacity;
size_t count;
} heap_t; //!< Min-heap data structure
/// Initialize a min-heap with the given capacity. The user_sizeof parameter specifies the size
/// of user data stored in each node.
/// Returns 0 on success, -1 on allocation failure.
int heap_init(heap_t* heap, size_t capacity, size_t user_sizeof);
/// Obtain the heap node that will be inserted next.
/// Returns heap node on success, or nullptr if the heap is full.
heap_node_t* heap_next_insert(heap_t* heap);
/// Insert a value into the heap.
void heap_insert(heap_t* heap, uint64_t value);
/// Peek the minimum value in the heap without removing it.
/// Returns heap node on success, or nullptr if the heap is empty.
heap_node_t* heap_next_extract(heap_t* heap);
/// Extract a node from the heap.
void heap_extract(heap_t* heap);
/// Free all resources associated with the heap.
void heap_free(heap_t* heap);
|
