heap.h

Go to the documentation of this file.

#ifndef CSNIP_HEAP_H
#define CSNIP_HEAP_H
 
#include <assert.h>
#include <stddef.h>
 
#include <csnip/util.h>
#include <csnip/preproc.h>
 
#define csnip_heap_SiftUp(u, v, au_lessthan_av, swap_au_av, K, N, i) \
        do { \
            size_t u = (size_t)(i); \
            assert(u < (N)); \
            while (u > 0) { \
                size_t v = (u - 1) / (K); \
                if (au_lessthan_av) { \
                    swap_au_av; \
                } \
                u = v; \
            } \
        } while(0)
 
#define csnip_heap_SiftDown(u, v, au_lessthan_av, swap_au_av, K, N, i) \
        do { \
            size_t u, v; \
            size_t csnip_heap_i = (size_t)(i); \
            v = csnip_heap_i * (K) + 1; \
            while (v < (size_t)(N)) { \
                size_t csnip_heap_nu = \
                    csnip_Min(v + (K), (size_t)(N)); \
                u = v + 1; \
                while (u < csnip_heap_nu) { \
                    if (au_lessthan_av) \
                        v = u; \
                    ++u; \
                } \
                u = csnip_heap_i; \
                if (au_lessthan_av) \
                    break; \
                swap_au_av; \
                csnip_heap_i = v; \
                v = v * (K) + 1; \
            } \
        } while(0)
 
#define csnip_heap_Heapify(u, v, au_lessthan_av, swap_au_av, K, N) \
        do { \
            if((N) <= 1) \
                break; \
            size_t csnip_h_make_i = ((N) - 1) / (K); \
            while(1) { \
                csnip_heap_SiftDown(u, v, \
                    au_lessthan_av, swap_au_av, \
                    K, N, csnip_h_make_i); \
                if (csnip_h_make_i == 0) \
                    break; \
                --csnip_h_make_i; \
            } \
        } while(0)
 
#define CSNIP_HEAP_DECL_FUNCS(scope, prefix, gen_args) \
        scope void prefix ## sift_up(csnip_pp_prepend_##gen_args \
                    size_t i); \
        scope void prefix ## sift_down(csnip_pp_prepend_##gen_args \
                    size_t i); \
        scope void prefix ## heapify(csnip_pp_list_##gen_args);
 
#define CSNIP_HEAP_DEF_FUNCS(scope, prefix, gen_args, \
        u, v, au_lessthan_av, swap_au_av, K, N) \
        scope void prefix ## sift_up(csnip_pp_prepend_##gen_args \
                    size_t i) \
        { \
            csnip_heap_SiftUp(u, v, \
                au_lessthan_av, swap_au_av, \
                K, N, i); \
        } \
        \
        scope void prefix ## sift_down(csnip_pp_prepend_##gen_args \
                    size_t i) \
        { \
            csnip_heap_SiftDown(u, v, \
                au_lessthan_av, swap_au_av, \
                K, N, i); \
        } \
        \
        scope void prefix ## heapify(csnip_pp_list_##gen_args) \
        { \
            csnip_heap_Heapify(u, v, \
                au_lessthan_av, swap_au_av, \
                K, N); \
        }
 
#endif /* CSNIP_HEAP_H */
 
#if defined(CSNIP_SHORT_NAMES) && !defined(CSNIP_HEAP_HAVE_SHORT_NAMES)
#define heap_SiftUp     csnip_heap_SiftUp
#define heap_SiftDown       csnip_heap_SiftDown
#define heap_Heapify        csnip_heap_Heapify
#define CSNIP_HEAP_HAVE_SHORT_NAMES
#endif /* CSNIP_SHORT_NAMES && !CSNIP_HEAP_HAVE_SHORT_NAMES */