ae47ebb8e4ba8f0b378e9a31b71b56ba4e4c207f
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 <linux/slab.h>
21 #include <linux/prio_heap.h>
23 int heap_init(struct ptr_heap
*heap
, size_t size
,
24 gfp_t gfpmask
, int gt(void *a
, void *b
))
26 WARN_ON_ONCE(size
== 0);
27 heap
->ptrs
= kmalloc(size
* sizeof(void *), gfpmask
);
36 void heap_free(struct ptr_heap
*heap
)
41 static void heapify(struct ptr_heap
*heap
, int pos
)
46 void *heap_replace_max(struct ptr_heap
*heap
, void *p
)
49 void **ptrs
= heap
->ptrs
;
57 /* Replace the current max and heapify */
64 void *heap_insert(struct ptr_heap
*heap
, void *p
)
66 void **ptrs
= heap
->ptrs
;
69 if (heap
->size
< heap
->max
) {
70 /* Add the element to the end */
71 heap
->ptrs
[heap
->size
++] = p
;
78 * Full. We need to replace the largest (if we are
79 * smaller or equal to this element).
81 if (heap
->gt(ptrs
[0], p
)) {
92 void *heap_remove(struct ptr_heap
*heap
)
94 void **ptrs
= heap
->ptrs
;
104 /* Shrink, replace the current max by previous last entry and heapify */
105 return heap_replace_max(heap
, ptrs
[--heap
->size
]);
108 void *heap_cherrypick(struct ptr_heap
*heap
, void *p
)
110 void **ptrs
= heap
->ptrs
;
111 size_t pos
, size
= heap
->size
;
113 for (pos
= 0; pos
< size
; pos
++)
118 if (heap
->size
== 1) {
123 * Replace p with previous last entry and heapify.
125 ptrs
[pos
] = ptrs
[--heap
->size
];
This page took 0.03122 seconds and 3 git commands to generate.