Mercurial > hg > octave-shane > gnulib-hg
annotate lib/fts-cycle.c @ 17255:d81be792518a
update from texinfo
author | Karl Berry <karl@freefriends.org> |
---|---|
date | Tue, 01 Jan 2013 15:51:49 -0800 |
parents | e542fd46ad6f |
children | 344018b6e5d7 |
rev | line source |
---|---|
5872 | 1 /* Detect cycles in file tree walks. |
2 | |
17249
e542fd46ad6f
maint: update all copyright year number ranges
Eric Blake <eblake@redhat.com>
parents:
16201
diff
changeset
|
3 Copyright (C) 2003-2006, 2009-2013 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 | |
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
7459
diff
changeset
|
18 along with this program. If not, see <http://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 } |