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
)
43 void **ptrs
= heap
->ptrs
;
47 int left
= 2 * pos
+ 1;
48 int right
= 2 * pos
+ 2;
50 if (left
< heap
->size
&& heap
->gt(ptrs
[left
], p
))
52 if (right
< heap
->size
&& heap
->gt(ptrs
[right
], ptrs
[largest
]))
56 /* Push p down the heap one level and bump one up */
57 ptrs
[pos
] = ptrs
[largest
];
63 void *heap_replace_max(struct ptr_heap
*heap
, void *p
)
66 void **ptrs
= heap
->ptrs
;
74 /* Replace the current max and heapify */
81 void *heap_insert(struct ptr_heap
*heap
, void *p
)
83 void **ptrs
= heap
->ptrs
;
86 if (heap
->size
< heap
->max
) {
87 /* Add the element to the end */
88 heap
->ptrs
[heap
->size
++] = p
;
95 * Full. We need to replace the largest (if we are
96 * smaller or equal to this element).
98 if (heap
->gt(ptrs
[0], p
)) {
109 void *heap_remove(struct ptr_heap
*heap
)
111 void **ptrs
= heap
->ptrs
;
113 switch (heap
->size
) {
121 /* Shrink, replace the current max by previous last entry and heapify */
122 return heap_replace_max(heap
, ptrs
[--heap
->size
]);
125 void *heap_cherrypick(struct ptr_heap
*heap
, void *p
)
127 void **ptrs
= heap
->ptrs
;
128 size_t pos
, size
= heap
->size
;
130 for (pos
= 0; pos
< size
; pos
++)
135 if (heap
->size
== 1) {
140 * Replace p with previous last entry and heapify.
142 ptrs
[pos
] = ptrs
[--heap
->size
];
This page took 0.037398 seconds and 4 git commands to generate.