第一部分简介：
最近有幸参加了一个网上的开源项目，需要我设计一个缩略图存储的方法。整个思路主要是模仿XP的实现方式，而对于Win7（或是Vista）里面将所有缩略图统一管理的模式没有采用。主要想法还是一切从简，这也就是初探的来由了。
整个缩略图的核心算法来自《Inside MoPaQ》http://shadowflare.samods.org/inside_mopaq/
核心是将文件名通过Hash散列到表中，从而达到快速查找的目的。
MPQ文件，对于大部分大学时间沉浸的游戏——War3是非常重要的，每次War3版本的更替都对这个文件做了修改。的确，对于一个计算机系的非常爱玩的我，现在才分析MPQ实在是惭愧。
对于我这个文件名，现在姑且命名为MP(MiniPic)。
这是我第一次用c++来写程序，整个程序很简单，花了差不多1个半月（我这个效率实在不行），和第一篇一样，希望各位大哥能帮忙看看。
第二部分实现：
- 需求
1.1 这里实现读取，修改固定大小的文件，即每个缩略图的存储空间大小一致。
1.2 根据文件名添加，查找，删除功能。
1.3 文件存储数目固定，不能动态增长。
1.4 储存文件名，使用ID形式访问。
2.存储方案
2.1 表结构设计
整个文件包括FileHeader，HashTable，BlockTable，DataHeader，Data构成。通过计算文件名的hash值，将文件名散列到HashTable中，然后根据HashTable中查找BlockTable（文件块表），在BlockTable中查找到实际文件data的位置。读入DataHeader和Data。
FileHeader HashTableItem HashTableItem …… HashTableItem
BlockTableItem BlockTableItem DataHeader Data DataHeader
Data
…
2.2 内存中存储。
内存中存储FileHeader、HashTable、BlockTable、DebrisBlock,dataBuffer。
DebrisBlock是队列结构。存储因删除操作而产生的碎片。
FileHeader，HashTable，BlockTable是数组。dataBuffer数据缓存
3.实现方案
实际还需要增加功能，以下是核心部分。对于每个功能的算法也只写核心部分。
3.1 增加
3.1.1 将文件名转换为数字。这里使用的是MPQ文件算法。
DWORD HashManager::HashString( TCHAR *lpszFileName,DWORD dwHashType )
{
BYTE *key = (BYTE *)lpszFileName;
DWORD seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;
while(*key != 0)
{
ch = toupper(*key++);
//原来是char，这里处理TCHAR中的0，这里也有小问题，如果要更多的地方使用，还需要做大头小头机数据转换
if(!*key)
{
++key;
}
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}
3.1.2 插入HashTable。
在处理冲突的时候，是采用最简单的线性探查法，在判断位置相同的时候，采用增加2个Hash值的方法。虽然不能保证肯定不会出问题。但是3个相同的概率很低，大概是10的22.3次方分之一，这个是在参考《Inside MoPaQ》，中的数据，是否可靠。我无法确定。
BOOL HashManager::InsertHashTable( TCHAR *lpszString, FILETIME FileTime, LONG &HashPos, DWORD dwFlags,
BOOL &isNew//设置，是否是新文件
)
{
ASSERT( m_pHashIndexTable!= NULL );
isNew = TRUE;
const DWORD HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
DWORD nHash = HashString(lpszString, HASH_OFFSET);
DWORD nHashA = HashString(lpszString, HASH_A);
DWORD nHashB = HashString(lpszString, HASH_B);
DWORD nHashStart = nHash %m_hashTableLength;
DWORD nHashPos = nHashStart;
DWORD x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
DWORD y = m_pHashIndexTable[nHashPos].dwFlag & FILE_DELETED;
while( x!=0 )
{
if( y==FILE_DELETED )
{
isNew = FALSE;
break;
}
//如果有同名文件
if (m_pHashIndexTable[nHashPos].dwHashValueA == nHashA && m_pHashIndexTable[nHashPos].dwHashValueB == nHashB)
{
if( dwFlags & INSERT_CHECK_FILETIME )
{
if(m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwHighDateTime == FileTime.dwHighDateTime
&& m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwLowDateTime == FileTime.dwLowDateTime)
{
return FALSE;//说明文件真实存在,插入失败
}
else
{
isNew = FALSE;
break;
}
}
if( dwFlags & INSERT_REPLACE_EXISTING )
{
isNew = FALSE;
break;
}
else
{
return FALSE;
}
}
nHashPos = (nHashPos + 1) % m_hashTableLength;
if(nHashPos == nHashStart)
{
return FALSE;
}
x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
y = m_pHashIndexTable[nHashPos].dwFlag & FILE_DELETED;
}
m_pHashIndexTable[nHashPos].dwFlag = FILE_EXISTS;
m_pHashIndexTable[nHashPos].dwHashValueA = nHashA;
m_pHashIndexTable[nHashPos].dwHashValueB = nHashB;
m_pHashIndexTable[nHashPos].iBlockIndex=nHashPos;
if( dwFlags & INSERT_CHECK_FILETIME )
{
m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwHighDateTime = FileTime.dwHighDateTime;
m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwLowDateTime = FileTime.dwLowDateTime;
}
HashPos = nHashPos;
return TRUE;
}
3.1.3 插入BlockTable
如果DebrisBlock（空闲表）为空，则将BlockTable中的文件偏移量指向文件最后。
如果DebrisBlock不为空，则将BlockTable中的文件偏移量指向BlockTable头结点，DebrisBlock头结点出列。
3.2 查找
3.2.1 查找HashTable
LONG HashManager::GetHashTablePos( TCHAR *lpszString )
{
const DWORD HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
DWORD nHash = HashString(lpszString, HASH_OFFSET);
DWORD nHashA = HashString(lpszString, HASH_A);
DWORD nHashB = HashString(lpszString, HASH_B);
DWORD nHashStart = nHash % m_hashTableLength;
DWORD nHashPos = nHashStart;
DWORD x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
while( x != 0 )
{
if(m_pHashIndexTable[nHashPos].dwHashValueA == nHashA && m_pHashIndexTable[nHashPos].dwHashValueB == nHashB)
{
return nHashPos;
}
else
{
nHashPos = (nHashPos + 1) % m_hashTableLength;
}
if(nHashPos == nHashStart)
break;
x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
}
return -1; //没有找到
}
3.3 删除
3.3.1 查找HashTable ：GetHashTablePos；
3.3.2 查找到则DebrisBlock入列文件偏移量，
3.3.3 在HashTable中Flag标记位FILE_DELETED
3.3.4 备注：这里不是真正删除。真正删除在MPFileClose()中的ManagerFileDebris进行。
BOOL MiniPic::DeleteData(TCHAR *lpszString)
{
ASSERT(m_isInit);
ASSERT( m_pHashManager != NULL );
ASSERT( lpszString != NULL );
LONG hashTablePos;
hashTablePos = m_pHashManager->GetHashTablePos(lpszString);
if( hashTablePos == -1 )
{
return FALSE;
}
MINIPICDEBRIS debris;
debris.dwBlockTableIndex = hashTablePos;
debris.dwDebrisStartAt = m_pBlockTableManager->GetBlockTable()[hashTablePos].FileStartAt;
m_pHashManager->DeleteHashTable(hashTablePos);
m_debrisBlock.push_back(debris);
DebugPrintString(L"Free data the pos is %d\n",hashTablePos);
#ifdef TEST
if(count1>=testNum)
{
count1=0;
}
testIns[count1++]=hashTablePos;
#endif
m_fileHeader.childFileCount--;
return TRUE;
}
3.4 回收资源
因为在删除的时候只是在hashTable中做了一个Deleted的标记，并没有真正删除文件。若是长时间使用，则会浪费很多空间。此时需要整理。
收集空闲区域。排序，将文件尾部数据移动至最早空闲处，删除空闲处，更新hashTable。
BOOL MiniPic::ManagerFileDebris( LPVOID lpBuffer, const UINT count )
{
ASSERT( lpBuffer != NULL );
ASSERT( m_MPFile != NULL );
if( m_debrisBlock.empty() )
{
return TRUE;
}
MINIPICDATAITEMHEADER dataItemHeader;
m_debrisBlock.sort();
/*
首先将比较Debris block末尾，若是处在文件的最后，则将Debris block末尾数据出列。并向前移动fileEndPointer 保证Debris block要小于文件末尾。
确认Debris block是否为空。
将末尾文件数据移动到Debris block的首部位置，fileEndPointer--，并将Debris block首部数据出列。
在判断条件1，2*/
//查找Debris。
while( !m_debrisBlock.empty() )
{
while( m_debrisBlock.back().dwDebrisStartAt + count + sizeof(MINIPICDATAITEMHEADER) == m_fileDataEndPointer )//处理文件末尾的空闲区域
{
m_fileDataEndPointer -= count + sizeof(MINIPICDATAITEMHEADER);
m_pHashManager->ClearHashTable( m_debrisBlock.back().dwBlockTableIndex );//New add
m_debrisBlock.pop_back();
if( m_debrisBlock.empty() )
{
break;
}
}
if( !m_debrisBlock.empty() )
{
if( 0xFFFFFFFF == m_MPFile->Seek( m_fileDataEndPointer - count - sizeof(MINIPICDATAITEMHEADER),
FILE_BEGIN ))//指向最后文件块开始处
{
return FALSE;
}
m_MPFile->Read( &dataItemHeader, sizeof(MINIPICDATAITEMHEADER) );
m_MPFile->Read( lpBuffer, count );
if( 0xFFFFFFFF == m_MPFile->Seek( m_debrisBlock.front().dwDebrisStartAt, FILE_BEGIN ) )
{
return FALSE;
}
m_MPFile->Write( &dataItemHeader, sizeof(MINIPICDATAITEMHEADER) );
m_MPFile->Write( lpBuffer, count );
m_fileDataEndPointer -= count+sizeof(MINIPICDATAITEMHEADER);
m_pBlockTableManager->SetBlockTableFileStartAt( dataItemHeader.dwBlockTableIndex,
m_debrisBlock.front().dwDebrisStartAt );
//将原来指向空此间的HashTable标记位空。
m_pHashManager->ClearHashTable( m_debrisBlock.front().dwBlockTableIndex );
m_debrisBlock.pop_front();
DebugPrintString(L"find freedata set in it ,and the pos is %d\n",dataItemHeader.dwBlockTableIndex);
}
}
m_fileHeader.bfSize = m_fileDataEndPointer;
return TRUE;
}
第三部分 使用
BOOL MPFileOpen( LPCTSTR lpFileName );
void MPFileClose();
BOOL MPFileAddFile( LPCVOID lpBuffer, TCHAR *lpszString, const DWORD fileSize,
const FILETIME LastModiTime, LONG &lIndex, DWORD dwFlags
);
BOOL MPFileReadFile( LPVOID lpBuffer, TCHAR *lpszString );
BOOL MPFileDeleteFile(TCHAR *lpszString);
void MPFileFlushData();
BOOL MPFileReadFileByIndex( LPVOID lpBuffer, const DWORD index );
BOOL MPFileGetFileName( TCHAR *FileNameBuffer, const size_t count,
const DWORD index
);
BOOL MPFileReName( LPCTSTR lpNewFileName, LPCTSTR lpOldFileName);
第四部分 未解决问题
没有实现动态增长，处理文件的最大值有限。
没有对文件正确性做足够保证。没有加入CRC or MD5校验。
没有设定返回的错误码只有TRUE,FALSE，不利于识别错误问题。
算法的有些地方效率不高。还需改进。
数据的大小没有做限制，插入过多数据会溢出。
第五部分 疑问
在处理非常多的数据时，是否该将文件压缩？
许多管理文件系统都加入了最近访问文件列表，这些在有大量文件读入时效率高，是否可以设计类似结构？
如何处理异常，特别是在写入时产生的异常，导致文件写入错误。如何能够更好的解决类似问题？在发生异常的时候，如何能够做到高效的完全释放资源？
把HashTable，BlockTable放置到文件末尾，方便文件以后动态扩展。但是具体的如何扩容hashTable，可能不好办。
在文件头部分增加一个Flag，标示文件的状态。（在读入的时候标记位0，最后如果没有异常则标记位1，那么如果在这个文件出现了问题，那么就可以通过检测这个Flag来判断文件异常），若是设计的更好，可以通过这个检测那部分有问题，而对问题修正。
我之前谈到的异常情况，导致有的文件没有即时更新。我的想法是来自IE浏览器，他会记录上次出错的位置，那么这时候就可以启动恢复程序。要是MP文件的Flag是正常，那么就说明问题不在MP文件处理，可能是别的地方异常导致结束，那么就可以重新查找，根据文件创建的时间来判断是否文件变化过，那么这样就比重新生成要快多了。我这里应该提供用来恢复的接口，这个由外部程序调用它。
第六部分 写给自己
如果仔细看的话，这个并不是很复杂的东西，只是实现了最基本最简单的内容，但是自己做的依然很不完整。问题依然很多。这也映射出自己学习不仔细，编程依然马虎。很多问题都想的不周全。这也进一步说明自己基础不扎实。
我相信我这里肯定还有不少问题，希望大家有时间给小弟看看，与此同时我也会不断改进，把这个做到自己的极限。