kal_eheap.h

Go to the documentation of this file.

#ifndef KAL_EHEAP_H_
#define KAL_EHEAP_H_

#include "qos_debug.h"
#include "qos_memory.h"

#define kal_define_eheap(key_type, value_type) \
  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

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

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

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

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

#define kal_eheap_init(self, N) ({ \
  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; \
})

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

#define kal_eheap_nodecpy(self, dst_pos, src_pos) \
  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)

#define kal_eheap_push_down(self, param_pos, param_key) ({ \
  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; \
})

#define kal_eheap_push_up(self, param_pos, param_key) ({ \
  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; \
})

#define kal_eheap_add(self, _key, _value, _p_it) ({ \
  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; \
})

#define kal_eheap_get_min(self, p_key, p_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; \
})

#define kal_eheap_del_min(self) ({ \
  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; \
})

#define kal_eheap_del(self, p_it) ({ \
  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; \
})

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

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

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

#define kal_eheap_begin(self, p_it) \
  do { \
    (p_it)->pos = 0; \
  } while (0)

#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) ({ \
  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; \
})

#endif /*KAL_EHEAP_H_*/

---