forked from awslabs/aws-c-common
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpriority_queue.c
136 lines (111 loc) · 4.52 KB
/
priority_queue.c
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 2010-2017 Amazon.com, Inc. or its affiliates. All Rights Reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License").
* You may not use this file except in compliance with the License.
* A copy of the License is located at
*
* http://aws.amazon.com/apache2.0
*
* or in the "license" file accompanying this file. This file is distributed
* on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
* express or implied. See the License for the specific language governing
* permissions and limitations under the License.
*/
#include <aws/common/priority_queue.h>
#include <string.h>
#define parent_of(index) ((index & 1) ? index >> 1 : index > 1 ? (index - 2) >> 1 : 0)
#define left_of(index) ((index << 1) + 1)
/* Precondition: with the exception of the first element, the container must be in heap order */
static void sift_down(struct aws_priority_queue *queue) {
size_t root = 0;
size_t left = left_of(root);
size_t len = aws_array_list_length(&queue->container);
void *right_item, *left_item, *root_item;
while(left < len) {
aws_array_list_get_at_ptr(&queue->container, &left_item, left);
size_t right = left + 1;
if(right < len) {
aws_array_list_get_at_ptr(&queue->container, &right_item, right);
/* choose the larger/smaller of the two in case of a max/min heap respectively */
if (queue->pred(left_item, right_item) > 0) {
left = right;
left_item = right_item;
}
}
aws_array_list_get_at_ptr(&queue->container, &root_item, root);
if(queue->pred(root_item, left_item) > 0) {
aws_array_list_swap(&queue->container, left, root);
root = left;
left = left_of(root);
}
else {
break;
}
}
}
/* Precondition: Elements prior to the specified index must be in heap order. */
static void sift_up(struct aws_priority_queue *queue, size_t index) {
void *parent_item, *child_item;
size_t parent = parent_of(index);
while(index) {
aws_array_list_get_at_ptr(&queue->container, &parent_item, parent);
aws_array_list_get_at_ptr(&queue->container, &child_item, index);
if (queue->pred(parent_item, child_item) > 0) {
aws_array_list_swap(&queue->container, index, parent);
index = parent;
parent = parent_of(index);
}
else {
break;
}
}
}
int aws_priority_queue_dynamic_init(struct aws_priority_queue *queue, struct aws_allocator *alloc, size_t default_size,
size_t item_size, aws_priority_queue_compare pred) {
queue->pred = pred;
return aws_array_list_init_dynamic(&queue->container, alloc, default_size, item_size);
}
void aws_priority_queue_static_init(struct aws_priority_queue *queue,
void *heap, size_t item_count, size_t item_size, aws_priority_queue_compare pred) {
queue->pred = pred;
aws_array_list_init_static(&queue->container, heap, item_count, item_size);
}
void aws_priority_queue_clean_up(struct aws_priority_queue *queue) {
aws_array_list_clean_up(&queue->container);
}
int aws_priority_queue_push(struct aws_priority_queue *queue, void *item) {
int err = aws_array_list_push_back(&queue->container, item);
if(err) {
return err;
}
sift_up(queue, aws_array_list_length(&queue->container) - 1);
return AWS_OP_SUCCESS;
}
int aws_priority_queue_pop(struct aws_priority_queue *queue, void *item) {
if(0 == aws_array_list_length(&queue->container)) {
return aws_raise_error(AWS_ERROR_PRIORITY_QUEUE_EMPTY);
}
/* in this case aws_raise_error(..) has already been called */
if(aws_array_list_get_at(&queue->container, item, 0)) {
return AWS_OP_ERR;
}
aws_array_list_swap(&queue->container, 0, aws_array_list_length(&queue->container) - 1);
if(aws_array_list_pop_back(&queue->container)) {
return AWS_OP_ERR;
}
sift_down(queue);
return AWS_OP_SUCCESS;
}
int aws_priority_queue_top(struct aws_priority_queue *queue, void **item) {
if(0 == aws_array_list_length(&queue->container)) {
return aws_raise_error(AWS_ERROR_PRIORITY_QUEUE_EMPTY);
}
return aws_array_list_get_at_ptr(&queue->container, item, 0);
}
size_t aws_priority_queue_size(struct aws_priority_queue *queue) {
return aws_array_list_length(&queue->container);
}
size_t aws_priority_queue_capacity(struct aws_priority_queue *queue) {
return aws_array_list_capacity(&queue->container);
}