008c4cc3eaa3680b37c5aae97c18f0fd970081c4
[babeltrace.git] / lib / prio_heap.c
1 /*
2 * prio_heap.c
3 *
4 * Static-sized priority heap containing pointers. Based on CLRS,
5 * chapter 6.
6 *
7 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 *
9 * Permission is hereby granted, free of charge, to any person obtaining a copy
10 * of this software and associated documentation files (the "Software"), to deal
11 * in the Software without restriction, including without limitation the rights
12 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 * copies of the Software, and to permit persons to whom the Software is
14 * furnished to do so, subject to the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be included in
17 * all copies or substantial portions of the Software.
18 */
19
20 #include <babeltrace/prio_heap.h>
21 #include <errno.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <assert.h>
25
26 #ifndef max_t
27 #define max_t(type, a, b) \
28 ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
29 #endif
30
31 #ifdef DEBUG_HEAP
32 void check_heap(const struct ptr_heap *heap)
33 {
34 size_t i;
35
36 if (!heap->len)
37 return;
38
39 for (i = 1; i < heap->len; i++)
40 assert(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
41 }
42 #endif
43
44 static
45 size_t parent(size_t i)
46 {
47 return (i - 1) >> 1;
48 }
49
50 static
51 size_t left(size_t i)
52 {
53 return (i << 1) + 1;
54 }
55
56 static
57 size_t right(size_t i)
58 {
59 return (i << 1) + 2;
60 }
61
62 /*
63 * Copy of heap->ptrs pointer is invalid after heap_grow.
64 */
65 static
66 int heap_grow(struct ptr_heap *heap, size_t new_len)
67 {
68 void **new_ptrs;
69
70 if (heap->alloc_len >= new_len)
71 return 0;
72
73 heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
74 new_ptrs = calloc(heap->alloc_len, sizeof(void *));
75 if (!new_ptrs)
76 return -ENOMEM;
77 if (heap->ptrs)
78 memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
79 free(heap->ptrs);
80 heap->ptrs = new_ptrs;
81 return 0;
82 }
83
84 static
85 int heap_set_len(struct ptr_heap *heap, size_t new_len)
86 {
87 int ret;
88
89 ret = heap_grow(heap, new_len);
90 if (ret)
91 return ret;
92 heap->len = new_len;
93 return 0;
94 }
95
96 int heap_init(struct ptr_heap *heap, size_t alloc_len,
97 int gt(void *a, void *b))
98 {
99 heap->ptrs = NULL;
100 heap->len = 0;
101 heap->alloc_len = 0;
102 heap->gt = gt;
103 /*
104 * Minimum size allocated is 1 entry to ensure memory allocation
105 * never fails within heap_replace_max.
106 */
107 return heap_grow(heap, max_t(size_t, 1, alloc_len));
108 }
109
110 void heap_free(struct ptr_heap *heap)
111 {
112 free(heap->ptrs);
113 }
114
115 static void heapify(struct ptr_heap *heap, size_t i)
116 {
117 void **ptrs = heap->ptrs;
118 size_t l, r, largest;
119
120 for (;;) {
121 void *tmp;
122
123 l = left(i);
124 r = right(i);
125 if (l < heap->len && heap->gt(ptrs[l], ptrs[i]))
126 largest = l;
127 else
128 largest = i;
129 if (r < heap->len && heap->gt(ptrs[r], ptrs[largest]))
130 largest = r;
131 if (largest == i)
132 break;
133 tmp = ptrs[i];
134 ptrs[i] = ptrs[largest];
135 ptrs[largest] = tmp;
136 i = largest;
137 }
138 check_heap(heap);
139 }
140
141 void *heap_replace_max(struct ptr_heap *heap, void *p)
142 {
143 void *res;
144
145 if (!heap->len) {
146 (void) heap_set_len(heap, 1);
147 heap->ptrs[0] = p;
148 check_heap(heap);
149 return NULL;
150 }
151
152 /* Replace the current max and heapify */
153 res = heap->ptrs[0];
154 heap->ptrs[0] = p;
155 heapify(heap, 0);
156 return res;
157 }
158
159 int heap_insert(struct ptr_heap *heap, void *p)
160 {
161 void **ptrs;
162 size_t pos;
163 int ret;
164
165 ret = heap_set_len(heap, heap->len + 1);
166 if (ret)
167 return ret;
168 ptrs = heap->ptrs;
169 pos = heap->len - 1;
170 while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
171 /* Move parent down until we find the right spot */
172 ptrs[pos] = ptrs[parent(pos)];
173 pos = parent(pos);
174 }
175 ptrs[pos] = p;
176 check_heap(heap);
177 return 0;
178 }
179
180 void *heap_remove(struct ptr_heap *heap)
181 {
182 switch (heap->len) {
183 case 0:
184 return NULL;
185 case 1:
186 (void) heap_set_len(heap, 0);
187 return heap->ptrs[0];
188 }
189 /* Shrink, replace the current max by previous last entry and heapify */
190 heap_set_len(heap, heap->len - 1);
191 /* len changed. previous last entry is at heap->len */
192 return heap_replace_max(heap, heap->ptrs[heap->len]);
193 }
194
195 void *heap_cherrypick(struct ptr_heap *heap, void *p)
196 {
197 size_t pos, len = heap->len;
198
199 for (pos = 0; pos < len; pos++)
200 if (heap->ptrs[pos] == p)
201 goto found;
202 return NULL;
203 found:
204 if (heap->len == 1) {
205 (void) heap_set_len(heap, 0);
206 check_heap(heap);
207 return heap->ptrs[0];
208 }
209 /* Replace p with previous last entry and heapify. */
210 heap_set_len(heap, heap->len - 1);
211 /* len changed. previous last entry is at heap->len */
212 heap->ptrs[pos] = heap->ptrs[heap->len];
213 heapify(heap, pos);
214 return p;
215 }
This page took 0.031947 seconds and 3 git commands to generate.