xorp

Heap Class Reference

Inheritance diagram for Heap:
TestHeap

List of all members.

Classes

struct  heap_entry

Public Member Functions

 Heap ()
 Default constructor used to build a standard heap with no support for removal from the middle.
 Heap (bool)
 Constructor used to build a standard heap with support for removal from the middle.
virtual ~Heap ()
 Destructor.
void push (Heap_Key k, HeapBase *p)
 Push an object into the heap by using a sorting key.
void push (int i)
 Bubble-up an object in the heap.
void move (Heap_Key new_key, HeapBase *object)
 Move an object in the heap according to the new key.
struct heap_entrytop () const
 Get a pointer to the entry at the top of the heap.
size_t size () const
 Get the number of elements in the heap.
void pop ()
 Remove the object top of the heap.
void pop_obj (HeapBase *p)
 Remove an object from an arbitrary position in the heap.
void heapify ()
 Rebuild the heap structure.

Protected Types

typedef TimeVal Heap_Key

Private Member Functions

void push (Heap_Key key, HeapBase *p, int son)
int resize (int new_size)
void verify ()

Private Attributes

int _size
int _elements
bool _intrude
struct heap_entry_p

Friends

class TimerList

Constructor & Destructor Documentation

Heap::Heap ( bool  intrude) [explicit]

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

Member Function Documentation

void Heap::move ( Heap_Key  new_key,
HeapBase object 
)

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.
void Heap::pop_obj ( HeapBase p)

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 Heap::push ( int  i) [inline]

Bubble-up an object in the heap.

Note: this probably should not be exposed.

Parameters:
ithe offset of the object to bubble-up.
void Heap::push ( Heap_Key  k,
HeapBase p 
) [inline]

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

Parameters:
kthe sorting key.
pthe object to push into the heap.
size_t Heap::size ( ) const [inline]

Get the number of elements in the heap.

Returns:
the number of elements in the heap.
struct heap_entry* Heap::top ( ) const [inline, read]

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.

The documentation for this class was generated from the following files:
 All Classes Namespaces Functions Variables Typedefs Enumerations