1/*********************************************************************
2   PicoTCP. Copyright (c) 2012-2017 Altran Intelligent Systems. Some rights reserved.
3   See COPYING, LICENSE.GPLv2 and LICENSE.GPLv3 for usage.
4
5 *********************************************************************/
6#define MAX_BLOCK_SIZE 1600
7#define MAX_BLOCK_COUNT 16
8
9#define DECLARE_HEAP(type, orderby) \
10    struct heap_ ## type {   \
11        uint32_t size;    \
12        uint32_t n;       \
13        type *top[MAX_BLOCK_COUNT];        \
14    }; \
15    typedef struct heap_ ## type heap_ ## type; \
16    static inline type* heap_get_element(struct heap_ ## type *heap, uint32_t idx) \
17    { \
18        uint32_t elements_per_block = MAX_BLOCK_SIZE/sizeof(type); \
19        return &heap->top[idx/elements_per_block][idx%elements_per_block];\
20    } \
21    static inline int8_t heap_increase_size(struct heap_ ## type *heap) \
22    {\
23        type *newTop; \
24        uint32_t elements_per_block = MAX_BLOCK_SIZE/sizeof(type); \
25        uint32_t elements = (heap->n + 1)%elements_per_block;\
26        elements = elements?elements:elements_per_block;\
27        if (heap->n+1 > elements_per_block * MAX_BLOCK_COUNT){\
28            return -1;\
29        }\
30        newTop = PICO_ZALLOC(elements*sizeof(type)); \
31        if(!newTop) { \
32            return -1; \
33        } \
34        if (heap->top[heap->n/elements_per_block])  { \
35            memcpy(newTop, heap->top[heap->n/elements_per_block], (elements - 1) * sizeof(type)); \
36            PICO_FREE(heap->top[heap->n/elements_per_block]); \
37        } \
38        heap->top[heap->n/elements_per_block] = newTop;             \
39        heap->size++;                                                               \
40        return 0;                                                               \
41    }\
42    static inline int heap_insert(struct heap_ ## type *heap, type * el) \
43    { \
44        type *half;                                                                 \
45        uint32_t i; \
46        if (++heap->n >= heap->size) {                                                \
47            if (heap_increase_size(heap)){                                                    \
48                heap->n--;                                                           \
49                return -1;                                                           \
50            }                                                                       \
51        }                                                                             \
52        if (heap->n == 1) {                                                       \
53            memcpy(heap_get_element(heap, 1), el, sizeof(type));                                    \
54            return 0;                                                                   \
55        }                                                                             \
56        i = heap->n;                                                                    \
57        half = heap_get_element(heap, i/2);                                                   \
58        while ( (i > 1) && (half->orderby > el->orderby) ) {        \
59            memcpy(heap_get_element(heap, i), heap_get_element(heap, i / 2), sizeof(type));                     \
60            i /= 2;                                                                     \
61            half = heap_get_element(heap, i/2);                                                   \
62        }             \
63        memcpy(heap_get_element(heap, i), el, sizeof(type));                                      \
64        return 0;                                                                     \
65    } \
66    static inline int heap_peek(struct heap_ ## type *heap, type * first) \
67    { \
68        type *last;           \
69        type *left_child;           \
70        type *right_child;           \
71        uint32_t i, child;        \
72        if(heap->n == 0) {    \
73            return -1;          \
74        }                     \
75        memcpy(first, heap_get_element(heap, 1), sizeof(type));   \
76        last = heap_get_element(heap, heap->n--);                 \
77        for(i = 1; (i * 2u) <= heap->n; i = child) {   \
78            child = 2u * i;                              \
79            right_child = heap_get_element(heap, child+1);     \
80            left_child = heap_get_element(heap, child);      \
81            if ((child != heap->n) &&                   \
82                (right_child->orderby          \
83                < left_child->orderby))           \
84                child++;                                \
85            left_child = heap_get_element(heap, child);      \
86            if (last->orderby >                         \
87                left_child->orderby)               \
88                memcpy(heap_get_element(heap,i), heap_get_element(heap,child), \
89                       sizeof(type));                  \
90            else                                        \
91                break;                                  \
92        }                                             \
93        memcpy(heap_get_element(heap, i), last, sizeof(type));    \
94        return 0;                                     \
95    } \
96    static inline type *heap_first(heap_ ## type * heap)  \
97    { \
98        if (heap->n == 0)     \
99            return NULL;        \
100        return heap_get_element(heap, 1);  \
101    } \
102    static inline heap_ ## type *heap_init(void) \
103    { \
104        heap_ ## type * p = (heap_ ## type *)PICO_ZALLOC(sizeof(heap_ ## type));  \
105        return p;     \
106    } \
107
108