自定义的打包文件 - lhf 的窝
平方根算法之四(翻译)
表达式求值的递归算法

自定义的打包文件

LiHengFeng posted @ 2008年5月30日 00:50 in 算法 with tags 目录 打包 压缩 , 2573 阅读
本blog所有文章,除声明了作者外,均为原创。欢迎转载,转载请注明作者。

本文实现了一个自定义的打包格式,可以将一个目录下的所有文件打包成一个文件,并保持完整的目录结构。另外,该格式还支持分文件压缩,可以提取每个单独的文件而不必解包整个包文件。

首先,要保存一个目录下所有文件的内容是很简单的,将该目录下每个文件的内容依次连接起来形成一个大文件就可以了。当然,为了能区分各文件的范围,还必须记录每个文件的起始位置和长度。

但要记录完整的目录结构,就必须采用一定的算法记录目录信息。这里采用的方法很简单,就是对每个文件(或目录)记录其父目录。读取的时候,从每个文件开始上溯到根目录(就是包文件对应的目录)就知道每个文件的完整目录信息了。

为了说清楚问题,将文件和目录统一视为一个存储节点。则一个目录下所有的内容(包括所有的子文件夹和文件)构成了一棵树。每一个文件都对应树的叶子节点,目录则对应中间节点或叶子节点(空目录)。

为了保存整个树的信息,只要按一定顺序遍历树的每个节点并依次记录下来。然后同时记录下当前节点的父节点就可以了。

注意,这里有一个隐含的问题。就是遍历节点是必须满足一定的要求才可以根据上述信息重建目录。这个要求就是,必须在访问子节点之前访问该子节点的父节点。否则,重建目录的时候,可能会出现先生成一个子文件夹中的文件,后生成子文件夹的情况(这当然会导致创建文件失败)。

打包算法描述:定义一个结构StorageItem表示一个文件或目录,用该结构的数组描述一个目录下所有的内容,每一个文件或文件夹都对应数组的一个元素,该元素记录了为文件名,创建时间,文件大小等所有必须信息,另外,还记录了本元素对应的父节点元素在数组中的位置。只要保存该数组,就可以重现目录的所有详细信息。剩下的就是,按该数组的元素顺序,依次将对应的文件内容连接起来。

一个最简单的StorageItem结构可以如下定义:

typedef struct tagStorageItem
{
    WIN32_FIND_DATA wfd;
    int   parent;
}StorageItem; //一个目录或文件

一个最简单的包文件可以如下定义: n + n个StorageItem结构 + n个存储项的内容.

当然,实际使用的时候,往往会有其它的要求,比如压缩,加密等等。因此,上面的结构还要再增加几个成员。另外,包文件也要定义的完整一些以便支持压缩和抽取独立文件等等应用。最终的存储结构和包文件定义如下:

typedef struct tagStorageItem
{
 WIN32_FIND_DATA wfd;
 DWORD offset; //起始位置
        int   parent;
 int   type;//0,copy. 1,zlib compress
 DWORD size;
}StorageItem; //一个目录或文件

typedef struct tagPackFileHeader
{
 char   sign[8];
 DWORD  version;
 DWORD  FITPos;  //file info table position.
 DWORD  FITType; //0,copy. 1,zlib compress.
 DWORD  FITcount;//FIT items count;
        DWORD  FITSize; //FIT size after compress.
 DWORD  FBPos;   //file block position.
 DWORD  FBSize;
}PackFileHdr;

//pak文件 = 文件头 + 文件块 + 文件信息表.
//文件块 =  n个文件内容依次连接.
//文件信息表 = n个StorageItem

//文件头按原始格式存储,其它各个部分都可压缩或加密.

扫描目录形成一个StorageItem的向量的代码如下:

typedef std::vector<StorageItem>  FileVect;

BOOL ScanDir(LPCTSTR dir,int parent,FileVect &all)
{
 WIN32_FIND_DATA wfd;
 HANDLE hFind;      

 memset(&wfd,0,sizeof(WIN32_FIND_DATA));
 hFind = FindFirstFile(dir,&wfd);

 if(INVALID_HANDLE_VALUE == hFind)
  return FALSE;

 {//当前目录本身的记录项

  StorageItem temp;
  
  memcpy(&temp.wfd,&wfd,sizeof(WIN32_FIND_DATA));

  temp.offset = 0;
  temp.parent = parent;
  temp.type   = 0;
  temp.size   = 0;

  all.push_back(temp);

  FindClose(hFind);

  parent = all.size()-1;
 }

 TCHAR find[MAX_PATH];
 lstrcpy(find,dir);
 lstrcat(find,_T("\\*.*"));

 memset(&wfd,0,sizeof(WIN32_FIND_DATA));
 hFind = FindFirstFile(find,&wfd);

 if(INVALID_HANDLE_VALUE == hFind)
  return FALSE;
 
 while(1)
 {
  if(lstrcmp(wfd.cFileName,".")&&lstrcmp(wfd.cFileName,".."))
  {
   if(FILE_ATTRIBUTE_DIRECTORY & wfd.dwFileAttributes)//文件夹
   {
     TCHAR SubDir[MAX_PATH];

     lstrcpy(SubDir,dir);
     lstrcat(SubDir,"\\");
     lstrcat(SubDir,wfd.cFileName);

     ScanDir(SubDir,parent,all);
   }
   else//文件
   {
     StorageItem temp;

     memcpy(&temp.wfd,&wfd,sizeof(WIN32_FIND_DATA));

     temp.offset = 0;
     temp.parent = parent;
     temp.type   = 0;
     temp.size   = 0;
    
     all.push_back(temp);
   }
  }

  memset(&wfd,0,sizeof(WIN32_FIND_DATA));
  
  if(!FindNextFile(hFind,&wfd))
   break;
 }

 FindClose(hFind);

 return TRUE;
}

注意,上面的算法中,处理任何一个目录或子目录的时候,首先都保存自己的节点项,然后才处理目录中的文件。这样可以保证解包的时候一定是先碰到目录项,然后才碰到目录下的文件项。

完整代码见附件,其中使用了zlib进行了某些类型的文件压缩。

附件


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter