Daniele Lacamera / PicoTCP-Experimental_CDC_ECM_Branch

Free (GPLv2) TCP/IP stack developed by TASS Belgium

Fork of PicoTCP by Daniele Lacamera

include/heap.h@51:18637a3d071f, 2013-08-03 (annotated)

Committer:
daniele
Date:
Sat Aug 03 08:50:27 2013 +0000
Revision:
51:18637a3d071f
Parent:
3:b4047e8a0123 
Branch for CDC-ECM: Work in progress

Who changed what in which revision?

UserRevisionLine numberNew contents of line
daniele 3:b4047e8a0123 1 /*********************************************************************
daniele 3:b4047e8a0123 2 PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
daniele 3:b4047e8a0123 3 See LICENSE and COPYING for usage.
daniele 3:b4047e8a0123 4
daniele 3:b4047e8a0123 5 *********************************************************************/
daniele 3:b4047e8a0123 6
daniele 3:b4047e8a0123 7 #define DECLARE_HEAP(type, orderby) \
daniele 3:b4047e8a0123 8 struct heap_##type { \
daniele 3:b4047e8a0123 9 uint32_t size; \
daniele 3:b4047e8a0123 10 uint32_t n; \
daniele 3:b4047e8a0123 11 type *top; \
daniele 3:b4047e8a0123 12 }; \
daniele 3:b4047e8a0123 13 typedef struct heap_##type heap_##type; \
daniele 3:b4047e8a0123 14 static inline int heap_insert(struct heap_##type *heap, type *el) \
daniele 3:b4047e8a0123 15 { \
daniele 3:b4047e8a0123 16 int i; \
daniele 3:b4047e8a0123 17 type * newTop; \
daniele 3:b4047e8a0123 18 if (++heap->n >= heap->size) { \
daniele 3:b4047e8a0123 19 newTop = pico_zalloc((heap->n + 1) * sizeof(type)); \
daniele 3:b4047e8a0123 20 if(!newTop) \
daniele 3:b4047e8a0123 21 return -1; \
daniele 3:b4047e8a0123 22 if (heap->top) {\
daniele 3:b4047e8a0123 23 memcpy(newTop,heap->top,heap->n*sizeof(type)); \
daniele 3:b4047e8a0123 24 pico_free(heap->top); \
daniele 3:b4047e8a0123 25 } \
daniele 3:b4047e8a0123 26 heap->top = newTop; \
daniele 3:b4047e8a0123 27 heap->size++; \
daniele 3:b4047e8a0123 28 } \
daniele 3:b4047e8a0123 29 if (heap->n == 1) { \
daniele 3:b4047e8a0123 30 memcpy(&heap->top[1], el, sizeof(type)); \
daniele 3:b4047e8a0123 31 return 0; \
daniele 3:b4047e8a0123 32 } \
daniele 3:b4047e8a0123 33 for (i = heap->n; ((i > 1) && (heap->top[i / 2].orderby > el->orderby)); i /= 2) { \
daniele 3:b4047e8a0123 34 memcpy(&heap->top[i], &heap->top[i / 2], sizeof(type)); \
daniele 3:b4047e8a0123 35 } \
daniele 3:b4047e8a0123 36 memcpy(&heap->top[i], el, sizeof(type)); \
daniele 3:b4047e8a0123 37 return 0; \
daniele 3:b4047e8a0123 38 } \
daniele 3:b4047e8a0123 39 static inline int heap_peek(struct heap_##type *heap, type *first) \
daniele 3:b4047e8a0123 40 { \
daniele 3:b4047e8a0123 41 type *last; \
daniele 3:b4047e8a0123 42 int i, child; \
daniele 3:b4047e8a0123 43 if(heap->n == 0) { \
daniele 3:b4047e8a0123 44 return -1; \
daniele 3:b4047e8a0123 45 } \
daniele 3:b4047e8a0123 46 memcpy(first, &heap->top[1], sizeof(type)); \
daniele 3:b4047e8a0123 47 last = &heap->top[heap->n--]; \
daniele 3:b4047e8a0123 48 for(i = 1; (i * 2) <= heap->n; i = child) { \
daniele 3:b4047e8a0123 49 child = 2 * i; \
daniele 3:b4047e8a0123 50 if ((child != heap->n) && \
daniele 3:b4047e8a0123 51 (heap->top[child + 1]).orderby \
daniele 3:b4047e8a0123 52 < (heap->top[child]).orderby) \
daniele 3:b4047e8a0123 53 child++; \
daniele 3:b4047e8a0123 54 if (last->orderby > \
daniele 3:b4047e8a0123 55 heap->top[child].orderby) \
daniele 3:b4047e8a0123 56 memcpy(&heap->top[i], &heap->top[child],\
daniele 3:b4047e8a0123 57 sizeof(type)); \
daniele 3:b4047e8a0123 58 else \
daniele 3:b4047e8a0123 59 break; \
daniele 3:b4047e8a0123 60 } \
daniele 3:b4047e8a0123 61 memcpy(&heap->top[i], last, sizeof(type)); \
daniele 3:b4047e8a0123 62 return 0; \
daniele 3:b4047e8a0123 63 } \
daniele 3:b4047e8a0123 64 static inline type *heap_first(heap_##type *heap) \
daniele 3:b4047e8a0123 65 { \
daniele 3:b4047e8a0123 66 if (heap->n == 0) \
daniele 3:b4047e8a0123 67 return NULL; \
daniele 3:b4047e8a0123 68 return &heap->top[1]; \
daniele 3:b4047e8a0123 69 } \
daniele 3:b4047e8a0123 70 static inline heap_##type *heap_init(void) \
daniele 3:b4047e8a0123 71 { \
daniele 3:b4047e8a0123 72 heap_##type *p = (heap_##type *)pico_zalloc(sizeof(heap_##type)); \
daniele 3:b4047e8a0123 73 return p; \
daniele 3:b4047e8a0123 74 } \
daniele 3:b4047e8a0123 75 static inline void heap_destroy(heap_##type *h) \
daniele 3:b4047e8a0123 76 { \
daniele 3:b4047e8a0123 77 pico_free(h->top); \
daniele 3:b4047e8a0123 78 pico_free(h); \
daniele 3:b4047e8a0123 79 } \
daniele 3:b4047e8a0123 80
daniele 3:b4047e8a0123 81