1 /* Detect cycles in file tree walks.
3 Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
5 Written by Jim Meyering.
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
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.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
23 #include "cycle-check.h"
26 /* Use each of these to map a device/inode pair to an FTSENT. */
35 AD_compare (void const *x, void const *y)
37 struct Active_dir const *ax = x;
38 struct Active_dir const *ay = y;
39 return ax->ino == ay->ino
40 && ax->dev == ay->dev;
44 AD_hash (void const *x, size_t table_size)
46 struct Active_dir const *ax = x;
47 return (uintmax_t) ax->ino % table_size;
50 /* Set up the cycle-detection machinery. */
55 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
57 enum { HT_INITIAL_SIZE = 31 };
58 fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash,
60 if (! fts->fts_cycle.ht)
65 fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state);
66 if (! fts->fts_cycle.state)
68 cycle_check_init (fts->fts_cycle.state);
74 /* Enter a directory during a file tree walk. */
77 enter_dir (FTS *fts, FTSENT *ent)
79 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
81 struct stat const *st = ent->fts_statp;
82 struct Active_dir *ad = malloc (sizeof *ad);
83 struct Active_dir *ad_from_table;
92 /* See if we've already encountered this directory.
93 This can happen when following symlinks as well as
94 with a corrupted directory hierarchy. */
95 ad_from_table = hash_insert (fts->fts_cycle.ht, ad);
97 if (ad_from_table != ad)
103 /* There was an entry with matching dev/inode already in the table.
104 Record the fact that we've found a cycle. */
105 ent->fts_cycle = ad_from_table->fts_ent;
106 ent->fts_info = FTS_DC;
111 if (cycle_check (fts->fts_cycle.state, ent->fts_statp))
113 /* FIXME: setting fts_cycle like this isn't proper.
114 To do what the documentation requires, we'd have to
115 go around the cycle again and find the right entry.
116 But no callers in coreutils use the fts_cycle member. */
117 ent->fts_cycle = ent;
118 ent->fts_info = FTS_DC;
125 /* Leave a directory during a file tree walk. */
128 leave_dir (FTS *fts, FTSENT *ent)
130 struct stat const *st = ent->fts_statp;
131 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
133 struct Active_dir obj;
135 obj.dev = st->st_dev;
136 obj.ino = st->st_ino;
137 found = hash_delete (fts->fts_cycle.ht, &obj);
144 FTSENT *parent = ent->fts_parent;
146 CYCLE_CHECK_REFLECT_CHDIR_UP (fts->fts_cycle.state,
147 *(parent->fts_statp), *st);
151 /* Free any memory used for cycle detection. */
156 if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
158 if (sp->fts_cycle.ht)
159 hash_free (sp->fts_cycle.ht);
162 free (sp->fts_cycle.state);