projects
/
lttng-modules.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Add heap debug option, fix heap.
[lttng-modules.git]
/
lib
/
prio_heap
/
prio_heap.c
diff --git
a/lib/prio_heap/prio_heap.c
b/lib/prio_heap/prio_heap.c
index 58d5d6ae9df05a112026196b252a204cbd432407..f6b8158055c5b13da34fde1978ecb92a83396db6 100644
(file)
--- a/
lib/prio_heap/prio_heap.c
+++ b/
lib/prio_heap/prio_heap.c
@@
-19,24
+19,40
@@
#include <linux/slab.h>
#include "prio_heap.h"
#include <linux/slab.h>
#include "prio_heap.h"
+#ifdef DEBUG_HEAP
+void check_heap(const struct ptr_heap *heap)
+{
+ size_t i;
+
+ if (!heap->len)
+ return;
+
+ for (i = 1; i < heap->len; i++)
+ WARN_ON_ONCE(!heap->gt(heap->ptrs[i], heap->ptrs[0]));
+}
+#endif
+
static
size_t parent(size_t i)
{
static
size_t parent(size_t i)
{
- return
i
>> 1;
+ return
(i -1)
>> 1;
}
static
size_t left(size_t i)
{
}
static
size_t left(size_t i)
{
- return
i <<
1;
+ return
(i << 1) +
1;
}
static
size_t right(size_t i)
{
}
static
size_t right(size_t i)
{
- return (i << 1) +
1
;
+ return (i << 1) +
2
;
}
}
+/*
+ * Copy of heap->ptrs pointer is invalid after heap_grow.
+ */
static
int heap_grow(struct ptr_heap *heap, size_t new_len)
{
static
int heap_grow(struct ptr_heap *heap, size_t new_len)
{
@@
-93,94
+109,98
@@
static void heapify(struct ptr_heap *heap, size_t i)
size_t l, r, largest;
for (;;) {
size_t l, r, largest;
for (;;) {
+ void *tmp;
+
l = left(i);
r = right(i);
l = left(i);
r = right(i);
- if (l <
= heap->len && ptrs[l] > ptrs[i]
)
+ if (l <
heap->len && heap->gt(ptrs[l], ptrs[i])
)
largest = l;
else
largest = i;
largest = l;
else
largest = i;
- if (r <
= heap->len && ptrs[r] > ptrs[largest]
)
+ if (r <
heap->len && heap->gt(ptrs[r], ptrs[largest])
)
largest = r;
largest = r;
- if (largest != i) {
- void *tmp;
-
- tmp = ptrs[i];
- ptrs[i] = ptrs[largest];
- ptrs[largest] = tmp;
- i = largest;
- continue;
- } else {
+ if (largest == i)
break;
break;
- }
+ tmp = ptrs[i];
+ ptrs[i] = ptrs[largest];
+ ptrs[largest] = tmp;
+ i = largest;
}
}
+ check_heap(heap);
}
void *heap_replace_max(struct ptr_heap *heap, void *p)
{
void *res;
}
void *heap_replace_max(struct ptr_heap *heap, void *p)
{
void *res;
- void **ptrs = heap->ptrs;
if (!heap->len) {
(void) heap_set_len(heap, 1);
if (!heap->len) {
(void) heap_set_len(heap, 1);
- ptrs[0] = p;
+ heap->ptrs[0] = p;
+ check_heap(heap);
return NULL;
}
/* Replace the current max and heapify */
return NULL;
}
/* Replace the current max and heapify */
- res = ptrs[0];
- ptrs[0] = p;
+ res =
heap->
ptrs[0];
+
heap->
ptrs[0] = p;
heapify(heap, 0);
return res;
}
int heap_insert(struct ptr_heap *heap, void *p)
{
heapify(heap, 0);
return res;
}
int heap_insert(struct ptr_heap *heap, void *p)
{
- void **ptrs = heap->ptrs;
+ void **ptrs;
+ size_t pos;
int ret;
ret = heap_set_len(heap, heap->len + 1);
if (ret)
return ret;
int ret;
ret = heap_set_len(heap, heap->len + 1);
if (ret)
return ret;
- /* Add the element to the end */
- ptrs[heap->len - 1] = p;
- /* rebalance */
- heapify(heap, 0);
+ ptrs = heap->ptrs;
+ pos = heap->len - 1;
+ while (pos > 0 && heap->gt(p, ptrs[parent(pos)])) {
+ /* Move parent down until we find the right spot */
+ ptrs[pos] = ptrs[parent(pos)];
+ pos = parent(pos);
+ }
+ ptrs[pos] = p;
+ check_heap(heap);
return 0;
}
void *heap_remove(struct ptr_heap *heap)
{
return 0;
}
void *heap_remove(struct ptr_heap *heap)
{
- void **ptrs = heap->ptrs;
-
switch (heap->len) {
case 0:
return NULL;
case 1:
(void) heap_set_len(heap, 0);
switch (heap->len) {
case 0:
return NULL;
case 1:
(void) heap_set_len(heap, 0);
- return ptrs[0];
+ return
heap->
ptrs[0];
}
/* Shrink, replace the current max by previous last entry and heapify */
heap_set_len(heap, heap->len - 1);
}
/* Shrink, replace the current max by previous last entry and heapify */
heap_set_len(heap, heap->len - 1);
- return heap_replace_max(heap, ptrs[heap->len - 1]);
+ /* len changed. previous last entry is at heap->len */
+ return heap_replace_max(heap, heap->ptrs[heap->len]);
}
void *heap_cherrypick(struct ptr_heap *heap, void *p)
{
}
void *heap_cherrypick(struct ptr_heap *heap, void *p)
{
- void **ptrs = heap->ptrs;
size_t pos, len = heap->len;
for (pos = 0; pos < len; pos++)
size_t pos, len = heap->len;
for (pos = 0; pos < len; pos++)
- if (ptrs[pos] == p)
+ if (
heap->
ptrs[pos] == p)
goto found;
return NULL;
found:
if (heap->len == 1) {
(void) heap_set_len(heap, 0);
goto found;
return NULL;
found:
if (heap->len == 1) {
(void) heap_set_len(heap, 0);
- return ptrs[0];
+ check_heap(heap);
+ return heap->ptrs[0];
}
/* Replace p with previous last entry and heapify. */
heap_set_len(heap, heap->len - 1);
}
/* Replace p with previous last entry and heapify. */
heap_set_len(heap, heap->len - 1);
- ptrs[pos] = ptrs[heap->len - 1];
+ /* len changed. previous last entry is at heap->len */
+ heap->ptrs[pos] = heap->ptrs[heap->len];
heapify(heap, pos);
return p;
}
heapify(heap, pos);
return p;
}
This page took
0.025468 seconds
and
4
git commands to generate.