heap.h

00001 /*********************************************************************
00002 PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
00003 See LICENSE and COPYING for usage.
00004 
00005 *********************************************************************/
00006 
00007 #define DECLARE_HEAP(type, orderby) \
00008 struct heap_##type {   \
00009   uint32_t size;       \
00010   uint32_t n;       \
00011   type *top;        \
00012 }; \
00013 typedef struct heap_##type heap_##type; \
00014 static inline int heap_insert(struct heap_##type *heap, type *el) \
00015 { \
00016   int i; \
00017   type * newTop; \
00018   if (++heap->n >= heap->size) {                                                \
00019     newTop = pico_zalloc((heap->n + 1) * sizeof(type)); \
00020     if(!newTop) \
00021       return -1; \
00022     if (heap->top)  {\
00023       memcpy(newTop,heap->top,heap->n*sizeof(type)); \
00024       pico_free(heap->top); \
00025     } \
00026     heap->top = newTop;                \
00027     heap->size++;                                                                \
00028   }                                                                              \
00029   if (heap->n == 1) {                                                          \
00030     memcpy(&heap->top[1], el, sizeof(type));                                    \
00031     return 0;                                                                    \
00032   }                                                                              \
00033   for (i = heap->n; ((i > 1) && (heap->top[i / 2].orderby > el->orderby)); i /= 2) {          \
00034     memcpy(&heap->top[i], &heap->top[i / 2], sizeof(type));                        \
00035   }              \
00036   memcpy(&heap->top[i], el, sizeof(type));                                      \
00037   return 0;                                                                       \
00038 } \
00039 static inline int heap_peek(struct heap_##type *heap, type *first) \
00040 { \
00041   type *last;              \
00042   int i, child;          \
00043   if(heap->n == 0) {      \
00044     return -1;             \
00045   }                      \
00046   memcpy(first, &heap->top[1], sizeof(type));      \
00047   last = &heap->top[heap->n--];                  \
00048   for(i = 1; (i * 2) <= heap->n; i = child) {      \
00049     child = 2 * i;                                \
00050     if ((child != heap->n) &&                     \
00051         (heap->top[child + 1]).orderby             \
00052         < (heap->top[child]).orderby)            \
00053         child++;                                \
00054     if (last->orderby >                         \
00055         heap->top[child].orderby)                \
00056         memcpy(&heap->top[i], &heap->top[child],\
00057                 sizeof(type));                    \
00058     else                                        \
00059         break;                                    \
00060   }                                              \
00061   memcpy(&heap->top[i], last, sizeof(type));      \
00062   return 0;                                      \
00063 } \
00064 static inline type *heap_first(heap_##type *heap)  \
00065 { \
00066   if (heap->n == 0)      \
00067     return NULL;        \
00068   return &heap->top[1];  \
00069 } \
00070 static inline heap_##type *heap_init(void) \
00071 { \
00072   heap_##type *p = (heap_##type *)pico_zalloc(sizeof(heap_##type));  \
00073   return p;      \
00074 } \
00075 static inline void heap_destroy(heap_##type *h) \
00076 { \
00077   pico_free(h->top);   \
00078   pico_free(h);       \
00079 } \
00080 
00081