|
1
|
/* |
|
2
|
** Copyright (c) 2007 D. Richard Hipp |
|
3
|
** |
|
4
|
** This program is free software; you can redistribute it and/or |
|
5
|
** modify it under the terms of the Simplified BSD License (also |
|
6
|
** known as the "2-Clause License" or "FreeBSD License".) |
|
7
|
|
|
8
|
** This program is distributed in the hope that it will be useful, |
|
9
|
** but without any warranty; without even the implied warranty of |
|
10
|
** merchantability or fitness for a particular purpose. |
|
11
|
** |
|
12
|
** Author contact information: |
|
13
|
** [email protected] |
|
14
|
** http://www.hwaci.com/drh/ |
|
15
|
** |
|
16
|
******************************************************************************* |
|
17
|
** |
|
18
|
** This file contains code used to implement a priority queue. |
|
19
|
** A priority queue is a list of items order by a floating point |
|
20
|
** value. Each value can be associated with either a pointer or |
|
21
|
** an integer. Items are inserted into the queue in an arbitrary |
|
22
|
** order, but are returned in order of the floating point value. |
|
23
|
** |
|
24
|
** This implementation uses a heap of QueueElement objects. The |
|
25
|
** root of the heap is PQueue.a[0]. Each node a[x] has two daughter |
|
26
|
** nodes a[x*2+1] and a[x*2+2]. The mother node of a[y] is a[(y-1)/2] |
|
27
|
** (assuming integer division rounded down). The following is always true: |
|
28
|
** |
|
29
|
** The value of any node is less than or equal two the values |
|
30
|
** of both daughter nodes. (The Heap Property). |
|
31
|
** |
|
32
|
** A consequence of the heap property is that a[0] always contains |
|
33
|
** the node with the smallest value. |
|
34
|
** |
|
35
|
** Compatibility note: Some versions of OpenSSL export a symbols |
|
36
|
** like "pqueue_insert". This is, technically, a bug in OpenSSL. |
|
37
|
** We work around it here by using "pqueuex_" instead of "pqueue_". |
|
38
|
*/ |
|
39
|
#include "config.h" |
|
40
|
#include "pqueue.h" |
|
41
|
#include <assert.h> |
|
42
|
|
|
43
|
|
|
44
|
#if INTERFACE |
|
45
|
/* |
|
46
|
** An integer can appear in the bag at most once. |
|
47
|
** Integers must be positive. |
|
48
|
*/ |
|
49
|
struct PQueue { |
|
50
|
int cnt; /* Number of entries in the queue */ |
|
51
|
int sz; /* Number of slots in a[] */ |
|
52
|
struct QueueElement { |
|
53
|
union { |
|
54
|
int id; /* ID of the element */ |
|
55
|
void *p; /* Pointer to an object */ |
|
56
|
} u; |
|
57
|
double value; /* Value of element. Kept in ascending order */ |
|
58
|
} *a; |
|
59
|
}; |
|
60
|
#endif |
|
61
|
|
|
62
|
/* |
|
63
|
** Initialize a PQueue structure |
|
64
|
*/ |
|
65
|
void pqueuex_init(PQueue *p){ |
|
66
|
memset(p, 0, sizeof(*p)); |
|
67
|
} |
|
68
|
|
|
69
|
/* |
|
70
|
** Destroy a PQueue. Delete all of its content. |
|
71
|
*/ |
|
72
|
void pqueuex_clear(PQueue *p){ |
|
73
|
free(p->a); |
|
74
|
pqueuex_init(p); |
|
75
|
} |
|
76
|
|
|
77
|
/* |
|
78
|
** Change the size of the queue so that it contains N slots |
|
79
|
*/ |
|
80
|
static void pqueuex_resize(PQueue *p, int N){ |
|
81
|
p->a = fossil_realloc(p->a, sizeof(p->a[0])*N); |
|
82
|
p->sz = N; |
|
83
|
} |
|
84
|
|
|
85
|
/* |
|
86
|
** Allocate a new queue entry and return a pointer to it. |
|
87
|
*/ |
|
88
|
static struct QueueElement *pqueuex_new_entry(PQueue *p){ |
|
89
|
if( p->cnt+1>p->sz ){ |
|
90
|
pqueuex_resize(p, p->cnt+7); |
|
91
|
} |
|
92
|
return &p->a[p->cnt++]; |
|
93
|
} |
|
94
|
|
|
95
|
/* |
|
96
|
** Element p->a[p->cnt-1] has just been inserted. Shift entries |
|
97
|
** around so as to preserve the heap property. |
|
98
|
*/ |
|
99
|
static void pqueuex_rebalance(PQueue *p){ |
|
100
|
int i, j; |
|
101
|
struct QueueElement *a = p->a; |
|
102
|
i = p->cnt-1; |
|
103
|
while( (j = (i-1)/2)>=0 && a[j].value>a[i].value ){ |
|
104
|
struct QueueElement t = a[j]; |
|
105
|
a[j] = a[i]; |
|
106
|
a[i] = t; |
|
107
|
i = j; |
|
108
|
} |
|
109
|
} |
|
110
|
|
|
111
|
/* |
|
112
|
** Insert element e into the queue. |
|
113
|
*/ |
|
114
|
void pqueuex_insert(PQueue *p, int e, double v){ |
|
115
|
struct QueueElement *pE = pqueuex_new_entry(p); |
|
116
|
pE->value = v; |
|
117
|
pE->u.id = e; |
|
118
|
pqueuex_rebalance(p); |
|
119
|
} |
|
120
|
void pqueuex_insert_ptr(PQueue *p, void *pPtr, double v){ |
|
121
|
struct QueueElement *pE = pqueuex_new_entry(p); |
|
122
|
pE->value = v; |
|
123
|
pE->u.p = pPtr; |
|
124
|
pqueuex_rebalance(p); |
|
125
|
} |
|
126
|
|
|
127
|
/* |
|
128
|
** Remove and discard p->a[0] element from the queue. Rearrange |
|
129
|
** nodes to preserve the heap property. |
|
130
|
*/ |
|
131
|
static void pqueuex_pop(PQueue *p){ |
|
132
|
int i, j; |
|
133
|
struct QueueElement *a = p->a; |
|
134
|
struct QueueElement tmp; |
|
135
|
i = 0; |
|
136
|
a[0] = a[p->cnt-1]; |
|
137
|
p->cnt--; |
|
138
|
while( (j = i*2+1)<p->cnt ){ |
|
139
|
if( j+1<p->cnt && a[j].value > a[j+1].value ) j++; |
|
140
|
if( a[i].value < a[j].value ) break; |
|
141
|
tmp = a[i]; |
|
142
|
a[i] = a[j]; |
|
143
|
a[j] = tmp; |
|
144
|
i = j; |
|
145
|
} |
|
146
|
} |
|
147
|
|
|
148
|
/* |
|
149
|
** Extract the first element from the queue (the element with |
|
150
|
** the smallest value) and return its ID. Return 0 if the queue |
|
151
|
** is empty. |
|
152
|
*/ |
|
153
|
int pqueuex_extract(PQueue *p){ |
|
154
|
int e; |
|
155
|
if( p->cnt==0 ){ |
|
156
|
return 0; |
|
157
|
} |
|
158
|
e = p->a[0].u.id; |
|
159
|
pqueuex_pop(p); |
|
160
|
return e; |
|
161
|
} |
|
162
|
void *pqueuex_extract_ptr(PQueue *p){ |
|
163
|
void *pPtr; |
|
164
|
if( p->cnt==0 ){ |
|
165
|
return 0; |
|
166
|
} |
|
167
|
pPtr = p->a[0].u.p; |
|
168
|
pqueuex_pop(p); |
|
169
|
return pPtr; |
|
170
|
} |
|
171
|
|
|
172
|
/* |
|
173
|
** Print the entire heap associated with the test-pqueue command. |
|
174
|
*/ |
|
175
|
static void pqueuex_test_print(PQueue *p){ |
|
176
|
int j; |
|
177
|
for(j=0; j<p->cnt; j++){ |
|
178
|
fossil_print("(%d) %g/%s ",j,p->a[j].value,p->a[j].u.p); |
|
179
|
} |
|
180
|
fossil_print("\n"); |
|
181
|
} |
|
182
|
|
|
183
|
/* |
|
184
|
** COMMAND: test-pqueue |
|
185
|
** |
|
186
|
** This command is used for testing the PQueue object. There are one |
|
187
|
** or more arguments, each of the form: |
|
188
|
** |
|
189
|
** (1) NUMBER/TEXT |
|
190
|
** (2) ^ |
|
191
|
** (3) -v |
|
192
|
** |
|
193
|
** Form (1) arguments add an entry to the queue with value NUMBER and |
|
194
|
** content TEXT. Form (2) pops off the queue entry with the smallest |
|
195
|
** value. Form (3) (the -v option) causes the heap to be displayed after |
|
196
|
** each subsequent operation. |
|
197
|
*/ |
|
198
|
void pqueuex_test_cmd(void){ |
|
199
|
int i; |
|
200
|
PQueue x; |
|
201
|
const char *zId; |
|
202
|
int bDebug = 0; |
|
203
|
|
|
204
|
pqueuex_init(&x); |
|
205
|
for(i=2; i<g.argc; i++){ |
|
206
|
const char *zArg = g.argv[i]; |
|
207
|
if( strcmp(zArg,"-v")==0 ){ |
|
208
|
bDebug = 1; |
|
209
|
}else if( strcmp(zArg, "^")==0 ){ |
|
210
|
zId = pqueuex_extract_ptr(&x); |
|
211
|
if( zId==0 ){ |
|
212
|
fossil_print("%2d: POP NULL\n", i); |
|
213
|
}else{ |
|
214
|
fossil_print("%2d: POP \"%s\"\n", i, zId); |
|
215
|
} |
|
216
|
if( bDebug) pqueuex_test_print(&x); |
|
217
|
e{ |
|
218
|
double r = fossil_atof(zArg); |
|
219
|
zId = strchr(zArg,'/'); |
|
220
|
if( zId==0 ) zId = zArg; |
|
221
|
if( zId[0]=='/' ) zId++; |
|
222
|
pqueuex_insert_ptr(&x, (void*)zId, r); |
|
223
|
fossil_print("%2d: INSERT \"%s\"\n", i, zId); |
|
224
|
if( bDebug) pqueuex_test_print(&x); |
|
225
|
} |
|
226
|
} |
|
227
|
while( (zId = pqueuex_extract_ptr(&x))!=0 ){ |
|
228
|
fossil_print("... POP \"%s\"\n", zId); |
|
229
|
if( bDebug) pqueuex_test_print(&x); |
|
230
|
|