cd5114dd747dfba4c3399a677f9d1f8a49132ab9
[swftools.git] / 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 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 name##_destroy(name##_t*h)                                      \
72 {                                                                      \
73     free((h)->elements);                                               \
74 }