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