Mercurial > gnulib
annotate lib/fts-cycle.c @ 40057:b06060465f09
maint: Run 'make update-copyright'
| author | Paul Eggert <eggert@cs.ucla.edu> |
|---|---|
| date | Tue, 01 Jan 2019 00:25:11 +0100 |
| parents | 10eb9086bea0 |
| children |
| rev | line source |
|---|---|
| 5872 | 1 /* Detect cycles in file tree walks. |
| 2 | |
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
19484
diff
changeset
|
3 Copyright (C) 2003-2006, 2009-2019 Free Software Foundation, Inc. |
| 5872 | 4 |
| 5 Written by Jim Meyering. | |
| 6 | |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
7459
diff
changeset
|
7 This program is free software: you can redistribute it and/or modify |
| 5872 | 8 it under the terms of the GNU General Public License as published by |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
7459
diff
changeset
|
9 the Free Software Foundation; either version 3 of the License, or |
|
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
7459
diff
changeset
|
10 (at your option) any later version. |
| 5872 | 11 |
| 12 This program is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 19190 | 18 along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
| 5872 | 19 |
| 20 #include "cycle-check.h" | |
| 21 #include "hash.h" | |
| 22 | |
| 5907 | 23 /* Use each of these to map a device/inode pair to an FTSENT. */ |
| 5872 | 24 struct Active_dir |
| 25 { | |
| 26 dev_t dev; | |
| 27 ino_t ino; | |
| 28 FTSENT *fts_ent; | |
| 29 }; | |
| 30 | |
| 31 static bool | |
| 32 AD_compare (void const *x, void const *y) | |
| 33 { | |
| 34 struct Active_dir const *ax = x; | |
| 35 struct Active_dir const *ay = y; | |
| 36 return ax->ino == ay->ino | |
| 37 && ax->dev == ay->dev; | |
| 38 } | |
| 39 | |
| 40 static size_t | |
| 41 AD_hash (void const *x, size_t table_size) | |
| 42 { | |
| 43 struct Active_dir const *ax = x; | |
| 44 return (uintmax_t) ax->ino % table_size; | |
| 45 } | |
| 46 | |
| 47 /* Set up the cycle-detection machinery. */ | |
| 48 | |
| 49 static bool | |
| 50 setup_dir (FTS *fts) | |
| 51 { | |
|
6036
14b1cca449ad
(setup_dir, enter_dir, leave_dir, free_dir):
Jim Meyering <jim@meyering.net>
parents:
5907
diff
changeset
|
52 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL)) |
| 5872 | 53 { |
| 54 enum { HT_INITIAL_SIZE = 31 }; | |
| 55 fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
56 AD_compare, free); |
| 5872 | 57 if (! fts->fts_cycle.ht) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
58 return false; |
| 5872 | 59 } |
| 60 else | |
| 61 { | |
| 62 fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state); | |
| 63 if (! fts->fts_cycle.state) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
64 return false; |
| 5872 | 65 cycle_check_init (fts->fts_cycle.state); |
| 66 } | |
| 67 | |
| 68 return true; | |
| 69 } | |
| 70 | |
| 71 /* Enter a directory during a file tree walk. */ | |
| 72 | |
| 73 static bool | |
| 74 enter_dir (FTS *fts, FTSENT *ent) | |
| 75 { | |
|
6036
14b1cca449ad
(setup_dir, enter_dir, leave_dir, free_dir):
Jim Meyering <jim@meyering.net>
parents:
5907
diff
changeset
|
76 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL)) |
| 5872 | 77 { |
| 78 struct stat const *st = ent->fts_statp; | |
| 79 struct Active_dir *ad = malloc (sizeof *ad); | |
| 80 struct Active_dir *ad_from_table; | |
| 81 | |
| 82 if (!ad) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
83 return false; |
| 5872 | 84 |
| 85 ad->dev = st->st_dev; | |
| 86 ad->ino = st->st_ino; | |
| 87 ad->fts_ent = ent; | |
| 88 | |
| 89 /* See if we've already encountered this directory. | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
90 This can happen when following symlinks as well as |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
91 with a corrupted directory hierarchy. */ |
| 5872 | 92 ad_from_table = hash_insert (fts->fts_cycle.ht, ad); |
| 93 | |
| 94 if (ad_from_table != ad) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
95 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
96 free (ad); |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
97 if (!ad_from_table) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
98 return false; |
| 5872 | 99 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
100 /* There was an entry with matching dev/inode already in the table. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
101 Record the fact that we've found a cycle. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
102 ent->fts_cycle = ad_from_table->fts_ent; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
103 ent->fts_info = FTS_DC; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
104 } |
| 5872 | 105 } |
| 106 else | |
| 107 { | |
| 108 if (cycle_check (fts->fts_cycle.state, ent->fts_statp)) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
109 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
110 /* FIXME: setting fts_cycle like this isn't proper. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
111 To do what the documentation requires, we'd have to |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
112 go around the cycle again and find the right entry. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
113 But no callers in coreutils use the fts_cycle member. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
114 ent->fts_cycle = ent; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
115 ent->fts_info = FTS_DC; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
116 } |
| 5872 | 117 } |
| 118 | |
| 119 return true; | |
| 120 } | |
| 121 | |
| 122 /* Leave a directory during a file tree walk. */ | |
| 123 | |
| 124 static void | |
| 125 leave_dir (FTS *fts, FTSENT *ent) | |
| 126 { | |
| 6912 | 127 struct stat const *st = ent->fts_statp; |
|
6036
14b1cca449ad
(setup_dir, enter_dir, leave_dir, free_dir):
Jim Meyering <jim@meyering.net>
parents:
5907
diff
changeset
|
128 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL)) |
| 5872 | 129 { |
| 130 struct Active_dir obj; | |
| 131 void *found; | |
| 132 obj.dev = st->st_dev; | |
| 133 obj.ino = st->st_ino; | |
| 134 found = hash_delete (fts->fts_cycle.ht, &obj); | |
| 135 if (!found) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
136 abort (); |
| 5872 | 137 free (found); |
| 138 } | |
| 6912 | 139 else |
| 140 { | |
| 141 FTSENT *parent = ent->fts_parent; | |
|
7459
ed1c08123d81
* fts-cycle.c (leave_dir): When "leaving" a top level directory due
Jim Meyering <jim@meyering.net>
parents:
7455
diff
changeset
|
142 if (parent != NULL && 0 <= parent->fts_level) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
143 CYCLE_CHECK_REFLECT_CHDIR_UP (fts->fts_cycle.state, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
144 *(parent->fts_statp), *st); |
| 6912 | 145 } |
| 5872 | 146 } |
| 147 | |
| 148 /* Free any memory used for cycle detection. */ | |
| 149 | |
| 150 static void | |
| 151 free_dir (FTS *sp) | |
| 152 { | |
|
6036
14b1cca449ad
(setup_dir, enter_dir, leave_dir, free_dir):
Jim Meyering <jim@meyering.net>
parents:
5907
diff
changeset
|
153 if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL)) |
| 5872 | 154 { |
| 155 if (sp->fts_cycle.ht) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
156 hash_free (sp->fts_cycle.ht); |
| 5872 | 157 } |
| 158 else | |
| 159 free (sp->fts_cycle.state); | |
| 160 } |