#include "p382.cpp"		int PageFind ( const TwoChars & key, const paddr PageNumber )		//在由指針PageNumber所指的頁塊中搜索關鍵碼key, 如果找到則返回1, 否則返回0。		//因為在頁塊內的搜索方法一般為順序搜索, 算法不再特別給出, 可參看程序9.1。		{			for (int i=0;i<PageNumber->Count;i++)			{				if (key==PageNumber->Names[i]) return 1;			}			return 0;		};		paddr Find ( const TwoChars & key ) {		//在文件中搜索具有關鍵字key的記錄。若找到, 則返回該記錄所在頁塊的地址; 若沒有找到, 則返回 0。		   unsigned int id = makeAddress ( key, DicDepth );			//按key與DicDepth計算目錄地址		   paddr FoundPage;		   FoundPage= Directory[id];					//在目錄中找到相應頁塊地址		   if ( PageFind ( key, FoundPage ) ) return FoundPage;		//在該頁塊中搜索, 找到返回頁塊地址		   else return 0;		}		void DirDouble ( ) {							//目錄成倍擴充的算法		   unsigned int CurrentSize = Power2(DicDepth);		   		   paddr *TmpDir = Directory;				//創(chuàng)建臨時目錄		   		   Directory = new paddr[2*CurrentSize];			//創(chuàng)建新目錄		   for ( int i=0; i<CurrentSize; i++ )					//從臨時目錄向新目錄傳送頁塊指針			 { Directory[i] = TmpDir[i];  Directory[CurrentSize+i] = TmpDir[i]; } 		   DicDepth++;		   delete [] TmpDir;		}		int buddy ( const unsigned int index ) {		//根據(jù)一個頁塊的二進制地址index計算該頁塊的伙伴的二進制地址, 前端的二進位是互補的。		   if (DicDepth == 0 ) return 0;						//目錄深度為0, 沒有伙伴		   if ( Directory[index]->PgDepth < DicDepth ) 			//該頁塊的局部深度小于目錄深度			 return -1;								//沒有伙伴		   unsigned int mask = 1;						//工作變量		   mask <<= DicDepth - 1;						//左移DicDepth - 1位, 將1移到最高位 		   unsigned int buddyAddress = index ^ mask;			//做異或操作, 求伙伴		   return buddyAddress;		}		void ReDisTribute ( paddr PageNumber, paddr NewPage )			//將老頁塊中所有關鍵碼重新分布		{			int i=0;			int CurrentSize=PageNumber->PgDepth;			NewPage->Count=0;			while (i<PageNumber->Count)			{				TwoChars key=PageNumber->Names[i];				int NowPage=makeAddress ( key, CurrentSize );				if (Directory[NowPage]==NewPage) 				{					NewPage->Names[NewPage->Count]=key;					NewPage->Count++;					PageNumber->Count--;					PageNumber->Names[i]=PageNumber->Names[PageNumber->Count];				}				else					i++;			}		}		void Split ( const TwoChars key, paddr PageNumber ) {		//分裂頁塊		   int CurrentSize = DicDepth;						//記下老的目錄大小		   if ( PageNumber->PgDepth == DicDepth )			//頁塊深度等于目錄深度時			 DirDouble( );							//頁塊分裂將導致目錄成倍擴充		   paddr NewPage = new page;						//為伙伴頁塊分配存儲空間		   PageNumber->PgDepth ++;						//老頁塊的局部深度加1		   unsigned int id = makeAddress ( key, CurrentSize );		//按key與老DicDepth計算二進制地址		   unsigned int bd = buddy ( id );					//找伙伴頁塊的二進制地址			   Directory [ bd ] = NewPage;						//建立伙伴頁塊的目錄項		   		   NewPage->PgDepth = PageNumber->PgDepth;			//伙伴的局部深度等于老頁塊的局部深度		   ReDisTribute ( PageNumber, NewPage );				//將老頁塊中所有關鍵碼重新分布		} 		int Add (const TwoChars & key ) ;	   		void Insert ( paddr PageNumber, const TwoChars & key ) {		//將新關鍵碼key插入到由PageNumber指定的頁塊中。		   if ( PageNumber->Count != PageSize ) {				//若本頁塊中關鍵碼個數(shù)未滿			 PageNumber->Names [ PageNumber->Count ] = key;			 PageNumber->Count++;						//直接插入		   }		   else {									//否則			 Split ( key, PageNumber );						//將頁塊一分為二			 Add ( key);								//插入		   }		}		int Add (const TwoChars & key ) {		//將一個新關鍵碼key插入到目錄所指定的文件中。		   paddr foundPage = Find ( key );					//按key在文件中搜索		   if ( foundPage ) return 0;						//若找到, 則不插入, 返回主程序		   Insert ( Directory[makeAddress ( key, DicDepth )], key );						//將關鍵碼key插入foundPage頁塊		   return 1;		}