UNIX 高级环境编程实验二目录树的遍历

glm233

发布于 2020-10-28 14:58:34

9710

发布于 2020-10-28 14:58:34

文章被收录于专栏：glm的全栈学习之路glm的全栈学习之路

实验二目录树的遍历

1. 实验内容

以课本132-134页程序4-22为参考，在此基础上进行修改和扩展，实现目录树的遍历，具体需要根据传入参数的不同实现以下功能：

仅传入一个目录：统计该目录下的文件信息
传入-comp和文件名参数：在该目录下寻找与该文件名内容相同的文件，输出绝对路径
传入-name和文件名参数列表：在该目录下寻找与该文件名列表中的某一个相同的文件名，输出绝对路径
不能输出任何“文件打不开”等错误信息及无关目录

详细命令语法：

    myfind <pathname> [-comp <filename> | -name <str>…]

命令语义：

myfind <pathname> 的功能：除了具有与程序4-7相同的功能外，还要输出在目录子树之下，文件长度不大于4096字节的常规文件，在所有允许访问的普通文件中所占的百分比。程序不允许打印出任何路径名。
myfind <pathname> -comp <filename> 的功能：是常规文件的路径名（非目录名，但是其路径可以包含目录）。命令仅仅输出在目录子树之下，所有与文件内容一致的文件的绝对路径名。不允许输出任何其它的路径名，包括不可访问的路径名。
myfind <pathname> -name <str>… 的功能：…是一个以空格分隔的文件名序列(不带路径)。命令输出在目录子树之下，所有与…序列中文件名相同的文件的绝对路径名。不允许输出不可访问的或无关的路径名。

<pathname> 和 <filename> 均既可以是绝对路径名，也可以是相对路径名。<pathname> 即可以是目录，也可以是文件，此时，目录为当前工作目录。

2. 实验设计与实现

2.1 前置知识掌握，课本程序理解

static Myfunc	myfunc;
static int		myftw(char *, Myfunc *);
static int		dopath(Myfunc *);

主程序由myftw、dopath和myfunc三个主要函数

myftw：程序的主要功能封装，包括目录名的预处理，目录名存储空间的分配，以及调用dopath函数。
dopath：深度优先遍历目录，并对每个文件调用myfunc函数进行计数。
myfunc：使用lstat统计各类文件信息，以及相应打不开文件或未知文件类型出错处理。

int		ret;

	if (argc != 2)
		err_quit("usage:  ftw  <starting-pathname>");

	ret = myftw(argv[1], myfunc);		/* does it all */

	ntot = nreg + ndir + nblk + nchr + nfifo + nslink + nsock;
	if (ntot == 0)
		ntot = 1;		/* avoid divide by 0; print 0 for all counts */
	printf("regular files  = %7ld, %5.2f %%\n", nreg,
	  nreg*100.0/ntot);
	printf("directories    = %7ld, %5.2f %%\n", ndir,
	  ndir*100.0/ntot);
	printf("block special  = %7ld, %5.2f %%\n", nblk,
	  nblk*100.0/ntot);
	printf("char special   = %7ld, %5.2f %%\n", nchr,
	  nchr*100.0/ntot);
	printf("FIFOs          = %7ld, %5.2f %%\n", nfifo,
	  nfifo*100.0/ntot);
	printf("symbolic links = %7ld, %5.2f %%\n", nslink,
	  nslink*100.0/ntot);
	printf("sockets        = %7ld, %5.2f %%\n", nsock,
	  nsock*100.0/ntot);

	exit(ret);

对于常规文件、目录、块文件、字符文件、管道文件、符号链接文件、套间字文件，进行计数打印信息

static int					/* we return whatever func() returns */
myftw(char *pathname, Myfunc *func)
{
	int len;
	fullpath = path_alloc(&len);	/* malloc's for PATH_MAX+1 bytes */
									/* ({Prog pathalloc}) */
	strncpy(fullpath, pathname, len);	/* protect against */
	fullpath[len-1] = 0;				/* buffer overrun */

	return(dopath(func));
}

复制路径名至fullpath，传入函数指针，开始深度优先遍历文件

static int					/* we return whatever func() returns */
dopath(Myfunc* func)
{
	struct stat		statbuf;
	struct dirent	*dirp;
	DIR				*dp;
	int				ret;
	char			*ptr;

	if (lstat(fullpath, &statbuf) < 0)	/* stat error */
		return(func(fullpath, &statbuf, FTW_NS));
	if (S_ISDIR(statbuf.st_mode) == 0)	/* not a directory */
		return(func(fullpath, &statbuf, FTW_F));

	/*
	 * It's a directory.  First call func() for the directory,
	 * then process each filename in the directory.
	 */
	if ((ret = func(fullpath, &statbuf, FTW_D)) != 0)
		return(ret);

	ptr = fullpath + strlen(fullpath);	/* point to end of fullpath */
	*ptr++ = '/';
	*ptr = 0;

	if ((dp = opendir(fullpath)) == NULL)	/* can't read directory */
		return(func(fullpath, &statbuf, FTW_DNR));

	while ((dirp = readdir(dp)) != NULL) {
		if (strcmp(dirp->d_name, ".") == 0  ||
		    strcmp(dirp->d_name, "..") == 0)
				continue;		/* ignore dot and dot-dot */

		strcpy(ptr, dirp->d_name);	/* append name after slash */

		if ((ret = dopath(func)) != 0)		/* recursive */
			break;	/* time to leave */
	}
	ptr[-1] = 0;	/* erase everything from slash onwards */

	if (closedir(dp) < 0)
		err_ret("can't close directory %s", fullpath);

	return(ret);
}

核心代码部分：递归文件遍历，思路就是以根目录为起点，开始逐个搜索，添加上文件名与\0截断，判断是否是目录，如果是目录则继续递归。

2.2 自写程序功能解析

头文件使用：

#include <dirent.h>
#include <fcntl.h>
#include "apue.h"

dirent.h：用到 opendir、closedir
apue.h ：用到 malloc、 stdio.h、 printf 、 string.h、strcat、memcpy、strlen、sys/stat.h：lstat、unistd.h、lseek、getcwd、chdir、宏定义常量
fcntl.h：用到open

//Parameter:
//Regular file
//Directory file
//Character file
//Block file
//FIFO file
//Socket file
//Symbol link file
enum descrip{
    S_REGULAR,S_DIR,S_CHAR,S_BLOCK,S_FIFO,S_LINK,S_SOCKET,S_SPE,S_TOT,S_LENGTH
};

枚举类型来表示各类文件数

// find function
void find(char *basename, void (*visit)(char *, struct stat *))
{
    if (chdir(basename) == -1) // use chdir and getcwd to obtain fullpath of argv[1]
        return;

    long int len_pathname_max = pathconf("/", _PC_PATH_MAX);
    //printf("%ld\n",len_pathname_max);
    if ((pathname = (char *) malloc(len_pathname_max)) == NULL)
        return;
    if (getcwd(pathname, len_pathname_max) == NULL)return;
    len_pathname = strlen(pathname);
    //printf("%ld\n",len_pathname);

    deep_first_search(visit);
}

先切换到输入参数的绝对目录，然后获得系统文件名路径的最大值，之后再调用getcwd获得当前路径，更新当前文件长度，继续递归。

// myfunc for `-name` option
void work_name(char *path_name, struct stat *st)
{
    int i;
    for (i=0;i<len_filenames;i++)
    {
        //printf("%s %s\n",pathname,filenames[i]);
        if (strcmp(path_name, filenames[i]) == 0)printf("%s\n", pathname);
    }
        
}

这个函数针对argc>=4的-name实现，filenames为输入的需要比较的文件名字符数组，len_filenames就是该字符数组的长度大小，没啥好说的，就是暴力比较，如果strcmp返回值为0，就输出绝对路径

// myfunc for `-comp` option
void work_comp(char *path_name, struct stat *st)
{
    //printf("%s %d st->st_size:%d\n", pathname,filesize,st->st_size);
    if (st->st_size!=filesize)return;
    int fd2;
    if ((fd2=open(pathname,O_RDONLY)) == -1)
        return;
    if (~lseek(fd,0,SEEK_SET))
    {
        //printf("%s ac\n", pathname);
        char buf1[buffer]="",buf2[buffer]="";
        while (read(fd,buf1,buffer) > 0 && read(fd2,buf2,buffer)>0)
            if (memcmp(buf1, buf2, buffer) != 0)
            {
                close(fd2);
                return;
            }
        close(fd2);
        printf("%s\n", pathname);
    }
}

这一部分函数则是针对argc=4时的-comp参数实现，其实思路也很简单，就是先比较文件大小，如果文件大小不等于输入文件大小，则不需要进行接下来的操作，如果相等，需要进一步判断：设置两个字符数组分别将两个文件内容读入，最后调用memcmp函数，如果返回值为0，说明两个文件内容一致，关闭文件，输出文件名。

// dopath function
void deep_first_search(void (*visit)(char *, struct stat *))
{
    int len_filename;
    DIR *dp;
    struct dirent *dirp;
    struct stat st;
    //printf("%s\n",pathname);
    if ((dp = opendir(pathname)) == NULL)
        return;
    if (pathname[len_pathname - 1] == '/') // truncate redundant '/'
    {
        len_pathname -= 1;
        pathname[len_pathname] = '\0';
    }
    //printf("%s\n",pathname);
    while ((dirp = readdir(dp)) != NULL)
    {
        if (strcmp(dirp->d_name, ".") == 0 || strcmp(dirp->d_name, "..") == 0)
            continue; // filter two special dirs

        len_filename = strlen(dirp->d_name);
        len_pathname += len_filename + 1;
        strcat(pathname, "/");
        strcat(pathname, dirp->d_name);
        //printf("%s\n",pathname);
        if(~(lstat(pathname,&st)))
        {
            //printf("%s\n",pathname);
            visit(dirp->d_name, &st);
            if (S_ISDIR(st.st_mode))
                deep_first_search(visit); // recursive if it's a dir
        }
        len_pathname -= len_filename + 1;
        pathname[len_pathname] = '\0';
    }
    closedir(dp);
}

最重要函数dfs解析：处理一些特殊情况：文件打不开、起始点是根目录则直接截断如果发现是目录文件才进行dfs，注意到任何一个文件夹里都有两个隐藏文件夹.和…,代表本级目录以及上级目录，这两种目录自然不需要遍历，直接continue掉就好；还需要用到文件路径字符串的拼接，需要用到strcat函数，注意回溯，先加上下一级遍历的文件名搜索完再减去

3.运行结果

gcc -o myfind myfind.c libapue.a

调用二参数模式 ./myfind /

统计根目录下的所有文件类型，并输出在常规文件中，文件长度不大于4096字节的常规文件，在所有允许访问的普通文件中所占的百分比

调用四参数模式 ./myfind / -comp apue.h

输出在目录子树之下，所有与文件内容一致的文件的绝对路径名。

可能会很奇怪，因为根目录下每个用户（学生）都应该配了apue开发环境，但是为啥就我一个和另外一个14级的学生呢，其实也正常，因为我只是一个普通用户，访问不了其他用户的目录文件。

调用多(>=4)参数模式 ./myfind / -name apue.h apue.2e string.h

从二参数模式的统计信息可以看出，这台服务器上的文件分布与课本上给出的文件分布示例大致相符，绝大部分还是常规文件，其次是目录，再其次是符号链接。而其他的字符文件、套接字等也都存在，但有个不完美的地方就是其实很多其他用户的目录文件都没有打开。
从四参数模式 ./myfind / -comp apue.h 输出来看，程序成功比较了根目录下能成功打开的文件内容，输出了与用户提供的文件内容一致的文件绝对路径
从调用多(>=4)参数模式 ./myfind / -name apue.h apue.2e string.h 输出来看，程序可以找出同个目录下的多个相同文件名的文件，对输入多文件名也支持

4.实验收获暨总结

一开始对课本上的一百多行的递归遍历文件目录的代码整懵了，后面冷静下来仔细看了下发现其实理清楚了代码的结构就不是很难，之后就开始翻书查函数调用方法开始着手写了起来，就是在递归的过程中发现如果递归深度过大会直接退出程序，需要一定的剪枝比如不是目录文件就直接统计，打不开就直接返回，总体来说，这次实验对我来说是一次不小的挑战，但完成任务之后还是对自己unix环境下c语言编程有很大帮助的。

附myfind.c

#include "apue.h"
#include <dirent.h>
#include <limits.h>

/* function type that is called for each filename */
typedef	int	Myfunc(const char *, const struct stat *, int);

static Myfunc	myfunc;
static int		myftw(char *, Myfunc *);
static int		dopath(Myfunc *);

static long	nreg, ndir, nblk, nchr, nfifo, nslink, nsock, ntot;

int main(int argc, char *argv[])
{
	int		ret;

	if (argc != 2)
		err_quit("usage:  ftw  <starting-pathname>");

	ret = myftw(argv[1], myfunc);		/* does it all */

	ntot = nreg + ndir + nblk + nchr + nfifo + nslink + nsock;
	if (ntot == 0)
		ntot = 1;		/* avoid divide by 0; print 0 for all counts */
	printf("regular files  = %7ld, %5.2f %%\n", nreg,
	  nreg*100.0/ntot);
	printf("directories    = %7ld, %5.2f %%\n", ndir,
	  ndir*100.0/ntot);
	printf("block special  = %7ld, %5.2f %%\n", nblk,
	  nblk*100.0/ntot);
	printf("char special   = %7ld, %5.2f %%\n", nchr,
	  nchr*100.0/ntot);
	printf("FIFOs          = %7ld, %5.2f %%\n", nfifo,
	  nfifo*100.0/ntot);
	printf("symbolic links = %7ld, %5.2f %%\n", nslink,
	  nslink*100.0/ntot);
	printf("sockets        = %7ld, %5.2f %%\n", nsock,
	  nsock*100.0/ntot);

	exit(ret);
}

/*
 * Descend through the hierarchy, starting at "pathname".
 * The caller's func() is called for every file.
 */
#define	FTW_F	1		/* file other than directory */
#define	FTW_D	2		/* directory */
#define	FTW_DNR	3		/* directory that can't be read */
#define	FTW_NS	4		/* file that we can't stat */

static char	*fullpath;		/* contains full pathname for every file */

static int					/* we return whatever func() returns */
myftw(char *pathname, Myfunc *func)
{
	int len;
	fullpath = path_alloc(&len);	/* malloc's for PATH_MAX+1 bytes */
									/* ({Prog pathalloc}) */
	strncpy(fullpath, pathname, len);	/* protect against */
	fullpath[len-1] = 0;				/* buffer overrun */

	return(dopath(func));
}

/*
 * Descend through the hierarchy, starting at "fullpath".
 * If "fullpath" is anything other than a directory, we lstat() it,
 * call func(), and return.  For a directory, we call ourself
 * recursively for each name in the directory.
 */
static int					/* we return whatever func() returns */
dopath(Myfunc* func)
{
	struct stat		statbuf;
	struct dirent	*dirp;
	DIR				*dp;
	int				ret;
	char			*ptr;

	if (lstat(fullpath, &statbuf) < 0)	/* stat error */
		return(func(fullpath, &statbuf, FTW_NS));
	if (S_ISDIR(statbuf.st_mode) == 0)	/* not a directory */
		return(func(fullpath, &statbuf, FTW_F));

	/*
	 * It's a directory.  First call func() for the directory,
	 * then process each filename in the directory.
	 */
	if ((ret = func(fullpath, &statbuf, FTW_D)) != 0)
		return(ret);

	ptr = fullpath + strlen(fullpath);	/* point to end of fullpath */
	*ptr++ = '/';
	*ptr = 0;

	if ((dp = opendir(fullpath)) == NULL)	/* can't read directory */
		return(func(fullpath, &statbuf, FTW_DNR));

	while ((dirp = readdir(dp)) != NULL) {
		if (strcmp(dirp->d_name, ".") == 0  ||
		    strcmp(dirp->d_name, "..") == 0)
				continue;		/* ignore dot and dot-dot */

		strcpy(ptr, dirp->d_name);	/* append name after slash */

		if ((ret = dopath(func)) != 0)		/* recursive */
			break;	/* time to leave */
	}
	ptr[-1] = 0;	/* erase everything from slash onwards */

	if (closedir(dp) < 0)
		err_ret("can't close directory %s", fullpath);

	return(ret);
}

static int
myfunc(const char *pathname, const struct stat *statptr, int type)
{
	switch (type) {
	case FTW_F:
		switch (statptr->st_mode & S_IFMT) {
		case S_IFREG:	nreg++;		break;
		case S_IFBLK:	nblk++;		break;
		case S_IFCHR:	nchr++;		break;
		case S_IFIFO:	nfifo++;	break;
		case S_IFLNK:	nslink++;	break;
		case S_IFSOCK:	nsock++;	break;
		case S_IFDIR:
			err_dump("for S_IFDIR for %s", pathname);
					/* directories should have type = FTW_D */
		}
		break;

	case FTW_D:
		ndir++;
		break;

	case FTW_DNR:
		err_ret("can't read directory %s", pathname);
		break;

	case FTW_NS:
		err_ret("stat error for %s", pathname);
		break;

	default:
		err_dump("unknown type %d for pathname %s", type, pathname);
	}

	return(0);
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-10-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

html

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

html

登录后参与评论

0 条评论

热度