Fossil

Check-in [81162c71]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Change the "pqueue_" prefix on methods of the priority queue object to be "pqueuex_" to avoid conflicts with OpenSSL.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:81162c716c07678d757ec7f756311c0f3218afd2
User & Date: drh 2012-06-12 11:20:13
Context
2012-06-14
13:00
Remove temporary pqueue_insert renaming hack from the various Makefiles. check-in: 4006ee4f user: mistachkin tags: trunk
2012-06-12
11:20
Change the "pqueue_" prefix on methods of the priority queue object to be "pqueuex_" to avoid conflicts with OpenSSL. check-in: 81162c71 user: drh tags: trunk
2012-06-11
11:39
Minor pedantic wording change to accommodate a recent code change in how _FOSSIL_ stores the path to the repo file. check-in: 480367ce user: stephan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/descendants.c.

160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
...
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
*/
void compute_ancestors(int rid, int N){
  Bag seen;
  PQueue queue;
  Stmt ins;
  Stmt q;
  bag_init(&seen);
  pqueue_init(&queue);
  bag_insert(&seen, rid);
  pqueue_insert(&queue, rid, 0.0, 0);
  db_prepare(&ins, "INSERT OR IGNORE INTO ok VALUES(:rid)");
  db_prepare(&q,
    "SELECT a.pid, b.mtime FROM plink a LEFT JOIN plink b ON b.cid=a.pid"
    " WHERE a.cid=:rid"
  );
  while( (N--)>0 && (rid = pqueue_extract(&queue, 0))!=0 ){
    db_bind_int(&ins, ":rid", rid);
    db_step(&ins);
    db_reset(&ins);
    db_bind_int(&q, ":rid", rid);
    while( db_step(&q)==SQLITE_ROW ){
      int pid = db_column_int(&q, 0);
      double mtime = db_column_double(&q, 1);
      if( bag_insert(&seen, pid) ){
        pqueue_insert(&queue, pid, -mtime, 0);
      }
    }
    db_reset(&q);
  }
  bag_clear(&seen);
  pqueue_clear(&queue);
  db_finalize(&ins);
  db_finalize(&q);
}

/*
** Compute up to N direct ancestors (merge ancestors do not count)
** for the check-in rid and put them in a table named "ancestor".
................................................................................
void compute_descendants(int rid, int N){
  Bag seen;
  PQueue queue;
  Stmt ins;
  Stmt q;

  bag_init(&seen);
  pqueue_init(&queue);
  bag_insert(&seen, rid);
  pqueue_insert(&queue, rid, 0.0, 0);
  db_prepare(&ins, "INSERT OR IGNORE INTO ok VALUES(:rid)");
  db_prepare(&q, "SELECT cid, mtime FROM plink WHERE pid=:rid");
  while( (N--)>0 && (rid = pqueue_extract(&queue, 0))!=0 ){
    db_bind_int(&ins, ":rid", rid);
    db_step(&ins);
    db_reset(&ins);
    db_bind_int(&q, ":rid", rid);
    while( db_step(&q)==SQLITE_ROW ){
      int pid = db_column_int(&q, 0);
      double mtime = db_column_double(&q, 1);
      if( bag_insert(&seen, pid) ){
        pqueue_insert(&queue, pid, mtime, 0);
      }
    }
    db_reset(&q);
  }
  bag_clear(&seen);
  pqueue_clear(&queue);
  db_finalize(&ins);
  db_finalize(&q);
}

/*
** COMMAND: descendants*
**







|

|





|








|





|







 







|

|


|








|





|







160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
...
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
*/
void compute_ancestors(int rid, int N){
  Bag seen;
  PQueue queue;
  Stmt ins;
  Stmt q;
  bag_init(&seen);
  pqueuex_init(&queue);
  bag_insert(&seen, rid);
  pqueuex_insert(&queue, rid, 0.0, 0);
  db_prepare(&ins, "INSERT OR IGNORE INTO ok VALUES(:rid)");
  db_prepare(&q,
    "SELECT a.pid, b.mtime FROM plink a LEFT JOIN plink b ON b.cid=a.pid"
    " WHERE a.cid=:rid"
  );
  while( (N--)>0 && (rid = pqueuex_extract(&queue, 0))!=0 ){
    db_bind_int(&ins, ":rid", rid);
    db_step(&ins);
    db_reset(&ins);
    db_bind_int(&q, ":rid", rid);
    while( db_step(&q)==SQLITE_ROW ){
      int pid = db_column_int(&q, 0);
      double mtime = db_column_double(&q, 1);
      if( bag_insert(&seen, pid) ){
        pqueuex_insert(&queue, pid, -mtime, 0);
      }
    }
    db_reset(&q);
  }
  bag_clear(&seen);
  pqueuex_clear(&queue);
  db_finalize(&ins);
  db_finalize(&q);
}

/*
** Compute up to N direct ancestors (merge ancestors do not count)
** for the check-in rid and put them in a table named "ancestor".
................................................................................
void compute_descendants(int rid, int N){
  Bag seen;
  PQueue queue;
  Stmt ins;
  Stmt q;

  bag_init(&seen);
  pqueuex_init(&queue);
  bag_insert(&seen, rid);
  pqueuex_insert(&queue, rid, 0.0, 0);
  db_prepare(&ins, "INSERT OR IGNORE INTO ok VALUES(:rid)");
  db_prepare(&q, "SELECT cid, mtime FROM plink WHERE pid=:rid");
  while( (N--)>0 && (rid = pqueuex_extract(&queue, 0))!=0 ){
    db_bind_int(&ins, ":rid", rid);
    db_step(&ins);
    db_reset(&ins);
    db_bind_int(&q, ":rid", rid);
    while( db_step(&q)==SQLITE_ROW ){
      int pid = db_column_int(&q, 0);
      double mtime = db_column_double(&q, 1);
      if( bag_insert(&seen, pid) ){
        pqueuex_insert(&queue, pid, mtime, 0);
      }
    }
    db_reset(&q);
  }
  bag_clear(&seen);
  pqueuex_clear(&queue);
  db_finalize(&ins);
  db_finalize(&q);
}

/*
** COMMAND: descendants*
**

Changes to src/pqueue.c.

20
21
22
23
24
25
26




27
28
29
30
31
32
33
..
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
..
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
** value.  We can insert integers with each integer tied to its
** value then extract the integer with the smallest value.
**
** The way this queue is used, we never expect it to contain more
** than 2 or 3 elements, so a simple array is sufficient as the
** implementation.  This could give worst case O(N) insert times,
** but because of the nature of the problem we expect O(1) performance.




*/
#include "config.h"
#include "pqueue.h"
#include <assert.h>


#if INTERFACE
................................................................................
  } *a;
};
#endif

/*
** Initialize a PQueue structure
*/
void pqueue_init(PQueue *p){
  memset(p, 0, sizeof(*p));
}

/*
** Destroy a PQueue.  Delete all of its content.
*/
void pqueue_clear(PQueue *p){
  free(p->a);
  pqueue_init(p);
}

/*
** Change the size of the queue so that it contains N slots
*/
static void pqueue_resize(PQueue *p, int N){
  p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
  p->sz = N;
}

/*
** Insert element e into the queue.
*/
void pqueue_insert(PQueue *p, int e, double v, void *pData){
  int i, j;
  if( p->cnt+1>p->sz ){
    pqueue_resize(p, p->cnt+5);
  }
  for(i=0; i<p->cnt; i++){
    if( p->a[i].value>v ){
      for(j=p->cnt; j>i; j--){
        p->a[j] = p->a[j-1];
      }
      break;
................................................................................
}

/*
** Extract the first element from the queue (the element with
** the smallest value) and return its ID.  Return 0 if the queue
** is empty.
*/
int pqueue_extract(PQueue *p, void **pp){
  int e, i;
  if( p->cnt==0 ){
    if( pp ) *pp = 0;
    return 0;
  }
  e = p->a[0].id;
  if( pp ) *pp = p->a[0].p;
  for(i=0; i<p->cnt-1; i++){
    p->a[i] = p->a[i+1];
  }
  p->cnt--;
  return e;
}







>
>
>
>







 







|






|

|





|







|


|







 







|













20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
..
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
..
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
** value.  We can insert integers with each integer tied to its
** value then extract the integer with the smallest value.
**
** The way this queue is used, we never expect it to contain more
** than 2 or 3 elements, so a simple array is sufficient as the
** implementation.  This could give worst case O(N) insert times,
** but because of the nature of the problem we expect O(1) performance.
**
** Compatibility note:  Some versions of OpenSSL export a symbols
** like "pqueue_insert".  This is, technically, a bug in OpenSSL.
** We work around it here by using "pqueuex_" instead of "pqueue_".
*/
#include "config.h"
#include "pqueue.h"
#include <assert.h>


#if INTERFACE
................................................................................
  } *a;
};
#endif

/*
** Initialize a PQueue structure
*/
void pqueuex_init(PQueue *p){
  memset(p, 0, sizeof(*p));
}

/*
** Destroy a PQueue.  Delete all of its content.
*/
void pqueuex_clear(PQueue *p){
  free(p->a);
  pqueuex_init(p);
}

/*
** Change the size of the queue so that it contains N slots
*/
static void pqueuex_resize(PQueue *p, int N){
  p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
  p->sz = N;
}

/*
** Insert element e into the queue.
*/
void pqueuex_insert(PQueue *p, int e, double v, void *pData){
  int i, j;
  if( p->cnt+1>p->sz ){
    pqueuex_resize(p, p->cnt+5);
  }
  for(i=0; i<p->cnt; i++){
    if( p->a[i].value>v ){
      for(j=p->cnt; j>i; j--){
        p->a[j] = p->a[j-1];
      }
      break;
................................................................................
}

/*
** Extract the first element from the queue (the element with
** the smallest value) and return its ID.  Return 0 if the queue
** is empty.
*/
int pqueuex_extract(PQueue *p, void **pp){
  int e, i;
  if( p->cnt==0 ){
    if( pp ) *pp = 0;
    return 0;
  }
  e = p->a[0].id;
  if( pp ) *pp = p->a[0].p;
  for(i=0; i<p->cnt-1; i++){
    p->a[i] = p->a[i+1];
  }
  p->cnt--;
  return e;
}

Changes to src/tag.c.

41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
..
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
){
  PQueue queue;        /* Queue of check-ins to be tagged */
  Stmt s;              /* Query the children of :pid to which to propagate */
  Stmt ins;            /* INSERT INTO tagxref */
  Stmt eventupdate;    /* UPDATE event */

  assert( tagType==0 || tagType==2 );
  pqueue_init(&queue);
  pqueue_insert(&queue, pid, 0.0, 0);

  /* Query for children of :pid to which to propagate the tag.
  ** Three returns:  (1) rid of the child.  (2) timestamp of child.
  ** (3) True to propagate or false to block.
  */
  db_prepare(&s, 
     "SELECT cid, plink.mtime,"
................................................................................
    );
  }
  if( tagid==TAG_BGCOLOR ){
    db_prepare(&eventupdate,
      "UPDATE event SET bgcolor=%Q WHERE objid=:rid", zValue
    );
  }
  while( (pid = pqueue_extract(&queue, 0))!=0 ){
    db_bind_int(&s, ":pid", pid);
    while( db_step(&s)==SQLITE_ROW ){
      int doit = db_column_int(&s, 2);
      if( doit ){
        int cid = db_column_int(&s, 0);
        double mtime = db_column_double(&s, 1);
        pqueue_insert(&queue, cid, mtime, 0);
        db_bind_int(&ins, ":rid", cid);
        db_step(&ins);
        db_reset(&ins);
        if( tagid==TAG_BGCOLOR ){
          db_bind_int(&eventupdate, ":rid", cid);
          db_step(&eventupdate);
          db_reset(&eventupdate);
................................................................................
        if( tagid==TAG_BRANCH ){
          leaf_eventually_check(cid);
        }
      }
    }
    db_reset(&s);
  }
  pqueue_clear(&queue);
  db_finalize(&ins);
  db_finalize(&s);
  if( tagid==TAG_BGCOLOR ){
    db_finalize(&eventupdate);
  }
}








|
|







 







|






|







 







|







41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
..
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
){
  PQueue queue;        /* Queue of check-ins to be tagged */
  Stmt s;              /* Query the children of :pid to which to propagate */
  Stmt ins;            /* INSERT INTO tagxref */
  Stmt eventupdate;    /* UPDATE event */

  assert( tagType==0 || tagType==2 );
  pqueuex_init(&queue);
  pqueuex_insert(&queue, pid, 0.0, 0);

  /* Query for children of :pid to which to propagate the tag.
  ** Three returns:  (1) rid of the child.  (2) timestamp of child.
  ** (3) True to propagate or false to block.
  */
  db_prepare(&s, 
     "SELECT cid, plink.mtime,"
................................................................................
    );
  }
  if( tagid==TAG_BGCOLOR ){
    db_prepare(&eventupdate,
      "UPDATE event SET bgcolor=%Q WHERE objid=:rid", zValue
    );
  }
  while( (pid = pqueuex_extract(&queue, 0))!=0 ){
    db_bind_int(&s, ":pid", pid);
    while( db_step(&s)==SQLITE_ROW ){
      int doit = db_column_int(&s, 2);
      if( doit ){
        int cid = db_column_int(&s, 0);
        double mtime = db_column_double(&s, 1);
        pqueuex_insert(&queue, cid, mtime, 0);
        db_bind_int(&ins, ":rid", cid);
        db_step(&ins);
        db_reset(&ins);
        if( tagid==TAG_BGCOLOR ){
          db_bind_int(&eventupdate, ":rid", cid);
          db_step(&eventupdate);
          db_reset(&eventupdate);
................................................................................
        if( tagid==TAG_BRANCH ){
          leaf_eventually_check(cid);
        }
      }
    }
    db_reset(&s);
  }
  pqueuex_clear(&queue);
  db_finalize(&ins);
  db_finalize(&s);
  if( tagid==TAG_BGCOLOR ){
    db_finalize(&eventupdate);
  }
}