1 /*!**************************************************************************** 2 3 @file PVRTSkipGraph.h 4 @copyright Copyright (c) Imagination Technologies Limited. 5 @brief A "tree-like" structure for storing data which, unlike a tree, can 6 reference any other node. 7 8 ******************************************************************************/ 9 #ifndef __PVRTSKIPGRAPH_H__ 10 #define __PVRTSKIPGRAPH_H__ 11 12 13 #include "PVRTArray.h" 14 #include "PVRTHash.h" 15 16 /*!*************************************************************************** 17 @class CPVRTSkipGraphNode 18 @brief Stores a pointer to the node's data and also uses a dynamic 19 array to store pointer to nodes this node depends on and 20 another to store pointers to nodes that are dependant on this node 21 *****************************************************************************/ 22 template<class T> 23 class CPVRTSkipGraphNode 24 { 25 private: 26 T m_pData; 27 CPVRTArray<CPVRTSkipGraphNode*> m_apDependencies; // What I depend on 28 CPVRTArray<CPVRTSkipGraphNode*> m_apDependents; // What depends on me 29 30 public: 31 /*!*************************************************************************** 32 @brief Constructor 33 *****************************************************************************/ CPVRTSkipGraphNode()34 CPVRTSkipGraphNode() 35 {} 36 37 /*!*************************************************************************** 38 @brief Overloaded constructor 39 @param[in] data Pointer to a node 40 *****************************************************************************/ CPVRTSkipGraphNode(const T & data)41 CPVRTSkipGraphNode(const T& data) : m_pData(data) 42 {} 43 44 /*!*************************************************************************** 45 @brief Destructor 46 *****************************************************************************/ ~CPVRTSkipGraphNode()47 ~CPVRTSkipGraphNode() 48 {} 49 50 /*!*************************************************************************** 51 @fn GetNumDependencies 52 @return unsigned int 53 @brief Returns the number of dependencies referenced by this node. 54 *****************************************************************************/ GetNumDependencies()55 unsigned int GetNumDependencies() const 56 { 57 return (unsigned int)m_apDependencies.GetSize(); 58 } 59 60 /*!*************************************************************************** 61 @fn GetDependency 62 @param[in] ui32Id 63 @return CPVRTSkipGraphNode & 64 @brief Returns given dependency. 65 *****************************************************************************/ GetDependency(const unsigned int ui32Id)66 CPVRTSkipGraphNode& GetDependency(const unsigned int ui32Id) const 67 { 68 _ASSERT(ui32Id >= 0 && ui32Id < (unsigned int)m_apDependencies.GetSize()); 69 return *m_apDependencies[ui32Id]; 70 } 71 72 73 /*!*************************************************************************** 74 @fn AddDependency 75 @param[out] pDependentNode 76 @return bool 77 @brief Adds a dependency to this node. 78 *****************************************************************************/ AddDependency(CPVRTSkipGraphNode * pDependentNode)79 bool AddDependency(CPVRTSkipGraphNode* pDependentNode) 80 { 81 unsigned int ui(0); 82 83 if(pDependentNode == this) 84 return false; 85 86 if(!pDependentNode) 87 return false; 88 89 /* 90 Check the dependency doesn't already exist 91 */ 92 for(ui = 0; ui < (unsigned int)m_apDependencies.GetSize(); ++ui) 93 { 94 if(m_apDependencies[ui] == pDependentNode) 95 { 96 return true; 97 } 98 } 99 100 /* 101 Add the dependency and also set this node as a dependent of 102 the referenced node 103 */ 104 m_apDependencies.Append(pDependentNode); 105 pDependentNode->AddDependent(this); 106 107 return true; 108 } 109 110 /*!*************************************************************************** 111 @fn GetData 112 @return T & 113 @brief Returns the data associated with this node. 114 *****************************************************************************/ GetData()115 T& GetData() 116 { 117 return m_pData; 118 } 119 120 private: 121 /*!*************************************************************************** 122 @fn AddDependent 123 @param[out] pDependancyNode 124 @return bool 125 @brief Adds a dependent to this node. 126 *****************************************************************************/ AddDependent(CPVRTSkipGraphNode * pDependencyNode)127 bool AddDependent(CPVRTSkipGraphNode* pDependencyNode) 128 { 129 unsigned int ui(0); 130 131 if(!pDependencyNode) 132 return false; 133 134 /* 135 Check the dependency doesn't already exist 136 */ 137 for(ui = 0; ui < (unsigned int)m_apDependents.GetSize(); ++ui) 138 { 139 if(m_apDependencies[ui] == pDependencyNode) 140 { 141 return true; 142 } 143 } 144 145 /* 146 Add the dependancy 147 */ 148 m_apDependents.Append(pDependencyNode); 149 return true; 150 } 151 }; 152 153 /*!*************************************************************************** 154 @class CPVRTSkipGraphRoot 155 @brief This class is the entry point for creating and accessing 156 the elements of a skip graph. It uses a hash table to store 157 the nodes of the structure and a hash value that allows 158 fast searching of the skip graph 159 *****************************************************************************/ 160 template<class T> 161 class CPVRTSkipGraphRoot 162 { 163 //-------------------------------------------------------------------------// 164 private: 165 166 /*!*************************************************************************** 167 @struct SPVRTHashElement 168 @brief A struct to store data and a hash value generated from the 169 data. The hash value allows faster searching of the skip graph. 170 *****************************************************************************/ 171 struct SPVRTHashElement 172 { 173 public: 174 /*!*************************************************************************** 175 @fn SPVRTHashElement 176 @param[in] hash 177 @param[in] data 178 @brief Overloaded constructor. 179 *****************************************************************************/ SPVRTHashElementSPVRTHashElement180 SPVRTHashElement(const CPVRTHash& hash, const T& data) 181 : 182 m_hash(hash), 183 m_skipGraphNode(data) 184 {} 185 186 /*!*************************************************************************** 187 @fn SPVRTHashElement 188 @brief Constructor 189 *****************************************************************************/ SPVRTHashElementSPVRTHashElement190 SPVRTHashElement() 191 {} 192 193 /*!*************************************************************************** 194 @fn ~SPVRTHashElement 195 @brief Destructor 196 *****************************************************************************/ ~SPVRTHashElementSPVRTHashElement197 ~SPVRTHashElement() 198 {} 199 200 /*!*************************************************************************** 201 @fn GetHash 202 @return unsigned int 203 @brief Returns the element's hash value. 204 *****************************************************************************/ GetHashSPVRTHashElement205 const CPVRTHash& GetHash() const 206 { 207 return m_hash; 208 } 209 210 /*!*************************************************************************** 211 @fn GetNode 212 @return CPVRTSkipGraphNode<T>& 213 @brief Return the node associated with this element. 214 *****************************************************************************/ GetNodeSPVRTHashElement215 CPVRTSkipGraphNode<T>& GetNode() 216 { 217 return m_skipGraphNode; 218 } 219 220 /*!*************************************************************************** 221 @fn GetNode 222 @return CPVRTSkipGraphNode<T>& 223 @brief Return the node associated with this element. 224 *****************************************************************************/ GetNodeSPVRTHashElement225 const CPVRTSkipGraphNode<T>& GetNode() const 226 { 227 return m_skipGraphNode; 228 } 229 230 private: 231 CPVRTHash m_hash; 232 CPVRTSkipGraphNode<T> m_skipGraphNode; 233 }; 234 235 236 CPVRTArray<SPVRTHashElement> m_aHashTable; 237 238 //-------------------------------------------------------------------------// 239 public: 240 241 /*!*************************************************************************** 242 @fn AddNode 243 @param[in] data The data of the node to be added 244 @return CPVRTSkipGraphNode<T>* const A handle to the added node 245 @brief Searches through the hash table to see if the added node already 246 exists. If it doesn't, it creates a node. 247 The function returns true if the node was found or was created 248 successfully. 249 *****************************************************************************/ AddNode(const T & data)250 bool AddNode(const T& data) 251 { 252 CPVRTHash NewNodeHash((void*)&data, sizeof(T), 1); 253 int iArrayElement(-1); 254 /* 255 First, search the hash table to see 256 if the node already exists 257 */ 258 CPVRTSkipGraphNode<T>* skipGraphNode(FindNode(NewNodeHash)); 259 260 if(skipGraphNode == NULL) 261 { 262 /* 263 The node wasn't found, so a new node needs to be 264 created 265 */ 266 iArrayElement = m_aHashTable.Append(SPVRTHashElement(NewNodeHash, data)); 267 268 /* 269 Now point to the new instance 270 */ 271 skipGraphNode = &m_aHashTable[iArrayElement].GetNode(); 272 } 273 274 return skipGraphNode ? true : false; 275 } 276 277 278 /*!*************************************************************************** 279 @brief Adds a node dependency. 280 @param[in] nodeData 281 @param[in] dependantData 282 @return bool 283 *****************************************************************************/ AddNodeDependency(const T & nodeData,const T & dependantData)284 bool AddNodeDependency(const T& nodeData, const T& dependantData) 285 { 286 CPVRTSkipGraphNode<T>* pNode(NULL); 287 CPVRTSkipGraphNode<T>* pDependantNode(NULL); 288 289 pNode = FindNode(nodeData); 290 if(!pNode) 291 { 292 return false; 293 } 294 295 pDependantNode = FindNode(dependantData); 296 if(!pDependantNode) 297 { 298 return false; 299 } 300 301 /* 302 Nodes are not allowed to self reference 303 */ 304 if(pNode == pDependantNode) 305 { 306 return false; 307 } 308 pNode->AddDependency(pDependantNode); 309 310 return true; 311 } 312 313 /*!*************************************************************************** 314 @fn GetNumNodes 315 @return unsigned int The total number of nodes 316 @brief Returns the total number of nodes in the skip graph. 317 *****************************************************************************/ GetNumNodes()318 unsigned int GetNumNodes() const 319 { 320 return (unsigned int)m_aHashTable.GetSize(); 321 } 322 323 /*!*************************************************************************** 324 @brief Returns a sorted list of dependencies for the specified 325 node. The list is ordered with the leaf nodes at the front, 326 followed by nodes that depend on them and so forth until 327 the root node is reached and added at the end of the list 328 @param[in] aOutputArray The dynamic array to store 329 the sorted results in 330 @param[in] ui32NodeID The ID of the root node for 331 the dependency search 332 *****************************************************************************/ RetreiveSortedDependencyList(CPVRTArray<T> & aOutputArray,const unsigned int ui32NodeID)333 void RetreiveSortedDependencyList(CPVRTArray<T> &aOutputArray, 334 const unsigned int ui32NodeID) 335 { 336 _ASSERT(ui32NodeID >= 0 && ui32NodeID < (unsigned int)m_aHashTable.GetSize()); 337 RecursiveSortedListAdd(aOutputArray, m_aHashTable[ui32NodeID].GetNode()); 338 } 339 340 /*!*************************************************************************** 341 @brief Overloads operator[] to returns a handle to the node data 342 for the specified ID 343 @return T& Handle to the node data 344 *****************************************************************************/ 345 T& operator[](const unsigned int ui32NodeID) 346 { 347 return *(GetNodeData(ui32NodeID)); 348 } 349 350 /*!*************************************************************************** 351 @brief Overloads operator[] to returns a const handle to the node 352 data for the specified ID 353 @return T& Handle to the node data 354 *****************************************************************************/ 355 const T& operator[](const unsigned int ui32NodeID) const 356 { 357 return *(GetNodeData(ui32NodeID)); 358 } 359 360 //-------------------------------------------------------------------------// 361 private: 362 /*!*************************************************************************** 363 @brief Recursively adds node dependancies to aOutputArray. 364 By doing so, aOutputArray will be ordered from leaf nodes to 365 the root node that started the recursive chain 366 @param[in] aOutputArray The dynamic array to store 367 the sorted results in 368 @param[in] currentNode The current node to process 369 *****************************************************************************/ RecursiveSortedListAdd(CPVRTArray<T> & aOutputArray,CPVRTSkipGraphNode<T> & currentNode)370 void RecursiveSortedListAdd(CPVRTArray<T> &aOutputArray, 371 CPVRTSkipGraphNode<T> ¤tNode) 372 { 373 unsigned int ui(0); 374 375 /* 376 Recursively add dependancies first 377 */ 378 for(ui = 0; ui < currentNode.GetNumDependencies(); ++ui) 379 { 380 RecursiveSortedListAdd(aOutputArray, currentNode.GetDependency(ui)); 381 } 382 383 /* 384 Then add this node to the array 385 */ 386 aOutputArray.Append(currentNode.GetData()); 387 } 388 389 /*!*************************************************************************** 390 @fn GetNodeData 391 @param[in,out] ui32NodeID The node's ID 392 @return T* A handle to node's data 393 @brief Retrieve a handle to the specified node's data 394 *****************************************************************************/ GetNodeData(unsigned int ui32NodeID)395 T* GetNodeData(unsigned int ui32NodeID) 396 { 397 _ASSERT(ui32NodeID >= 0 && ui32NodeID < (unsigned int)m_aHashTable.GetSize()); 398 return &m_aHashTable[ui32NodeID].GetNode().GetData(); 399 } 400 401 /*!*************************************************************************** 402 @brief Use the input hash to search the hash table and see if the 403 node already exists. If it does, the function returns a pointer 404 to the node. If it doesn't, it returns NULL 405 @param[in,out] ui32Hash The hash value to search with 406 @return CPVRTSkipGraphNode<T>* const A handle to the found node 407 *****************************************************************************/ FindNode(const CPVRTHash & Hash)408 CPVRTSkipGraphNode<T>* FindNode(const CPVRTHash& Hash) 409 { 410 int i(0); 411 int i32HashTableSize(m_aHashTable.GetSize()); 412 413 /* 414 A NULL hash means the node has not initialised 415 correctly 416 */ 417 if(Hash == 0) 418 return NULL; 419 420 /* 421 NOTE: 422 In the future, the hash table could be sorted from 423 lowest hash value to highest so that binary search could 424 be used to find a given node. It should be possible to 425 use a bool (or some other mechanism) to toggle this form of search 426 (if the skip graph is small, it might be faster to just use a brute 427 force for loop to search through) 428 */ 429 for(i = 0; i < i32HashTableSize; i++) 430 { 431 if(m_aHashTable[i].GetHash() == Hash) 432 { 433 return &m_aHashTable[i].GetNode(); 434 } 435 } 436 437 /* 438 The element wasn't found, so return null 439 */ 440 return NULL; 441 } 442 443 /*!*************************************************************************** 444 @brief Use the input data to generate a hash and then 445 search the hash table and see if the node already exists. 446 If it does, the function returns a pointer 447 to the node. If it doesn't, it returns NULL 448 @param[in,out] data Data to use as a source for the hash 449 @return CPVRTSkipGraphNode<T>* const A handle to the found node 450 *****************************************************************************/ FindNode(const T & data)451 CPVRTSkipGraphNode<T>* FindNode(const T& data) 452 { 453 CPVRTHash inputHash((void*)&data, sizeof(T), 1); // Generate hash for searching 454 return FindNode(inputHash); 455 } 456 }; 457 458 #endif //__PVRTSKIPGRAPH_H__ 459 460 /***************************************************************************** 461 End of file (PVRTSkipGraph.h) 462 *****************************************************************************/ 463 464