SimGrid  3.14.159
Versatile Simulation of Distributed Systems
Heap: generic heap data structure

Detailed Description

This section describes the API to generic heap with O(log(n)) access.

Deprecated:
If you are using C++ you might want to use std::priority_queue instead.

Typedefs

typedef struct xbt_heapxbt_heap_t
 

Functions

xbt_heap_t xbt_heap_new (int init_size, void_f_pvoid_t const free_func)
 Creates a new heap. More...
 
void xbt_heap_free (xbt_heap_t H)
 kilkil a heap and its content More...
 
int xbt_heap_size (xbt_heap_t H)
 returns the number of elements in the heap More...
 
void xbt_heap_push (xbt_heap_t H, void *content, double key)
 Add an element into the heap. More...
 
voidxbt_heap_pop (xbt_heap_t H)
 Extracts from the heap and returns the element with the smallest key. More...
 
void xbt_heap_rm_elm (xbt_heap_t H, void *content, double key)
 Remove an arbitrary element from the heap. More...
 
double xbt_heap_maxkey (xbt_heap_t H)
 returns the smallest key in the heap (heap unchanged) More...
 
voidxbt_heap_maxcontent (xbt_heap_t H)
 returns the value associated to the smallest key in the heap (heap unchanged) More...
 
void xbt_heap_set_update_callback (xbt_heap_t H, void(*update_callback)(void *, int))
 Set the update callback function. More...
 
voidxbt_heap_remove (xbt_heap_t H, int i)
 Extracts from the heap and returns the element at position i. More...
 
void xbt_heap_update (xbt_heap_t H, int i, double key)
 Updates an element of the heap with a new value. More...
 

Typedef Documentation

◆ xbt_heap_t

typedef struct xbt_heap* xbt_heap_t

Function Documentation

◆ xbt_heap_new()

xbt_heap_t xbt_heap_new ( int  init_size,
void_f_pvoid_t const  free_func 
)
inline

Creates a new heap.

Parameters
init_sizeinitial size of the heap
free_funcfunction to call on each element when you want to free the whole heap (or NULL if nothing to do).

Creates a new heap.

◆ xbt_heap_free()

void xbt_heap_free ( xbt_heap_t  H)

kilkil a heap and its content

Parameters
Hpoor victim

◆ xbt_heap_size()

int xbt_heap_size ( xbt_heap_t  H)
inline

returns the number of elements in the heap

Parameters
Hthe heap we're working on
Returns
the number of elements in the heap

◆ xbt_heap_push()

void xbt_heap_push ( xbt_heap_t  H,
void content,
double  key 
)

Add an element into the heap.

Parameters
Hthe heap we're working on
contentthe object you want to add to the heap
keythe key associated to this object

The element with the smallest key is automatically moved at the top of the heap.

◆ xbt_heap_pop()

void* xbt_heap_pop ( xbt_heap_t  H)

Extracts from the heap and returns the element with the smallest key.

Parameters
Hthe heap we're working on
Returns
the element with the smallest key

Extracts from the heap and returns the element with the smallest key. The element with the next smallest key is automatically moved at the top of the heap.

◆ xbt_heap_rm_elm()

void xbt_heap_rm_elm ( xbt_heap_t  H,
void content,
double  key 
)

Remove an arbitrary element from the heap.

Parameters
Hthe heap we're working on
contentthe object you want to add to the heap
keythe key associated to this object

◆ xbt_heap_maxkey()

double xbt_heap_maxkey ( xbt_heap_t  H)
inline

returns the smallest key in the heap (heap unchanged)

Parameters
Hthe heap we're working on
Returns
the smallest key in the heap without modifying the heap.

◆ xbt_heap_maxcontent()

void* xbt_heap_maxcontent ( xbt_heap_t  H)

returns the value associated to the smallest key in the heap (heap unchanged)

Parameters
Hthe heap we're working on
Returns
the value associated to the smallest key in the heap without modifying the heap.

◆ xbt_heap_set_update_callback()

void xbt_heap_set_update_callback ( xbt_heap_t  H,
void(*)(void *, int)  update_callback 
)
inline

Set the update callback function.

Parameters
Hthe heap we're working on
update_callbackfunction to call on each element to update its index when needed.

◆ xbt_heap_remove()

void* xbt_heap_remove ( xbt_heap_t  H,
int  i 
)

Extracts from the heap and returns the element at position i.

Parameters
Hthe heap we're working on
ielement position
Returns
the element at position i if ok, NULL otherwise

Extracts from the heap and returns the element at position i. The heap is automatically reordered.

◆ xbt_heap_update()

void xbt_heap_update ( xbt_heap_t  H,
int  i,
double  key 
)

Updates an element of the heap with a new value.

Parameters
Hthe heap we're working on
ielement position
keynew value for the element

Updates an element of the heap with a new value.