Mercurial > hg > octave-kai > gnulib-hg
annotate lib/fts-cycle.c @ 6163:bba2240c9260
* iconvme.h: Add prototype for iconv_alloc.
| author | Simon Josefsson <simon@josefsson.org> |
|---|---|
| date | Tue, 30 Aug 2005 07:38:53 +0000 |
| parents | 14b1cca449ad |
| children | 716071856296 |
| rev | line source |
|---|---|
| 5872 | 1 /* Detect cycles in file tree walks. |
| 2 | |
| 3 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. | |
| 4 | |
| 5 Written by Jim Meyering. | |
| 6 | |
| 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) | |
| 10 any later version. | |
| 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 | |
| 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. */ | |
| 20 | |
| 21 #include "cycle-check.h" | |
| 22 #include "hash.h" | |
| 23 | |
| 5907 | 24 /* Use each of these to map a device/inode pair to an FTSENT. */ |
| 5872 | 25 struct Active_dir |
| 26 { | |
| 27 dev_t dev; | |
| 28 ino_t ino; | |
| 29 FTSENT *fts_ent; | |
| 30 }; | |
| 31 | |
| 32 static bool | |
| 33 AD_compare (void const *x, void const *y) | |
| 34 { | |
| 35 struct Active_dir const *ax = x; | |
| 36 struct Active_dir const *ay = y; | |
| 37 return ax->ino == ay->ino | |
| 38 && ax->dev == ay->dev; | |
| 39 } | |
| 40 | |
| 41 static size_t | |
| 42 AD_hash (void const *x, size_t table_size) | |
| 43 { | |
| 44 struct Active_dir const *ax = x; | |
| 45 return (uintmax_t) ax->ino % table_size; | |
| 46 } | |
| 47 | |
| 48 /* Set up the cycle-detection machinery. */ | |
| 49 | |
| 50 static bool | |
| 51 setup_dir (FTS *fts) | |
| 52 { | |
|
6036
14b1cca449ad
(setup_dir, enter_dir, leave_dir, free_dir):
Jim Meyering <jim@meyering.net>
parents:
5907
diff
changeset
|
53 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL)) |
| 5872 | 54 { |
| 55 enum { HT_INITIAL_SIZE = 31 }; | |
| 56 fts->fts_cycle.ht = hash_initialize (HT_INITIAL_SIZE, NULL, AD_hash, | |
| 57 AD_compare, free); | |
| 58 if (! fts->fts_cycle.ht) | |
| 59 return false; | |
| 60 } | |
| 61 else | |
| 62 { | |
| 63 fts->fts_cycle.state = malloc (sizeof *fts->fts_cycle.state); | |
| 64 if (! fts->fts_cycle.state) | |
| 65 return false; | |
| 66 cycle_check_init (fts->fts_cycle.state); | |
| 67 } | |
| 68 | |
| 69 return true; | |
| 70 } | |
| 71 | |
| 72 /* Enter a directory during a file tree walk. */ | |
| 73 | |
| 74 static bool | |
| 75 enter_dir (FTS *fts, FTSENT *ent) | |
| 76 { | |
|
6036
14b1cca449ad
(setup_dir, enter_dir, leave_dir, free_dir):
Jim Meyering <jim@meyering.net>
parents:
5907
diff
changeset
|
77 if (fts->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL)) |
| 5872 | 78 { |
| 79 struct stat const *st = ent->fts_statp; | |
| 80 struct Active_dir *ad = malloc (sizeof *ad); | |
| 81 struct Active_dir *ad_from_table; | |
| 82 | |
| 83 if (!ad) | |
| 84 return false; | |
| 85 | |
| 86 ad->dev = st->st_dev; | |
| 87 ad->ino = st->st_ino; | |
| 88 ad->fts_ent = ent; | |
| 89 | |
| 90 /* See if we've already encountered this directory. | |
| 91 This can happen when following symlinks as well as | |
| 92 with a corrupted directory hierarchy. */ | |
| 93 ad_from_table = hash_insert (fts->fts_cycle.ht, ad); | |
| 94 | |
| 95 if (ad_from_table != ad) | |
| 96 { | |
| 97 free (ad); | |
| 98 if (!ad_from_table) | |
| 99 return false; | |
| 100 | |
| 101 /* There was an entry with matching dev/inode already in the table. | |
| 102 Record the fact that we've found a cycle. */ | |
| 103 ent->fts_cycle = ad_from_table->fts_ent; | |
| 104 ent->fts_info = FTS_DC; | |
| 105 } | |
| 106 } | |
| 107 else | |
| 108 { | |
| 109 if (cycle_check (fts->fts_cycle.state, ent->fts_statp)) | |
| 110 { | |
| 111 /* FIXME: setting fts_cycle like this isn't proper. | |
| 112 To do what the documentation requires, we'd have to | |
| 113 go around the cycle again and find the right entry. | |
| 114 But no callers in coreutils use the fts_cycle member. */ | |
| 115 ent->fts_cycle = ent; | |
| 116 ent->fts_info = FTS_DC; | |
| 117 } | |
| 118 } | |
| 119 | |
| 120 return true; | |
| 121 } | |
| 122 | |
| 123 /* Leave a directory during a file tree walk. */ | |
| 124 | |
| 125 static void | |
| 126 leave_dir (FTS *fts, FTSENT *ent) | |
| 127 { | |
|
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 stat const *st = ent->fts_statp; | |
| 131 struct Active_dir obj; | |
| 132 void *found; | |
| 133 obj.dev = st->st_dev; | |
| 134 obj.ino = st->st_ino; | |
| 135 found = hash_delete (fts->fts_cycle.ht, &obj); | |
| 136 if (!found) | |
| 137 abort (); | |
| 138 free (found); | |
| 139 } | |
| 140 } | |
| 141 | |
| 142 /* Free any memory used for cycle detection. */ | |
| 143 | |
| 144 static void | |
| 145 free_dir (FTS *sp) | |
| 146 { | |
|
6036
14b1cca449ad
(setup_dir, enter_dir, leave_dir, free_dir):
Jim Meyering <jim@meyering.net>
parents:
5907
diff
changeset
|
147 if (sp->fts_options & (FTS_TIGHT_CYCLE_CHECK | FTS_LOGICAL)) |
| 5872 | 148 { |
| 149 if (sp->fts_cycle.ht) | |
| 150 hash_free (sp->fts_cycle.ht); | |
| 151 } | |
| 152 else | |
| 153 free (sp->fts_cycle.state); | |
| 154 } |