Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/coreutils/src/gnulib/lib/cycle-check.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | /* help detect directory cycles efficiently | - | ||||||||||||||||||
2 | - | |||||||||||||||||||
3 | Copyright (C) 2003-2006, 2009-2018 Free Software Foundation, Inc. | - | ||||||||||||||||||
4 | - | |||||||||||||||||||
5 | This program is free software: you can redistribute it and/or modify | - | ||||||||||||||||||
6 | it under the terms of the GNU General Public License as published by | - | ||||||||||||||||||
7 | the Free Software Foundation; either version 3 of the License, or | - | ||||||||||||||||||
8 | (at your option) any later version. | - | ||||||||||||||||||
9 | - | |||||||||||||||||||
10 | This program is distributed in the hope that it will be useful, | - | ||||||||||||||||||
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | - | ||||||||||||||||||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | - | ||||||||||||||||||
13 | GNU General Public License for more details. | - | ||||||||||||||||||
14 | - | |||||||||||||||||||
15 | You should have received a copy of the GNU General Public License | - | ||||||||||||||||||
16 | along with this program. If not, see <https://www.gnu.org/licenses/>. */ | - | ||||||||||||||||||
17 | - | |||||||||||||||||||
18 | /* Written by Jim Meyering */ | - | ||||||||||||||||||
19 | - | |||||||||||||||||||
20 | #include <config.h> | - | ||||||||||||||||||
21 | - | |||||||||||||||||||
22 | #include "cycle-check.h" | - | ||||||||||||||||||
23 | - | |||||||||||||||||||
24 | #include <sys/types.h> | - | ||||||||||||||||||
25 | #include <sys/stat.h> | - | ||||||||||||||||||
26 | #include <stdio.h> | - | ||||||||||||||||||
27 | #include <stdlib.h> | - | ||||||||||||||||||
28 | #include <stdbool.h> | - | ||||||||||||||||||
29 | - | |||||||||||||||||||
30 | #include "assure.h" | - | ||||||||||||||||||
31 | - | |||||||||||||||||||
32 | #define CC_MAGIC 9827862 | - | ||||||||||||||||||
33 | - | |||||||||||||||||||
34 | /* Return true if I is a power of 2, or is zero. */ | - | ||||||||||||||||||
35 | - | |||||||||||||||||||
36 | static bool | - | ||||||||||||||||||
37 | is_zero_or_power_of_two (uintmax_t i) | - | ||||||||||||||||||
38 | { | - | ||||||||||||||||||
39 | return (i & (i - 1)) == 0; executed 100755 times by 6 tests: return (i & (i - 1)) == 0; Executed by:
| 100755 | ||||||||||||||||||
40 | } | - | ||||||||||||||||||
41 | - | |||||||||||||||||||
42 | void | - | ||||||||||||||||||
43 | cycle_check_init (struct cycle_check_state *state) | - | ||||||||||||||||||
44 | { | - | ||||||||||||||||||
45 | state->chdir_counter = 0; | - | ||||||||||||||||||
46 | state->magic = CC_MAGIC; | - | ||||||||||||||||||
47 | } executed 14208 times by 6 tests: end of block Executed by:
| 14208 | ||||||||||||||||||
48 | - | |||||||||||||||||||
49 | /* In traversing a directory hierarchy, call this function once for each | - | ||||||||||||||||||
50 | descending chdir call, with SB corresponding to the chdir operand. | - | ||||||||||||||||||
51 | If SB corresponds to a directory that has already been seen, | - | ||||||||||||||||||
52 | return true to indicate that there is a directory cycle. | - | ||||||||||||||||||
53 | Note that this is done "lazily", which means that some of | - | ||||||||||||||||||
54 | the directories in the cycle may be processed twice before | - | ||||||||||||||||||
55 | the cycle is detected. */ | - | ||||||||||||||||||
56 | - | |||||||||||||||||||
57 | bool | - | ||||||||||||||||||
58 | cycle_check (struct cycle_check_state *state, struct stat const *sb) | - | ||||||||||||||||||
59 | { | - | ||||||||||||||||||
60 | assure (state->magic == CC_MAGIC); | - | ||||||||||||||||||
61 | - | |||||||||||||||||||
62 | /* If the current directory ever happens to be the same | - | ||||||||||||||||||
63 | as the one we last recorded for the cycle detection, | - | ||||||||||||||||||
64 | then it's obviously part of a cycle. */ | - | ||||||||||||||||||
65 | if (state->chdir_counter && SAME_INODE (*sb, state->dev_ino))
| 0-95864 | ||||||||||||||||||
66 | return true; never executed: return 1 ; | 0 | ||||||||||||||||||
67 | - | |||||||||||||||||||
68 | /* If the number of "descending" chdir calls is a power of two, | - | ||||||||||||||||||
69 | record the dev/ino of the current directory. */ | - | ||||||||||||||||||
70 | if (is_zero_or_power_of_two (++(state->chdir_counter)))
| 5269-95486 | ||||||||||||||||||
71 | { | - | ||||||||||||||||||
72 | /* On all architectures that we know about, if the counter | - | ||||||||||||||||||
73 | overflows then there is a directory cycle here somewhere, | - | ||||||||||||||||||
74 | even if we haven't detected it yet. Typically this happens | - | ||||||||||||||||||
75 | only after the counter is incremented 2**64 times, so it's a | - | ||||||||||||||||||
76 | fairly theoretical point. */ | - | ||||||||||||||||||
77 | if (state->chdir_counter == 0)
| 0-5269 | ||||||||||||||||||
78 | return true; never executed: return 1 ; | 0 | ||||||||||||||||||
79 | - | |||||||||||||||||||
80 | state->dev_ino.st_dev = sb->st_dev; | - | ||||||||||||||||||
81 | state->dev_ino.st_ino = sb->st_ino; | - | ||||||||||||||||||
82 | } executed 5269 times by 6 tests: end of block Executed by:
| 5269 | ||||||||||||||||||
83 | - | |||||||||||||||||||
84 | return false; executed 100755 times by 6 tests: return 0 ; Executed by:
| 100755 | ||||||||||||||||||
85 | } | - | ||||||||||||||||||
Source code | Switch to Preprocessed file |