SphinxBase 5prealpha
heap.h File Reference

Heap Implementation. More...

#include <stdlib.h>
#include <sphinxbase/sphinxbase_export.h>
#include <sphinxbase/prim_type.h>

Go to the source code of this file.

Typedefs

typedef struct heap_s heap_t
 

Functions

SPHINXBASE_EXPORT heap_theap_new (void)
 Allocate a new heap and return handle to it.
 
SPHINXBASE_EXPORT int heap_insert (heap_t *heap, void *data, int32 val)
 Insert a new item into the given heap.
 
SPHINXBASE_EXPORT int heap_top (heap_t *heap, void **data, int32 *val)
 Return the topmost item in the heap.
 
SPHINXBASE_EXPORT int heap_pop (heap_t *heap, void **data, int32 *val)
 Like heap_top but also pop the top item off the heap.
 
SPHINXBASE_EXPORT int heap_remove (heap_t *heap, void *data)
 Remove an item from the heap.
 
SPHINXBASE_EXPORT size_t heap_size (heap_t *heap)
 Return the number of items in the heap.
 
SPHINXBASE_EXPORT int heap_destroy (heap_t *heap)
 Destroy the given heap; free the heap nodes.
 

Detailed Description

Heap Implementation.

General Comment: Sorted heap structure with three main operations:

  1. Insert a data item (with two attributes: an application supplied pointer and an integer value; the heap is maintained in ascending order of the integer value).
  2. Return the currently topmost item (i.e., item with smallest associated value).
  3. Return the currently topmost item and pop it off the heap.

Definition in file heap.h.

Typedef Documentation

◆ heap_t

typedef struct heap_s heap_t

Definition at line 94 of file heap.h.

Function Documentation

◆ heap_destroy()

SPHINXBASE_EXPORT int heap_destroy ( heap_t * heap)

Destroy the given heap; free the heap nodes.

NOTE: Data pointers in the nodes are NOT freed. Return value: 0 if successful, -1 otherwise.

Definition at line 281 of file heap.c.

References ckd_free(), heap_destroy(), and heap_pop().

Referenced by heap_destroy().

◆ heap_insert()

SPHINXBASE_EXPORT int heap_insert ( heap_t * heap,
void * data,
int32 val )

Insert a new item into the given heap.

Return value: 0 if successful, -1 otherwise.

Parameters
heapIn: Heap into which item is to be inserted
dataIn: Application-determined data pointer
valIn: According to item entered in sorted heap

Definition at line 161 of file heap.c.

References heap_insert().

Referenced by heap_insert().

◆ heap_new()

SPHINXBASE_EXPORT heap_t * heap_new ( void )

Allocate a new heap and return handle to it.

Definition at line 113 of file heap.c.

References ckd_calloc, and heap_new().

Referenced by heap_new().

◆ heap_pop()

SPHINXBASE_EXPORT int heap_pop ( heap_t * heap,
void ** data,
int32 * val )

Like heap_top but also pop the top item off the heap.

Definition at line 209 of file heap.c.

References heapnode_s::data, heap_pop(), and heapnode_s::val.

Referenced by heap_destroy(), and heap_pop().

◆ heap_remove()

SPHINXBASE_EXPORT int heap_remove ( heap_t * heap,
void * data )

Remove an item from the heap.

Definition at line 266 of file heap.c.

References heap_remove().

Referenced by heap_remove().

◆ heap_size()

SPHINXBASE_EXPORT size_t heap_size ( heap_t * heap)

Return the number of items in the heap.

Definition at line 273 of file heap.c.

References heap_size(), and heapnode_s::nr.

Referenced by heap_size().

◆ heap_top()

SPHINXBASE_EXPORT int heap_top ( heap_t * heap,
void ** data,
int32 * val )

Return the topmost item in the heap.

Return value: 1 if heap is not empty and the topmost value is returned; 0 if heap is empty; -1 if some error occurred.

Parameters
heapIn: Heap whose topmost item is to be returned
dataOut: Data pointer associated with the topmost item
valOut: Value associated with the topmost item

Definition at line 221 of file heap.c.

References heapnode_s::data, heap_top(), and heapnode_s::val.

Referenced by heap_top().