C语言测试。自己实现scandir 函数

在C语言课程的后端，讲完指针和标准文件IO处理，我会做出一个难度较大练习，题目就是，利用标准的目录处理函数 opendir/readdir/closedir实现类似于 scandir的功能。其中接口要scandir 函数一致。

  这个题目看起来简单，实现难度相当大，主要采用复杂指针的操作。我第一次拿出来测试，全班大约只一二名实现80%的功能，其余很多觉得无从下手。程序很容易就会出现段错误。基本上短时间内正确的做出来的人可以划归专业级的程度了。有兴趣的人可以先不看后面内容，自行实现一下。

 

 首先看一下man的scandir 接口定义

int scandir(const char *dir, struct dirent ***namelist,
              int(*filter)(const struct dirent *),
              int(*compar)(const struct dirent **, const struct dirent **));

,从定义来看就不是一个简单的函数，形参里，出现一个三级指针，二个函数指针。它的功能是，扫描名字为dir的目录，把满足filter函数的过滤条件（即filter执行为非0值）的目录项加入到一维指针数组namelist.数组的总长度为返回值n,如果compar不为空，则最终输出结果还要调用qsort来对数组进行排序后再输出。

 

从scandir的演示代码，我们可以推算出namelist是一个指向一维指针数组的指针。（一维指针数组等同于 struct dirent ** namelist,这里写在三级指针是因为要从函数里改变namelist的值，必须再多做一级）原因可以参考我的函数传值类型的说明。

 

以下是一个简单扫描 /usr/lib，并且把所有以lib打头的文件扫描到namelist数组的测试程序,这是参考scandir 提供的样例来修改,alphasort是做原始的ASCII码值比较进行排序的

 

可以看到namelist是完全动态分配的，不仅数组本身是动态分配，而且数组项指向的空间也是动态分配的。

 

 

#include <sys/types.h>
#include <dirent.h>

#include <sys/stat.h>
#include <unistd.h>

#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <stdlib.h>

//扫描所有的lib打头的文件

 int filter_fn(const struct dirent * ent)
 {
   if(ent->d_type != DT_REG)
     return 0;
     
   return (strncmp(ent->d_name,"lib",3) == 0);
 }


void scan_lib(char * dir_name)
{
  int n;
   struct dirent **namelist; // struct dirent * namelist[];

   n = scandir(dir_name, &namelist, filter_fn, alphasort);
   if (n < 0)
        perror("scandir");
   else {
               while(n--) {
                   printf("%s\n", namelist[n]->d_name);
                   free(namelist[n]);
               }
               free(namelist);
           }
}

int main(int argc ,char * argv[])
{
   scan_lib("/usr/lib");
}


从这个样例，我们可以推算出namelist 的数据结构是.另外一个难点是，这个数组是动态形成的。即根据扫描结果来生成数组。这样在函数里构造这样数据结构还是相当有难度。

最后正式程序如下。完全的源码及测试程序参见附件。

 

 

/*
 * Author : Andrew Huang
 *
*/
#define MAX_DIR_ENT 1024

typedef int(*qsort_compar)(const void *, const void *);

int hxy_scandir(const char *dir, struct dirent ***namelist,
              int(*filter)(const struct dirent *),
              int(*compar)(const struct dirent **, const struct dirent **))
{
  DIR * od;
  int n = 0;
  struct dirent ** list = NULL;
  struct dirent * ent ,* p;
  
  if((dir == NULL) || (namelist == NULL))
    return -1;
    
  od = opendir(dir);
  if(od == NULL)
    return -1;
    
   /* 分配一个最大数组 */
  list = (struct dirent **)malloc(MAX_DIR_ENT*sizeof(struct dirent *));
  
  
   while(( ent = readdir(od)) != NULL)
    {
       if( filter && !filter(ent))
          continue;
          
        
          p = (struct dirent *)malloc(sizeof(struct dirent));
          
          memcpy((void *)p,(void *)ent,sizeof(struct dirent));
          list[n] = p;
          
          n++;
          if(n >= MAX_DIR_ENT)
            break;
       
    }
       
    closedir(od);
   
    /* 改变返回数组大小*/
    *namelist = realloc((void *)list,n*sizeof(struct dirent *));
     if(*namelist == NULL)
        *namelist = list;
  

    /* 数组排序*/
    if(compar)
       qsort((void *)*namelist,n,sizeof(struct dirent *),(qsort_compar)compar);
     
    return n;
   
}


 

文件:	hxy_scandir.zip
大小:	1KB
下载:	下载

程序分析

1.这一个程序的第一个难点是 namelist个数不确定的.是根据扫描目录的结果来确定,并且通过返回值告诉调用者.一种办法是做两次循环,先扫描一次readdir从头读一次,确定个数,然后再重新读一次读入内容,这样结果是准确了,但是效率极低.另外一种方法读入时采用是使用链表缓存,然后最后一次性存入数组.这样代码过于复杂了.

  最后采用一个折中的办法,即开始一次性分配最大值(1024)的数组,在读入时直接对数组操作.这样代码处理简单,绝大部分情况能正确运行.万一有超过1024,一种是简单丢弃多余,二是扩大最大值.这个方法是在效率和正确性采用一个折衷。

 

2.最后输出时，可以用realloc调整namelist大小再输出，这样可以节约堆空间。

3.关于最后的数组的排序，scandir文档明确告之是采用qsort进行排序，因此最后需要进行这一步，关键是参数怎么填写。

4.这个函数内部的指针操作相当复杂，象三级指针namelist最好不要直接使用，而是要在函数用一个中间指针变量struct dirent ** list 来简化。而且在函数是直接将其作为数组