class Heap

Heap class. More...

Definition#include <heap.hh>
Inherited byTimerList
List of all Methods
Annotated List
Files
Globals
Hierarchy
Index

Public Methods


Detailed Description

Heap implements a priority queue, mostly used by Timer objects. This implementation supports removal of arbitrary objects from the heap, even if they are not located at the top. To support this, the objects must reserve an "int" field, whose offset is passed to the heap constructor, and which is is used to store the position of the object within the heap. This offset can be computed using the OFFSET_OF macro.

The OFFSET_OF macro is used to return the offset of a field within a structure. It is used by the heap management routines.

 Heap ()

Heap

Default constructor used to build a standard heap with no support for removal from the middle.

explicit  Heap (int)

Heap

Constructor used to build a standard heap with support for removal from the middle. Should be used with something like:


 struct _foo { ... ; int my_index ; ... } x;
 ...
 Heap *h = new Heap (OFFSET_OF(x, my_index));

 ~Heap ()

~Heap

[virtual]

Destructor

void  push (Heap_Key k, void *p)

push

Push an object into the heap by using a sorting key.

Parameters:
kthe sorting key.
pthe object to push into the heap.

void  push (int i)

push

Bubble-up an object in the heap.

Note: this probably should not be exposed.

Parameters:
ithe offset of the object to bubble-up.

void  move (Heap_Key new_key, void *object)

move

Move an object in the heap according to the new key. Note: can only be used if the heap supports removal from the middle.

Parameters:
new_keythe new key.
objectthe object to move.

struct heap_entry * top ()

top

[const]

Get a pointer to the entry at the top of the heap.

Both the key and the value can be derived from the return value.

Returns: the pointer to the entry at the top of the heap.

size_t  size ()

size

[const]

Get the number of elements in the heap.

Returns: the number of elements in the heap.

void  pop ()

pop

Remove the object top of the heap.

void  pop_obj (void *p)

pop_obj

Remove an object from an arbitrary position in the heap.

Note: only valid if the heap supports this kind of operation.

Parameters:
pthe object to remove if not NULL, otherwise the top element from the heap.

void  heapify ()

heapify

Rebuild the heap structure.

void  print ()

print

void  print_all (int)

print_all


Generated by: pavlin on possum.icir.org on Mon Mar 10 19:34:43 2003, using kdoc 2.0a54+XORP.