[Bug-gnulib] new module cycle-check imported from coreutils; stdbool dependency?

[Paul Eggert]

I installed the following new module from coreutils.

This module doesn't list 'stdbool' as an explicit dependency, even
though it uses <stdbool.h>.  I started to add that dependency, but
it required adding a new file and I thought "Wait a minute! If
someone is building an app  that requires C99, they won't need
the stdbool module."

I'm starting to think that we should remove the stdbool dependency
even on modules that have it already.  It is a bit of a pain to
maintain the dependency here, and apps generally get stdbool
themselves anyway.

2004-08-04  Paul Eggert  <address@hidden>

        * lib/cycle-check.c, lib/cycle-check.h, lib/dev-ino.h,
        modules/cycle-check: New files.

--- /dev/null   2003-03-18 13:55:57 -0800
+++ lib/cycle-check.c   2004-08-04 23:12:59 -0700
@@ -0,0 +1,94 @@
+/* help detect directory cycles efficiently
+
+   Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+
+   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; see the file COPYING.
+   If not, write to the Free Software Foundation,
+   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Written by Jim Meyering */
+
+#if HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <stdio.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <stdbool.h>
+
+#include "cycle-check.h"
+#include "xalloc.h"
+
+#define SAME_INODE(Stat_buf_1, Stat_buf_2) \
+  ((Stat_buf_1).st_ino == (Stat_buf_2).st_ino \
+   && (Stat_buf_1).st_dev == (Stat_buf_2).st_dev)
+
+#define CC_MAGIC 9827862
+
+/* Return true if I is a power of 2, or is zero.  */
+
+static inline bool
+is_zero_or_power_of_two (uintmax_t i)
+{
+  return (i & (i - 1)) == 0;
+}
+
+void
+cycle_check_init (struct cycle_check_state *state)
+{
+  state->chdir_counter = 0;
+  state->magic = CC_MAGIC;
+}
+
+/* In traversing a directory hierarchy, call this function once for each
+   descending chdir call, with SB corresponding to the chdir operand.
+   If SB corresponds to a directory that has already been seen,
+   return true to indicate that there is a directory cycle.
+   Note that this is done `lazily', which means that some of
+   the directories in the cycle may be processed twice before
+   the cycle is detected.  */
+
+bool
+cycle_check (struct cycle_check_state *state, struct stat const *sb)
+{
+  assert (state->magic == CC_MAGIC);
+
+  /* If the current directory ever happens to be the same
+     as the one we last recorded for the cycle detection,
+     then it's obviously part of a cycle.  */
+  if (state->chdir_counter && SAME_INODE (*sb, state->dev_ino))
+    return true;
+
+  /* If the number of `descending' chdir calls is a power of two,
+     record the dev/ino of the current directory.  */
+  if (is_zero_or_power_of_two (++(state->chdir_counter)))
+    {
+      /* On all architectures that we know about, if the counter
+        overflows then there is a directory cycle here somewhere,
+        even if we haven't detected it yet.  Typically this happens
+        only after the counter is incremented 2**64 times, so it's a
+        fairly theoretical point.  */
+      if (state->chdir_counter == 0)
+       return true;
+
+      state->dev_ino.st_dev = sb->st_dev;
+      state->dev_ino.st_ino = sb->st_ino;
+    }
+
+  return false;
+}
--- /dev/null   2003-03-18 13:55:57 -0800
+++ lib/cycle-check.h   2004-08-05 16:43:21 -0700
@@ -0,0 +1,44 @@
+/* help detect directory cycles efficiently
+
+   Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+
+   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; see the file COPYING.
+   If not, write to the Free Software Foundation,
+   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Written by Jim Meyering */
+
+#ifndef CYCLE_CHECK_H
+# define CYCLE_CHECK_H 1
+
+# if HAVE_INTTYPES_H
+#  include <inttypes.h>
+# endif
+# if HAVE_STDINT_H
+#  include <stdint.h>
+# endif
+# include <stdbool.h>
+# include "dev-ino.h"
+
+struct cycle_check_state
+{
+  struct dev_ino dev_ino;
+  uintmax_t chdir_counter;
+  int magic;
+};
+
+void cycle_check_init (struct cycle_check_state *state);
+bool cycle_check (struct cycle_check_state *state, struct stat const *sb);
+
+#endif
--- /dev/null   2003-03-18 13:55:57 -0800
+++ lib/dev-ino.h       2004-08-04 23:13:43 -0700
@@ -0,0 +1,13 @@
+#ifndef DEV_INO_H
+# define DEV_INO_H 1
+
+# include <sys/types.h>
+# include <sys/stat.h>
+
+struct dev_ino
+{
+  ino_t st_ino;
+  dev_t st_dev;
+};
+
+#endif
--- /dev/null   2003-03-18 13:55:57 -0800
+++ modules/cycle-check 2004-08-05 16:48:59 -0700
@@ -0,0 +1,21 @@
+Description:
+help detect directory cycles efficiently
+
+Files:
+lib/cycle-check.c
+lib/cycle-check.h
+lib/dev-ino.h
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += cycle-check.c cycle-check.h dev-ino.h
+
+Include:
+"cycle-check.h"
+
+Maintainer:
+Jim Meyering
+