--- /dev/null
+/* heap.h
+
+ An inline heap implementation
+
+ Copyright (c) 2009 Matthias Kramm <kramm@quiss.org>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
+
+#define HEAP_DEFINE(name,t,lt) \
+typedef struct { \
+ t**elements; \
+ int size; \
+ int max_size; \
+} name##_t; \
+static void name##_put(name##_t*h, t*e) \
+{ \
+ int parent = h->size++; \
+ if(h->size>=h->max_size) { \
+ h->max_size = h->max_size<15?15:(h->max_size+1)*2-1; \
+ h->elements = (t**)realloc(h->elements, \
+ h->max_size*sizeof(t*)); \
+ } \
+ int node; \
+ do { \
+ node = parent; \
+ if(!node) break; \
+ parent = (node-1)/2; \
+ h->elements[node] = h->elements[parent]; \
+ } while(lt(e, h->elements[parent])); \
+ h->elements[node] = e; \
+} \
+static t* name##_get(name##_t*h) \
+{ \
+ if(!h->size) return 0; \
+ t*r = h->elements[0]; \
+ int node,child = 0; \
+ t*node_p = h->elements[--h->size]; \
+ h->elements[0] = node_p; /* for the size==1 case */ \
+ do { \
+ node = child; \
+ child = node<<1|1; \
+ if(child >= h->size) { \
+ break; \
+ } \
+ if(child+1 < h->size && lt(h->elements[child+1], \
+ h->elements[child])) \
+ child++; \
+ h->elements[node] = h->elements[child]; \
+ } while(lt(h->elements[child],node_p)); \
+ h->elements[node] = node_p; \
+ return r; \
+} \
+static name##_init(name##_t*h) \
+{ \
+ memset(h, 0, sizeof(*h)); \
+ h->max_size = 15; \
+ h->elements = malloc(h->max_size*sizeof(t*)); \
+} \
+static name##_destroy(name##_t*h) \
+{ \
+ free((h)->elements); \
+}