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