/*

  File: walk_tree.c

  Copyright (C) 2007 Andreas Gruenbacher <a.gruenbacher@computer.org>

  This program is free software; you can redistribute it and/or modify it under

  the terms of the GNU Lesser General Public License as published by the

  Free Software Foundation; either version 2.1 of the License, 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 Lesser General Public

  License for more details.

  You should have received a copy of the GNU Lesser General Public

  License along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include "config.h"

#include <sys/types.h>

#include <sys/stat.h>

#include <unistd.h>

#include <sys/time.h>

#include <sys/resource.h>

#include <dirent.h>

#include <stdio.h>

#include <string.h>

#include <errno.h>

#include "walk_tree.h"

struct entry_handle {

	struct entry_handle *prev, *next;

	dev_t dev;

	ino_t ino;

	DIR *stream;

	long pos;

};

static struct entry_handle head = {

	.next = &head,

	.prev = &head,

	/* The other fields are unused. */

};

static struct entry_handle *closed = &head;

static unsigned int num_dir_handles;

static int walk_tree_visited(dev_t dev, ino_t ino)

{

	struct entry_handle *i;

	for (i = head.next; i != &head; i = i->next)

		if (i->dev == dev && i->ino == ino)

			return 1;

	return 0;

}

static int walk_tree_rec(const char *path, int walk_flags,

			 int (*func)(const char *, const struct stat *, int,

				     void *), void *arg, int depth)

{

	int follow_symlinks = (walk_flags & WALK_TREE_LOGICAL) ||

			      ((walk_flags & WALK_TREE_DEREFERENCE) &&

			       !(walk_flags & WALK_TREE_PHYSICAL) &&

			       depth == 0);

	int have_dir_stat = 0, flags = walk_flags, err;

	struct entry_handle dir;

	struct stat st;

	/*

	 * If (walk_flags & WALK_TREE_PHYSICAL), do not traverse symlinks.

	 * If (walk_flags & WALK_TREE_LOGICAL), traverse all symlinks.

	 * Otherwise, traverse only top-level symlinks.

	 */

	if (depth == 0)

		flags |= WALK_TREE_TOPLEVEL;

	if (lstat(path, &st) != 0)

		return func(path, NULL, flags | WALK_TREE_FAILED, arg);

	if (S_ISLNK(st.st_mode)) {

		flags |= WALK_TREE_SYMLINK;

		if ((flags & WALK_TREE_DEREFERENCE) ||

		    ((flags & WALK_TREE_TOPLEVEL) &&

		     (flags & WALK_TREE_DEREFERENCE_TOPLEVEL))) {

			if (stat(path, &st) != 0)

				return func(path, NULL,

					    flags | WALK_TREE_FAILED, arg);

			dir.dev = st.st_dev;

			dir.ino = st.st_ino;

			have_dir_stat = 1;

		}

	} else if (S_ISDIR(st.st_mode)) {

		dir.dev = st.st_dev;

		dir.ino = st.st_ino;

		have_dir_stat = 1;

	}

	err = func(path, &st, flags, arg);

	/*

	 * Recurse if WALK_TREE_RECURSIVE and the path is:

	 *      a dir not from a symlink

	 *      a link and follow_symlinks

	 */

        if ((flags & WALK_TREE_RECURSIVE) &&

	    ((!(flags & WALK_TREE_SYMLINK) && S_ISDIR(st.st_mode)) ||

	     ((flags & WALK_TREE_SYMLINK) && follow_symlinks))) {

		struct dirent *entry;

		/*

		 * Check if we have already visited this directory to break

		 * endless loops.

		 *

		 * If we haven't stat()ed the file yet, do an opendir() for

		 * figuring out whether we have a directory, and check whether

		 * the directory has been visited afterwards. This saves a

		 * system call for each non-directory found.

		 */

		if (have_dir_stat && walk_tree_visited(dir.dev, dir.ino))

			return err;

		if (num_dir_handles == 0 && closed->prev != &head) {

close_another_dir:

			/* Close the topmost directory handle still open. */

			closed = closed->prev;

			closed->pos = telldir(closed->stream);

			closedir(closed->stream);

			closed->stream = NULL;

			num_dir_handles++;

		}

		dir.stream = opendir(path);

		if (!dir.stream) {

			if (errno == ENFILE && closed->prev != &head) {

				/* Ran out of file descriptors. */

				num_dir_handles = 0;

				goto close_another_dir;

			}

			/*

			 * PATH may be a symlink to a regular file, or a dead

			 * symlink which we didn't follow above.

			 */

			if (errno != ENOTDIR && errno != ENOENT)

				err += func(path, NULL, flags |

							WALK_TREE_FAILED, arg);

			return err;

		}

		/* See walk_tree_visited() comment above... */

		if (!have_dir_stat) {

			if (stat(path, &st) != 0)

				goto skip_dir;

			dir.dev = st.st_dev;

			dir.ino = st.st_ino;

			if (walk_tree_visited(dir.dev, dir.ino))

				goto skip_dir;

		}

		/* Insert into the list of handles. */

		dir.next = head.next;

		dir.prev = &head;

		dir.prev->next = &dir;

		dir.next->prev = &dir;

		num_dir_handles--;

		while ((entry = readdir(dir.stream)) != NULL) {

			char *path_end;

			if (!strcmp(entry->d_name, ".") ||

			    !strcmp(entry->d_name, ".."))

				continue;

			path_end = strchr(path, 0);

			if ((path_end - path) + strlen(entry->d_name) + 1 >=

			    FILENAME_MAX) {

				errno = ENAMETOOLONG;

				err += func(path, NULL,

					    flags | WALK_TREE_FAILED, arg);

				continue;

			}

			*path_end++ = '/';

			strcpy(path_end, entry->d_name);

			err += walk_tree_rec(path, walk_flags, func, arg,

					     depth + 1);

			*--path_end = 0;

			if (!dir.stream) {

				/* Reopen the directory handle. */

				dir.stream = opendir(path);

				if (!dir.stream)

					return err + func(path, NULL, flags |

						    WALK_TREE_FAILED, arg);

				seekdir(dir.stream, dir.pos);

				closed = closed->next;

				num_dir_handles--;

			}

		}

		/* Remove from the list of handles. */

		dir.prev->next = dir.next;

		dir.next->prev = dir.prev;

		num_dir_handles++;

	skip_dir:

		if (closedir(dir.stream) != 0)

			err += func(path, NULL, flags | WALK_TREE_FAILED, arg);

	}

	return err;

}

int walk_tree(const char *path, int walk_flags, unsigned int num,

	      int (*func)(const char *, const struct stat *, int, void *),

	      void *arg)

{

	char path_copy[FILENAME_MAX];

	num_dir_handles = num;

	if (num_dir_handles < 1) {

		struct rlimit rlimit;

		num_dir_handles = 1;

		if (getrlimit(RLIMIT_NOFILE, &rlimit) == 0 &&

		    rlimit.rlim_cur >= 2)

			num_dir_handles = rlimit.rlim_cur / 2;

	}

	if (strlen(path) >= FILENAME_MAX) {

		errno = ENAMETOOLONG;

		return func(path, NULL, WALK_TREE_FAILED, arg);

	}

	strcpy(path_copy, path);

	return walk_tree_rec(path_copy, walk_flags, func, arg, 0);

}