Introduction
The template class walker captures only the algorithm of walking and depends on ContextType, the template argument type, for context sensitive functionalities. The context based information are the context identifier type, filter type, context item, opening a context and reserved context. The ContextType template argument should support the required typedefs and inner classes, CItem and COpenContext.
Before going any further on the details of implementation, I would like to talk about the need for such a class. We program with different kind of structures that look like or are trees, and sometimes we will have to repeat the walking algorithm for a small variation in the structure. Repeating an algorithm like that has many problems we know, and that is the reason stl has for_each algorithm. Like the goals of stl, an algorithm should be independent of the data structure. The dependency of walk algorithm on data structure is moved to the ContextType class. The class should have types ContextIdentifierType, ContentFilterType, CItem and COpenContext and should support a static function IsReserved(const CItem*).
CItem should have the following interface :-
bool IsAContext() const
COpenContext should have the following interface
C'tor
D'tor
cont CItem* GetNext()
const CItem* Get() const
bool GetNewContextId(ContextIdentifierType& newId) const
For ContextIdentifierType and ContentFilterType there are no interface specification. None of the functions can throw exceptions.
Using the code
A class can derive from a particular instantiation of this template and override bool OnContextChange(UserDataType*, const ContextType::CItem&, const ContextType::ContextIdentifierType& , bool bMovedToNewOrBackToOld). This will be called by WalkI private method when entering or leaving a context.
The arguments are :-
- user data passed by reference to allow any modification
- item, which is the new context here
- present(old)/new context identifier
- moving in to/moving out of the context
And there is void OnItemFound(UserDataType,const ContextType::CItem&,const ContextType::ContextIdentifierType&). This method will be called by WalkI private method when a new item is found. Even though a new context is an item in the present context only OnContextChange is called.
- user data passed by value.
- item
- present context identifier
Both these methods are private. Here is the code for the template
template <class UserDataTypeT,class ContextTypeT>
class CWalker
{
public:
typedef ContextTypeT ContextType;
typedef UserDataTypeT UserDataType;
typedef CWalker<UserDataType,ContextType> MyType;
CWalker():m_bStopped(false)
{}
int Walk(UserDataType userData,
const ContextType::ContextIdentifierType& iContext
)
{
ContextType::ContentFilterType filter = m_filter;
int nRet = WalkI(userData,iContext,filter,m_bStopped);
m_bStopped = false;
return nRet;
}
void SetContentFilter(const ContextType::ContentFilterType& filter)
{
m_filter = filter;
}
void StopWalking()
{
m_bStopped = true;
}
private:
int WalkI(UserDataType userData,
const ContextType::ContextIdentifierType& iContext,
const ContextType::ContentFilterType& filter,
bool& bStopped
)
{
if(bStopped) return stopped;
ContextType::COpenContext openContext(iContext,filter);
const ContextType::CItem *item = openContext.Get();
if(!item) return fail;
if(!item->IsAContext())
{
this->OnItemFound(userData,*item,iContext);
}
else
{
if(!ContextType::IsReserved(*item))
{
ContextType::ContextIdentifierType newContext;
openContext.GetNewContextId(newContext);
if(this->OnContextChange(&userData,*item,newContext,true))
{
WalkI(userData,newContext,filter,bStopped);
if(bStopped) return stopped;
this->OnContextChange(&userData,*item,iContext,false);
}
}
else this->OnItemFound(userData,*item,iContext);
}
while(true)
{
if(bStopped) return stopped;
const ContextType::CItem *item = openContext.GetNext();
if(!item)
break;
if(!item->IsAContext())
{
this->OnItemFound(userData,*item,iContext);
}
else
{
if(!ContextType::IsReserved(*item))
{
ContextType::ContextIdentifierType newContext;
openContext.GetNewContextId(newContext);
if(this->OnContextChange(&userData,*item,newContext,true))
{
WalkI(userData,newContext,filter,bStopped);
if(bStopped) return stopped;
this->OnContextChange(&userData,*item,iContext,false);
}
}
else this->OnItemFound(userData,*item,iContext);
}
}
return success;
}
ContextType::ContentFilterType m_filter;
virtual bool OnContextChange(UserDataType*,const ContextType::CItem&,
const ContextType::ContextIdentifierType&,bool bMovedToNewOrBackToOld)
{
return false;
}
virtual void OnItemFound(UserDataType,const ContextType::CItem&,
const ContextType::ContextIdentifierType&)
{
}
bool m_bStopped;
};
An example context
For example we will create an FolderContext which, will capture the required function and details. The identifier type is string, because folders are uniquely identified through their names. The filter type is string, because the contents of folder are again uniquely identified through their names. Here is how CITem is coded :-
...
class CItem
{
public:
bool IsAContext() const
{
return fileInfo.dwFileAttributes==FILE_ATTRIBUTE_DIRECTORY;
}
WIN32_FIND_DATA& GetInfo()
{
return fileInfo;
}
const WIN32_FIND_DATA& GetInfo() const
{
return fileInfo;
}
private:
WIN32_FIND_DATA fileInfo;
};
...
If you can see, the
CItem wraps
WIN32_FIND_DATA, and uses that structure to implement
IsAContext method. Here is how
COpenContext has been coded :-
...
class COpenContext
{
public:
COpenContext(const ContextIdentifierType& context,
const ContentFilterType& filter)
{
m_context = context;
std::string szToSearchFor = context;
if(!filter.empty())
szToSearchFor += "\\" + filter;
m_hFind = ::FindFirstFile(szToSearchFor.data(),&m_folderItem.GetInfo());
}
~COpenContext()
{
if(m_hFind!=INVALID_HANDLE_VALUE) ::FindClose(m_hFind);
}
const CItem* GetNext()
{
if(m_hFind==INVALID_HANDLE_VALUE) return 0;
if(!::FindNextFile(m_hFind,&m_folderItem.GetInfo()))
return 0;
return &m_folderItem;
}
const CItem* Get() const
{
if(m_hFind==INVALID_HANDLE_VALUE) return 0;
return &m_folderItem;
}
bool GetNewContextId(ContextIdentifierType& newId) const
{
if(m_folderItem.IsAContext())
{
newId = m_context + "\\" + m_folderItem.GetInfo().cFileName;
return true;
}
return false;
}
private:
CItem m_folderItem;
HANDLE m_hFind;
ContextIdentifierType m_context;
COpenContext(const COpenContext&);
COpenContext& operator = (const COpenContext&);
};
...
Here the context is folder so a find handle on the folder is created when a COpenContext object is created. In the destructor we close the handle. GetNext will get the next file or folder in the present folder using the find handle. Get will return the current item. GetNewContextId will copy the new context id in to the out parameter using the present context and item name. The attributes are CITem, present context identifier and a handle to find. The copy c'tor and = operator are not a part of the interface specification so they not implemented and made private. Let's see IsReserved now :-
...
static bool IsReserved(const CItem& item)
{
if(std::string(".")==item.GetInfo().cFileName ||
std::string("..")==item.GetInfo().cFileName) return true;
return false;
}
...The reserved items of a folder are the '.' directory and '..' directory.
Points of Interest
One interesting idea I got to protect the call back function changing the attributes of the class is to provide a wrapper to the actual function whose job is to copy the required attributes. If you have noticed the WalkI function does not use any member variables. The list of possible uses I can think of is in :-
- Walking through the MIB (snmp)
- Walking through binary tree
- Walking through linked list
- Walking through xml document/element
