Generic Macro Generated Interval Heap in C

When I saw this amazing data structure I couldn’t stop myself from trying it! I first sought resources such as this and an article about it here. It basically works as a Max-Heap and a Min-Heap at the same time. I was heavily based on these amazing Java implementations here and here.

This implementation is a macro that generates code for whichever data type you wish to work with and it is part of the C Macro Collections library currently hosted on GitHub and further to be improved when needed.

The main macro is INTERVALHEAP_GENERATE with the following parameters:

  • PFX – Functions prefix
  • SNAME – The struct name
  • FMOD – Function modifier (currently only static or empty)
  • V – Data type you wish to work with

All you need to get started is the header intervalheap.h. Now since a question is limited to 65536 characters I had to strip down a lot of code and lines so that it could fit in this question since the macro takes a lot of characters. The code might seem a bit squished together but you can find the original code (and maybe in the future, updated) here.

intervalheap.h

#ifndef CMC_INTERVALHEAP_H #define CMC_INTERVALHEAP_H  #include <stdlib.h> #include <stdbool.h> #include <string.h>  #define INTERVALHEAP_GENERATE(PFX, SNAME, FMOD, V)    \     INTERVALHEAP_GENERATE_HEADER(PFX, SNAME, FMOD, V) \     INTERVALHEAP_GENERATE_SOURCE(PFX, SNAME, FMOD, V)  /* HEADER ********************************************************************/ #define INTERVALHEAP_GENERATE_HEADER(PFX, SNAME, FMOD, V)                    \                                                                              \     /* Heap Structure */                                                     \     typedef struct SNAME##_s                                                 \     {                                                                        \         /* Dynamic array of nodes */                                         \         struct SNAME##_node_s *buffer;                                       \         /* Current array capacity (how many nodes can be stored) */          \         size_t capacity;                                                     \         /* Current amount of nodes in the dynamic array */                   \         size_t size;                                                         \         /* Current amount of elements in the heap */                         \         size_t count;                                                        \         /* Element comparison function */                                    \         int (*cmp)(V, V);                                                    \         /* Function that returns an iterator to the start of the heap */     \         struct SNAME##_iter_s (*it_start)(struct SNAME##_s *);               \         /* Function that returns an iterator to the end of the heap */       \         struct SNAME##_iter_s (*it_end)(struct SNAME##_s *);                 \     } SNAME, *SNAME##_ptr;                                                   \                                                                              \     /* Heap Node */                                                          \     typedef struct SNAME##_node_s                                            \     {                                                                        \         /* 0 - Value belonging to the MinHeap */                             \         /* 1 - Value belonging to the MaxHeap */                             \         V data[2];                                                           \     } SNAME##_node, *SNAME##_node_ptr;                                       \                                                                              \     /* Heap Iterator */                                                      \     typedef struct SNAME##_iter_s                                            \     {                                                                        \         /* Target heap */                                                    \         struct SNAME##_s *target;                                            \         /* Cursor's position (index) */                                      \         size_t cursor;                                                       \         /* If the iterator has reached the start of the iteration */         \         bool start;                                                          \         /* If the iterator has reached the end of the iteration */           \         bool end;                                                            \     } SNAME##_iter, *SNAME##_iter_ptr;                                       \                                                                              \     FMOD SNAME *PFX##_new(size_t capacity, int (*compare)(V, V));            \     FMOD void PFX##_clear(SNAME *_heap_);                                    \     FMOD void PFX##_free(SNAME *_heap_);                                     \     FMOD bool PFX##_insert(SNAME *_heap_, V element);                        \     FMOD bool PFX##_remove_max(SNAME *_heap_, V *result);                    \     FMOD bool PFX##_remove_min(SNAME *_heap_, V *result);                    \     FMOD bool PFX##_insert_if(SNAME *_heap_, V element, bool condition);     \     FMOD bool PFX##_remove_max_if(SNAME *_heap_, V *result, bool condition); \     FMOD bool PFX##_remove_min_if(SNAME *_heap_, V *result, bool condition); \     FMOD bool PFX##_update_max(SNAME *_heap_, V element);                    \     FMOD bool PFX##_update_min(SNAME *_heap_, V element);                    \     FMOD bool PFX##_max(SNAME *_heap_, V *value);                            \     FMOD bool PFX##_min(SNAME *_heap_, V *value);                            \     FMOD bool PFX##_contains(SNAME *_heap_, V element);                      \     FMOD bool PFX##_empty(SNAME *_heap_);                                    \     FMOD bool PFX##_full(SNAME *_heap_);                                     \     FMOD size_t PFX##_count(SNAME *_heap_);                                  \     FMOD size_t PFX##_capacity(SNAME *_heap_);                               \                                                                              \     FMOD SNAME##_iter *PFX##_iter_new(SNAME *target);                        \     FMOD void PFX##_iter_free(SNAME##_iter *iter);                           \     FMOD void PFX##_iter_init(SNAME##_iter *iter, SNAME *target);            \     FMOD bool PFX##_iter_start(SNAME##_iter *iter);                          \     FMOD bool PFX##_iter_end(SNAME##_iter *iter);                            \     FMOD void PFX##_iter_to_start(SNAME##_iter *iter);                       \     FMOD void PFX##_iter_to_end(SNAME##_iter *iter);                         \     FMOD bool PFX##_iter_next(SNAME##_iter *iter);                           \     FMOD bool PFX##_iter_prev(SNAME##_iter *iter);                           \     FMOD V PFX##_iter_value(SNAME##_iter *iter);                             \     FMOD size_t PFX##_iter_index(SNAME##_iter *iter);                        \                                                                              \     /* Default Value */                                                      \     static inline V PFX##_impl_default_value(void)                           \     {                                                                        \         V _empty_value_;                                                     \                                                                              \         memset(&_empty_value_, 0, sizeof(V));                                \                                                                              \         return _empty_value_;                                                \     }  #define INTERVALHEAP_GENERATE_SOURCE(PFX, SNAME, FMOD, V)                                   \                                                                                             \     /* Implementation Detail Functions */                                                   \     static bool PFX##_impl_grow(SNAME *_heap_);                                             \     static void PFX##_impl_float_up_max(SNAME *_heap_);                                     \     static void PFX##_impl_float_up_min(SNAME *_heap_);                                     \     static void PFX##_impl_float_down_max(SNAME *_heap_);                                   \     static void PFX##_impl_float_down_min(SNAME *_heap_);                                   \     static SNAME##_iter PFX##_impl_it_start(SNAME *_heap_);                                 \     static SNAME##_iter PFX##_impl_it_end(SNAME *_heap_);                                   \                                                                                             \     FMOD SNAME *PFX##_new(size_t capacity, int (*compare)(V, V))                            \     {                                                                                       \         SNAME *_heap_ = malloc(sizeof(SNAME));                                              \         if (!_heap_)                                                                        \             return NULL;                                                                    \                                                                                             \         /* Since each node can store two elements, divide the actual capacity by 2 */       \         /* Round the capacity of nodes up */                                                \         capacity = capacity % 2 == 0 ? capacity / 2 : (capacity + 1) / 2;                   \         _heap_->buffer = malloc(sizeof(SNAME##_node) * capacity);                           \                                                                                             \         if (!_heap_->buffer)                                                                \         {                                                                                   \             free(_heap_);                                                                   \             return NULL;                                                                    \         }                                                                                   \         memset(_heap_->buffer, 0, sizeof(SNAME##_node) * capacity);                         \         _heap_->capacity = capacity;                                                        \         _heap_->size = 0;                                                                   \         _heap_->count = 0;                                                                  \         _heap_->cmp = compare;                                                              \         _heap_->it_start = PFX##_impl_it_start;                                             \         _heap_->it_end = PFX##_impl_it_end;                                                 \         return _heap_;                                                                      \     }                                                                                       \                                                                                             \     FMOD void PFX##_clear(SNAME *_heap_)                                                    \     {                                                                                       \         memset(_heap_->buffer, 0, sizeof(V) * _heap_->capacity);                            \         _heap_->size = 0;                                                                   \         _heap_->count = 0;                                                                  \     }                                                                                       \                                                                                             \     FMOD void PFX##_free(SNAME *_heap_)                                                     \     {                                                                                       \         free(_heap_->buffer);                                                               \         free(_heap_);                                                                       \     }                                                                                       \                                                                                             \     FMOD bool PFX##_insert(SNAME *_heap_, V element)                                        \     {                                                                                       \         if (PFX##_full(_heap_))                                                             \         {                                                                                   \             if (!PFX##_impl_grow(_heap_))                                                   \                 return false;                                                               \         }                                                                                   \                                                                                             \         if (PFX##_count(_heap_) % 2 == 0)                                                   \         {                                                                                   \             /* Occupying a new node */                                                      \             _heap_->buffer[_heap_->size].data[0] = element;                                 \             _heap_->buffer[_heap_->size].data[1] = PFX##_impl_default_value();              \                                                                                             \             _heap_->size++;                                                                 \         }                                                                                   \         else                                                                                \         {                                                                                   \             SNAME##_node *curr_node = &(_heap_->buffer[_heap_->size - 1]);                  \                                                                                             \             if (_heap_->cmp(curr_node->data[0], element) > 0)                               \             {                                                                               \                 curr_node->data[1] = curr_node->data[0];                                    \                 curr_node->data[0] = element;                                               \             }                                                                               \             else                                                                            \             {                                                                               \                 curr_node->data[1] = element;                                               \             }                                                                               \         }                                                                                   \                                                                                             \         _heap_->count++;                                                                    \                                                                                             \         if (PFX##_count(_heap_) <= 2)                                                       \             return true;                                                                    \                                                                                             \         SNAME##_node *parent = &(_heap_->buffer[(_heap_->size - 1) / 2]);                   \                                                                                             \         if (_heap_->cmp(parent->data[0], element) > 0)                                      \             PFX##_impl_float_up_min(_heap_);                                                \         else if (_heap_->cmp(parent->data[1], element) < 0)                                 \             PFX##_impl_float_up_max(_heap_);                                                \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_remove_max(SNAME *_heap_, V *result)                                    \     {                                                                                       \         if (PFX##_empty(_heap_))                                                            \             return false;                                                                   \                                                                                             \         if (PFX##_count(_heap_) == 1)                                                       \         {                                                                                   \             *result = _heap_->buffer[0].data[0];                                            \             _heap_->buffer[0].data[0] = PFX##_impl_default_value();                         \             _heap_->count--;                                                                \             return true;                                                                    \         }                                                                                   \         else                                                                                \             *result = _heap_->buffer[0].data[1];                                            \                                                                                             \         SNAME##_node *last_node = &(_heap_->buffer[_heap_->size - 1]);                      \                                                                                             \         if (PFX##_count(_heap_) % 2 == 1)                                                   \         {                                                                                   \             _heap_->buffer[0].data[1] = last_node->data[0];                                 \             last_node->data[0] = PFX##_impl_default_value();                                \             _heap_->size--;                                                                 \         }                                                                                   \         else                                                                                \         {                                                                                   \             _heap_->buffer[0].data[1] = last_node->data[1];                                 \                                                                                             \             last_node->data[1] = PFX##_impl_default_value();                                \         }                                                                                   \                                                                                             \         _heap_->count--;                                                                    \                                                                                             \         PFX##_impl_float_down_max(_heap_);                                                  \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_remove_min(SNAME *_heap_, V *result)                                    \     {                                                                                       \         if (PFX##_empty(_heap_))                                                            \             return false;                                                                   \                                                                                             \         *result = _heap_->buffer[0].data[0];                                                \                                                                                             \         if (PFX##_count(_heap_) == 1)                                                       \         {                                                                                   \             _heap_->buffer[0].data[0] = PFX##_impl_default_value();                         \                                                                                             \             _heap_->count--;                                                                \                                                                                             \             return true;                                                                    \         }                                                                                   \                                                                                             \         SNAME##_node *last_node = &(_heap_->buffer[_heap_->size - 1]);                      \                                                                                             \         _heap_->buffer[0].data[0] = last_node->data[0];                                     \                                                                                             \         if (PFX##_count(_heap_) % 2 == 1)                                                   \         {                                                                                   \             last_node->data[0] = PFX##_impl_default_value();                                \                                                                                             \             _heap_->size--;                                                                 \         }                                                                                   \         else                                                                                \         {                                                                                   \             last_node->data[0] = last_node->data[1];                                        \             last_node->data[1] = PFX##_impl_default_value();                                \         }                                                                                   \                                                                                             \         _heap_->count--;                                                                    \                                                                                             \         PFX##_impl_float_down_min(_heap_);                                                  \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_insert_if(SNAME *_heap_, V element, bool condition)                     \     {                                                                                       \         if (condition)                                                                      \             return PFX##_insert(_heap_, element);                                           \                                                                                             \         return false;                                                                       \     }                                                                                       \                                                                                             \     FMOD bool PFX##_remove_max_if(SNAME *_heap_, V *result, bool condition)                 \     {                                                                                       \         if (condition)                                                                      \             return PFX##_remove_max(_heap_, result);                                        \                                                                                             \         return false;                                                                       \     }                                                                                       \                                                                                             \     FMOD bool PFX##_remove_min_if(SNAME *_heap_, V *result, bool condition)                 \     {                                                                                       \         if (condition)                                                                      \             return PFX##_remove_min(_heap_, result);                                        \                                                                                             \         return false;                                                                       \     }                                                                                       \                                                                                             \     FMOD bool PFX##_update_max(SNAME *_heap_, V element)                                    \     {                                                                                       \         if (PFX##_empty(_heap_))                                                            \             return false;                                                                   \                                                                                             \         if (PFX##_count(_heap_) == 1)                                                       \         {                                                                                   \             _heap_->buffer[0].data[0] = element;                                            \         }                                                                                   \         else if (_heap_->cmp(element, _heap_->buffer[0].data[0]) < 0)                       \         {                                                                                   \             _heap_->buffer[0].data[1] = _heap_->buffer[0].data[0];                          \             _heap_->buffer[0].data[0] = element;                                            \                                                                                             \             PFX##_impl_float_down_max(_heap_);                                              \         }                                                                                   \         else                                                                                \         {                                                                                   \             _heap_->buffer[0].data[1] = element;                                            \                                                                                             \             PFX##_impl_float_down_max(_heap_);                                              \         }                                                                                   \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_update_min(SNAME *_heap_, V element)                                    \     {                                                                                       \         if (PFX##_empty(_heap_))                                                            \             return false;                                                                   \                                                                                             \         if (PFX##_count(_heap_) == 1)                                                       \         {                                                                                   \             _heap_->buffer[0].data[0] = element;                                            \         }                                                                                   \         else if (_heap_->cmp(element, _heap_->buffer[0].data[1]) > 0)                       \         {                                                                                   \             _heap_->buffer[0].data[0] = _heap_->buffer[0].data[1];                          \             _heap_->buffer[0].data[1] = element;                                            \                                                                                             \             PFX##_impl_float_down_min(_heap_);                                              \         }                                                                                   \         else                                                                                \         {                                                                                   \             _heap_->buffer[0].data[0] = element;                                            \                                                                                             \             PFX##_impl_float_down_min(_heap_);                                              \         }                                                                                   \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_max(SNAME *_heap_, V *value)                                            \     {                                                                                       \         if (PFX##_empty(_heap_))                                                            \             return false;                                                                   \                                                                                             \         if (PFX##_count(_heap_) == 1)                                                       \             *value = _heap_->buffer[0].data[0];                                             \         else                                                                                \             *value = _heap_->buffer[0].data[1];                                             \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_min(SNAME *_heap_, V *value)                                            \     {                                                                                       \         if (PFX##_empty(_heap_))                                                            \             return false;                                                                   \                                                                                             \         *value = _heap_->buffer[0].data[0];                                                 \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_contains(SNAME *_heap_, V element)                                      \     {                                                                                       \         for (size_t i = 0; i < _heap_->count; i++)                                          \         {                                                                                   \             if (_heap_->cmp(_heap_->buffer[i / 2].data[i % 2], element) == 0)               \                 return true;                                                                \         }                                                                                   \                                                                                             \         return false;                                                                       \     }                                                                                       \                                                                                             \     FMOD bool PFX##_empty(SNAME *_heap_)                                                    \     {                                                                                       \         return _heap_->count == 0;                                                          \     }                                                                                       \                                                                                             \     FMOD bool PFX##_full(SNAME *_heap_)                                                     \     {                                                                                       \         /* The heap is full if all nodes are completely filled */                           \         return _heap_->size >= _heap_->capacity && _heap_->count % 2 == 0;                  \     }                                                                                       \                                                                                             \     FMOD size_t PFX##_count(SNAME *_heap_)                                                  \     {                                                                                       \         return _heap_->count;                                                               \     }                                                                                       \                                                                                             \     FMOD size_t PFX##_capacity(SNAME *_heap_)                                               \     {                                                                                       \         /* Multiply by 2 since each node can store two elements */                          \         return _heap_->capacity * 2;                                                        \     }                                                                                       \                                                                                             \     FMOD SNAME##_iter *PFX##_iter_new(SNAME *target)                                        \     {                                                                                       \         SNAME##_iter *iter = malloc(sizeof(SNAME##_iter));                                  \                                                                                             \         if (!iter)                                                                          \             return NULL;                                                                    \                                                                                             \         PFX##_iter_init(iter, target);                                                      \                                                                                             \         return iter;                                                                        \     }                                                                                       \                                                                                             \     FMOD void PFX##_iter_free(SNAME##_iter *iter)                                           \     {                                                                                       \         free(iter);                                                                         \     }                                                                                       \                                                                                             \     FMOD void PFX##_iter_init(SNAME##_iter *iter, SNAME *target)                            \     {                                                                                       \         iter->target = target;                                                              \         iter->cursor = 0;                                                                   \         iter->start = true;                                                                 \         iter->end = PFX##_empty(target);                                                    \     }                                                                                       \                                                                                             \     FMOD bool PFX##_iter_start(SNAME##_iter *iter)                                          \     {                                                                                       \         return PFX##_empty(iter->target) || iter->start;                                    \     }                                                                                       \                                                                                             \     FMOD bool PFX##_iter_end(SNAME##_iter *iter)                                            \     {                                                                                       \         return PFX##_empty(iter->target) || iter->end;                                      \     }                                                                                       \                                                                                             \     FMOD void PFX##_iter_to_start(SNAME##_iter *iter)                                       \     {                                                                                       \         iter->cursor = 0;                                                                   \         iter->start = true;                                                                 \         iter->end = PFX##_empty(iter->target);                                              \     }                                                                                       \                                                                                             \     FMOD void PFX##_iter_to_end(SNAME##_iter *iter)                                         \     {                                                                                       \         iter->cursor = iter->target->count - 1;                                             \         iter->start = PFX##_empty(iter->target);                                            \         iter->end = true;                                                                   \     }                                                                                       \                                                                                             \     FMOD bool PFX##_iter_next(SNAME##_iter *iter)                                           \     {                                                                                       \         if (iter->end)                                                                      \             return false;                                                                   \                                                                                             \         iter->start = false;                                                                \                                                                                             \         if (iter->cursor == iter->target->count - 1)                                        \             iter->end = true;                                                               \         else                                                                                \             iter->cursor++;                                                                 \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD bool PFX##_iter_prev(SNAME##_iter *iter)                                           \     {                                                                                       \         if (iter->start)                                                                    \             return false;                                                                   \                                                                                             \         iter->end = false;                                                                  \                                                                                             \         if (iter->cursor == 0)                                                              \             iter->start = true;                                                             \         else                                                                                \             iter->cursor--;                                                                 \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     FMOD V PFX##_iter_value(SNAME##_iter *iter)                                             \     {                                                                                       \         if (PFX##_empty(iter->target))                                                      \             return PFX##_impl_default_value();                                              \                                                                                             \         return iter->target->buffer[iter->cursor / 2].data[iter->cursor % 2];               \     }                                                                                       \                                                                                             \     FMOD size_t PFX##_iter_index(SNAME##_iter *iter)                                        \     {                                                                                       \         return iter->cursor;                                                                \     }                                                                                       \                                                                                             \     static bool PFX##_impl_grow(SNAME *_heap_)                                              \     {                                                                                       \         size_t new_cap = _heap_->capacity * 2;                                              \                                                                                             \         SNAME##_node *new_buffer = realloc(_heap_->buffer, sizeof(SNAME##_node) * new_cap); \                                                                                             \         if (!new_buffer)                                                                    \             return false;                                                                   \                                                                                             \         memset(new_buffer + _heap_->capacity, 0, sizeof(SNAME##_node) * _heap_->capacity);  \                                                                                             \         _heap_->buffer = new_buffer;                                                        \         _heap_->capacity = new_cap;                                                         \                                                                                             \         return true;                                                                        \     }                                                                                       \                                                                                             \     static void PFX##_impl_float_up_max(SNAME *_heap_)                                      \     {                                                                                       \         size_t index = _heap_->size - 1;                                                    \                                                                                             \         SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \                                                                                             \         while (index > 0)                                                                   \         {                                                                                   \             /* Parent index */                                                              \             size_t P_index = (index - 1) / 2;                                               \                                                                                             \             SNAME##_node *parent = &(_heap_->buffer[P_index]);                              \                                                                                             \             if (index == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0)                  \             {                                                                               \                 if (_heap_->cmp(curr_node->data[0], parent->data[1]) < 0)                   \                     break;                                                                  \                                                                                             \                 V tmp = curr_node->data[0];                                                 \                 curr_node->data[0] = parent->data[1];                                       \                 parent->data[1] = tmp;                                                      \             }                                                                               \             else                                                                            \             {                                                                               \                 if (_heap_->cmp(curr_node->data[1], parent->data[1]) < 0)                   \                     break;                                                                  \                                                                                             \                 V tmp = curr_node->data[1];                                                 \                 curr_node->data[1] = parent->data[1];                                       \                 parent->data[1] = tmp;                                                      \             }                                                                               \                                                                                             \             index = P_index;                                                                \             curr_node = parent;                                                             \         }                                                                                   \     }                                                                                       \                                                                                             \     static void PFX##_impl_float_up_min(SNAME *_heap_)                                      \     {                                                                                       \         size_t index = _heap_->size - 1;                                                    \         SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \                                                                                             \         while (index > 0)                                                                   \         {                                                                                   \             size_t P_index = (index - 1) / 2;                                               \             SNAME##_node *parent = &(_heap_->buffer[P_index]);                              \                                                                                             \             if (_heap_->cmp(curr_node->data[0], parent->data[0]) >= 0)                      \                 break;                                                                      \                                                                                             \             V tmp = curr_node->data[0];                                                     \             curr_node->data[0] = parent->data[0];                                           \             parent->data[0] = tmp;                                                          \             index = P_index;                                                                \             curr_node = parent;                                                             \         }                                                                                   \     }                                                                                       \                                                                                             \     static void PFX##_impl_float_down_max(SNAME *_heap_)                                    \     {                                                                                       \         size_t index = 0;                                                                   \         SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \                                                                                             \         while (true)                                                                        \         {                                                                                   \             if (2 * index + 1 >= _heap_->size)                                              \                 break;                                                                      \                                                                                             \             size_t child;                                                                   \             size_t L_index = index * 2 + 1;                                                 \             size_t R_index = index * 2 + 2;                                                 \                                                                                             \             if (R_index < _heap_->size)                                                     \             {                                                                               \                 SNAME##_node *L = &(_heap_->buffer[L_index]);                               \                 SNAME##_node *R = &(_heap_->buffer[R_index]);                               \                                                                                             \                 if (R_index == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0)            \                     child = _heap_->cmp(L->data[1], R->data[0]) > 0 ? L_index : R_index;    \                 else                                                                        \                     child = _heap_->cmp(L->data[1], R->data[1]) > 0 ? L_index : R_index;    \             }                                                                               \             else                                                                            \                 child = L_index;                                                            \                                                                                             \             SNAME##_node *child_node = &(_heap_->buffer[child]);                            \                                                                                             \             if (child == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0)                  \             {                                                                               \                 if (_heap_->cmp(curr_node->data[1], child_node->data[0]) >= 0)              \                     break;                                                                  \                                                                                             \                 V tmp = child_node->data[0];                                                \                 child_node->data[0] = curr_node->data[1];                                   \                 curr_node->data[1] = tmp;                                                   \             }                                                                               \             else                                                                            \             {                                                                               \                 if (_heap_->cmp(curr_node->data[1], child_node->data[1]) >= 0)              \                     break;                                                                  \                                                                                             \                 V tmp = child_node->data[1];                                                \                 child_node->data[1] = curr_node->data[1];                                   \                 curr_node->data[1] = tmp;                                                   \                                                                                             \                 if (_heap_->cmp(child_node->data[0], child_node->data[1]) > 0)              \                 {                                                                           \                     tmp = child_node->data[0];                                              \                     child_node->data[0] = child_node->data[1];                              \                     child_node->data[1] = tmp;                                              \                 }                                                                           \             }                                                                               \             index = child;                                                                  \             curr_node = child_node;                                                         \         }                                                                                   \     }                                                                                       \                                                                                             \     static void PFX##_impl_float_down_min(SNAME *_heap_)                                    \     {                                                                                       \         size_t index = 0;                                                                   \                                                                                             \         SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \                                                                                             \         while (true)                                                                        \         {                                                                                   \             if (2 * index + 1 >= _heap_->size)                                              \                 break;                                                                      \                                                                                             \             size_t child;                                                                   \             size_t L_index = index * 2 + 1;                                                 \             size_t R_index = index * 2 + 2;                                                 \                                                                                             \             if (R_index < _heap_->size)                                                     \             {                                                                               \                 SNAME##_node *L = &(_heap_->buffer[L_index]);                               \                 SNAME##_node *R = &(_heap_->buffer[R_index]);                               \                 child = _heap_->cmp(L->data[0], R->data[0]) < 0 ? L_index : R_index;        \             }                                                                               \             else                                                                            \                 child = L_index;                                                            \                                                                                             \             SNAME##_node *child_node = &(_heap_->buffer[child]);                            \                                                                                             \             if (_heap_->cmp(curr_node->data[0], child_node->data[0]) < 0)                   \                 break;                                                                      \                                                                                             \             V tmp = child_node->data[0];                                                    \             child_node->data[0] = curr_node->data[0];                                       \             curr_node->data[0] = tmp;                                                       \                                                                                             \             if (child != _heap_->size - 1 || PFX##_count(_heap_) % 2 == 0)                  \             {                                                                               \                 if (_heap_->cmp(child_node->data[0], child_node->data[1]) > 0)              \                 {                                                                           \                     tmp = child_node->data[0];                                              \                     child_node->data[0] = child_node->data[1];                              \                     child_node->data[1] = tmp;                                              \                 }                                                                           \             }                                                                               \             index = child;                                                                  \             curr_node = child_node;                                                         \         }                                                                                   \     }                                                                                       \                                                                                             \     static SNAME##_iter PFX##_impl_it_start(SNAME *_heap_)                                  \     {                                                                                       \         SNAME##_iter iter;                                                                  \         PFX##_iter_init(&iter, _heap_);                                                     \         PFX##_iter_to_start(&iter);                                                         \         return iter;                                                                        \     }                                                                                       \                                                                                             \     static SNAME##_iter PFX##_impl_it_end(SNAME *_heap_)                                    \     {                                                                                       \         SNAME##_iter iter;                                                                  \         PFX##_iter_init(&iter, _heap_);                                                     \         PFX##_iter_to_end(&iter);                                                           \         return iter;                                                                        \     }  #endif /* CMC_INTERVALHEAP_H */ 

test.c

#include "intervalheap.h" #include <stdio.h>  /* Generate the Interval Heap */ INTERVALHEAP_GENERATE(h, heap, , int)  /* Comparison function */ int intcmp(int a, int b) {     return (a > b) - (a < b); }  #define TOTAL 100  int main(void) {     heap *my_heap = h_new(50, intcmp);      for (size_t i = 1; i <= TOTAL; i++)     {         h_insert(my_heap, i);     }      size_t half = h_count(my_heap) / 2;      for (size_t i = 0; !h_empty(my_heap); i++)     {         int r;          i < half ? h_remove_max(my_heap, &r) : h_remove_min(my_heap, &r);          printf("%d ", r);     }      h_free(my_heap);      return 0; }