Data Structures
struct	EGeKHeap_t
	Structure to hold a whole heap structure, this structure is designed so that it can grow on the fly with a low cost. More...
struct	EGeKHeapCn_t
	Structure to store the information relevant to an element in the heap. More...
Files
file	eg_ekheap.c
file	eg_ekheap.ex.c
file	eg_ekheap.h
Defines
#define	EG_EKHEAP_DEBUG 100
	Debug level for the heap.
#define	EG_EKHEAP_ENTRY 3
	number of maximum entries in the vector values
#define	EG_EKHEAP_POISON UINT_MAX
	Poison position for heap connector not in a heap.
#define	EGeKHeapAdd(__hp, __hcn)
	Add an element to the heap.
#define	EGeKHeapChangeD(__hp, __width)
	set the breath of the heap, this function must be called only when the heap is empty.
#define	EGeKHeapChangeVal(__hp, __hcn, __new_val)
	Change the value of an element in the heap.
#define	EGeKHeapCheck(__hp) 0
	Check the integrity of the given heap.
#define	EGeKHeapClear(__hp) EGeKHeapResize(__hp,0)
	Clear a heap structure, and free any internal memory (not allocated by the user).
#define	EGeKHeapCnClear(__hcn)
	Free all internal memory used by this structured not allocated by the user. This function should be called after an init call, and only once.
#define	EGeKHeapCnInit(__hcn)
	Initialize a heap conector structure. This function will allocate any interal memory not allocated by the user, it should be called only once, or after a clear function call.
#define	EGeKHeapCnReset(__hcn) ((__hcn)->pos = EG_EKHEAP_POISON)
	Reset a heap conector to the same state as after an init call, this function is provided only for completness.
#define	EGeKHeapDel(__hp, __hcn)
	Eliminate an element from the heap, note that the position stored in the eliminated element is reset to zero.
#define	EGeKHeapEmpty(__hp) ((__hp)->sz = 0)
	set the number of elements in hte heap to zero.
#define	EGeKHeapFatherId(__d, __id) ((__id)?(((__id)-1)/(__d)):0)
	return the index of the father of the given index.
#define	EGeKHeapFirstChildId(__d, __id) ((__d)*(__id)+1)
	Give the first child for a given position.
#define	EGeKHeapGetMin(__hp)
	get the minimum conector in the heap, if the heap is empty, return NULL.
#define	EGeKHeapGetMinKVal(__hp, __k, __number)
	get the k-th value of the first element in the heap.
#define	EGeKHeapGetMinVal(__hp, __number)
	get the minimum value in the heap, note that since we are dealing with a vector of values sorted lexicographically, the value is the value in the first coordinate, other values can be accesses through EGeKHeapGetMinKVal function.
#define	EGeKHeapInit(__hp) (*(__hp) = (EGeKHeap_t){0,0,0,0})
	Initialize a heap as an empty heap (with no space for conectors).
#define	EGeKHeapIsFull(__hp) ({EGeKHeap_t*const __EGekhp = (__hp); __EGekhp->sz == __EGekhp->max_sz;})
	Return one if the heap is full, zero otherwise.
#define	EGeKHeapIsLess(__hcn1, __hcn2)
	given two heap connectors, return one if the first is less than the second (in lexicographic order).
#define	EGeKHeapResize(__hp, __new_sz)
	resize the heap cn array to the given size, if the new size is zero, it is equivalent to free the internal memory, and left the heap as an empty heap with zero space.
#define	EGeKHeapSiftDown(__hp, __hcn)
	Move an element down in the heap (position 0 is the top), this kind of operation is needed whenever we increase the value in a heap element.
#define	EGeKHeapSiftUp(__hp, __hcn)
	move an element in the heap up in the heap (position 0 is the top, this kind of move is neded whenever we decrease the value in a heap element).
#define	EGeKHepReset(__hp) EGeKHeapResize(__hp,0)
	Reset the given heap as an empty heap (just as returned by the init call.
Functions
void	EGeKHeapCopyVal (EGlpNum_t const dst, const EGlpNum_t const src)
	copy two vector of values (only EG_EKHEAP_ENTRY positions) from the rource to the destination.
int	ekheap_parseargs (int argc, char *argv, unsigned int d, unsigned int ch, EGlpNum_t v, char **file_name)
	parse the input argumenbts for the program
void	ekheap_usage (char *program)
	This program reads a list of double values from a text file and uses a heap to sort them. It also allows the user to change the value of one of the read numbers after they have been placed in the heap. The purpose of this program is to illustrate the use of the EGeKHeap structure and its associated functions.
int	main (int argc, char **argv)
	main function
Test macros, enabled only if debug level is high enough.

#define	EGeKHeapCHECK_CN(__hp, __hcn)
#define	EGeKHeapCHECK_NF(__hp)

Detailed Description

Here we define the basic interface for d-heaps with an array of values with the lexicographic order for vectors as an embeded structure. In this implementation the heap does not grow on the fly, meaning that it may fill-up during an add call, to avoid that, the user must call re-allocate when necesary. the heap start as a heap of size zero. This implementatioon is a minimum-heap implementatiton. Note also that the internal connector array is shifted one position to the left. This is done so that the first element is in position 1, this also speed-up the computation of the parent and childrens of a given position.

Version:: 0.0.1

History:

2010-09-05
- Change implementation of EGeKHeapClear to free all internal memory, including the one asked for the user during a EGeKHeapResize call.
2008-07-30
- First implementation

Note:: This implementatiton is designed as a template using as base the types of EGlpNum

Define Documentation

#define EG_EKHEAP_DEBUG 100

Debug level for the heap.

Examples:: eg_ekheap.ex.c.

Definition at line 60 of file eg_ekheap.h.

Referenced by main().

#define EG_EKHEAP_ENTRY 3

number of maximum entries in the vector values

Examples:: eg_ekheap.ex.c.

Definition at line 77 of file eg_ekheap.h.

Referenced by main().

#define EG_EKHEAP_POISON UINT_MAX

Poison position for heap connector not in a heap.

Definition at line 93 of file eg_ekheap.h.

#define EGeKHeapAdd	(	__hp,
		__hcn
	)

Value:

({\
  EGeKHeap_t*const __EGlhp = (__hp);\
  EGeKHeapCn_t*const __EGlcn = (__hcn);\
  EGeKHeapCHECK_NF(__EGlhp);\
  __EGlcn->pos = __EGlhp->sz, \
  __EGlhp->cn[__EGlhp->sz] = __EGlcn, \
  __EGlhp->sz +=1, \
  EGeKHeapSiftUp(__EGlhp,__EGlcn), 0;})

Add an element to the heap.

Parameters:

	__hp	heap where to add the element.
	__hcn	element to be added.

Returns:: zero on success, non-zero otherwise.

Examples:: eg_ekheap.ex.c.

Definition at line 285 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapChangeD	(	__hp,
		__width
	)

Value:

({\
  EGeKHeap_t*const __EGehp = (__hp);\
  EXIT((__width)<2,"Width should be at least 2 for heaps");\
  __EGehp->sz ? 1 : (__EGehp->d = (__width), 0);})

set the breath of the heap, this function must be called only when the heap is empty.

Parameters:

	__hp	heap to set breath.
	__width	new with for the heap.

Returns:: zero on success, non-zero otherwise.

Examples:: eg_ekheap.ex.c.

Definition at line 407 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapChangeVal	(	__hp,
		__hcn,
		__new_val
	)

Value:

({\
  EGeKHeapCn_t*const __EGEKHcn = (__hcn);\
  (EGeKHeapIsLess(__new_val,(__EGEKHcn)->val)) ? (EGeKHeapCopyVal((__EGEKHcn)->val,__new_val),EGeKHeapSiftUp(__hp,__EGEKHcn)) : (EGeKHeapCopyVal((__EGEKHcn)->val,__new_val),EGeKHeapSiftDown(__hp,__EGEKHcn));})

Change the value of an element in the heap.

Parameters:

	__hp	heap where we are working.
	__hcn	element in the heap that we are going to change it's value.
	__new_val	new value for the element (note this is an array of size at least EG_EKHEAP_ENTRY.

Returns:: zero on success, non-zero otherwise.

Examples:: eg_ekheap.ex.c.

Definition at line 350 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCheck ( __hp ) 0

Check the integrity of the given heap.

Parameters:

__hp

heap to check.

Returns:: zero on success, non-zero otherwise.

Examples:: eg_ekheap.ex.c.

Definition at line 397 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCHECK_CN	(	__hp,
		__hcn
	)

Definition at line 70 of file eg_ekheap.h.

#define EGeKHeapCHECK_NF ( __hp )

Definition at line 71 of file eg_ekheap.h.

#define EGeKHeapClear ( __hp ) EGeKHeapResize(__hp,0)

Clear a heap structure, and free any internal memory (not allocated by the user).

Parameters:

__hp

heap to clear.

Examples:: eg_ekheap.ex.c.

Definition at line 166 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCnClear ( __hcn )

Value:

do{\
  EGeKHeapCn_t*const __EKHcn = (__hcn);\
  int __EKHi = EG_EKHEAP_ENTRY;\
  for( ; __EKHi-- ; ){EGlpNumClearVar(__EKHcn->val[__EKHi]);}}while(0)

Free all internal memory used by this structured not allocated by the user. This function should be called after an init call, and only once.

Parameters:

__hcn

conector to clear.

Examples:: eg_ekheap.ex.c.

Definition at line 120 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCnInit ( __hcn )

Value:

do{\
  EGeKHeapCn_t*const __EKHcn = (__hcn);\
  int __EKHi = EG_EKHEAP_ENTRY;\
  memset(__EKHcn,0,sizeof(EGeKHeapCn_t));\
  for( ; __EKHi-- ; ){EGlpNumInitVar(__EKHcn->val[__EKHi]);}\
  __EKHcn->pos = EG_EKHEAP_POISON;}while(0)

Initialize a heap conector structure. This function will allocate any interal memory not allocated by the user, it should be called only once, or after a clear function call.

Parameters:

__hcn

conector to initialize.

Examples:: eg_ekheap.ex.c.

Definition at line 101 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapCnReset ( __hcn ) ((__hcn)->pos = EG_EKHEAP_POISON)

Reset a heap conector to the same state as after an init call, this function is provided only for completness.

Parameters:

__hcn

conector to reset

Definition at line 113 of file eg_ekheap.h.

#define EGeKHeapDel	(	__hp,
		__hcn
	)

Value:

({\
  EGeKHeap_t*const __EGlhp = (__hp);\
  EGeKHeapCn_t*const __EGlhpcn = (__hcn);\
  unsigned int const __EGlcn = __EGlhpcn->pos;\
  unsigned int const __EGlhsz = __EGlhp->sz - 1;\
  __EGlhpcn->pos = EG_EKHEAP_POISON;\
  __EGlhp->sz = __EGlhsz;\
  if(__EGlhsz && __EGlhsz != __EGlcn){\
    __EGlhp->cn[__EGlcn] = __EGlhp->cn[__EGlhp->sz];\
    __EGlhp->cn[__EGlcn]->pos = __EGlcn;\
    EGeKHeapSiftDown(__EGlhp,__EGlhp->cn[__EGlcn]);}\
  __EGlhp->cn[__EGlhp->sz] = 0;})

Eliminate an element from the heap, note that the position stored in the eliminated element is reset to zero.

Parameters:

	__hp	heap where we are working.
	__hcn	element to eliminate from the heap.

Returns:: zero on success, non-zero otherwise.

Examples:: eg_ekheap.ex.c.

Definition at line 361 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapEmpty ( __hp ) ((__hp)->sz = 0)

set the number of elements in hte heap to zero.

Parameters:

__hp

heap to empty.

Definition at line 146 of file eg_ekheap.h.

#define EGeKHeapFatherId	(	__d,
		__id
	)		((__id)?(((__id)-1)/(__d)):0)

return the index of the father of the given index.

Parameters:

	__d	breadth of the heap.
	__id	position in the array to wich we want to compute it's father.

Definition at line 223 of file eg_ekheap.h.

#define EGeKHeapFirstChildId	(	__d,
		__id
	)		((__d)*(__id)+1)

Give the first child for a given position.

Parameters:

	__id	position that we want to get the first child.
	__d	breath of the heap.

Definition at line 298 of file eg_ekheap.h.

#define EGeKHeapGetMin ( __hp )

Value:

({\
  EGeKHeap_t*const __EGehp = (__hp);\
  __EGehp->sz ? __EGehp->cn[0] : 0;})

get the minimum conector in the heap, if the heap is empty, return NULL.

Parameters:

__hp

eap where we are working.

Returns:: pointer to the minimum element in the heap.

Examples:: eg_ekheap.ex.c.

Definition at line 201 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapGetMinKVal	(	__hp,
		__k,
		__number
	)

Value:

({\
  EGeKHeap_t*const __EGehp = (__hp);\
  const int __EGki = (__k);\
  EXITL(EG_EKHEAP_DEBUG,(__EGki >= EG_EKHEAP_ENTRY) || (__EGki <0),\
        "K=%d out of range in EGeKHeapGetMinKVal", __EGki);\
  __EGehp->sz ? (EGlpNumCopy(__number,__EGehp->cn[0]->val[__EGki]),0):1;})

get the k-th value of the first element in the heap.

Parameters:

	__hp	heap where we are working.
	__number	where to store the result.
	__k	which value to get (between 0 and EG_EKHEAP_ENTRY.

Returns:: zero on success, non-zero otherwise.

Definition at line 188 of file eg_ekheap.h.

#define EGeKHeapGetMinVal	(	__hp,
		__number
	)

Value:

({\
  EGeKHeap_t*const __EGehp = (__hp);\
  __EGehp->sz ? (EGlpNumCopy(__number,__EGehp->cn[0]->val[0]),0):1;})

get the minimum value in the heap, note that since we are dealing with a vector of values sorted lexicographically, the value is the value in the first coordinate, other values can be accesses through EGeKHeapGetMinKVal function.

Parameters:

	__hp	heap where we are working.
	__number	where to store the result

Returns:: zero on success, non-zero otherwise.

Definition at line 177 of file eg_ekheap.h.

#define EGeKHeapInit ( __hp ) (*(__hp) = (EGeKHeap_t){0,0,0,0})

Initialize a heap as an empty heap (with no space for conectors).

Parameters:

__hp

heap to initialize.

Examples:: eg_ekheap.ex.c.

Definition at line 152 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapIsFull ( __hp ) ({EGeKHeap_t*const __EGekhp = (__hp); __EGekhp->sz == __EGekhp->max_sz;})

Return one if the heap is full, zero otherwise.

Parameters:

__hp

heat to check

Definition at line 140 of file eg_ekheap.h.

#define EGeKHeapIsLess	(	__hcn1,
		__hcn2
	)

Value:

({\
  EGlpNum_t*const __EGEKH1 = (__hcn1);\
  EGlpNum_t*const __EGEKH2 = (__hcn2);\
  int __EGEKHj = 0, __EGEKHrval = 0;\
  for( ; __EGEKHj < EG_EKHEAP_ENTRY ; __EGEKHj++)\
  {\
    if(EGlpNumIsLess(__EGEKH1[__EGEKHj], __EGEKH2[__EGEKHj])){\
      __EGEKHrval = 1; break;}\
    else if (EGlpNumIsNeq(__EGEKH1[__EGEKHj], __EGEKH2[__EGEKHj],epsLpNum)){\
      __EGEKHrval = 0; break;}\
  }\
  __EGEKHrval;})

given two heap connectors, return one if the first is less than the second (in lexicographic order).

Parameters:

	__hcn1	first vector array.
	__hcn2	second vector array.

Returns:: one if __hcn1 <_LEX __hcn2

Definition at line 231 of file eg_ekheap.h.

#define EGeKHeapResize	(	__hp,
		__new_sz
	)

Value:

({\
  EGeKHeap_t*const __EGehp = (__hp);\
  const size_t __EGehp_nsz = (size_t)(__new_sz);\
  __EGehp->cn = EGrealloc((__EGehp->cn), __EGehp_nsz * sizeof(EGeKHeapCn_t*));\
  __EGehp->max_sz = (unsigned int)(__EGehp_nsz);})

resize the heap cn array to the given size, if the new size is zero, it is equivalent to free the internal memory, and left the heap as an empty heap with zero space.

Parameters:

	__hp	heap where we are working.
	__new_sz	new size for the cn array .

Examples:: eg_ekheap.ex.c.

Definition at line 212 of file eg_ekheap.h.

Referenced by main().

#define EGeKHeapSiftDown	(	__hp,
		__hcn
	)

Move an element down in the heap (position 0 is the top), this kind of operation is needed whenever we increase the value in a heap element.

Parameters:

	__hp	heap where we are working.
	__hcn	element in the heap to move.

Returns:: zero on success, non-zero otherwise.

Definition at line 308 of file eg_ekheap.h.

#define EGeKHeapSiftUp	(	__hp,
		__hcn
	)

Value:

({\
  EGeKHeap_t*const __EGehp = (__hp);\
  EGeKHeapCn_t*const __EGecn = (__hcn);\
  unsigned int __EGcpos = __EGecn->pos;\
  unsigned int __EGfpos = EGeKHeapFatherId(__EGehp->d,__EGcpos);\
  EGeKHeapCn_t*__EGfcn = __EGehp->cn[__EGfpos];\
  EGeKHeapCHECK_CN(__EGehp,__EGecn);\
  while(__EGcpos && \
        EGeKHeapIsLess(__EGecn->val,__EGfcn->val))\
  {\
    __EGfcn->pos = __EGcpos;\
    __EGehp->cn[__EGcpos] = __EGfcn;\
    __EGcpos = __EGfpos;\
    __EGfpos = EGeKHeapFatherId(__EGehp->d,__EGcpos);\
    __EGfcn = __EGehp->cn[__EGfpos];\
  }\
  __EGecn->pos = __EGcpos;\
  __EGehp->cn[__EGcpos] = __EGecn;\
  0;})

move an element in the heap up in the heap (position 0 is the top, this kind of move is neded whenever we decrease the value in a heap element).

Parameters:

	__hp	heap where we are working.
	__hcn	element in the heap to move.

Returns:: zero on success, non-zero otherwise.

Definition at line 259 of file eg_ekheap.h.

#define EGeKHepReset ( __hp ) EGeKHeapResize(__hp,0)

Reset the given heap as an empty heap (just as returned by the init call.

Parameters:

__hp

heap to reset

Definition at line 159 of file eg_ekheap.h.

Function Documentation

void EGeKHeapCopyVal	(	EGlpNum_t *const	dst,
		const EGlpNum_t *const	src
	)

copy two vector of values (only EG_EKHEAP_ENTRY positions) from the rource to the destination.

Parameters:

	src	source array.
	dst	destination array.

int ekheap_parseargs	(	int	argc,
		char **	argv,
		unsigned int *	d,
		unsigned int *	ch,
		EGlpNum_t *	v,
		char **	file_name
	)

parse the input argumenbts for the program

Examples:: eg_ekheap.ex.c.

Definition at line 57 of file eg_ekheap.ex.c.

References ekheap_usage().

Referenced by main().

Here is the call graph for this function:

void ekheap_usage ( char * program )

This program reads a list of double values from a text file and uses a heap to sort them. It also allows the user to change the value of one of the read numbers after they have been placed in the heap. The purpose of this program is to illustrate the use of the EGeKHeap structure and its associated functions.

The input file format is: n Value_0 Value_1 Value_2 Value_3 ... Value_n display the usage message for this program

Examples:: eg_ekheap.ex.c.

Definition at line 45 of file eg_ekheap.ex.c.

Referenced by ekheap_parseargs().

int main	(	int	argc,
		char **	argv
	)

main function

Definition at line 105 of file eg_ekheap.ex.c.

References CHECKRVALG, EG_EKHEAP_DEBUG, EG_EKHEAP_ENTRY, EGeKHeapAdd, EGeKHeapChangeD, EGeKHeapChangeVal, EGeKHeapCheck, EGeKHeapClear, EGeKHeapCnClear, EGeKHeapCnInit, EGeKHeapDel, EGeKHeapGetMin, EGeKHeapInit, EGeKHeapResize, EGfree, EGioClose(), EGioGets(), EGioNParse(), EGioOpen(), EGlib_info(), EGlib_version(), EGlpNumClear(), EGlpNumStart(), EGsetLimits(), EGsigSet, EGsMalloc, ekheap_parseargs(), file_name, MESSAGE, TEST, and TESTG.

Here is the call graph for this function:

EGeKHeap

Data Structures

Files

Defines

Functions

Test macros, enabled only if debug level is high enough.

Detailed Description

Define Documentation

Function Documentation