From 42aab6b2ae52fe33588bc91e857d0ae2dfa02a5b Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Fri, 20 May 2005 22:32:50 +0000 Subject: New file, containing GPL'ed code migrated out of fts.c, with the following changes: (setup_dir, free_dir): New functions. (enter_dir): Now returns bool. Return true if successful, false if memory exhausted. All callers changed. Do not bother partly cleaning up on memory allocation failure; that is free_dir's job. However, free ad if hash_insert fails, to avoid memory leak. (enter_dir, leave_dir): Accommodate change to FTS by inspecting fts->fts_options to see which union member to use. --- lib/fts-cycle.c | 154 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 154 insertions(+) create mode 100644 lib/fts-cycle.c (limited to 'lib/fts-cycle.c') diff --git a/lib/fts-cycle.c b/lib/fts-cycle.c new file mode 100644 index 000000000..a0310c2e5 --- /dev/null +++ b/lib/fts-cycle.c @@ -0,0 +1,154 @@ +/* Detect cycles in file tree walks. + + Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. + + Written by Jim Meyering. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software Foundation, + Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + +#include "cycle-check.h" +#include "hash.h" + +/* Use these each of these to map a device/inode pair to an FTSENT. */ +struct Active_dir +{ + dev_t dev; + ino_t ino; + FTSENT *fts_ent; +}; + +static bool +AD_compare (void const *x, void const *y) +{ + struct Active_dir const *ax = x; + struct Active_dir const *ay = y; + return ax->ino == ay->ino + && ax->dev == ay->dev; +} + +static size_t +AD_hash (void const *x, size_t table_size) +{ + struct Active_dir const *ax = x; + return (uintmax_t) ax->ino % table_size; +} + +/* Set up the cycle-detection machinery. */ + +static bool +setup_dir (FTS *fts) +{ + if (fts->fts_options & FTS_TIGHT_CYCLE_CHECK) + { + enum { HT_INITIAL_SIZE = 31 }; + fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash, + AD_compare, free); + if (! fts->fts_cycle.ht) + return false; + } + else + { + fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state); + if (! fts->fts_cycle.state) + return false; + cycle_check_init (fts->fts_cycle.state); + } + + return true; +} + +/* Enter a directory during a file tree walk. */ + +static bool +enter_dir (FTS *fts, FTSENT *ent) +{ + if (fts->fts_options & FTS_TIGHT_CYCLE_CHECK) + { + struct stat const *st = ent->fts_statp; + struct Active_dir *ad = malloc (sizeof *ad); + struct Active_dir *ad_from_table; + + if (!ad) + return false; + + ad->dev = st->st_dev; + ad->ino = st->st_ino; + ad->fts_ent = ent; + + /* See if we've already encountered this directory. + This can happen when following symlinks as well as + with a corrupted directory hierarchy. */ + ad_from_table = hash_insert (fts->fts_cycle.ht, ad); + + if (ad_from_table != ad) + { + free (ad); + if (!ad_from_table) + return false; + + /* There was an entry with matching dev/inode already in the table. + Record the fact that we've found a cycle. */ + ent->fts_cycle = ad_from_table->fts_ent; + ent->fts_info = FTS_DC; + } + } + else + { + if (cycle_check (fts->fts_cycle.state, ent->fts_statp)) + { + /* FIXME: setting fts_cycle like this isn't proper. + To do what the documentation requires, we'd have to + go around the cycle again and find the right entry. + But no callers in coreutils use the fts_cycle member. */ + ent->fts_cycle = ent; + ent->fts_info = FTS_DC; + } + } + + return true; +} + +/* Leave a directory during a file tree walk. */ + +static void +leave_dir (FTS *fts, FTSENT *ent) +{ + if (fts->fts_options & FTS_TIGHT_CYCLE_CHECK) + { + struct stat const *st = ent->fts_statp; + struct Active_dir obj; + void *found; + obj.dev = st->st_dev; + obj.ino = st->st_ino; + found = hash_delete (fts->fts_cycle.ht, &obj); + if (!found) + abort (); + free (found); + } +} + +/* Free any memory used for cycle detection. */ + +static void +free_dir (FTS *sp) +{ + if (sp->fts_options & FTS_TIGHT_CYCLE_CHECK) + { + if (sp->fts_cycle.ht) + hash_free (sp->fts_cycle.ht); + } + else + free (sp->fts_cycle.state); +} -- cgit v1.2.3-54-g00ecf