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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
#include <sys/time.h>
#include <assert.h>
#include <stdlib.h>
#include "timeheap.h"
struct th_entry {
struct timespec t;
struct th_handle *h;
};
static struct th_entry *heap;
static int heap_cap;
static int heap_use;
static int
cmptime_lt(struct timespec a, struct timespec b)
{
if (a.tv_sec == b.tv_sec)
return a.tv_nsec < b.tv_nsec;
else
return a.tv_sec < b.tv_sec;
}
static int
cmpentry_lt(int a, int b)
{
return cmptime_lt(heap[a].t, heap[b].t);
}
static void
swap(int i, int j)
{
struct th_entry tmp = heap[i];
heap[i] = heap[j];
heap[i].h->i = i;
heap[j] = tmp;
heap[j].h->i = j;
}
static void
bubble_up(int i)
{
while (i != 0) {
int p = (i-1)/2;
if (cmpentry_lt(i, p)) {
swap(i, p);
i = p;
} else
return;
}
}
static void
bubble_down(int i)
{
int li, ri, ci;
loop:
li = 2*i+1;
ri = 2*i+2;
if (ri < heap_use)
ci = cmpentry_lt(li, ri) ? li : ri;
else if (li < heap_use)
ci = li;
else
return;
if (cmpentry_lt(ci, i)) {
swap(i, ci);
i = ci;
goto loop;
}
}
int
timeheap_init(void)
{
heap_cap = 10;
heap_use = 0;
if ((heap = malloc(sizeof(struct th_entry) * heap_cap)) == NULL)
return -1;
else
return 0;
}
int
timeheap_size(void)
{
return heap_use;
}
int
timeheap_insert(struct th_handle *h, struct timespec *t)
{
if (heap_use == heap_cap) {
int ncap = heap_cap * 2;
struct th_entry *nheap = realloc(heap, ncap * sizeof(struct th_entry));
if (nheap == NULL)
return -1;
heap_cap = ncap;
heap = nheap;
}
heap[heap_use].t = *t;
heap[heap_use].h = h;
h->i = heap_use;
heap_use++;
bubble_up(h->i);
return 0;
}
void
timeheap_remove(struct th_handle *h)
{
assert(h->i >= 0 && h->i < heap_use);
heap_use--;
if (heap_use > 0) {
int i = h->i;
int earlier = cmpentry_lt(heap_use, i);
heap[i] = heap[heap_use];
heap[i].h->i = i;
if (earlier)
bubble_up(i);
else
bubble_down(i);
}
}
void
timeheap_change(struct th_handle *h, struct timespec *t)
{
assert(h->i >= 0 && h->i < heap_use);
int earlier = cmptime_lt(*t, heap[h->i].t);
heap[h->i].t = *t;
if (earlier)
bubble_up(h->i);
else
bubble_down(h->i);
}
struct timespec
timeheap_top(void)
{
return heap[0].t;
}
void *
timeheap_remove_top(void)
{
void *ret = heap[0].h->data;
struct th_handle h = { 0, NULL };
timeheap_remove(&h);
return ret;
}
|