Keep packet header and context current
[babeltrace.git] / lib / prio_heap.c
CommitLineData
1eb0c69c
MD
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
25#ifndef max_t
26#define max_t(type, a, b) \
27 ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
28#endif
29
557255e5 30static
1eb0c69c
MD
31size_t parent(size_t i)
32{
33 return i >> 1;
34}
35
36static
37size_t left(size_t i)
38{
39 return i << 1;
40}
41
42static
43size_t right(size_t i)
44{
45 return (i << 1) + 1;
46}
47
557255e5
MD
48/*
49 * Copy of heap->ptrs pointer is invalid after heap_grow.
50 */
1eb0c69c
MD
51static
52int heap_grow(struct ptr_heap *heap, size_t new_len)
53{
54 void **new_ptrs;
55
56 if (heap->alloc_len >= new_len)
57 return 0;
58
59 heap->alloc_len = max_t(size_t, new_len, heap->alloc_len << 1);
60 new_ptrs = calloc(heap->alloc_len, sizeof(void *));
61 if (!new_ptrs)
62 return -ENOMEM;
63 if (heap->ptrs)
64 memcpy(new_ptrs, heap->ptrs, heap->len * sizeof(void *));
65 free(heap->ptrs);
66 heap->ptrs = new_ptrs;
67 return 0;
68}
69
70static
71int heap_set_len(struct ptr_heap *heap, size_t new_len)
72{
73 int ret;
74
75 ret = heap_grow(heap, new_len);
76 if (ret)
77 return ret;
78 heap->len = new_len;
79 return 0;
80}
81
82int heap_init(struct ptr_heap *heap, size_t alloc_len,
83 int gt(void *a, void *b))
84{
85 heap->ptrs = NULL;
86 heap->len = 0;
87 heap->alloc_len = 0;
88 heap->gt = gt;
89 /*
90 * Minimum size allocated is 1 entry to ensure memory allocation
91 * never fails within heap_replace_max.
92 */
93 return heap_grow(heap, max_t(size_t, 1, alloc_len));
94}
95
96void heap_free(struct ptr_heap *heap)
97{
98 free(heap->ptrs);
99}
100
101static void heapify(struct ptr_heap *heap, size_t i)
102{
103 void **ptrs = heap->ptrs;
104 size_t l, r, largest;
105
106 for (;;) {
107 l = left(i);
108 r = right(i);
109 if (l <= heap->len && ptrs[l] > ptrs[i])
110 largest = l;
111 else
112 largest = i;
113 if (r <= heap->len && ptrs[r] > ptrs[largest])
114 largest = r;
115 if (largest != i) {
116 void *tmp;
117
118 tmp = ptrs[i];
119 ptrs[i] = ptrs[largest];
120 ptrs[largest] = tmp;
121 i = largest;
122 continue;
123 } else {
124 break;
125 }
126 }
127}
128
129void *heap_replace_max(struct ptr_heap *heap, void *p)
130{
131 void *res;
1eb0c69c
MD
132
133 if (!heap->len) {
134 (void) heap_set_len(heap, 1);
557255e5 135 heap->ptrs[0] = p;
1eb0c69c
MD
136 return NULL;
137 }
138
139 /* Replace the current max and heapify */
557255e5
MD
140 res = heap->ptrs[0];
141 heap->ptrs[0] = p;
1eb0c69c
MD
142 heapify(heap, 0);
143 return res;
144}
145
146int heap_insert(struct ptr_heap *heap, void *p)
147{
557255e5
MD
148 void **ptrs;
149 size_t pos;
1eb0c69c
MD
150 int ret;
151
152 ret = heap_set_len(heap, heap->len + 1);
153 if (ret)
154 return ret;
557255e5 155 ptrs = heap->ptrs;
1eb0c69c
MD
156 /* Add the element to the end */
157 ptrs[heap->len - 1] = p;
557255e5
MD
158 pos = heap->len - 1;
159 /* Bubble it up to the appropriate position. */
160 for (;;) {
161 if (pos > 0 && heap->gt(ptrs[pos], ptrs[parent(pos)])) {
162 void *tmp;
163
164 /* Need to exchange */
165 tmp = ptrs[pos];
166 ptrs[pos] = ptrs[parent(pos)];
167 ptrs[parent(pos)] = tmp;
168 pos = parent(pos);
169 /*
170 * No need to rebalance: if we are larger than
171 * our parent, we are necessarily larger than
172 * its other child.
173 */
174 } else {
175 break;
176 }
177 }
1eb0c69c
MD
178 return 0;
179}
180
181void *heap_remove(struct ptr_heap *heap)
182{
1eb0c69c
MD
183 switch (heap->len) {
184 case 0:
185 return NULL;
186 case 1:
187 (void) heap_set_len(heap, 0);
557255e5 188 return heap->ptrs[0];
1eb0c69c
MD
189 }
190 /* Shrink, replace the current max by previous last entry and heapify */
191 heap_set_len(heap, heap->len - 1);
557255e5 192 return heap_replace_max(heap, heap->ptrs[heap->len - 1]);
1eb0c69c
MD
193}
194
195void *heap_cherrypick(struct ptr_heap *heap, void *p)
196{
1eb0c69c
MD
197 size_t pos, len = heap->len;
198
199 for (pos = 0; pos < len; pos++)
557255e5 200 if (heap->ptrs[pos] == p)
1eb0c69c
MD
201 goto found;
202 return NULL;
203found:
204 if (heap->len == 1) {
205 (void) heap_set_len(heap, 0);
557255e5 206 return heap->ptrs[0];
1eb0c69c
MD
207 }
208 /* Replace p with previous last entry and heapify. */
209 heap_set_len(heap, heap->len - 1);
557255e5 210 heap->ptrs[pos] = heap->ptrs[heap->len - 1];
1eb0c69c
MD
211 heapify(heap, pos);
212 return p;
213}
This page took 0.031061 seconds and 4 git commands to generate.