Fossil SCM

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

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button