libfossil
vpath.h
Go to the documentation of this file.
1/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2/* vim: set ts=2 et sw=2 tw=80: */
3#if !defined(ORG_FOSSIL_SCM_FSL_VPATH_H_INCLUDED)
4#define ORG_FOSSIL_SCM_FSL_VPATH_H_INCLUDED
5/*
6 Copyright 2013-2021 The Libfossil Authors, see LICENSES/BSD-2-Clause.txt
7
8 SPDX-License-Identifier: BSD-2-Clause-FreeBSD
9 SPDX-FileCopyrightText: 2021 The Libfossil Authors
10 SPDX-FileType: Code
11
12 Heavily indebted to the Fossil SCM project (https://fossil-scm.org).
13
14 *****************************************************************************
15 This file declares public APIs relating to calculating paths via
16 Fossil SCM version history.
17*/
18
19#include "internal.h" /* MUST come first b/c of config macros */
20
21#if defined(__cplusplus)
22extern "C" {
23#endif
24
26typedef struct fsl_vpath fsl_vpath;
27
28/**
29 Holds information for a single node in a path of checkin versions.
30
31 @see fsl_vpath
32*/
34 /** ID for this node */
36 /** True if pFrom is the parent of rid */
38 /** True if primary side of common ancestor */
40 /* HISTORICAL: Abbreviate output in "fossil bisect ls" */
42 /** Node this one came from. */
44 union {
45 /** List of nodes of the same generation */
47 /** Next on path from beginning to end */
49 } u;
50 /** List of all nodes */
52};
53
54/**
55 A utility type for collecting "paths" between two checkin versions.
56*/
57struct fsl_vpath{
58 /** Current generation of nodes */
60 /** All nodes */
62 /** Nodes seen before */
64 /** Number of steps from first to last. */
65 int nStep;
66 /** Earliest node in the path. */
68 /** Common ancestor of pStart and pEnd */
70 /** Most recent node in the path. */
72};
73
74/**
75 An empty-initialize fsl_vpath object, intended for const-copy
76 initialization.
77*/
78#define fsl_vpath_empty_m {0,0,fsl_id_bag_empty_m,0,0,0,0}
79
80/**
81 An empty-initialize fsl_vpath object, intended for copy
82 initialization.
83*/
85
86
87/**
88 Returns the first node in p's path.
89
90 The returned node is owned by path may be invalidated by any APIs
91 which manipulate path.
92*/
94
95/**
96 Returns the last node in p's path.
97
98 The returned node is owned by path may be invalidated by any APIs
99 which manipulate path.
100*/
102
103/**
104 Returns the next node p's path.
105
106 The returned node is owned by path may be invalidated by any APIs
107 which manipulate path.
108
109 Intended to be used like this:
110
111 ```
112 for( p = fsl_vpath_first(path) ;
113 p ;
114 p = fsl_vpath_next(p)){
115 ...
116 }
117 ```
118*/
120
121/**
122 Returns p's path length.
123*/
125
126/**
127 Frees all nodes in path (which must not be NULL) and resets all
128 state in path. Does not free path.
129*/
131
132/**
133 Find the mid-point of the path. If the path contains fewer than 2
134 steps, returns 0. The returned node is owned by path and may be
135 invalidated by any APIs which manipulate path.
136*/
138
139
140/**
141 Computes the shortest path from checkin versions iFrom to iTo
142 (inclusive), storing the result state in path. If path has
143 state before this is called, it is cleared by this call.
144
145 iFrom and iTo must both be valid checkin version RIDs.
146
147 If directOnly is true, then use only the "primary" links from
148 parent to child. In other words, ignore merges.
149
150 On success, returns 0 and path->pStart will point to the
151 beginning of the path (the iFrom node). If pStart is 0 then no
152 path could be found but 0 is still returned.
153
154 Elements of the path can be traversed like so:
155
156 ```
157 fsl_vpath path = fsl_vpath_empty;
158 fsl_vpath_node * n = 0;
159 int rc = fsl_vpath_shortest(f, &path, versionFrom, versionTo, 1, 0);
160 if(rc) { ... error ... }
161 for( n = fsl_vpath_first(&path); n; n = fsl_vpath_next(n) ){
162 ...
163 }
164 fsl_vpath_clear(&path);
165 ```
166
167 On error, f's error state may be updated with a description of the
168 problem.
169*/
170FSL_EXPORT int fsl_vpath_shortest( fsl_cx * const f, fsl_vpath * const path,
171 fsl_id_t iFrom, fsl_id_t iTo,
172 bool directOnly, bool oneWayOnly );
173
174/**
175 This variant of fsl_vpath_shortest() stores the shortest direct
176 path from version iFrom to version iTo in the ANCESTOR temporary
177 table using f's current repo db handle. That table gets created, if
178 needed, else cleared by this call.
179
180 The ANCESTOR temp table has the following interface:
181
182 ```
183 rid INT UNIQUE
184 generation INTEGER PRIMARY KEY
185 ```
186
187 Where [rid] is a checkin version RID and [generation] is the
188 1-based number of steps from iFrom, including iFrom (so iFrom's own
189 generation is 1).
190
191 On error returns 0 and, if pSteps is not NULL, assigns *pSteps to
192 the number of entries added to the ancestor table. On error, pSteps
193 is never modifed, any number of various non-0 codes may be
194 returned, and f's error state will, if possible (not an OOM), be
195 updated to describe the problem.
196
197 This function's name is far too long and descriptive. We might want
198 to consider something shorter.
199
200 Maintenance reminder: this impl swaps the 2nd and 3rd parameters
201 compared to fossil(1)'s version!
202*/
204 fsl_id_t iFrom,
205 fsl_id_t iTo,
206 uint32_t *pSteps);
207
208/**
209 Computes a list of direct (non-merge) ancestors of the given
210 checkin RID and stores it in the TEMP table [ancestor], which it
211 creates if needed or clears if it currently exists.
212
213 The [ancestor] schema is described in
214 fsl_vpath_shortest_store_in_ancestor(). The [generation] value of
215 the record corresponding to rid is 1, increasing by 1 for each
216 generation back in the history.
217
218 Returns 0 on success, FSL_RC_NOT_A_REPO if f has no repo db opened,
219 and any number of lower-level result codes if something goes wrong.
220*/
222
223/**
224 Reconstructs path from path->pStart to path->pEnd, reversing its
225 order by fiddling with the u->pTo fields.
226
227 Unfortunately does not reverse after the initial creation/reversal
228 :/.
229*/
231
232
233#if defined(__cplusplus)
234} /*extern "C"*/
235#endif
236#endif
237/* ORG_FOSSIL_SCM_FSL_VPATH_H_INCLUDED */
int32_t fsl_id_t
fsl_id_t is a signed integer type used to store database record IDs.
Definition config.h:271
#define FSL_EXPORT
Definition config.h:66
The main Fossil "context" type.
Definition internal.h:400
A container type for lists of db record IDs.
Definition util.h:5694
Holds information for a single node in a path of checkin versions.
Definition vpath.h:33
bool fromIsParent
True if pFrom is the parent of rid.
Definition vpath.h:37
fsl_vpath_node * pPeer
List of nodes of the same generation.
Definition vpath.h:46
bool isHidden
Definition vpath.h:41
union fsl_vpath_node::@166032324341334222304251103243013332167162031034 u
fsl_vpath_node * pAll
List of all nodes.
Definition vpath.h:51
fsl_id_t rid
ID for this node.
Definition vpath.h:35
fsl_vpath_node * pFrom
Node this one came from.
Definition vpath.h:43
fsl_vpath_node * pTo
Next on path from beginning to end.
Definition vpath.h:48
bool isPrimary
True if primary side of common ancestor.
Definition vpath.h:39
A utility type for collecting "paths" between two checkin versions.
Definition vpath.h:57
fsl_id_bag seen
Nodes seen before.
Definition vpath.h:63
fsl_vpath_node * pEnd
Most recent node in the path.
Definition vpath.h:71
fsl_vpath_node * pPivot
Common ancestor of pStart and pEnd.
Definition vpath.h:69
fsl_vpath_node * pCurrent
Current generation of nodes.
Definition vpath.h:59
int nStep
Number of steps from first to last.
Definition vpath.h:65
fsl_vpath_node * pAll
All nodes.
Definition vpath.h:61
fsl_vpath_node * pStart
Earliest node in the path.
Definition vpath.h:67
FSL_EXPORT void fsl_vpath_reverse(fsl_vpath *path)
Reconstructs path from path->pStart to path->pEnd, reversing its order by fiddling with the u->pTo fi...
FSL_EXPORT const fsl_vpath fsl_vpath_empty
An empty-initialize fsl_vpath object, intended for copy initialization.
Definition vpath.h:84
FSL_EXPORT fsl_vpath_node * fsl_vpath_last(fsl_vpath *p)
Returns the last node in p's path.
FSL_EXPORT int fsl_vpath_shortest_store_in_ancestor(fsl_cx *const f, fsl_id_t iFrom, fsl_id_t iTo, uint32_t *pSteps)
This variant of fsl_vpath_shortest() stores the shortest direct path from version iFrom to version iT...
FSL_EXPORT void fsl_vpath_clear(fsl_vpath *path)
Frees all nodes in path (which must not be NULL) and resets all state in path.
FSL_EXPORT fsl_vpath_node * fsl_vpath_first(fsl_vpath *p)
Returns the first node in p's path.
FSL_EXPORT fsl_vpath_node * fsl_vpath_next(fsl_vpath_node *p)
Returns the next node p's path.
FSL_EXPORT int fsl_compute_direct_ancestors(fsl_cx *const f, fsl_id_t rid)
Computes a list of direct (non-merge) ancestors of the given checkin RID and stores it in the TEMP ta...
FSL_EXPORT int fsl_vpath_length(fsl_vpath const *p)
Returns p's path length.
FSL_EXPORT int fsl_vpath_shortest(fsl_cx *const f, fsl_vpath *const path, fsl_id_t iFrom, fsl_id_t iTo, bool directOnly, bool oneWayOnly)
Computes the shortest path from checkin versions iFrom to iTo (inclusive), storing the result state i...
FSL_EXPORT fsl_vpath_node * fsl_vpath_midpoint(fsl_vpath *path)
Find the mid-point of the path.