lib/gfxpoly/heap.h

   1 /* heap.h
   2
   3    An inline heap implementation
   4
   5    Copyright (c) 2009 Matthias Kramm <kramm@quiss.org>
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  20
  21 #define HEAP_DEFINE(name,t,lt)                                         \
  22 typedef struct {                                                       \
  23     t**elements;                                                       \
  24     int size;                                                          \
  25     int max_size;                                                      \
  26 } name##_t;                                                            \
  27 static void name##_put(name##_t*h, t*e)                                \
  28 {                                                                      \
  29     int parent = h->size++;                                            \
  30     if(h->size>=h->max_size) {                                         \
  31         h->max_size = h->max_size<15?15:(h->max_size+1)*2-1;           \
  32         h->elements = (t**)realloc(h->elements,                        \
  33                                       h->max_size*sizeof(t*));         \
  34     }                                                                  \
  35     int node;                                                          \
  36     do {                                                               \
  37         node = parent;                                                 \
  38         if(!node) break;                                               \
  39         parent = (node-1)/2;                                           \
  40         h->elements[node] = h->elements[parent];                       \
  41     } while(lt(e, h->elements[parent]));                               \
  42     h->elements[node] = e;                                             \
  43 }                                                                      \
  44 static t* name##_get(name##_t*h)                                       \
  45 {                                                                      \
  46     if(!h->size) return 0;                                             \
  47     t*r = h->elements[0];                                              \
  48     int node,child = 0;                                                \
  49     t*node_p = h->elements[--h->size];                                 \
  50     h->elements[0] = node_p; /* for the size==1 case */                \
  51     do {                                                               \
  52         node = child;                                                  \
  53         child = node<<1|1;                                             \
  54         if(child >= h->size) {                                         \
  55             break;                                                     \
  56         }                                                              \
  57         if(child+1 < h->size && lt(h->elements[child+1],               \
  58                                    h->elements[child]))                \
  59             child++;                                                   \
  60         h->elements[node] = h->elements[child];                        \
  61     } while(lt(h->elements[child],node_p));                            \
  62     h->elements[node] = node_p;                                        \
  63     return r;                                                          \
  64 }                                                                      \
  65 static void name##_init(name##_t*h)                                    \
  66 {                                                                      \
  67     memset(h, 0, sizeof(*h));                                          \
  68     h->max_size = 15;                                                  \
  69     h->elements = malloc(h->max_size*sizeof(t*));                      \
  70 }                                                                      \
  71 static void name##_destroy(name##_t*h)                                 \
  72 {                                                                      \
  73     free((h)->elements);                                               \
  74 }