6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Copyright (c) 2007 D. Richard Hipp 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** This program is free software; you can redistribute it and/or 6458f020fc 2008-05-14 drh: ** modify it under the terms of the GNU General Public 6458f020fc 2008-05-14 drh: ** License version 2 as published by the Free Software Foundation. 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** This program is distributed in the hope that it will be useful, 6458f020fc 2008-05-14 drh: ** but WITHOUT ANY WARRANTY; without even the implied warranty of 6458f020fc 2008-05-14 drh: ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 6458f020fc 2008-05-14 drh: ** General Public License for more details. 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** You should have received a copy of the GNU General Public 6458f020fc 2008-05-14 drh: ** License along with this library; if not, write to the 6458f020fc 2008-05-14 drh: ** Free Software Foundation, Inc., 59 Temple Place - Suite 330, 6458f020fc 2008-05-14 drh: ** Boston, MA 02111-1307, USA. 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** Author contact information: 6458f020fc 2008-05-14 drh: ** drh@hwaci.com 6458f020fc 2008-05-14 drh: ** http://www.hwaci.com/drh/ 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ******************************************************************************* 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** This file contains code used to find decendants of a version 6458f020fc 2008-05-14 drh: ** or leaves of a version tree. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: #include "config.h" 6458f020fc 2008-05-14 drh: #include "descendants.h" 6458f020fc 2008-05-14 drh: #include <assert.h> 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Create a temporary table named "leaves" if it does not 6458f020fc 2008-05-14 drh: ** already exist. Load this table with the RID of all 6458f020fc 2008-05-14 drh: ** versions that are leaves which are decended from 6458f020fc 2008-05-14 drh: ** version iBase. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void compute_leaves(int iBase){ 6458f020fc 2008-05-14 drh: Bag seen; /* Descendants seen */ 6458f020fc 2008-05-14 drh: Bag pending; /* Unpropagated descendants */ 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: db_multi_exec( 6458f020fc 2008-05-14 drh: "CREATE TEMP TABLE IF NOT EXISTS leaves(" 6458f020fc 2008-05-14 drh: " rid INTEGER PRIMARY KEY" 6458f020fc 2008-05-14 drh: ");" 6458f020fc 2008-05-14 drh: "DELETE FROM leaves;" 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: bag_init(&seen); 6458f020fc 2008-05-14 drh: bag_init(&pending); 6458f020fc 2008-05-14 drh: bag_insert(&pending, iBase); 6458f020fc 2008-05-14 drh: while( bag_count(&pending) ){ 6458f020fc 2008-05-14 drh: int rid = bag_first(&pending); 6458f020fc 2008-05-14 drh: int cnt = 0; 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: bag_remove(&pending, rid); 6458f020fc 2008-05-14 drh: db_prepare(&q, "SELECT cid FROM plink WHERE pid=%d", rid); 6458f020fc 2008-05-14 drh: while( db_step(&q)==SQLITE_ROW ){ 6458f020fc 2008-05-14 drh: int cid = db_column_int(&q, 0); 6458f020fc 2008-05-14 drh: if( bag_insert(&seen, cid) ){ 6458f020fc 2008-05-14 drh: bag_insert(&pending, cid); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: cnt++; 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: if( cnt==0 ){ 6458f020fc 2008-05-14 drh: db_multi_exec("INSERT INTO leaves VALUES(%d)", rid); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: bag_clear(&pending); 6458f020fc 2008-05-14 drh: bag_clear(&seen); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Load the record ID rid and up to N-1 closest ancestors into 6458f020fc 2008-05-14 drh: ** the "ok" table. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void compute_ancestors(int rid, int N){ 6458f020fc 2008-05-14 drh: Bag seen; 6458f020fc 2008-05-14 drh: PQueue queue; 6458f020fc 2008-05-14 drh: bag_init(&seen); 6458f020fc 2008-05-14 drh: pqueue_init(&queue); 6458f020fc 2008-05-14 drh: bag_insert(&seen, rid); 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, rid, 0.0); 6458f020fc 2008-05-14 drh: while( (N--)>0 && (rid = pqueue_extract(&queue))!=0 ){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: db_multi_exec("INSERT OR IGNORE INTO ok VALUES(%d)", rid); 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "SELECT a.pid, b.mtime FROM plink a LEFT JOIN plink b ON b.cid=a.pid" 6458f020fc 2008-05-14 drh: " WHERE a.cid=%d", rid 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: while( db_step(&q)==SQLITE_ROW ){ 6458f020fc 2008-05-14 drh: int pid = db_column_int(&q, 0); 6458f020fc 2008-05-14 drh: double mtime = db_column_double(&q, 1); 6458f020fc 2008-05-14 drh: if( bag_insert(&seen, pid) ){ 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, pid, -mtime); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: bag_clear(&seen); 6458f020fc 2008-05-14 drh: pqueue_clear(&queue); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** Load the record ID rid and up to N-1 closest descendants into 6458f020fc 2008-05-14 drh: ** the "ok" table. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void compute_descendants(int rid, int N){ 6458f020fc 2008-05-14 drh: Bag seen; 6458f020fc 2008-05-14 drh: PQueue queue; 6458f020fc 2008-05-14 drh: bag_init(&seen); 6458f020fc 2008-05-14 drh: pqueue_init(&queue); 6458f020fc 2008-05-14 drh: bag_insert(&seen, rid); 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, rid, 0.0); 6458f020fc 2008-05-14 drh: while( (N--)>0 && (rid = pqueue_extract(&queue))!=0 ){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: db_multi_exec("INSERT OR IGNORE INTO ok VALUES(%d)", rid); 6458f020fc 2008-05-14 drh: db_prepare(&q,"SELECT cid, mtime FROM plink WHERE pid=%d", rid); 6458f020fc 2008-05-14 drh: while( db_step(&q)==SQLITE_ROW ){ 6458f020fc 2008-05-14 drh: int pid = db_column_int(&q, 0); 6458f020fc 2008-05-14 drh: double mtime = db_column_double(&q, 1); 6458f020fc 2008-05-14 drh: if( bag_insert(&seen, pid) ){ 6458f020fc 2008-05-14 drh: pqueue_insert(&queue, pid, mtime); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: bag_clear(&seen); 6458f020fc 2008-05-14 drh: pqueue_clear(&queue); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** COMMAND: descendants 6458f020fc 2008-05-14 drh: ** e8c4f69c50 2008-10-24 drh: ** Usage: %fossil descendants ?BASELINE-ID? 6458f020fc 2008-05-14 drh: ** e8c4f69c50 2008-10-24 drh: ** Find all leaf descendants of the baseline specified or if the argument e8c4f69c50 2008-10-24 drh: ** is omitted, of the baseline currently checked out. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void descendants_cmd(void){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: int base; 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: db_must_be_within_tree(); 6458f020fc 2008-05-14 drh: if( g.argc==2 ){ 6458f020fc 2008-05-14 drh: base = db_lget_int("checkout", 0); 6458f020fc 2008-05-14 drh: }else{ 6458f020fc 2008-05-14 drh: base = name_to_rid(g.argv[2]); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: if( base==0 ) return; 6458f020fc 2008-05-14 drh: compute_leaves(base); 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "%s" 6458f020fc 2008-05-14 drh: " AND event.objid IN (SELECT rid FROM leaves)" 6458f020fc 2008-05-14 drh: " ORDER BY event.mtime DESC", 6458f020fc 2008-05-14 drh: timeline_query_for_tty() 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: print_timeline(&q, 20); 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** COMMAND: leaves 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** Usage: %fossil leaves 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** Find leaves of all branches. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void branches_cmd(void){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: db_must_be_within_tree(); 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "%s" 6458f020fc 2008-05-14 drh: " AND blob.rid IN" 6458f020fc 2008-05-14 drh: " (SELECT cid FROM plink EXCEPT SELECT pid FROM plink)" 6458f020fc 2008-05-14 drh: " ORDER BY event.mtime DESC", 6458f020fc 2008-05-14 drh: timeline_query_for_tty() 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: print_timeline(&q, 2000); 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: /* 6458f020fc 2008-05-14 drh: ** WEBPAGE: leaves 6458f020fc 2008-05-14 drh: ** 6458f020fc 2008-05-14 drh: ** Find leaves of all branches. 6458f020fc 2008-05-14 drh: */ 6458f020fc 2008-05-14 drh: void leaves_page(void){ 6458f020fc 2008-05-14 drh: Stmt q; 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: login_check_credentials(); 6458f020fc 2008-05-14 drh: if( !g.okRead ){ login_needed(); return; } 6458f020fc 2008-05-14 drh: 6458f020fc 2008-05-14 drh: style_header("Leaves"); 6458f020fc 2008-05-14 drh: login_anonymous_available(); 6458f020fc 2008-05-14 drh: db_prepare(&q, 6458f020fc 2008-05-14 drh: "%s" 6458f020fc 2008-05-14 drh: " AND blob.rid IN" 6458f020fc 2008-05-14 drh: " (SELECT cid FROM plink EXCEPT SELECT pid FROM plink)" 6458f020fc 2008-05-14 drh: " ORDER BY event.mtime DESC", 6458f020fc 2008-05-14 drh: timeline_query_for_www() 6458f020fc 2008-05-14 drh: ); 6458f020fc 2008-05-14 drh: www_print_timeline(&q); 6458f020fc 2008-05-14 drh: db_finalize(&q); 6458f020fc 2008-05-14 drh: @ <script> 6458f020fc 2008-05-14 drh: @ function xin(id){ 6458f020fc 2008-05-14 drh: @ } 6458f020fc 2008-05-14 drh: @ function xout(id){ 6458f020fc 2008-05-14 drh: @ } 6458f020fc 2008-05-14 drh: @ </script> 6458f020fc 2008-05-14 drh: style_footer(); 6458f020fc 2008-05-14 drh: }
File Annotation