Chinaunix首页 | 论坛 | 博客
  • 博客访问: 207037
  • 博文数量: 91
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 15
  • 用 户 组: 普通用户
  • 注册时间: 2015-12-09 10:37
文章分类
文章存档

2016年(87)

2015年(4)

我的朋友

分类: LINUX

2016-05-17 16:07:17

原文地址:Linux文件目录树的遍历 作者:zyd_cu

1.  linux提供opendirreaddir(readdir_r)closedir和scandir等接口实现对目录的读取;

2.  readdir返回指向下一个目录项的指针,如果要自己传入缓冲区存储目录项,应使用readdir_r代替。readdir的结果中包含当前目录和上一级目录的目录项信息。

3.  在遍历过程中,进程的工作目录不会改变,在递归遍历的时候,需要改变工作目录(chdir)以识别相对路径,或者每次都限定全局路径。

4.  深度优先遍历目录树采用递归实现易编码(参见如下代码),广度优先遍历则需借助队列实现。当目录下的文件数量较少时,采用广度优先遍历效率会更高,因目录下的目录项基本都是连续存放,减少了很多磁盘寻道;而采用深度优先遍历,结果的聚合性更高。

 

  1. int dir_traverse(const char *dir_name)
  2. {
  3.     DIR *dirp = opendir(dir_name);
  4.     if(!dirp) {
  5.         perror("opendir");
  6.         return -1;
  7.     }

  8.     struct stat st;
  9.     struct dirent *dir;
  10.     char fullpath[FILENM_MAX];
  11.     while((dir = readdir(dirp)) != NULL) {
  12.         if(!strcmp(dir->d_name, ".") || // 考虑当前目录和上级目录,否则会死循环
  13.            !strcmp(dir->d_name, "..")) {
  14.             continue;
  15.         }

  16.         sprintf(fullpath, "%s/%s", dir_name, dir->d_name); //获取全局路径
  17.         printf("%s\n", fullpath); // 打印路径
  18.         if(lstat(fullpath, &st) < 0) {
  19.             perror("lstat");
  20.             continue;
  21.         }
  22.         if(S_ISDIR(st.st_mode)) {
  23.             dir_traverse(fullpath); // 递归遍历子目录
  24.         }

  25.     }

  26.     closedir(dirp);

  27.     return 0;
  28. }

访问目录下某个文件时,需要逐个读取目录数据中的目录项并与目标进行匹配获得文件的inode号,假设文件的平均长度为10byte,加上inode、type及reclen等信息,每个目录项的平均长度为16byte,假设采用4K的数据块,则一个块可以存放256个目录项,按照ext2文件数据索引的方式,当目录下文件数n少于256*12时,则在目录下查找文件最多需要访问n/256(向上取整)个数据块,当目录下文件数更多的时候,需要访问的块数会更快的增加(后面得到存储数据的物理块号需要多级索引),这也是在目录下不应放太多文件的原因,如果将拥有很多文件的目录均分成多个子目录,多一级目录会多一次(或多次,具体依赖于子目录下文件数量)磁盘块访问,但在子目录中查找文件的磁盘访问开销会小很多。


阅读(5382) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~