| /*!**************************************************************************** |
| |
| @file PVRTSkipGraph.h |
| @copyright Copyright (c) Imagination Technologies Limited. |
| @brief A "tree-like" structure for storing data which, unlike a tree, can |
| reference any other node. |
| |
| ******************************************************************************/ |
| #ifndef __PVRTSKIPGRAPH_H__ |
| #define __PVRTSKIPGRAPH_H__ |
| |
| |
| #include "PVRTArray.h" |
| #include "PVRTHash.h" |
| |
| /*!*************************************************************************** |
| @class CPVRTSkipGraphNode |
| @brief Stores a pointer to the node's data and also uses a dynamic |
| array to store pointer to nodes this node depends on and |
| another to store pointers to nodes that are dependant on this node |
| *****************************************************************************/ |
| template<class T> |
| class CPVRTSkipGraphNode |
| { |
| private: |
| T m_pData; |
| CPVRTArray<CPVRTSkipGraphNode*> m_apDependencies; // What I depend on |
| CPVRTArray<CPVRTSkipGraphNode*> m_apDependents; // What depends on me |
| |
| public: |
| /*!*************************************************************************** |
| @brief Constructor |
| *****************************************************************************/ |
| CPVRTSkipGraphNode() |
| {} |
| |
| /*!*************************************************************************** |
| @brief Overloaded constructor |
| @param[in] data Pointer to a node |
| *****************************************************************************/ |
| CPVRTSkipGraphNode(const T& data) : m_pData(data) |
| {} |
| |
| /*!*************************************************************************** |
| @brief Destructor |
| *****************************************************************************/ |
| ~CPVRTSkipGraphNode() |
| {} |
| |
| /*!*************************************************************************** |
| @fn GetNumDependencies |
| @return unsigned int |
| @brief Returns the number of dependencies referenced by this node. |
| *****************************************************************************/ |
| unsigned int GetNumDependencies() const |
| { |
| return (unsigned int)m_apDependencies.GetSize(); |
| } |
| |
| /*!*************************************************************************** |
| @fn GetDependency |
| @param[in] ui32Id |
| @return CPVRTSkipGraphNode & |
| @brief Returns given dependency. |
| *****************************************************************************/ |
| CPVRTSkipGraphNode& GetDependency(const unsigned int ui32Id) const |
| { |
| _ASSERT(ui32Id >= 0 && ui32Id < (unsigned int)m_apDependencies.GetSize()); |
| return *m_apDependencies[ui32Id]; |
| } |
| |
| |
| /*!*************************************************************************** |
| @fn AddDependency |
| @param[out] pDependentNode |
| @return bool |
| @brief Adds a dependency to this node. |
| *****************************************************************************/ |
| bool AddDependency(CPVRTSkipGraphNode* pDependentNode) |
| { |
| unsigned int ui(0); |
| |
| if(pDependentNode == this) |
| return false; |
| |
| if(!pDependentNode) |
| return false; |
| |
| /* |
| Check the dependency doesn't already exist |
| */ |
| for(ui = 0; ui < (unsigned int)m_apDependencies.GetSize(); ++ui) |
| { |
| if(m_apDependencies[ui] == pDependentNode) |
| { |
| return true; |
| } |
| } |
| |
| /* |
| Add the dependency and also set this node as a dependent of |
| the referenced node |
| */ |
| m_apDependencies.Append(pDependentNode); |
| pDependentNode->AddDependent(this); |
| |
| return true; |
| } |
| |
| /*!*************************************************************************** |
| @fn GetData |
| @return T & |
| @brief Returns the data associated with this node. |
| *****************************************************************************/ |
| T& GetData() |
| { |
| return m_pData; |
| } |
| |
| private: |
| /*!*************************************************************************** |
| @fn AddDependent |
| @param[out] pDependancyNode |
| @return bool |
| @brief Adds a dependent to this node. |
| *****************************************************************************/ |
| bool AddDependent(CPVRTSkipGraphNode* pDependencyNode) |
| { |
| unsigned int ui(0); |
| |
| if(!pDependencyNode) |
| return false; |
| |
| /* |
| Check the dependency doesn't already exist |
| */ |
| for(ui = 0; ui < (unsigned int)m_apDependents.GetSize(); ++ui) |
| { |
| if(m_apDependencies[ui] == pDependencyNode) |
| { |
| return true; |
| } |
| } |
| |
| /* |
| Add the dependancy |
| */ |
| m_apDependents.Append(pDependencyNode); |
| return true; |
| } |
| }; |
| |
| /*!*************************************************************************** |
| @class CPVRTSkipGraphRoot |
| @brief This class is the entry point for creating and accessing |
| the elements of a skip graph. It uses a hash table to store |
| the nodes of the structure and a hash value that allows |
| fast searching of the skip graph |
| *****************************************************************************/ |
| template<class T> |
| class CPVRTSkipGraphRoot |
| { |
| //-------------------------------------------------------------------------// |
| private: |
| |
| /*!*************************************************************************** |
| @struct SPVRTHashElement |
| @brief A struct to store data and a hash value generated from the |
| data. The hash value allows faster searching of the skip graph. |
| *****************************************************************************/ |
| struct SPVRTHashElement |
| { |
| public: |
| /*!*************************************************************************** |
| @fn SPVRTHashElement |
| @param[in] hash |
| @param[in] data |
| @brief Overloaded constructor. |
| *****************************************************************************/ |
| SPVRTHashElement(const CPVRTHash& hash, const T& data) |
| : |
| m_hash(hash), |
| m_skipGraphNode(data) |
| {} |
| |
| /*!*************************************************************************** |
| @fn SPVRTHashElement |
| @brief Constructor |
| *****************************************************************************/ |
| SPVRTHashElement() |
| {} |
| |
| /*!*************************************************************************** |
| @fn ~SPVRTHashElement |
| @brief Destructor |
| *****************************************************************************/ |
| ~SPVRTHashElement() |
| {} |
| |
| /*!*************************************************************************** |
| @fn GetHash |
| @return unsigned int |
| @brief Returns the element's hash value. |
| *****************************************************************************/ |
| const CPVRTHash& GetHash() const |
| { |
| return m_hash; |
| } |
| |
| /*!*************************************************************************** |
| @fn GetNode |
| @return CPVRTSkipGraphNode<T>& |
| @brief Return the node associated with this element. |
| *****************************************************************************/ |
| CPVRTSkipGraphNode<T>& GetNode() |
| { |
| return m_skipGraphNode; |
| } |
| |
| /*!*************************************************************************** |
| @fn GetNode |
| @return CPVRTSkipGraphNode<T>& |
| @brief Return the node associated with this element. |
| *****************************************************************************/ |
| const CPVRTSkipGraphNode<T>& GetNode() const |
| { |
| return m_skipGraphNode; |
| } |
| |
| private: |
| CPVRTHash m_hash; |
| CPVRTSkipGraphNode<T> m_skipGraphNode; |
| }; |
| |
| |
| CPVRTArray<SPVRTHashElement> m_aHashTable; |
| |
| //-------------------------------------------------------------------------// |
| public: |
| |
| /*!*************************************************************************** |
| @fn AddNode |
| @param[in] data The data of the node to be added |
| @return CPVRTSkipGraphNode<T>* const A handle to the added node |
| @brief Searches through the hash table to see if the added node already |
| exists. If it doesn't, it creates a node. |
| The function returns true if the node was found or was created |
| successfully. |
| *****************************************************************************/ |
| bool AddNode(const T& data) |
| { |
| CPVRTHash NewNodeHash((void*)&data, sizeof(T), 1); |
| int iArrayElement(-1); |
| /* |
| First, search the hash table to see |
| if the node already exists |
| */ |
| CPVRTSkipGraphNode<T>* skipGraphNode(FindNode(NewNodeHash)); |
| |
| if(skipGraphNode == NULL) |
| { |
| /* |
| The node wasn't found, so a new node needs to be |
| created |
| */ |
| iArrayElement = m_aHashTable.Append(SPVRTHashElement(NewNodeHash, data)); |
| |
| /* |
| Now point to the new instance |
| */ |
| skipGraphNode = &m_aHashTable[iArrayElement].GetNode(); |
| } |
| |
| return skipGraphNode ? true : false; |
| } |
| |
| |
| /*!*************************************************************************** |
| @brief Adds a node dependency. |
| @param[in] nodeData |
| @param[in] dependantData |
| @return bool |
| *****************************************************************************/ |
| bool AddNodeDependency(const T& nodeData, const T& dependantData) |
| { |
| CPVRTSkipGraphNode<T>* pNode(NULL); |
| CPVRTSkipGraphNode<T>* pDependantNode(NULL); |
| |
| pNode = FindNode(nodeData); |
| if(!pNode) |
| { |
| return false; |
| } |
| |
| pDependantNode = FindNode(dependantData); |
| if(!pDependantNode) |
| { |
| return false; |
| } |
| |
| /* |
| Nodes are not allowed to self reference |
| */ |
| if(pNode == pDependantNode) |
| { |
| return false; |
| } |
| pNode->AddDependency(pDependantNode); |
| |
| return true; |
| } |
| |
| /*!*************************************************************************** |
| @fn GetNumNodes |
| @return unsigned int The total number of nodes |
| @brief Returns the total number of nodes in the skip graph. |
| *****************************************************************************/ |
| unsigned int GetNumNodes() const |
| { |
| return (unsigned int)m_aHashTable.GetSize(); |
| } |
| |
| /*!*************************************************************************** |
| @brief Returns a sorted list of dependencies for the specified |
| node. The list is ordered with the leaf nodes at the front, |
| followed by nodes that depend on them and so forth until |
| the root node is reached and added at the end of the list |
| @param[in] aOutputArray The dynamic array to store |
| the sorted results in |
| @param[in] ui32NodeID The ID of the root node for |
| the dependency search |
| *****************************************************************************/ |
| void RetreiveSortedDependencyList(CPVRTArray<T> &aOutputArray, |
| const unsigned int ui32NodeID) |
| { |
| _ASSERT(ui32NodeID >= 0 && ui32NodeID < (unsigned int)m_aHashTable.GetSize()); |
| RecursiveSortedListAdd(aOutputArray, m_aHashTable[ui32NodeID].GetNode()); |
| } |
| |
| /*!*************************************************************************** |
| @brief Overloads operator[] to returns a handle to the node data |
| for the specified ID |
| @return T& Handle to the node data |
| *****************************************************************************/ |
| T& operator[](const unsigned int ui32NodeID) |
| { |
| return *(GetNodeData(ui32NodeID)); |
| } |
| |
| /*!*************************************************************************** |
| @brief Overloads operator[] to returns a const handle to the node |
| data for the specified ID |
| @return T& Handle to the node data |
| *****************************************************************************/ |
| const T& operator[](const unsigned int ui32NodeID) const |
| { |
| return *(GetNodeData(ui32NodeID)); |
| } |
| |
| //-------------------------------------------------------------------------// |
| private: |
| /*!*************************************************************************** |
| @brief Recursively adds node dependancies to aOutputArray. |
| By doing so, aOutputArray will be ordered from leaf nodes to |
| the root node that started the recursive chain |
| @param[in] aOutputArray The dynamic array to store |
| the sorted results in |
| @param[in] currentNode The current node to process |
| *****************************************************************************/ |
| void RecursiveSortedListAdd(CPVRTArray<T> &aOutputArray, |
| CPVRTSkipGraphNode<T> ¤tNode) |
| { |
| unsigned int ui(0); |
| |
| /* |
| Recursively add dependancies first |
| */ |
| for(ui = 0; ui < currentNode.GetNumDependencies(); ++ui) |
| { |
| RecursiveSortedListAdd(aOutputArray, currentNode.GetDependency(ui)); |
| } |
| |
| /* |
| Then add this node to the array |
| */ |
| aOutputArray.Append(currentNode.GetData()); |
| } |
| |
| /*!*************************************************************************** |
| @fn GetNodeData |
| @param[in,out] ui32NodeID The node's ID |
| @return T* A handle to node's data |
| @brief Retrieve a handle to the specified node's data |
| *****************************************************************************/ |
| T* GetNodeData(unsigned int ui32NodeID) |
| { |
| _ASSERT(ui32NodeID >= 0 && ui32NodeID < (unsigned int)m_aHashTable.GetSize()); |
| return &m_aHashTable[ui32NodeID].GetNode().GetData(); |
| } |
| |
| /*!*************************************************************************** |
| @brief Use the input hash to search the hash table and see if the |
| node already exists. If it does, the function returns a pointer |
| to the node. If it doesn't, it returns NULL |
| @param[in,out] ui32Hash The hash value to search with |
| @return CPVRTSkipGraphNode<T>* const A handle to the found node |
| *****************************************************************************/ |
| CPVRTSkipGraphNode<T>* FindNode(const CPVRTHash& Hash) |
| { |
| int i(0); |
| int i32HashTableSize(m_aHashTable.GetSize()); |
| |
| /* |
| A NULL hash means the node has not initialised |
| correctly |
| */ |
| if(Hash == 0) |
| return NULL; |
| |
| /* |
| NOTE: |
| In the future, the hash table could be sorted from |
| lowest hash value to highest so that binary search could |
| be used to find a given node. It should be possible to |
| use a bool (or some other mechanism) to toggle this form of search |
| (if the skip graph is small, it might be faster to just use a brute |
| force for loop to search through) |
| */ |
| for(i = 0; i < i32HashTableSize; i++) |
| { |
| if(m_aHashTable[i].GetHash() == Hash) |
| { |
| return &m_aHashTable[i].GetNode(); |
| } |
| } |
| |
| /* |
| The element wasn't found, so return null |
| */ |
| return NULL; |
| } |
| |
| /*!*************************************************************************** |
| @brief Use the input data to generate a hash and then |
| search the hash table and see if the node already exists. |
| If it does, the function returns a pointer |
| to the node. If it doesn't, it returns NULL |
| @param[in,out] data Data to use as a source for the hash |
| @return CPVRTSkipGraphNode<T>* const A handle to the found node |
| *****************************************************************************/ |
| CPVRTSkipGraphNode<T>* FindNode(const T& data) |
| { |
| CPVRTHash inputHash((void*)&data, sizeof(T), 1); // Generate hash for searching |
| return FindNode(inputHash); |
| } |
| }; |
| |
| #endif //__PVRTSKIPGRAPH_H__ |
| |
| /***************************************************************************** |
| End of file (PVRTSkipGraph.h) |
| *****************************************************************************/ |
| |
