51cdac56c26d693a9a655f2318c8b81d3e2c67b8

1 #ifndef _BABELTRACE_PRIO_HEAP_H

2 #define _BABELTRACE_PRIO_HEAP_H

4 /*

5 * prio_heap.h

6 *

7 * Static-sized priority heap containing pointers. Based on CLRS,

8 * chapter 6.

9 *

10 * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

11 *

12 * Permission is hereby granted, free of charge, to any person obtaining a copy

13 * of this software and associated documentation files (the "Software"), to deal

14 * in the Software without restriction, including without limitation the rights

15 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

16 * copies of the Software, and to permit persons to whom the Software is

17 * furnished to do so, subject to the following conditions:

18 *

19 * The above copyright notice and this permission notice shall be included in

20 * all copies or substantial portions of the Software.

21 */

23 #include <unistd.h>

29 };

31 /**

32 * heap_maximum - return the largest element in the heap

33 * @heap: the heap to be operated on

34 *

35 * Returns the largest element in the heap, without performing any modification

36 * to the heap structure. Returns NULL if the heap is empty.

37 */

39 {

41 }

43 /**

44 * heap_init - initialize the heap

45 * @heap: the heap to initialize

46 * @alloc_len: number of elements initially allocated

47 * @gt: function to compare the elements

48 *

49 * Returns -ENOMEM if out of memory.

50 */

55 /**

56 * heap_free - free the heap

57 * @heap: the heap to free

58 */

61 /**

62 * heap_insert - insert an element into the heap

63 * @heap: the heap to be operated on

64 * @p: the element to add

65 *

66 * Insert an element into the heap.

67 *

68 * Returns -ENOMEM if out of memory.

69 */

72 /**

73 * heap_remove - remove the largest element from the heap

74 * @heap: the heap to be operated on

75 *

76 * Returns the largest element in the heap. It removes this element from the

77 * heap. Returns NULL if the heap is empty.

78 */

81 /**

82 * heap_cherrypick - remove a given element from the heap

83 * @heap: the heap to be operated on

84 * @p: the element

85 *

86 * Remove the given element from the heap. Return the element if present, else

87 * return NULL. This algorithm has a complexity of O(n), which is higher than

88 * O(log(n)) provided by the rest of this API.

89 */

92 /**

93 * heap_replace_max - replace the the largest element from the heap

94 * @heap: the heap to be operated on

95 * @p: the pointer to be inserted as topmost element replacement

96 *

97 * Returns the largest element in the heap. It removes this element from the

98 * heap. The heap is rebalanced only once after the insertion. Returns NULL if

99 * the heap is empty.

100 *

101 * This is the equivalent of calling heap_remove() and then heap_insert(), but

102 * it only rebalances the heap once. It never allocates memory.

103 */

This page took 0.030865 seconds and 4 git commands to generate.