Fossil SCM

Improved implementation of the PQueue object, with the added option to carry an arbitrary pointer as content.

drh 2025-03-08 12:13 min-from-to

Commit 4111717eae6f26dfd5b78a32b6a2d25dce9a10495a6ec759e6a133175e6c28c1

Parent d82b52aac459a15…

1 file changed +147 -27

M src/pqueue.c

+147 -27

		--- src/pqueue.c
		+++ src/pqueue.c
		@@ -15,17 +15,24 @@
15	15	**
16	16	*******************************************************************************
17	17	**
18	18	** This file contains code used to implement a priority queue.
19	19	** A priority queue is a list of items order by a floating point
20		-** value. We can insert integers with each integer tied to its
21		-** value then extract the integer with the smallest value.
	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[x2+1] and a[x2+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).
22	31	**
23		-** The way this queue is used, we never expect it to contain more
24		-** than 2 or 3 elements, so a simple array is sufficient as the
25		-** implementation. This could give worst case O(N) insert times,
26		-** but because of the nature of the problem we expect O(1) performance.
	32	+** A consequence of the heap property is that a[0] always contains
	33	+** the node with the smallest value.
27	34	**
28	35	** Compatibility note: Some versions of OpenSSL export a symbols
29	36	** like "pqueue_insert". This is, technically, a bug in OpenSSL.
30	37	** We work around it here by using "pqueuex_" instead of "pqueue_".
31	38	*/
		@@ -41,11 +48,14 @@
41	48	*/
42	49	struct PQueue {
43	50	int cnt; /* Number of entries in the queue */
44	51	int sz; /* Number of slots in a[] */
45	52	struct QueueElement {
46		- int id; /* ID of the element */
	53	+ union {
	54	+ int id; /* ID of the element */
	55	+ void p; / Pointer to an object */
	56	+ } u;
47	57	double value; /* Value of element. Kept in ascending order */
48	58	} *a;
49	59	};
50	60	#endif
51	61
		@@ -69,44 +79,154 @@
69	79	*/
70	80	static void pqueuex_resize(PQueue *p, int N){
71	81	p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
72	82	p->sz = N;
73	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	+}
74	110
75	111	/*
76	112	** Insert element e into the queue.
77	113	*/
78	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){
79	132	int i, j;
80		- if( p->cnt+1>p->sz ){
81		- pqueuex_resize(p, p->cnt+5);
82		- }
83		- for(i=0; i<p->cnt; i++){
84		- if( p->a[i].value>v ){
85		- for(j=p->cnt; j>i; j--){
86		- p->a[j] = p->a[j-1];
87		- }
88		- break;
89		- }
90		- }
91		- p->a[i].id = e;
92		- p->a[i].value = v;
93		- p->cnt++;
	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	+ }
94	146	}
95	147
96	148	/*
97	149	** Extract the first element from the queue (the element with
98	150	** the smallest value) and return its ID. Return 0 if the queue
99	151	** is empty.
100	152	*/
101	153	int pqueuex_extract(PQueue *p){
102		- int e, i;
	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;
103	164	if( p->cnt==0 ){
104	165	return 0;
105	166	}
106		- e = p->a[0].id;
107		- for(i=0; i<p->cnt-1; i++){
108		- p->a[i] = p->a[i+1];
	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	+ }else{
	218	+ double r = 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);
109	230	}
110		- p->cnt--;
111		- return e;
	231	+ pqueuex_clear(&x);
112	232	}
113	233

	--- src/pqueue.c
	+++ src/pqueue.c
	@@ -15,17 +15,24 @@
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. We can insert integers with each integer tied to its
21	** value then extract the integer with the smallest value.









22	**
23	** The way this queue is used, we never expect it to contain more
24	** than 2 or 3 elements, so a simple array is sufficient as the
25	** implementation. This could give worst case O(N) insert times,
26	** but because of the nature of the problem we expect O(1) performance.
27	**
28	** Compatibility note: Some versions of OpenSSL export a symbols
29	** like "pqueue_insert". This is, technically, a bug in OpenSSL.
30	** We work around it here by using "pqueuex_" instead of "pqueue_".
31	*/
	@@ -41,11 +48,14 @@
41	*/
42	struct PQueue {
43	int cnt; /* Number of entries in the queue */
44	int sz; /* Number of slots in a[] */
45	struct QueueElement {
46	int id; /* ID of the element */



47	double value; /* Value of element. Kept in ascending order */
48	} *a;
49	};
50	#endif
51
	@@ -69,44 +79,154 @@
69	*/
70	static void pqueuex_resize(PQueue *p, int N){
71	p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
72	p->sz = N;
73	}


























74
75	/*
76	** Insert element e into the queue.
77	*/
78	void pqueuex_insert(PQueue *p, int e, double v){

















79	int i, j;
80	if( p->cnt+1>p->sz ){
81	pqueuex_resize(p, p->cnt+5);
82	}
83	for(i=0; i<p->cnt; i++){
84	if( p->a[i].value>v ){
85	for(j=p->cnt; j>i; j--){
86	p->a[j] = p->a[j-1];
87	}
88	break;
89	}
90	}
91	p->a[i].id = e;
92	p->a[i].value = v;
93	p->cnt++;
94	}
95
96	/*
97	** Extract the first element from the queue (the element with
98	** the smallest value) and return its ID. Return 0 if the queue
99	** is empty.
100	*/
101	int pqueuex_extract(PQueue *p){
102	int e, i;









103	if( p->cnt==0 ){
104	return 0;
105	}
106	e = p->a[0].id;
107	for(i=0; i<p->cnt-1; i++){
108	p->a[i] = p->a[i+1];




























































109	}
110	p->cnt--;
111	return e;
112	}
113

	--- src/pqueue.c
	+++ src/pqueue.c
	@@ -15,17 +15,24 @@
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[x2+1] and a[x2+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	*/
	@@ -41,11 +48,14 @@
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
	@@ -69,44 +79,154 @@
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	}else{
218	double r = 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	}
231	pqueuex_clear(&x);

232	}
233

Fossil SCM

Keyboard Shortcuts