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 the most recent common dbda8d6ce9 2007-07-21 drh: ** ancestor of time versions of the same file. We call this dbda8d6ce9 2007-07-21 drh: ** common ancestor the "pivot" in a 3-way merge. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: #include "config.h" dbda8d6ce9 2007-07-21 drh: #include "pivot.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: ** Set the primary file. The primary version is one of the two dbda8d6ce9 2007-07-21 drh: ** files that have a common ancestor. The other file is the secondary. dbda8d6ce9 2007-07-21 drh: ** There can be multiple secondaries but only a single primary. dbda8d6ce9 2007-07-21 drh: ** The primary must be set first. dbda8d6ce9 2007-07-21 drh: ** dbda8d6ce9 2007-07-21 drh: ** In the merge algorithm, the file being merged in is the primary. dbda8d6ce9 2007-07-21 drh: ** The current check-out or other files that have been merged into dbda8d6ce9 2007-07-21 drh: ** the current checkout are the secondaries. dbda8d6ce9 2007-07-21 drh: ** dbda8d6ce9 2007-07-21 drh: ** The act of setting the primary resets the pivot-finding algorithm. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: void pivot_set_primary(int rid){ dbda8d6ce9 2007-07-21 drh: /* Set up table used to do the search */ dbda8d6ce9 2007-07-21 drh: db_multi_exec( dbda8d6ce9 2007-07-21 drh: "CREATE TEMP TABLE IF NOT EXISTS aqueue(" dbda8d6ce9 2007-07-21 drh: " rid INTEGER PRIMARY KEY," /* The record id for this version */ dbda8d6ce9 2007-07-21 drh: " mtime REAL," /* Time when this version was created */ dbda8d6ce9 2007-07-21 drh: " pending BOOLEAN," /* True if we have not check this one yet */ dbda8d6ce9 2007-07-21 drh: " src BOOLEAN" /* 1 for primary. 0 for others */ dbda8d6ce9 2007-07-21 drh: ");" dbda8d6ce9 2007-07-21 drh: "DELETE FROM aqueue;" dbda8d6ce9 2007-07-21 drh: "CREATE INDEX IF NOT EXISTS aqueue_idx1 ON aqueue(pending, mtime);" dbda8d6ce9 2007-07-21 drh: ); dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* Insert the primary record */ dbda8d6ce9 2007-07-21 drh: db_multi_exec( dbda8d6ce9 2007-07-21 drh: "INSERT INTO aqueue(rid, mtime, pending, src)" fa0ba20a51 2007-07-30 drh: " SELECT %d, mtime, 1, 1 FROM plink WHERE cid=%d LIMIT 1", dbda8d6ce9 2007-07-21 drh: rid, rid dbda8d6ce9 2007-07-21 drh: ); dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* dbda8d6ce9 2007-07-21 drh: ** Set a secondary file. The primary file must be set first. There dbda8d6ce9 2007-07-21 drh: ** must be at least one secondary but there can be more than one if dbda8d6ce9 2007-07-21 drh: ** desired. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: void pivot_set_secondary(int rid){ dbda8d6ce9 2007-07-21 drh: /* Insert the primary record */ dbda8d6ce9 2007-07-21 drh: db_multi_exec( 5602bbbaff 2007-07-30 drh: "INSERT OR IGNORE INTO aqueue(rid, mtime, pending, src)" dbda8d6ce9 2007-07-21 drh: " SELECT %d, mtime, 1, 0 FROM plink WHERE cid=%d", dbda8d6ce9 2007-07-21 drh: rid, rid dbda8d6ce9 2007-07-21 drh: ); dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* dbda8d6ce9 2007-07-21 drh: ** Find the most recent common ancestor of the primary and one of dbda8d6ce9 2007-07-21 drh: ** the secondaries. Return its rid. Return 0 if no common ancestor dbda8d6ce9 2007-07-21 drh: ** can be found. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: int pivot_find(void){ dbda8d6ce9 2007-07-21 drh: Stmt q1, q2, u1, i1; dbda8d6ce9 2007-07-21 drh: int rid; dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* aqueue must contain at least one primary and one other. Otherwise dbda8d6ce9 2007-07-21 drh: ** we abort early dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: if( db_int(0, "SELECT count(distinct src) FROM aqueue")<2 ){ dbda8d6ce9 2007-07-21 drh: fossil_panic("lack both primary and secondary files"); dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* Prepare queries we will be needing dbda8d6ce9 2007-07-21 drh: ** dbda8d6ce9 2007-07-21 drh: ** The first query finds the oldest pending version on the aqueue. This dbda8d6ce9 2007-07-21 drh: ** will be next one searched. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: db_prepare(&q1, "SELECT rid FROM aqueue WHERE pending" dbda8d6ce9 2007-07-21 drh: " ORDER BY pending DESC, mtime DESC"); dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* Check to see if the record :rid is a common ancestor. The result dbda8d6ce9 2007-07-21 drh: ** set contains one or more rows if it is and is the empty set if it dbda8d6ce9 2007-07-21 drh: ** is not. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: db_prepare(&q2, dbda8d6ce9 2007-07-21 drh: "SELECT 1 FROM aqueue A, plink, aqueue B" dbda8d6ce9 2007-07-21 drh: " WHERE plink.pid=:rid" dbda8d6ce9 2007-07-21 drh: " AND plink.cid=B.rid" dbda8d6ce9 2007-07-21 drh: " AND A.rid=:rid" dbda8d6ce9 2007-07-21 drh: " AND A.src!=B.src" dbda8d6ce9 2007-07-21 drh: ); dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* Mark the :rid record has having been checked. It is not the dbda8d6ce9 2007-07-21 drh: ** common ancestor. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: db_prepare(&u1, dbda8d6ce9 2007-07-21 drh: "UPDATE aqueue SET pending=0 WHERE rid=:rid" dbda8d6ce9 2007-07-21 drh: ); dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* Add to the queue all ancestors of :rid. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: db_prepare(&i1, dbda8d6ce9 2007-07-21 drh: "INSERT OR IGNORE INTO aqueue " dbda8d6ce9 2007-07-21 drh: "SELECT plink.pid," dbda8d6ce9 2007-07-21 drh: " coalesce((SELECT mtime FROM plink X WHERE X.cid=plink.pid), 0.0)," dbda8d6ce9 2007-07-21 drh: " 1," dbda8d6ce9 2007-07-21 drh: " aqueue.src " dbda8d6ce9 2007-07-21 drh: " FROM plink, aqueue" dbda8d6ce9 2007-07-21 drh: " WHERE plink.cid=:rid" dbda8d6ce9 2007-07-21 drh: " AND aqueue.rid=:rid" dbda8d6ce9 2007-07-21 drh: ); dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: while( db_step(&q1)==SQLITE_ROW ){ dbda8d6ce9 2007-07-21 drh: rid = db_column_int(&q1, 0); dbda8d6ce9 2007-07-21 drh: db_reset(&q1); dbda8d6ce9 2007-07-21 drh: db_bind_int(&q2, ":rid", rid); dbda8d6ce9 2007-07-21 drh: if( db_step(&q2)==SQLITE_ROW ){ dbda8d6ce9 2007-07-21 drh: break; dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: db_reset(&q2); dbda8d6ce9 2007-07-21 drh: db_bind_int(&i1, ":rid", rid); dbda8d6ce9 2007-07-21 drh: db_exec(&i1); dbda8d6ce9 2007-07-21 drh: db_bind_int(&u1, ":rid", rid); dbda8d6ce9 2007-07-21 drh: db_exec(&u1); dbda8d6ce9 2007-07-21 drh: rid = 0; dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: db_finalize(&q1); dbda8d6ce9 2007-07-21 drh: db_finalize(&q2); dbda8d6ce9 2007-07-21 drh: db_finalize(&i1); dbda8d6ce9 2007-07-21 drh: db_finalize(&u1); dbda8d6ce9 2007-07-21 drh: return rid; dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: dbda8d6ce9 2007-07-21 drh: /* dbda8d6ce9 2007-07-21 drh: ** COMMAND: test-find-pivot dbda8d6ce9 2007-07-21 drh: ** dbda8d6ce9 2007-07-21 drh: ** Test the pivot_find() procedure. dbda8d6ce9 2007-07-21 drh: */ dbda8d6ce9 2007-07-21 drh: void test_find_pivot(void){ dbda8d6ce9 2007-07-21 drh: int i, rid; dbda8d6ce9 2007-07-21 drh: if( g.argc<4 ){ dbda8d6ce9 2007-07-21 drh: usage("PRIMARY SECONDARY ..."); dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: db_must_be_within_tree(); dbda8d6ce9 2007-07-21 drh: pivot_set_primary(name_to_rid(g.argv[2])); dbda8d6ce9 2007-07-21 drh: for(i=3; i<g.argc; i++){ dbda8d6ce9 2007-07-21 drh: pivot_set_secondary(name_to_rid(g.argv[i])); dbda8d6ce9 2007-07-21 drh: } dbda8d6ce9 2007-07-21 drh: rid = pivot_find(); dbda8d6ce9 2007-07-21 drh: printf("pivot=%s\n", dbda8d6ce9 2007-07-21 drh: db_text("?","SELECT uuid FROM blob WHERE rid=%d",rid) dbda8d6ce9 2007-07-21 drh: ); dbda8d6ce9 2007-07-21 drh: }
File Annotation