author | Florian Westphal <fw@strlen.de> |
Sun, 11 Jan 2009 20:20:11 +0100 | |
changeset 0 | aa628870c1d3 |
permissions | -rw-r--r-- |
0
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
1 |
#ifndef _LINUX_PRIO_HEAP_H |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
2 |
#define _LINUX_PRIO_HEAP_H |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
3 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
4 |
/* |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
5 |
* Simple insertion-only static-sized priority heap containing |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
6 |
* pointers, based on CLR, chapter 7 |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
7 |
*/ |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
8 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
9 |
#include <linux/gfp.h> |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
10 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
11 |
/** |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
12 |
* struct ptr_heap - simple static-sized priority heap |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
13 |
* @ptrs - pointer to data area |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
14 |
* @max - max number of elements that can be stored in @ptrs |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
15 |
* @size - current number of valid elements in @ptrs (in the range 0..@size-1 |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
16 |
* @gt: comparison operator, which should implement "greater than" |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
17 |
*/ |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
18 |
struct ptr_heap { |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
19 |
void **ptrs; |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
20 |
int max; |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
21 |
int size; |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
22 |
int (*gt)(void *, void *); |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
23 |
}; |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
24 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
25 |
/** |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
26 |
* heap_init - initialize an empty heap with a given memory size |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
27 |
* @heap: the heap structure to be initialized |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
28 |
* @size: amount of memory to use in bytes |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
29 |
* @gfp_mask: mask to pass to kmalloc() |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
30 |
* @gt: comparison operator, which should implement "greater than" |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
31 |
*/ |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
32 |
extern int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask, |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
33 |
int (*gt)(void *, void *)); |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
34 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
35 |
/** |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
36 |
* heap_free - release a heap's storage |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
37 |
* @heap: the heap structure whose data should be released |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
38 |
*/ |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
39 |
void heap_free(struct ptr_heap *heap); |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
40 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
41 |
/** |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
42 |
* heap_insert - insert a value into the heap and return any overflowed value |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
43 |
* @heap: the heap to be operated on |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
44 |
* @p: the pointer to be inserted |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
45 |
* |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
46 |
* Attempts to insert the given value into the priority heap. If the |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
47 |
* heap is full prior to the insertion, then the resulting heap will |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
48 |
* consist of the smallest @max elements of the original heap and the |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
49 |
* new element; the greatest element will be removed from the heap and |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
50 |
* returned. Note that the returned element will be the new element |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
51 |
* (i.e. no change to the heap) if the new element is greater than all |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
52 |
* elements currently in the heap. |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
53 |
*/ |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
54 |
extern void *heap_insert(struct ptr_heap *heap, void *p); |
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
55 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
56 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
57 |
|
aa628870c1d3
Port of Linux 2.6.28 for use with network simulation cradle.
Florian Westphal <fw@strlen.de>
parents:
diff
changeset
|
58 |
#endif /* _LINUX_PRIO_HEAP_H */ |