3 * Duplicate multiple files
5 * (c) 2008 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software Foundation,
22 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
25 /*----- Header files ------------------------------------------------------*/
34 /*----- Data structures ---------------------------------------------------*/
36 typedef struct mdup_fdinfo
{
39 /* Each @fdinfo@ structure refers to one of the caller's @fd@ structures.
43 struct mdup_fdinfo
*eqnext
, *eqprev
;
44 /* The caller's request list can contain more than one entry with any given
45 * @cur@ descriptor. We group them together into an equivalence class,
46 * which is doubly linked using these fields.
49 struct mdup_fdinfo
*up
;
50 /* We require that there be at most one node with any given @want@
51 * descriptor (other than @-1@). There is therefore at most one node whose
52 * @want@ is equal to my @cur@. If such a node exists, @up@ points to it;
53 * otherwise @up@ is null.
56 struct mdup_fdinfo
*down
;
57 /* Obviously, @down@ links in the opposite direction from @up@. However,
58 * there may be several nodes whose @cur@ equals my @want@; therefore
59 * @down@ simply links to one of the nodes in the equivalence class.
61 * Unsurprisingly, @down@ is the direction we move during the depth-first
62 * traversal phase of the operation.
65 struct mdup_fdinfo
*dlink
;
66 /* Nodes with @want == -1@, and nodes where we've broken cycles, are
67 * considered `dynamic': their @cur@ has been chosen by @dup@ to be
68 * distinct from any existing descriptor, but may collide with a @want@.
69 * We check each proposed move against the list of dynamic nodes, and move
70 * them out of the way as necessary. Note that this is really a list of
71 * equivalence classes rather than single nodes.
75 /* The current state of this node. One of the @ST@ constants described
82 /* Node has not yet been processed.
86 /* Node has been reached by the depth-first traversal, but its descriptor
87 * has not yet been moved. This state is used to detect cycles using the
88 * depth-first traversal.
92 /* Node has been processed completely. We have @want == -1@ or
97 /* Node has been clobbered in order to break a cycle. The node's
98 * equivalence class has been remapped to a fresh descriptor which (we
99 * hope) is not equal to any node's @want@. All broken nodes are put on
100 * the dynamic list: if our hope turns out to be misplaced we can remap the
105 /*----- Main code ---------------------------------------------------------*/
107 /* --- @DO_EQUIVS@ --- *
109 * Perform @body@ once for each @g@ in the equivalence class of @f@.
112 #define DO_EQUIVS(g, f, body) do { \
113 mdup_fdinfo *f_ = (f), *g_ = f_; \
114 do { mdup_fdinfo *g = g_; g_ = g_->eqnext; body; } while (g_ != f_); \
119 * Arguments: @mdup_fdinfo *v@ = pointer to info vector
120 * @size_t n@ = size of vector
124 * Use: Dumps a scary-looking description of the state of @mdup@'s
135 static void dump(mdup_fdinfo
*v
, size_t n
, mdup_fdinfo
*dhead
,
136 const char *fmt
, ...)
140 static const char *state
[] = { "READY", "MARK", "DONE", "BROKEN" };
143 #define INDEX(p) ((p) ? (int)((p) - (v)) : -1)
145 /* --- Dump the items, fairly raw --- */
148 fputs("*** ", stdout
);
151 for (i
= 0; i
< n
; i
++) {
153 printf("%3d: %-6s %3d -> %3d; "
154 "equivs: %3d, %3d; up: %3d; down: %3d; dyn: %3d\n",
155 i
, state
[f
->state
], f
->f
->cur
, f
->f
->want
,
156 INDEX(f
->eqprev
), INDEX(f
->eqnext
),
157 INDEX(f
->up
), INDEX(f
->down
), INDEX(f
->dlink
));
173 * Arguments: @mdup_fdinfo *f@ = which node to process
174 * @mdup_fdinfo **dhead, ***dtail@ = the dynamic list
176 * Returns: Zero on success, @-1@ on some OS failure.
178 * Use: Recursive depth-first traversal of the descriptor graph.
180 * On exit, the node @f@ will be in state @ST_DONE@ or
184 static int dfs(mdup_fdinfo
*f
, mdup_fdinfo
**dhead
, mdup_fdinfo
***dtail
)
192 /* --- Null pointers need no processing --- *
194 * Null pointers mark the end of descending chains.
200 /* --- Otherwise our behaviour depends on the node's state --- */
204 /* --- The standard processing, in several phases --- */
208 /* --- Mark the class as being in-progress --- */
210 DO_EQUIVS(g
, f
, { g
->state
= ST_MARK
; });
212 /* --- Ensure that the our proposed destination is clear --- *
214 * The depth-first traversal will leave the node in @ST_DONE@ or
215 * @ST_BROKEN@ afterwards; either way, its @cur@ will not be same as
218 * Note that this can move @%\emph{us}@ to @ST_BROKEN@. This is not a
219 * significant problem.
222 DO_EQUIVS(g
, f
, { if (dfs(g
->down
, dhead
, dtail
)) return (-1); });
224 /* --- Now the real work can begin --- *
226 * For each node in the class, copy the descriptor from @cur@ to
227 * @want@. Before doing this, we must move out of the way any (other)
228 * dynamic nodes whose @cur@ matches our @want@.
230 * Interestingly, this is the only point in the function where we need
231 * nontrivial error handling: if something goes wrong with one of the
232 * @dup2@ calls, we must close the descriptors made so far this pass
239 for (d
= *dhead
; d
; d
= d
->dlink
) {
240 if (d
!= f
&& d
->f
->cur
== ff
->want
) {
241 if ((fd
= dup(ff
->want
)) < 0)
243 DO_EQUIVS(dd
, d
, { dd
->f
->cur
= fd
; });
247 if (ff
->cur
== ff
->want
)
249 else if (dup2(ofd
, ff
->want
) < 0)
254 for (g
= g
->eqprev
; g
!= f
->eqprev
; g
= g
->eqprev
) {
255 if (g
->f
->want
!= g
->f
->cur
)
263 /* --- We're done --- *
265 * If the original descriptor isn't wanted by anyone we can (and must)
266 * close it. Nodes can now move to @ST_DONE@.
272 g
->f
->cur
= g
->f
->want
;
277 /* --- We have encoutered a cycle --- *
279 * The caller wants our descriptor. We therefore shunt this entire
280 * equivalence class to a new descriptor, and link it onto the dynamic
281 * list. Mark it as broken so that we don't try to do anything
282 * complicated to it again.
287 if ((fd
= dup(ofd
)) < 0)
291 g
->state
= ST_BROKEN
;
298 /* --- Nothing to be done here --- *
300 * @ST_DONE@ nodes have already been completely processed; @ST_BROKEN@
301 * nodes will be fixed up after the main traversal.
314 * Arguments: @mdup_fd *v@ = pointer to @mdup_fd@ vector
315 * @size_t n@ = size of vector
317 * Returns: Zero if successful, @-1@ on failure.
319 * Use: Rearranges file descriptors.
321 * The vector @v@ consists of a number of @mdup_fd@ structures.
322 * Each `slot' in the table represents a file. The slot's @cur@
323 * member names the current file descriptor for this file; the
324 * @want@ member is the file descriptor we want to use for it.
325 * if you want to keep a file alive but don't care which
326 * descriptor it ends up with, set @want = -1@. Several slots
327 * may specify the same @cur@ descriptor; but they all have to
328 * declare different @want@s (except that several slots may have
331 * On successful exit, the function will have rearranged the
332 * file descriptors as requested. To reflect this, the @cur@
333 * members will all be set to match the (non-@-1@) @want@
336 * If there is a failure, then some rearrangement may have been
337 * performed and some not; the @cur@ members are set to reflect
338 * which file descriptors are to be used. The old file
339 * descriptors are closed. (This is different from usual @dup@
340 * behaviour, of course, but essential for reliable error
341 * handling.) If you want to keep a particular source file
342 * descriptor open as well as make a new copy then specify two
343 * slots with the same @cur@, one with @want = cur@ and one with
344 * the desired output descriptor.
346 * This function works correctly even if the desired remappings
350 int mdup(mdup_fd
*v
, size_t n
)
354 mdup_fdinfo
*f
, *g
, *dhead
, **dtail
;
360 /* --- Allocate and initialize the table of info nodes --- *
362 * Each entry @ff@ in the caller's @v@ array will have a corresponding node
363 * @f@ in @vv@ with @f->f = ff@. Initially each node's links are null, and
364 * the node is in the @ST_READY@ state.
366 * We also initialize a list given by @dhead@ and @dtail@ containing the
367 * entries with `dynamically-assigned' descriptors -- i.e., those whose
368 * values we made up using @dup@. The list lets us detect collisions with
369 * explicitly requested descriptors and move the dynamic ones out of the
373 if ((vv
= malloc(sizeof(*vv
) * n
)) == 0)
378 for (i
= 0; i
< n
; i
++) {
382 f
->eqnext
= f
->eqprev
= 0;
386 /* --- Pass one: link the graph together --- *
388 * Once this pass is complete, the following properties will hold.
390 * * The nodes which have the same @cur@ are linked together by their
391 * @eqnext@ and @eqprev@ fields into a doubly-linked circular list
392 * representing this equivalence class.
394 * * @f->up == g@ if and only if @f->f->cur == g->f->want@. (Note that
395 * @want@ fields are unique according to our interface. We detect
396 * violations and exit with @errno == EINVAL@.)
398 * * If @f->up == g@ then there exists a @ff@ in the same equivalence
399 * class (and therefore on @f@'s @eqnext@ list) as @f@ with
403 for (i
= 0; i
< n
; i
++) {
406 f
->eqnext
= f
->eqprev
= f
;
407 for (j
= 0; j
< n
; j
++) {
411 if (f
->f
->cur
== g
->f
->cur
) {
413 g
->eqnext
= f
->eqnext
;
415 f
->eqnext
->eqprev
= g
;
419 if (g
->f
->want
== -1)
421 else if (f
->f
->want
== g
->f
->want
) {
424 } else if (f
->f
->cur
== g
->f
->want
) {
432 /* --- Pass two: handle don't-care requests --- *
434 * By the end of this pass, we have the following properties.
436 * * Every node will be marked @ST_DONE@. This is a temporary abuse of
437 * the @ST_DONE@ state which will be rectified during the next pass.
439 * * Every node with @want == -1@ will have @cur@ set to a freshly
440 * allocated file descriptor distinct from every previously open file.
443 for (i
= 0; i
< n
; i
++) {
456 if ((fd
= dup(ofd
)) < 0)
468 /* --- Pass three: restore equivalence classes and @down@ links --- *
470 * This pass re-establishes the properties from pass one. Because we've
471 * changed some @cur@ members, the equivalence classes will have changed,
472 * so we must fix up the @eqnext@ lists and @down@ links.
474 * Nodes with @want == -1@ are now finished with (modulo tweaking
475 * dynamically allocated descriptors as we process the others), so we leave
476 * them in @ST_DONE@; other nodes are restored to @ST_READY@.
479 for (i
= 0; i
< n
; i
++) {
482 if (ff
->want
== -1) {
483 f
->eqnext
->eqprev
= f
->eqprev
;
484 f
->eqprev
->eqnext
= f
->eqnext
;
485 f
->eqnext
= f
->eqprev
= f
;
492 /* --- Pass four: main depth-first traversal --- *
494 * See the description of the function @dfs@ above. After this pass, every
495 * node is in state @ST_DONE@ or @ST_BROKEN@.
498 for (i
= 0; i
< n
; i
++) {
499 if (dfs(&vv
[i
], &dhead
, &dtail
))
503 /* --- Finished --- */
511 /*----- That's all, folks -------------------------------------------------*/