contrib/cvs-1.12/lib/cycle-check.c

   1 /* help detect directory cycles efficiently
   2
   3    Copyright (C) 2003, 2004, 2005 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 2, or (at your option)
   8    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; see the file COPYING.
  17    If not, write to the Free Software Foundation,
  18    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 /* Written by Jim Meyering */
  21
  22 #ifdef HAVE_CONFIG_H
  23 # include <config.h>
  24 #endif
  25
  26 #include <sys/types.h>
  27 #include <sys/stat.h>
  28 #include <stdio.h>
  29 #include <assert.h>
  30 #include <stdlib.h>
  31
  32 #include <stdbool.h>
  33
  34 #include "cycle-check.h"
  35
  36 #define SAME_INODE(Stat_buf_1, Stat_buf_2) \
  37   ((Stat_buf_1).st_ino == (Stat_buf_2).st_ino \
  38    && (Stat_buf_1).st_dev == (Stat_buf_2).st_dev)
  39
  40 #define CC_MAGIC 9827862
  41
  42 /* Return true if I is a power of 2, or is zero.  */
  43
  44 static inline bool
  45 is_zero_or_power_of_two (uintmax_t i)
  46 {
  47   return (i & (i - 1)) == 0;
  48 }
  49
  50 void
  51 cycle_check_init (struct cycle_check_state *state)
  52 {
  53   state->chdir_counter = 0;
  54   state->magic = CC_MAGIC;
  55 }
  56
  57 /* In traversing a directory hierarchy, call this function once for each
  58    descending chdir call, with SB corresponding to the chdir operand.
  59    If SB corresponds to a directory that has already been seen,
  60    return true to indicate that there is a directory cycle.
  61    Note that this is done `lazily', which means that some of
  62    the directories in the cycle may be processed twice before
  63    the cycle is detected.  */
  64
  65 bool
  66 cycle_check (struct cycle_check_state *state, struct stat const *sb)
  67 {
  68   assert (state->magic == CC_MAGIC);
  69
  70   /* If the current directory ever happens to be the same
  71      as the one we last recorded for the cycle detection,
  72      then it's obviously part of a cycle.  */
  73   if (state->chdir_counter && SAME_INODE (*sb, state->dev_ino))
  74     return true;
  75
  76   /* If the number of `descending' chdir calls is a power of two,
  77      record the dev/ino of the current directory.  */
  78   if (is_zero_or_power_of_two (++(state->chdir_counter)))
  79     {
  80       /* On all architectures that we know about, if the counter
  81          overflows then there is a directory cycle here somewhere,
  82          even if we haven't detected it yet.  Typically this happens
  83          only after the counter is incremented 2**64 times, so it's a
  84          fairly theoretical point.  */
  85       if (state->chdir_counter == 0)
  86         return true;
  87
  88       state->dev_ino.st_dev = sb->st_dev;
  89       state->dev_ino.st_ino = sb->st_ino;
  90     }
  91
  92   return false;
  93 }