kal_eheap.h File Reference

Generic array-based extraction-efficient heap implementation. More...

#include "qos_debug.h"
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

Defines
#define	kal_define_eheap(key_type, value_type)
	Define eheap related types: use this macro only once per compilation unit.
#define	kal_eheap_key_lt(a, b) ((a) < (b))
#define	kal_eheap_node_t(key_type, value_type) struct kal_eheap_node_##key_type ##_##value_type ##_t
	Template-like type for a eheap node (users should not use this).
#define	kal_eheap_t(key_type, value_type) kal_eheap_##key_type ##_##value_type ##_t
	Template-like type for a eheap container.
#define	kal_eheap_iterator_t(key_type, value_type) kal_eheap_iterator_##key_type ##_##value_type ##_t
	Template-like type for a eheap iterator.
#define	kal_eheap_init(self, N)
	Initialize an empty eheap with (initial) max storage capacity of N.
#define	kal_eheap_cleanup(self)
#define	kal_eheap_nodecpy(self, dst_pos, src_pos)
	Move a node contents from src_pos to dst_pos, overwriting destination contents.
#define	kal_eheap_push_down(self, param_pos, param_key)
	Push the specified key down the heap, as if it started from position (1-based) param_pos, moving up all the necessary items.
#define	kal_eheap_push_up(self, param_pos, param_key)
	Push the specified key up the heap, as if it started from position (1-based) param_pos, moving down all the necessary items.
#define	kal_eheap_add(self, _key, _value, _p_it)
	Add the pair (_key, _value) to the eheap, and store the corresponding removal iterator in *_p_it.
#define	kal_eheap_get_min(self, p_key, p_value)
	Return (without removing) the heap root pair, corresponding to the minimum key value.
#define	kal_eheap_del_min(self)
	Remove the top (root) of the heap, alias the minimum-key element.
#define	kal_eheap_del(self, p_it)
	Remove an arbitrary element of the heap, through the iterator stored during a kal_eheap_add() operation.
#define	kal_eheap_size(self) (self)->num_elems
	Return the current size of the heap.
#define	kal_eheap_iterator_valid(p_it) ((p_it)->pos != 0)
	Check if provided iterator is valid or has been invalidated.
#define	kal_eheap_iterator_init(p_it)
	Initialize an iterator as non-valid.
#define	kal_eheap_begin(self, p_it)
#define	kal_eheap_has_next(self, p_it) ((p_it)->pos < (self)->num_elems)
#define	kal_eheap_next(self, p_it, p_key, p_val)

Detailed Description

Generic array-based extraction-efficient heap implementation.

Definition in file kal_eheap.h.

Define Documentation

#define kal_define_eheap	(	key_type,
		value_type		)

Value:

typedef struct kal_eheap_iterator_##key_type ##_##value_type ##_t { \
    int pos; \
  } kal_eheap_iterator_##key_type ##_##value_type ##_t; \
  typedef struct kal_eheap_node_##key_type ##_##value_type ##_t { \
    key_type key; \
    value_type value; \
    kal_eheap_iterator_##key_type ##_##value_type ##_t *p_iterator; \
  } kal_eheap_node_##key_type ##_##value_type ##_t; \
  typedef struct kal_eheap_##key_type ##_##value_type ##_t { \
    kal_eheap_node_t(key_type, value_type) *elems; \
    int num_elems; \
    int max_num_elems; \
  } kal_eheap_##key_type ##_##value_type ##_t

Define eheap related types: use this macro only once per compilation unit.

Definition at line 14 of file kal_eheap.h.

#define kal_eheap_add	(	self,
		_key,
		_value,
		_p_it	)

Value:

({ \
  qos_rv __rv = QOS_OK; \
  typeof((self)->elems[0].p_iterator) _a_p_it = (_p_it); \
  do { \
    int _a_pos = (self)->num_elems + 1; \
    if (_a_pos == (self)->max_num_elems + 1) { \
      __rv = QOS_E_FULL; \
      break; \
    } \
    (self)->num_elems++; \
    _a_pos = kal_eheap_push_up((self), _a_pos, (_key)); \
    (self)->elems[_a_pos - 1].key = (_key); \
    (self)->elems[_a_pos - 1].value = (_value); \
    if (_a_p_it) { \
      (self)->elems[_a_pos - 1].p_iterator = _a_p_it; \
      _a_p_it->pos = _a_pos; \
    } else { \
      (self)->elems[_a_pos - 1].p_iterator = NULL; \
    } \
  } while (0); \
  __rv; \
})

Add the pair (_key, _value) to the eheap, and store the corresponding removal iterator in *_p_it.

Definition at line 128 of file kal_eheap.h.

Referenced by kal_eheap_t(), and main().

#define kal_eheap_begin	(	self,
		p_it		)

Value:

do { \
    (p_it)->pos = 0; \
  } while (0)

Definition at line 242 of file kal_eheap.h.

#define kal_eheap_cleanup ( self )

Value:

({ \
  qos_rv __rv = QOS_OK; \
  do { \
    qos_free((self)->elems); \
    (self)->num_elems = (self)->max_num_elems = 0; \
  } while (0); \
  __rv; \
})

Definition at line 64 of file kal_eheap.h.

Referenced by kal_eheap_t(), and main().

#define kal_eheap_del	(	self,
		p_it		)

Value:

({ \
  qos_rv __rv = QOS_OK; \
  int _d_pos = (p_it)->pos, _d_pos2; \
  typeof((self)->elems[0].key) _d_key; \
  do { \
    if ((self)->num_elems == 0) { \
      __rv = QOS_E_EMPTY; \
      break; \
    } \
    if (_d_pos == 0) { /* Invalid iterator detection */ \
      __rv = QOS_E_INVALID_PARAM; \
      break; \
    } \
    (p_it)->pos = 0; /* Invalidate iterator */ \
    _d_key = (self)->elems[(self)->num_elems - 1].key; \
    (self)->num_elems--; \
    if ((self)->num_elems == 0 || (self)->num_elems + 1 == _d_pos) \
      break; \
    _d_pos2 = kal_eheap_push_down((self), _d_pos, _d_key); \
    if (_d_pos2 == _d_pos) \
      _d_pos2 = kal_eheap_push_up((self), _d_pos, _d_key); \
    /* We use on purpose num_elems + 1, as we know it is legal */ \
    kal_eheap_nodecpy((self), _d_pos2, (self)->num_elems + 1); \
  } while (0); \
  __rv; \
})

Remove an arbitrary element of the heap, through the iterator stored during a kal_eheap_add() operation.

Note:: The corresponding iterator is not deallocated, but it is invalidated.

Definition at line 198 of file kal_eheap.h.

Referenced by kal_eheap_t().

#define kal_eheap_del_min ( self )

Value:

({ \
  qos_rv __dm_rv = QOS_OK; \
  int _dm_pos = 1; \
  int _dm_key; \
  do { \
    if ((self)->num_elems == 0) { \
      __dm_rv = QOS_E_EMPTY; \
      break; \
    } \
    if ((self)->elems[0].p_iterator) \
      (self)->elems[0].p_iterator->pos = 0; /* Invalidate iterator */ \
    _dm_key = (self)->elems[(self)->num_elems - 1].key; \
    (self)->num_elems--; \
/*    printf("Pushing down pos: %d\n", _dm_pos); \
*/    _dm_pos = kal_eheap_push_down((self), _dm_pos, _dm_key); \
/*    printf("Copying into pos: %d\n", _dm_pos); \
*/    /* This copies on purpose from a position == num_elems + 1, 'cause we know it is legal */ \
    kal_eheap_nodecpy((self), _dm_pos, (self)->num_elems + 1); \
  } while (0); \
  __dm_rv; \
})

Remove the top (root) of the heap, alias the minimum-key element.

Note:: The corresponding iterator, if any, is not deallocated, but it is invalidated.

Definition at line 171 of file kal_eheap.h.

Referenced by kal_eheap_t(), and main().

#define kal_eheap_get_min	(	self,
		p_key,
		p_value	)

Value:

({ \
  qos_rv __gm_rv = QOS_OK; \
  do { \
    if ((self)->num_elems == 0) { \
      __gm_rv = QOS_E_EMPTY; \
      break; \
    } \
    *(p_key) = (self)->elems[0].key; \
    *(p_value) = (self)->elems[0].value; \
  } while (0); \
  __gm_rv; \
})

Return (without removing) the heap root pair, corresponding to the minimum key value.

Definition at line 152 of file kal_eheap.h.

Referenced by kal_eheap_t(), and main().

#define kal_eheap_has_next	(	self,
		p_it		)	((p_it)->pos < (self)->num_elems)

Definition at line 247 of file kal_eheap.h.

#define kal_eheap_init	(	self,
		N		)

Value:

({ \
  qos_rv __rv = QOS_OK; \
  do { \
    (self)->elems = qos_malloc(sizeof((self)->elems[0]) << N); \
    if ((self)->elems == NULL) { \
      __rv = QOS_E_NO_MEMORY; \
      break; \
    } \
    (self)->max_num_elems = 1 << N; \
    (self)->num_elems = 0; \
  } while (0); \
  __rv; \
})

Initialize an empty eheap with (initial) max storage capacity of N.

Todo:: Investigate possibility of use of realloc() or similar within the kernel

Definition at line 50 of file kal_eheap.h.

Referenced by kal_eheap_t(), and main().

#define kal_eheap_iterator_init ( p_it )

Value:

do { \
    (p_it)->pos = 0; \
  } while (0)

Initialize an iterator as non-valid.

Definition at line 237 of file kal_eheap.h.

#define kal_eheap_iterator_t	(	key_type,
		value_type		)	kal_eheap_iterator_##key_type ##_##value_type ##_t

Template-like type for a eheap iterator.

Definition at line 42 of file kal_eheap.h.

Referenced by kal_eheap_t().

#define kal_eheap_iterator_valid ( p_it ) ((p_it)->pos != 0)

Check if provided iterator is valid or has been invalidated.

Note:: An extraction operation invalidates the iterator, for example.

Definition at line 234 of file kal_eheap.h.

Referenced by kal_eheap_t().

#define kal_eheap_key_lt	(	a,
		b		)	((a) < (b))

Definition at line 30 of file kal_eheap.h.

#define kal_eheap_next	(	self,
		p_it,
		p_key,
		p_val	)

Value:

({ \
  typeof(&(self)->elems[0].key) _p_key = (p_key); \
  typeof(&(self)->elems[0].value) _p_val = (p_val); \
  qos_rv __rv = QOS_OK; \
  do { \
    if ((p_it)->pos < (self)->num_elems) { \
      (p_it)->pos++; \
      if (_p_key) \
        *(_p_key) = (self)->elems[(p_it)->pos - 1].key; \
      if (_p_val) \
        *(_p_val) = (self)->elems[(p_it)->pos - 1].value; \
    } else { \
      __rv = QOS_E_EMPTY; \
      break; \
    } \
  } while (0); \
  __rv; \
})

Definition at line 250 of file kal_eheap.h.

#define kal_eheap_node_t	(	key_type,
		value_type		)	struct kal_eheap_node_##key_type ##_##value_type ##_t

Template-like type for a eheap node (users should not use this).

Definition at line 34 of file kal_eheap.h.

#define kal_eheap_nodecpy	(	self,
		dst_pos,
		src_pos	)

Value:

do { \
    (self)->elems[(dst_pos) - 1] = (self)->elems[(src_pos) - 1]; \
    if ((self)->elems[(dst_pos) - 1].p_iterator) \
      (self)->elems[(dst_pos) - 1].p_iterator->pos = (dst_pos); \
  } while (0)

Move a node contents from src_pos to dst_pos, overwriting destination contents.

Definition at line 74 of file kal_eheap.h.

#define kal_eheap_push_down	(	self,
		param_pos,
		param_key	)

Value:

({ \
  int _pd_pos = (param_pos); \
  do { \
    int _pd_pos_child; \
    typeof((self)->elems[0].key) _pd_key = (param_key); \
/*    printf("pos: %d\n", _pd_pos);  fflush(stdout); \
*/      _pd_pos_child = _pd_pos * 2; \
    while ( \
        ((_pd_pos_child <= (self)->num_elems) && kal_eheap_key_lt((self)->elems[_pd_pos_child - 1].key, _pd_key)) \
        || ((_pd_pos_child + 1 <= (self)->num_elems) && kal_eheap_key_lt((self)->elems[_pd_pos_child].key, _pd_key)) \
      ) { \
        if ((_pd_pos_child + 1 <= (self)->num_elems) && kal_eheap_key_lt((self)->elems[_pd_pos_child].key, (self)->elems[_pd_pos_child - 1].key)) \
          _pd_pos_child++; \
        kal_eheap_nodecpy((self), _pd_pos, _pd_pos_child); \
        _pd_pos = _pd_pos_child; \
        _pd_pos_child = _pd_pos * 2; \
/*      printf("pos: %d\n", _pd_pos); \
*/    } \
  } while (0); \
  _pd_pos; \
})

Push the specified key down the heap, as if it started from position (1-based) param_pos, moving up all the necessary items.

Returns the correct position, in which the element has not been copied yet.

Definition at line 86 of file kal_eheap.h.

#define kal_eheap_push_up	(	self,
		param_pos,
		param_key	)

Value:

({ \
  int _pu_pos = (param_pos); \
  do { \
    int _pu_pos_fath = _pu_pos / 2; \
/*    printf("xpos: %d\n", _pu_pos);  fflush(stdout); \
*/    while ((_pu_pos != 1) && kal_eheap_key_lt((param_key), (self)->elems[_pu_pos_fath - 1].key)) { \
      kal_eheap_nodecpy((self), _pu_pos, _pu_pos_fath); \
      _pu_pos = _pu_pos_fath; \
      _pu_pos_fath = _pu_pos / 2; \
/*      printf("pos: %d\n", _pu_pos);  fflush(stdout); \
*/    } \
  } while (0); \
  _pu_pos; \
})

Push the specified key up the heap, as if it started from position (1-based) param_pos, moving down all the necessary items.

Returns the correct position, in which the element has not been copied yet.

Definition at line 111 of file kal_eheap.h.

#define kal_eheap_size ( self ) (self)->num_elems

Return the current size of the heap.

Definition at line 226 of file kal_eheap.h.

Referenced by kal_eheap_t(), and main().

#define kal_eheap_t	(	key_type,
		value_type		)	kal_eheap_##key_type ##_##value_type ##_t

Template-like type for a eheap container.

Definition at line 38 of file kal_eheap.h.

kal_eheap.h File Reference

Defines

Detailed Description

Define Documentation