4 * Static-sized priority heap containing pointers. Based on CLRS,
7 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
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:
16 * The above copyright notice and this permission notice shall be included in
17 * all copies or substantial portions of the Software.
20 #include <babeltrace/prio_heap.h>
26 #define max_t(type, a, b) \
27 ((type) (a) > (type) (b) ? (type) (a) : (type) (b))
31 size_t parent(size_t i
)
43 size_t right(size_t i
)
49 * Copy of heap->ptrs pointer is invalid after heap_grow.
52 int heap_grow(struct ptr_heap
*heap
, size_t new_len
)
56 if (heap
->alloc_len
>= new_len
)
59 heap
->alloc_len
= max_t(size_t, new_len
, heap
->alloc_len
<< 1);
60 new_ptrs
= calloc(heap
->alloc_len
, sizeof(void *));
64 memcpy(new_ptrs
, heap
->ptrs
, heap
->len
* sizeof(void *));
66 heap
->ptrs
= new_ptrs
;
71 int heap_set_len(struct ptr_heap
*heap
, size_t new_len
)
75 ret
= heap_grow(heap
, new_len
);
82 int heap_init(struct ptr_heap
*heap
, size_t alloc_len
,
83 int gt(void *a
, void *b
))
90 * Minimum size allocated is 1 entry to ensure memory allocation
91 * never fails within heap_replace_max.
93 return heap_grow(heap
, max_t(size_t, 1, alloc_len
));
96 void heap_free(struct ptr_heap
*heap
)
101 static void heapify(struct ptr_heap
*heap
, size_t i
)
103 void **ptrs
= heap
->ptrs
;
104 size_t l
, r
, largest
;
109 if (l
<= heap
->len
&& ptrs
[l
] > ptrs
[i
])
113 if (r
<= heap
->len
&& ptrs
[r
] > ptrs
[largest
])
119 ptrs
[i
] = ptrs
[largest
];
129 void *heap_replace_max(struct ptr_heap
*heap
, void *p
)
134 (void) heap_set_len(heap
, 1);
139 /* Replace the current max and heapify */
146 int heap_insert(struct ptr_heap
*heap
, void *p
)
152 ret
= heap_set_len(heap
, heap
->len
+ 1);
156 /* Add the element to the end */
157 ptrs
[heap
->len
- 1] = p
;
159 /* Bubble it up to the appropriate position. */
161 if (pos
> 0 && heap
->gt(ptrs
[pos
], ptrs
[parent(pos
)])) {
164 /* Need to exchange */
166 ptrs
[pos
] = ptrs
[parent(pos
)];
167 ptrs
[parent(pos
)] = tmp
;
170 * No need to rebalance: if we are larger than
171 * our parent, we are necessarily larger than
181 void *heap_remove(struct ptr_heap
*heap
)
187 (void) heap_set_len(heap
, 0);
188 return heap
->ptrs
[0];
190 /* Shrink, replace the current max by previous last entry and heapify */
191 heap_set_len(heap
, heap
->len
- 1);
192 return heap_replace_max(heap
, heap
->ptrs
[heap
->len
- 1]);
195 void *heap_cherrypick(struct ptr_heap
*heap
, void *p
)
197 size_t pos
, len
= heap
->len
;
199 for (pos
= 0; pos
< len
; pos
++)
200 if (heap
->ptrs
[pos
] == p
)
204 if (heap
->len
== 1) {
205 (void) heap_set_len(heap
, 0);
206 return heap
->ptrs
[0];
208 /* Replace p with previous last entry and heapify. */
209 heap_set_len(heap
, heap
->len
- 1);
210 heap
->ptrs
[pos
] = heap
->ptrs
[heap
->len
- 1];
This page took 0.034205 seconds and 5 git commands to generate.