lib/gfxpoly/heap.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/* 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 void name##_init(name##_t*h)                                    \
{                                                                      \
    memset(h, 0, sizeof(*h));                                          \
    h->max_size = 15;                                                  \
    h->elements = malloc(h->max_size*sizeof(t*));                      \
}                                                                      \
static void name##_destroy(name##_t*h)                                 \
{                                                                      \
    free((h)->elements);                                               \
}