priority_queue.h
3.42 KB
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
* Copyright (C) 2013, 2014 Freie Universität Berlin
*
* This file is subject to the terms and conditions of the GNU Lesser
* General Public License v2.1. See the file LICENSE in the top level
* directory for more details.
*/
/**
* @addtogroup core_util
* @{
*
* @file
* @brief A simple priority queue
*
* @author Kaspar Schleiser <kaspar@schleiser.de>
*/
#ifndef QUEUE_H
#define QUEUE_H
#include <stddef.h>
#include <stdint.h>
#ifdef __cplusplus
extern "C" {
#endif
/**
* @brief data type for priority queue nodes
*/
typedef struct priority_queue_node {
struct priority_queue_node *next; /**< next queue node */
uint32_t priority; /**< queue node priority */
unsigned int data; /**< queue node data */
} priority_queue_node_t;
/**
* @brief data type for priority queues
*/
typedef struct {
priority_queue_node_t *first; /**< first queue node */
} priority_queue_t;
/**
* @brief Static initializer for priority_queue_node_t.
*/
#define PRIORITY_QUEUE_NODE_INIT { NULL, 0, 0 }
/**
* @brief Initialize a priority queue node object.
* @details For initialization of variables use PRIORITY_QUEUE_NODE_INIT
* instead. Only use this function for dynamically allocated
* priority queue nodes.
* @param[out] priority_queue_node
* pre-allocated priority_queue_node_t object, must not be NULL.
*/
static inline void priority_queue_node_init(
priority_queue_node_t *priority_queue_node)
{
priority_queue_node_t qn = PRIORITY_QUEUE_NODE_INIT;
*priority_queue_node = qn;
}
/**
* @brief Static initializer for priority_queue_t.
*/
#define PRIORITY_QUEUE_INIT { NULL }
/**
* @brief Initialize a priority queue object.
* @details For initialization of variables use PRIORITY_QUEUE_INIT
* instead. Only use this function for dynamically allocated
* priority queues.
* @param[out] priority_queue
* pre-allocated priority_queue_t object, must not be NULL.
*/
static inline void priority_queue_init(priority_queue_t *priority_queue)
{
priority_queue_t q = PRIORITY_QUEUE_INIT;
*priority_queue = q;
}
/**
* @brief remove the priority queue's head
*
* @param[out] root the queue's root
*
* @return the old head
*/
priority_queue_node_t *priority_queue_remove_head(priority_queue_t *root);
/**
* @brief insert `new_obj` into `root` based on its priority
*
* @details
* The new object will be appended after objects with the same priority.
*
* @param[in,out] root the queue's root
* @param[in] new_obj the object to prepend
*
* @pre The queue does not already contain @p new_obj.
*/
void priority_queue_add(priority_queue_t *root, priority_queue_node_t *new_obj);
/**
* @brief remove `node` from `root`
*
* @param[in,out] root the priority queue's root
* @param[in] node the node to remove
*/
void priority_queue_remove(priority_queue_t *root, priority_queue_node_t *node);
#if ENABLE_DEBUG
/**
* @brief print the data and priority of every node in the given priority queue
*
* @note requires ::ENABLE_DEBUG to be set to 1 for this file
*/
void priority_queue_print(priority_queue_t *root);
/**
* @brief print the data, priority, and successor of a given node
*
* @note requires ::ENABLE_DEBUG to be set to 1 for this file
*/
void priority_queue_print_node(priority_queue_t *root);
#endif
#ifdef __cplusplus
}
#endif
/** @} */
#endif /* QUEUE_H */