3 * Duplicate multiple files
5 * (c) 2008 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of the mLib utilities library.
12 * mLib is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * mLib is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with mLib; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
37 /*----- Data structures ---------------------------------------------------*/
39 typedef struct mdup_fdinfo {
42 /* Each @fdinfo@ structure refers to one of the caller's @fd@ structures.
46 struct mdup_fdinfo *eqnext, *eqprev;
47 /* The caller's request list can contain more than one entry with any given
48 * @cur@ descriptor. We group them together into an equivalence class,
49 * which is doubly linked using these fields.
52 struct mdup_fdinfo *up;
53 /* We require that there be at most one node with any given @want@
54 * descriptor (other than @-1@). There is therefore at most one node whose
55 * @want@ is equal to my @cur@. If such a node exists, @up@ points to it;
56 * otherwise @up@ is null.
59 struct mdup_fdinfo *down;
60 /* Obviously, @down@ links in the opposite direction from @up@. However,
61 * there may be several nodes whose @cur@ equals my @want@; therefore
62 * @down@ simply links to one of the nodes in the equivalence class.
64 * Unsurprisingly, @down@ is the direction we move during the depth-first
65 * traversal phase of the operation.
68 struct mdup_fdinfo *dlink;
69 /* Nodes with @want == -1@, and nodes where we've broken cycles, are
70 * considered `dynamic': their @cur@ has been chosen by @dup@ to be
71 * distinct from any existing descriptor, but may collide with a @want@.
72 * We check each proposed move against the list of dynamic nodes, and move
73 * them out of the way as necessary. Note that this is really a list of
74 * equivalence classes rather than single nodes.
78 /* The current state of this node. One of the @ST@ constants described
85 /* Node has not yet been processed.
89 /* Node has been reached by the depth-first traversal, but its descriptor
90 * has not yet been moved. This state is used to detect cycles using the
91 * depth-first traversal.
95 /* Node has been processed completely. We have @want == -1@ or
100 /* Node has been clobbered in order to break a cycle. The node's
101 * equivalence class has been remapped to a fresh descriptor which (we
102 * hope) is not equal to any node's @want@. All broken nodes are put on
103 * the dynamic list: if our hope turns out to be misplaced we can remap the
108 /*----- Main code ---------------------------------------------------------*/
110 /* --- @DO_EQUIVS@ --- *
112 * Perform @body@ once for each @g@ in the equivalence class of @f@.
115 #define DO_EQUIVS(g, f, body) do { \
116 mdup_fdinfo *f_ = (f), *g_ = f_; \
117 do { mdup_fdinfo *g = g_; g_ = g_->eqnext; body; } while (g_ != f_); \
122 * Arguments: @mdup_fdinfo *v@ = pointer to info vector
123 * @size_t n@ = size of vector
127 * Use: Dumps a scary-looking description of the state of @mdup@'s
140 static void PRINTF_LIKE(4, 5) IGNORABLE
141 dump(mdup_fdinfo *v, size_t n, mdup_fdinfo *dhead, const char *fmt, ...)
145 static const char *state[] = { "READY", "MARK", "DONE", "BROKEN" };
148 #define INDEX(p) ((p) ? (int)((p) - (v)) : -1)
150 /* --- Dump the items, fairly raw --- */
153 fputs("*** ", stdout);
156 for (i = 0; i < n; i++) {
158 printf("%3d: %-6s %3d -> %3d; "
159 "equivs: %3d, %3d; up: %3d; down: %3d; dyn: %3d\n",
160 i, state[f->state], f->f->cur, f->f->want,
161 INDEX(f->eqprev), INDEX(f->eqnext),
162 INDEX(f->up), INDEX(f->down), INDEX(f->dlink));
178 * Arguments: @mdup_fdinfo *f@ = which node to process
179 * @mdup_fdinfo **dhead, ***dtail@ = the dynamic list
181 * Returns: Zero on success, @-1@ on some OS failure.
183 * Use: Recursive depth-first traversal of the descriptor graph.
185 * On exit, the node @f@ will be in state @ST_DONE@ or
189 static int dfs(mdup_fdinfo *f, mdup_fdinfo **dhead, mdup_fdinfo ***dtail)
197 /* --- Null pointers need no processing --- *
199 * Null pointers mark the end of descending chains.
205 /* --- Otherwise our behaviour depends on the node's state --- */
209 /* --- The standard processing, in several phases --- */
213 /* --- Mark the class as being in-progress --- */
215 DO_EQUIVS(g, f, { g->state = ST_MARK; });
217 /* --- Ensure that the our proposed destination is clear --- *
219 * The depth-first traversal will leave the node in @ST_DONE@ or
220 * @ST_BROKEN@ afterwards; either way, its @cur@ will not be same as
223 * Note that this can move @%\emph{us}@ to @ST_BROKEN@. This is not a
224 * significant problem.
227 DO_EQUIVS(g, f, { if (dfs(g->down, dhead, dtail)) return (-1); });
229 /* --- Now the real work can begin --- *
231 * For each node in the class, copy the descriptor from @cur@ to
232 * @want@. Before doing this, we must move out of the way any (other)
233 * dynamic nodes whose @cur@ matches our @want@.
235 * Interestingly, this is the only point in the function where we need
236 * nontrivial error handling: if something goes wrong with one of the
237 * @dup2@ calls, we must close the descriptors made so far this pass
244 for (d = *dhead; d; d = d->dlink) {
245 if (d != f && d->f->cur == ff->want) {
246 if ((fd = dup(ff->want)) < 0)
248 DO_EQUIVS(dd, d, { dd->f->cur = fd; });
252 if (ff->cur == ff->want)
254 else if (dup2(ofd, ff->want) < 0)
259 for (g = g->eqprev; g != f->eqprev; g = g->eqprev) {
260 if (g->f->want != g->f->cur)
268 /* --- We're done --- *
270 * If the original descriptor isn't wanted by anyone we can (and must)
271 * close it. Nodes can now move to @ST_DONE@.
277 g->f->cur = g->f->want;
282 /* --- We have encoutered a cycle --- *
284 * The caller wants our descriptor. We therefore shunt this entire
285 * equivalence class to a new descriptor, and link it onto the dynamic
286 * list. Mark it as broken so that we don't try to do anything
287 * complicated to it again.
292 if ((fd = dup(ofd)) < 0)
296 g->state = ST_BROKEN;
303 /* --- Nothing to be done here --- *
305 * @ST_DONE@ nodes have already been completely processed; @ST_BROKEN@
306 * nodes will be fixed up after the main traversal.
319 * Arguments: @mdup_fd *v@ = pointer to @mdup_fd@ vector
320 * @size_t n@ = size of vector
322 * Returns: Zero if successful, @-1@ on failure.
324 * Use: Rearranges file descriptors.
326 * The vector @v@ consists of a number of @mdup_fd@ structures.
327 * Each `slot' in the table represents a file. The slot's @cur@
328 * member names the current file descriptor for this file; the
329 * @want@ member is the file descriptor we want to use for it.
330 * if you want to keep a file alive but don't care which
331 * descriptor it ends up with, set @want = -1@. Several slots
332 * may specify the same @cur@ descriptor; but they all have to
333 * declare different @want@s (except that several slots may have
336 * On successful exit, the function will have rearranged the
337 * file descriptors as requested. To reflect this, the @cur@
338 * members will all be set to match the (non-@-1@) @want@
341 * If there is a failure, then some rearrangement may have been
342 * performed and some not; the @cur@ members are set to reflect
343 * which file descriptors are to be used. The old file
344 * descriptors are closed. (This is different from usual @dup@
345 * behaviour, of course, but essential for reliable error
346 * handling.) If you want to keep a particular source file
347 * descriptor open as well as make a new copy then specify two
348 * slots with the same @cur@, one with @want = cur@ and one with
349 * the desired output descriptor.
351 * This function works correctly even if the desired remappings
355 int mdup(mdup_fd *v, size_t n)
359 mdup_fdinfo *f, *g, *dhead, **dtail;
365 /* --- Allocate and initialize the table of info nodes --- *
367 * Each entry @ff@ in the caller's @v@ array will have a corresponding node
368 * @f@ in @vv@ with @f->f = ff@. Initially each node's links are null, and
369 * the node is in the @ST_READY@ state.
371 * We also initialize a list given by @dhead@ and @dtail@ containing the
372 * entries with `dynamically-assigned' descriptors -- i.e., those whose
373 * values we made up using @dup@. The list lets us detect collisions with
374 * explicitly requested descriptors and move the dynamic ones out of the
378 if ((vv = malloc(sizeof(*vv) * n)) == 0)
383 for (i = 0; i < n; i++) {
387 f->eqnext = f->eqprev = 0;
391 /* --- Pass one: link the graph together --- *
393 * Once this pass is complete, the following properties will hold.
395 * * The nodes which have the same @cur@ are linked together by their
396 * @eqnext@ and @eqprev@ fields into a doubly-linked circular list
397 * representing this equivalence class.
399 * * @f->up == g@ if and only if @f->f->cur == g->f->want@. (Note that
400 * @want@ fields are unique according to our interface. We detect
401 * violations and exit with @errno == EINVAL@.)
403 * * If @f->up == g@ then there exists a @ff@ in the same equivalence
404 * class (and therefore on @f@'s @eqnext@ list) as @f@ with
408 for (i = 0; i < n; i++) {
411 f->eqnext = f->eqprev = f;
412 for (j = 0; j < n; j++) {
416 if (f->f->cur == g->f->cur) {
418 g->eqnext = f->eqnext;
420 f->eqnext->eqprev = g;
424 if (g->f->want == -1)
426 else if (f->f->want == g->f->want) {
429 } else if (f->f->cur == g->f->want) {
437 /* --- Pass two: handle don't-care requests --- *
439 * By the end of this pass, we have the following properties.
441 * * Every node will be marked @ST_DONE@. This is a temporary abuse of
442 * the @ST_DONE@ state which will be rectified during the next pass.
444 * * Every node with @want == -1@ will have @cur@ set to a freshly
445 * allocated file descriptor distinct from every previously open file.
448 for (i = 0; i < n; i++) {
461 if ((fd = dup(ofd)) < 0)
473 /* --- Pass three: restore equivalence classes and @down@ links --- *
475 * This pass re-establishes the properties from pass one. Because we've
476 * changed some @cur@ members, the equivalence classes will have changed,
477 * so we must fix up the @eqnext@ lists and @down@ links.
479 * Nodes with @want == -1@ are now finished with (modulo tweaking
480 * dynamically allocated descriptors as we process the others), so we leave
481 * them in @ST_DONE@; other nodes are restored to @ST_READY@.
484 for (i = 0; i < n; i++) {
487 if (ff->want == -1) {
488 f->eqnext->eqprev = f->eqprev;
489 f->eqprev->eqnext = f->eqnext;
490 f->eqnext = f->eqprev = f;
497 /* --- Pass four: main depth-first traversal --- *
499 * See the description of the function @dfs@ above. After this pass, every
500 * node is in state @ST_DONE@ or @ST_BROKEN@.
503 for (i = 0; i < n; i++) {
504 if (dfs(&vv[i], &dhead, &dtail))
508 /* --- Finished --- */
516 /*----- That's all, folks -------------------------------------------------*/