3 An inline heap implementation
5 Copyright (c) 2009 Matthias Kramm <kramm@quiss.org>
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.
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.
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 */
21 #define HEAP_DEFINE(name,t,lt) \
27 static void name##_put(name##_t*h, t*e) \
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*)); \
39 parent = (node-1)/2; \
40 h->elements[node] = h->elements[parent]; \
41 } while(lt(e, h->elements[parent])); \
42 h->elements[node] = e; \
44 static t* name##_get(name##_t*h) \
46 if(!h->size) return 0; \
47 t*r = h->elements[0]; \
49 t*node_p = h->elements[--h->size]; \
50 h->elements[0] = node_p; /* for the size==1 case */ \
54 if(child >= h->size) { \
57 if(child+1 < h->size && lt(h->elements[child+1], \
58 h->elements[child])) \
60 h->elements[node] = h->elements[child]; \
61 } while(lt(h->elements[child],node_p)); \
62 h->elements[node] = node_p; \
65 static name##_init(name##_t*h) \
67 memset(h, 0, sizeof(*h)); \
69 h->elements = malloc(h->max_size*sizeof(t*)); \
71 static name##_destroy(name##_t*h) \
73 free((h)->elements); \