/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=2 et sw=2 tw=80: */
/*
Copyright (c) 2014 D. Richard Hipp
This program is free software; you can redistribute it and/or
modify it under the terms of the Simplified BSD License (also
known as the "2-Clause License" or "FreeBSD License".)
This program is distributed in the hope that it will be useful,
but without any warranty; without even the implied warranty of
merchantability or fitness for a particular purpose.
Author contact information:
drh@hwaci.com
http://www.hwaci.com/drh/
*****************************************************************************
This file contains routines related to working with the filesystem.
*/
#include "fossil-scm/fossil-internal.h"
#include "fossil-scm/fossil-path.h"
#include <assert.h>
/* Only for debugging */
#include <stdio.h>
#define MARKER(pfexp) \
do{ printf("MARKER: %s:%d:%s():\t",__FILE__,__LINE__,__func__); \
printf pfexp; \
} while(0)
static const fsl_path_node fsl_path_node_empty = {0,0,0,0,0,{0},0};
const fsl_path fsl_path_empty = fsl_path_empty_m;
void fsl_path_clear(fsl_path *path){
fsl_path_node * p;
while(path->pAll){
p = path->pAll;
path->pAll = p->pAll;
fsl_free(p);
}
fsl_id_bag_clear(&path->seen);
*path = fsl_path_empty;
}
fsl_path_node * fsl_path_first(fsl_path *p){
return p->pStart;
}
fsl_path_node * fsl_path_last(fsl_path *p){
return p->pEnd;
}
int fsl_path_length(fsl_path const * p){
return p->nStep;
}
fsl_path_node * fsl_path_next(fsl_path_node *p){
return p->u.pTo;
}
fsl_path_node * fsl_path_midpoint(fsl_path * path){
if( path->nStep<2 ) return 0;
else{
fsl_path_node *p;
int i;
int const max = path->nStep/2;
for(p=path->pEnd, i=0; p && i<max; p=p->pFrom, i++){}
return p;
}
}
/**
Reconstructs path from path->pStart to path->pEnd, reversing its
order by fiddling with the u->pTo fields.
Unfortunately does not reverse after the initial creation/reversal
:/.
*/
void fsl_path_reverse(fsl_path * path);
void fsl_path_reverse(fsl_path * path){
fsl_path_node *p;
assert( path->pEnd!=0 );
for(p=path->pEnd; p && p->pFrom; p = p->pFrom){
p->pFrom->u.pTo = p;
}
path->pEnd->u.pTo = 0;
assert( p==path->pStart );
}
/**
Adds a new node to path and returns it. Returns 0 on allocation error.
path must not be 0. rid must be greater than 0. pFrom may be 0. If
pFrom is not 0 then isParent must be true if pFrom is a parent of
rid.
On success, sets the returned node as path->pCurrent, sets its
pFrom to the given pFrom, and sets rc->u.pPeer to the prior
path->pCurrent value.
*/
static fsl_path_node * fsl_path_new_node(fsl_path * path, fsl_id_t rid,
fsl_path_node * pFrom, char isParent){
fsl_path_node * rc = 0;
assert(path);
assert(rid>0);
if(0 != fsl_id_bag_insert(&path->seen, rid)) return 0;
rc = (fsl_path_node*)fsl_malloc(sizeof(fsl_path_node));
if(!rc){
fsl_id_bag_remove(&path->seen, rid);
return 0;
}
*rc = fsl_path_node_empty;
rc->rid = rid;
rc->fromIsParent = pFrom ? isParent : 0;
rc->pFrom = pFrom;
rc->u.pPeer = path->pCurrent;
path->pCurrent = rc;
rc->pAll = path->pAll;
path->pAll = rc;
return rc;
}
int fsl_path_shortest( fsl_cx * f, fsl_path * path,
fsl_id_t iFrom, fsl_id_t iTo,
char directOnly, char oneWayOnly ){
fsl_stmt s = fsl_stmt_empty;
fsl_db * db = fsl_needs_repo(f);
int rc = 0;
fsl_path_node * pPrev;
fsl_path_node * p;
assert(db);
if(!db) return FSL_RC_NOT_A_REPO;
else if(iFrom<=0){
return fsl_cx_err_set(f, FSL_RC_RANGE,
"Invalid 'from' RID: %d", (int)iFrom);
}else if(iTo<=0){
/*
Possible TODO: if iTo==0, use... what? Checkout? Tip of current
checkout branch? Trunk? The multitude of options make it impossible
to decide :/.
*/
return fsl_cx_err_set(f, FSL_RC_RANGE,
"Invalid 'to' RID: %d", (int)iTo);
}
fsl_path_clear(path);
path->pStart = fsl_path_new_node(path, iFrom, 0, 0);
if(!path->pStart){
return fsl_cx_err_set(f, FSL_RC_OOM, 0);
}
if( iTo == iFrom ){
path->pEnd = path->pStart;
return 0;
}
if( oneWayOnly ){
if(directOnly){
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1 AND isprim");
}else{
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1");
}
}else if( directOnly ){
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1 AND isprim "
"UNION ALL "
"SELECT pid, 0 FROM plink WHERE cid=?1 AND isprim");
}else{
rc = fsl_db_prepare(db, &s,
"SELECT cid, 1 FROM plink WHERE pid=?1 "
"UNION ALL "
"SELECT pid, 0 FROM plink WHERE cid=?1");
}
if(rc){
fsl_cx_uplift_db_error(f, db);
assert(f->error.code);
goto end;
}
while(path->pCurrent){
++path->nStep;
pPrev = path->pCurrent;
path->pCurrent = 0;
while( pPrev ){
rc = fsl_stmt_bind_id(&s, 1, pPrev->rid);
assert(0==rc);
while( FSL_RC_STEP_ROW == fsl_stmt_step(&s) ){
fsl_id_t const cid = fsl_stmt_g_id(&s, 0);
int const isParent = fsl_stmt_g_int32(&s, 1);
assert((cid>0) && "fsl_id_bag_find() asserts this.");
if( fsl_id_bag_contains(&path->seen, cid) ) continue;
p = fsl_path_new_node(path, cid, pPrev, isParent ? 1 : 0);
if(!p){
rc = fsl_cx_err_set(f, FSL_RC_OOM, 0);
goto end;
}
if( cid == iTo ){
fsl_stmt_finalize(&s);
path->pEnd = p;
fsl_path_reverse( path );
return 0;
}
}
fsl_stmt_reset(&s);
pPrev = pPrev->u.pPeer;
}
}
end:
fsl_stmt_finalize(&s);
fsl_path_clear(path);
return rc;
}
#undef MARKER