class Heap Heap class. More... Definition #include <heap.hh> Inherited by TimerList List of all Methods

Annotated List Files Globals Hierarchy Index

Public Methods

•  Heap ()
• explicit  Heap (int)
• virtual  ~Heap ()
• void  push (Heap_Key k, void *p)
• void  push (int i)
• void  move (Heap_Key new_key, void *object)
• struct heap_entry * top () const
• size_t  size () const
• void  pop ()
• void  pop_obj (void *p)
• void  heapify ()
• void  print ()
• void  print_all (int)

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.

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

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));

[virtual]

Destructor

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

Parameters:

k	the sorting key.
p	the object to push into the heap.

Bubble-up an object in the heap.

Note: this probably should not be exposed.

Parameters:

i	the offset of the object to bubble-up.

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_key	the new key.
object	the object to move.

[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.

[const]

Get the number of elements in the heap.

Returns: the number of elements in the heap.

Remove the object top of the heap.

Remove an object from an arbitrary position in the heap.

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

Parameters:

p	the object to remove if not NULL, otherwise the top element from the heap.

Rebuild the heap structure.