1 /* Detect cycles in file tree walks.
3 Copyright (C) 2003, 2004, 2005 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. */
25 #include "cycle-check.h"
28 /* Use each of these to map a device/inode pair to an FTSENT. */
37 AD_compare (void const *x, void const *y)
39 struct Active_dir const *ax = x;
40 struct Active_dir const *ay = y;
41 return ax->ino == ay->ino
42 && ax->dev == ay->dev;
46 AD_hash (void const *x, size_t table_size)
48 struct Active_dir const *ax = x;
49 return (uintmax_t) ax->ino % table_size;
52 /* Set up the cycle-detection machinery. */
57 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
59 enum { HT_INITIAL_SIZE = 31 };
60 fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash,
62 if (! fts->fts_cycle.ht)
67 fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state);
68 if (! fts->fts_cycle.state)
70 cycle_check_init (fts->fts_cycle.state);
76 /* Enter a directory during a file tree walk. */
79 enter_dir (FTS *fts, FTSENT *ent)
81 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
83 struct stat const *st = ent->fts_statp;
84 struct Active_dir *ad = malloc (sizeof *ad);
85 struct Active_dir *ad_from_table;
94 /* See if we've already encountered this directory.
95 This can happen when following symlinks as well as
96 with a corrupted directory hierarchy. */
97 ad_from_table = hash_insert (fts->fts_cycle.ht, ad);
99 if (ad_from_table != ad)
105 /* There was an entry with matching dev/inode already in the table.
106 Record the fact that we've found a cycle. */
107 ent->fts_cycle = ad_from_table->fts_ent;
108 ent->fts_info = FTS_DC;
113 if (cycle_check (fts->fts_cycle.state, ent->fts_statp))
115 /* FIXME: setting fts_cycle like this isn't proper.
116 To do what the documentation requires, we'd have to
117 go around the cycle again and find the right entry.
118 But no callers in coreutils use the fts_cycle member. */
119 ent->fts_cycle = ent;
120 ent->fts_info = FTS_DC;
127 /* Leave a directory during a file tree walk. */
130 leave_dir (FTS *fts, FTSENT *ent)
132 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
134 struct stat const *st = ent->fts_statp;
135 struct Active_dir obj;
137 obj.dev = st->st_dev;
138 obj.ino = st->st_ino;
139 found = hash_delete (fts->fts_cycle.ht, &obj);
146 /* Free any memory used for cycle detection. */
151 if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL))
153 if (sp->fts_cycle.ht)
154 hash_free (sp->fts_cycle.ht);
157 free (sp->fts_cycle.state);