1ANTLR_BEGIN_NAMESPACE() 2 3template< class ImplTraits, class DataType > 4ANTLR_INLINE TrieEntry<ImplTraits, DataType>::TrieEntry(const DataType& data, TrieEntry* next) 5 :m_data(data) 6{ 7 m_next = next; 8} 9template< class ImplTraits, class DataType > 10ANTLR_INLINE DataType& TrieEntry<ImplTraits, DataType>::get_data() 11{ 12 return m_data; 13} 14template< class ImplTraits, class DataType > 15ANTLR_INLINE const DataType& TrieEntry<ImplTraits, DataType>::get_data() const 16{ 17 return m_data; 18} 19template< class ImplTraits, class DataType > 20ANTLR_INLINE TrieEntry<ImplTraits, DataType>* TrieEntry<ImplTraits, DataType>::get_next() const 21{ 22 return m_next; 23} 24 25template< class ImplTraits, class DataType > 26ANTLR_INLINE void TrieEntry<ImplTraits, DataType>::set_next( TrieEntry* next ) 27{ 28 m_next = next; 29} 30 31template< class ImplTraits, class DataType > 32ANTLR_INLINE ANTLR_UINT32 IntTrieNode<ImplTraits, DataType>::get_bitNum() const 33{ 34 return m_bitNum; 35} 36template< class ImplTraits, class DataType > 37ANTLR_INLINE ANTLR_INTKEY IntTrieNode<ImplTraits, DataType>::get_key() const 38{ 39 return m_key; 40} 41template< class ImplTraits, class DataType > 42ANTLR_INLINE typename IntTrieNode<ImplTraits, DataType>::BucketsType* IntTrieNode<ImplTraits, DataType>::get_buckets() const 43{ 44 return m_buckets; 45} 46template< class ImplTraits, class DataType > 47ANTLR_INLINE IntTrieNode<ImplTraits, DataType>* IntTrieNode<ImplTraits, DataType>::get_leftN() const 48{ 49 return m_leftN; 50} 51template< class ImplTraits, class DataType > 52ANTLR_INLINE IntTrieNode<ImplTraits, DataType>* IntTrieNode<ImplTraits, DataType>::get_rightN() const 53{ 54 return m_rightN; 55} 56template< class ImplTraits, class DataType > 57ANTLR_INLINE void IntTrieNode<ImplTraits, DataType>::set_bitNum( ANTLR_UINT32 bitNum ) 58{ 59 m_bitNum = bitNum; 60} 61template< class ImplTraits, class DataType > 62ANTLR_INLINE void IntTrieNode<ImplTraits, DataType>::set_key( ANTLR_INTKEY key ) 63{ 64 m_key = key; 65} 66template< class ImplTraits, class DataType > 67ANTLR_INLINE void IntTrieNode<ImplTraits, DataType>::set_buckets( BucketsType* buckets ) 68{ 69 m_buckets = buckets; 70} 71template< class ImplTraits, class DataType > 72ANTLR_INLINE void IntTrieNode<ImplTraits, DataType>::set_leftN( IntTrieNode* leftN ) 73{ 74 m_leftN = leftN; 75} 76template< class ImplTraits, class DataType > 77ANTLR_INLINE void IntTrieNode<ImplTraits, DataType>::set_rightN( IntTrieNode* rightN ) 78{ 79 m_rightN = rightN; 80} 81 82ANTLR_INLINE const ANTLR_UINT8* IntTrieBase::get_bitIndex() 83{ 84 static ANTLR_UINT8 bitIndex[256] = 85 { 86 0, // 0 - Just for padding 87 0, // 1 88 1, 1, // 2..3 89 2, 2, 2, 2, // 4..7 90 3, 3, 3, 3, 3, 3, 3, 3, // 8+ 91 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // 16+ 92 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 32+ 93 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 94 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 64+ 95 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 96 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 97 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 98 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 128+ 99 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 100 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 101 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 102 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 103 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 104 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 105 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 106 }; 107 return bitIndex; 108} 109 110ANTLR_INLINE const ANTLR_UINT64* IntTrieBase::get_bitMask() 111{ 112 static ANTLR_UINT64 bitMask[64] = 113 { 114 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL, 115 0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL, 116 0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL, 117 0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL, 118 0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL, 119 0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL, 120 0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL, 121 0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL, 122 0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL, 123 0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL, 124 0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL, 125 0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL, 126 0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL, 127 0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL, 128 0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL, 129 0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL 130 }; 131 132 return bitMask; 133} 134 135template< class ImplTraits, class DataType > 136IntTrie<ImplTraits, DataType>::IntTrie( ANTLR_UINT32 depth ) 137{ 138 /* Now we need to allocate the root node. This makes it easier 139 * to use the tree as we don't have to do anything special 140 * for the root node. 141 */ 142 m_root = new IntTrieNodeType; 143 144 /* Now we seed the root node with the index being the 145 * highest left most bit we want to test, which limits the 146 * keys in the trie. This is the trie 'depth'. The limit for 147 * this implementation is 63 (bits 0..63). 148 */ 149 m_root->set_bitNum( depth ); 150 151 /* And as we have nothing in here yet, we set both child pointers 152 * of the root node to point back to itself. 153 */ 154 m_root->set_leftN( m_root ); 155 m_root->set_rightN( m_root ); 156 m_count = 0; 157 158 /* Finally, note that the key for this root node is 0 because 159 * we use calloc() to initialise it. 160 */ 161 m_allowDups = false; 162 m_current = NULL; 163} 164 165template< class ImplTraits, class DataType > 166IntTrie<ImplTraits, DataType>::~IntTrie() 167{ 168 /* Descend from the root and free all the nodes 169 */ 170 delete m_root; 171 172 /* the nodes are all gone now, so we need only free the memory 173 * for the structure itself 174 */ 175} 176 177template< class ImplTraits, class DataType > 178typename IntTrie<ImplTraits, DataType>::TrieEntryType* IntTrie<ImplTraits, DataType>::get( ANTLR_INTKEY key) 179{ 180 IntTrieNodeType* thisNode; 181 IntTrieNodeType* nextNode; 182 183 if (m_count == 0) 184 return NULL; /* Nothing in this trie yet */ 185 186 /* Starting at the root node in the trie, compare the bit index 187 * of the current node with its next child node (starts left from root). 188 * When the bit index of the child node is greater than the bit index of the current node 189 * then by definition (as the bit index decreases as we descent the trie) 190 * we have reached a 'backward' pointer. A backward pointer means we 191 * have reached the only node that can be reached by the bits given us so far 192 * and it must either be the key we are looking for, or if not then it 193 * means the entry was not in the trie, and we return NULL. A backward pointer 194 * points back in to the tree structure rather than down (deeper) within the 195 * tree branches. 196 */ 197 thisNode = m_root; /* Start at the root node */ 198 nextNode = thisNode->get_leftN(); /* Examine the left node from the root */ 199 200 /* While we are descending the tree nodes... 201 */ 202 const ANTLR_UINT64* bitMask = this->get_bitMask(); 203 while( thisNode->get_bitNum() > nextNode->get_bitNum() ) 204 { 205 /* Next node now becomes the new 'current' node 206 */ 207 thisNode = nextNode; 208 209 /* We now test the bit indicated by the bitmap in the next node 210 * in the key we are searching for. The new next node is the 211 * right node if that bit is set and the left node it is not. 212 */ 213 if (key & bitMask[nextNode->get_bitNum()]) 214 { 215 nextNode = nextNode->get_rightN(); /* 1 is right */ 216 } 217 else 218 { 219 nextNode = nextNode->get_leftN(); /* 0 is left */ 220 } 221 } 222 223 /* Here we have reached a node where the bitMap index is lower than 224 * its parent. This means it is pointing backward in the tree and 225 * must therefore be a terminal node, being the only point than can 226 * be reached with the bits seen so far. It is either the actual key 227 * we wanted, or if that key is not in the trie it is another key 228 * that is currently the only one that can be reached by those bits. 229 * That situation would obviously change if the key was to be added 230 * to the trie. 231 * 232 * Hence it only remains to test whether this is actually the key or not. 233 */ 234 if (nextNode->get_key() == key) 235 { 236 /* This was the key, so return the entry pointer 237 */ 238 return nextNode->get_buckets(); 239 } 240 else 241 { 242 return NULL; /* That key is not in the trie (note that we set the pointer to -1 if no payload) */ 243 } 244} 245 246template< class ImplTraits, class DataType > 247bool IntTrie<ImplTraits, DataType>::del( ANTLR_INTKEY key) 248{ 249 IntTrieNodeType* p; 250 251 p = m_root; 252 253 return false; 254 255} 256 257template< class ImplTraits, class DataType > 258bool IntTrie<ImplTraits, DataType>::add( ANTLR_INTKEY key, const DataType& data ) 259{ 260 IntTrieNodeType* thisNode; 261 IntTrieNodeType* nextNode; 262 IntTrieNodeType* entNode; 263 ANTLR_UINT32 depth; 264 TrieEntryType* newEnt; 265 TrieEntryType* nextEnt; 266 ANTLR_INTKEY xorKey; 267 268 /* Cache the bit depth of this trie, which is always the highest index, 269 * which is in the root node 270 */ 271 depth = m_root->get_bitNum(); 272 273 thisNode = m_root; /* Start with the root node */ 274 nextNode = m_root->get_leftN(); /* And assume we start to the left */ 275 276 /* Now find the only node that can be currently reached by the bits in the 277 * key we are being asked to insert. 278 */ 279 const ANTLR_UINT64* bitMask = this->get_bitMask(); 280 while (thisNode->get_bitNum() > nextNode->get_bitNum() ) 281 { 282 /* Still descending the structure, next node becomes current. 283 */ 284 thisNode = nextNode; 285 286 if (key & bitMask[nextNode->get_bitNum()]) 287 { 288 /* Bit at the required index was 1, so travers the right node from here 289 */ 290 nextNode = nextNode->get_rightN(); 291 } 292 else 293 { 294 /* Bit at the required index was 0, so we traverse to the left 295 */ 296 nextNode = nextNode->get_leftN(); 297 } 298 } 299 /* Here we have located the only node that can be reached by the 300 * bits in the requested key. It could in fact be that key or the node 301 * we need to use to insert the new key. 302 */ 303 if (nextNode->get_key() == key) 304 { 305 /* We have located an exact match, but we will only append to the bucket chain 306 * if this trie accepts duplicate keys. 307 */ 308 if (m_allowDups ==true) 309 { 310 /* Yes, we are accepting duplicates 311 */ 312 newEnt = new TrieEntryType(data, NULL); 313 314 /* We want to be able to traverse the stored elements in the order that they were 315 * added as duplicate keys. We might need to revise this opinion if we end up having many duplicate keys 316 * as perhaps reverse order is just as good, so long as it is ordered. 317 */ 318 nextEnt = nextNode->get_buckets(); 319 while (nextEnt->get_next() != NULL) 320 { 321 nextEnt = nextEnt->get_next(); 322 } 323 nextEnt->set_next(newEnt); 324 325 m_count++; 326 return true; 327 } 328 else 329 { 330 /* We found the key is already there and we are not allowed duplicates in this 331 * trie. 332 */ 333 return false; 334 } 335 } 336 337 /* Here we have discovered the only node that can be reached by the bits in the key 338 * but we have found that this node is not the key we need to insert. We must find the 339 * the leftmost bit by which the current key for that node and the new key we are going 340 * to insert, differ. While this nested series of ifs may look a bit strange, experimentation 341 * showed that it allows a machine code path that works well with predicated execution 342 */ 343 xorKey = (key ^ nextNode->get_key() ); /* Gives 1 bits only where they differ then we find the left most 1 bit*/ 344 345 /* Most common case is a 32 bit key really 346 */ 347 const ANTLR_UINT8* bitIndex = this->get_bitIndex(); 348#ifdef ANTLR_USE_64BIT 349 if (xorKey & 0xFFFFFFFF00000000) 350 { 351 if (xorKey & 0xFFFF000000000000) 352 { 353 if (xorKey & 0xFF00000000000000) 354 { 355 depth = 56 + bitIndex[((xorKey & 0xFF00000000000000)>>56)]; 356 } 357 else 358 { 359 depth = 48 + bitIndex[((xorKey & 0x00FF000000000000)>>48)]; 360 } 361 } 362 else 363 { 364 if (xorKey & 0x0000FF0000000000) 365 { 366 depth = 40 + bitIndex[((xorKey & 0x0000FF0000000000)>>40)]; 367 } 368 else 369 { 370 depth = 32 + bitIndex[((xorKey & 0x000000FF00000000)>>32)]; 371 } 372 } 373 } 374 else 375#endif 376 { 377 if (xorKey & 0x00000000FFFF0000) 378 { 379 if (xorKey & 0x00000000FF000000) 380 { 381 depth = 24 + bitIndex[((xorKey & 0x00000000FF000000)>>24)]; 382 } 383 else 384 { 385 depth = 16 + bitIndex[((xorKey & 0x0000000000FF0000)>>16)]; 386 } 387 } 388 else 389 { 390 if (xorKey & 0x000000000000FF00) 391 { 392 depth = 8 + bitIndex[((xorKey & 0x0000000000000FF00)>>8)]; 393 } 394 else 395 { 396 depth = bitIndex[xorKey & 0x00000000000000FF]; 397 } 398 } 399 } 400 401 /* We have located the leftmost differing bit, indicated by the depth variable. So, we know what 402 * bit index we are to insert the new entry at. There are two cases, being where the two keys 403 * differ at a bit position that is not currently part of the bit testing, where they differ on a bit 404 * that is currently being skipped in the indexed comparisons, and where they differ on a bit 405 * that is merely lower down in the current bit search. If the bit index went bit 4, bit 2 and they differ 406 * at bit 3, then we have the "skipped" bit case. But if that chain was Bit 4, Bit 2 and they differ at bit 1 407 * then we have the easy bit <pun>. 408 * 409 * So, set up to descend the tree again, but this time looking for the insert point 410 * according to whether we skip the bit that differs or not. 411 */ 412 thisNode = m_root; 413 entNode = m_root->get_leftN(); 414 415 /* Note the slight difference in the checks here to cover both cases 416 */ 417 while (thisNode->get_bitNum() > entNode->get_bitNum() && entNode->get_bitNum() > depth) 418 { 419 /* Still descending the structure, next node becomes current. 420 */ 421 thisNode = entNode; 422 423 if (key & bitMask[entNode->get_bitNum()]) 424 { 425 /* Bit at the required index was 1, so traverse the right node from here 426 */ 427 entNode = entNode->get_rightN(); 428 } 429 else 430 { 431 /* Bit at the required index was 0, so we traverse to the left 432 */ 433 entNode = entNode->get_leftN(); 434 } 435 } 436 437 /* We have located the correct insert point for this new key, so we need 438 * to allocate our entry and insert it etc. 439 */ 440 nextNode = new IntTrieNodeType(); 441 442 /* Build a new entry block for the new node 443 */ 444 newEnt = new TrieEntryType(data, NULL); 445 446 /* Install it 447 */ 448 nextNode->set_buckets(newEnt); 449 nextNode->set_key(key); 450 nextNode->set_bitNum( depth ); 451 452 /* Work out the right and left pointers for this new node, which involve 453 * terminating with the current found node either right or left according 454 * to whether the current index bit is 1 or 0 455 */ 456 if (key & bitMask[depth]) 457 { 458 nextNode->set_leftN(entNode); /* Terminates at previous position */ 459 nextNode->set_rightN(nextNode); /* Terminates with itself */ 460 } 461 else 462 { 463 nextNode->set_rightN(entNode); /* Terminates at previous position */ 464 nextNode->set_leftN(nextNode); /* Terminates with itself */ 465 } 466 467 /* Finally, we need to change the pointers at the node we located 468 * for inserting. If the key bit at its index is set then the right 469 * pointer for that node becomes the newly created node, otherwise the left 470 * pointer does. 471 */ 472 if (key & bitMask[thisNode->get_bitNum()] ) 473 { 474 thisNode->set_rightN( nextNode ); 475 } 476 else 477 { 478 thisNode->set_leftN(nextNode); 479 } 480 481 /* Et voila 482 */ 483 m_count++; 484 return true; 485} 486 487template< class ImplTraits, class DataType > 488IntTrieNode<ImplTraits, DataType>::IntTrieNode() 489{ 490 m_bitNum = 0; 491 m_key = 0; 492 m_buckets = NULL; 493 m_leftN = NULL; 494 m_rightN = NULL; 495} 496 497template< class ImplTraits, class DataType > 498IntTrieNode<ImplTraits, DataType>::~IntTrieNode() 499{ 500 TrieEntryType* thisEntry; 501 TrieEntryType* nextEntry; 502 503 /* If this node has a left pointer that is not a back pointer 504 * then recursively call to free this 505 */ 506 if ( m_bitNum > m_leftN->get_bitNum()) 507 { 508 /* We have a left node that needs descending, so do it. 509 */ 510 delete m_leftN; 511 } 512 513 /* The left nodes from here should now be dealt with, so 514 * we need to descend any right nodes that are not back pointers 515 */ 516 if ( m_bitNum > m_rightN->get_bitNum() ) 517 { 518 /* There are some right nodes to descend and deal with. 519 */ 520 delete m_rightN; 521 } 522 523 /* Now all the children are dealt with, we can destroy 524 * this node too 525 */ 526 thisEntry = m_buckets; 527 528 while (thisEntry != NULL) 529 { 530 nextEntry = thisEntry->get_next(); 531 532 /* Now free the data for this bucket entry 533 */ 534 delete thisEntry; 535 thisEntry = nextEntry; /* See if there are any more to free */ 536 } 537 538 /* The bucket entry is now gone, so we can free the memory for 539 * the entry itself. 540 */ 541 542 /* And that should be it for everything under this node and itself 543 */ 544} 545 546/** 547 * Allocate and initialize a new ANTLR3 topological sorter, which can be 548 * used to define edges that identify numerical node indexes that depend on other 549 * numerical node indexes, which can then be sorted topologically such that 550 * any node is sorted after all its dependent nodes. 551 * 552 * Use: 553 * 554 * /verbatim 555 556 pANTLR3_TOPO topo; 557 topo = antlr3NewTopo(); 558 559 if (topo == NULL) { out of memory } 560 561 topo->addEdge(topo, 3, 0); // Node 3 depends on node 0 562 topo->addEdge(topo, 0, 1); // Node - depends on node 1 563 topo->sortVector(topo, myVector); // Sort the vector in place (node numbers are the vector entry numbers) 564 565 * /verbatim 566 */ 567template<class ImplTraits> 568Topo<ImplTraits>::Topo() 569{ 570 // Initialize variables 571 // 572 m_visited = NULL; // Don't know how big it is yet 573 m_limit = 1; // No edges added yet 574 m_edges = NULL; // No edges added yet 575 m_sorted = NULL; // Nothing sorted at the start 576 m_cycle = NULL; // No cycles at the start 577 m_cycleMark = 0; // No cycles at the start 578 m_hasCycle = false; // No cycle at the start 579} 580 581// Topological sorter 582// 583template<class ImplTraits> 584void Topo<ImplTraits>::addEdge(ANTLR_UINT32 edge, ANTLR_UINT32 dependency) 585{ 586 ANTLR_UINT32 i; 587 ANTLR_UINT32 maxEdge; 588 BitsetType* edgeDeps; 589 590 if (edge>dependency) 591 { 592 maxEdge = edge; 593 } 594 else 595 { 596 maxEdge = dependency; 597 } 598 // We need to add an edge to says that the node indexed by 'edge' is 599 // dependent on the node indexed by 'dependency' 600 // 601 602 // First see if we have enough room in the edges array to add the edge? 603 // 604 if ( m_edges == NULL) 605 { 606 // We don't have any edges yet, so create an array to hold them 607 // 608 m_edges = AllocPolicyType::alloc0(sizeof(BitsetType*) * (maxEdge + 1)); 609 610 // Set the limit to what we have now 611 // 612 m_limit = maxEdge + 1; 613 } 614 else if (m_limit <= maxEdge) 615 { 616 // WE have some edges but not enough 617 // 618 m_edges = AllocPolicyType::realloc(m_edges, sizeof(BitsetType*) * (maxEdge + 1)); 619 620 // Initialize the new bitmaps to ;indicate we have no edges defined yet 621 // 622 for (i = m_limit; i <= maxEdge; i++) 623 { 624 *((m_edges) + i) = NULL; 625 } 626 627 // Set the limit to what we have now 628 // 629 m_limit = maxEdge + 1; 630 } 631 632 // If the edge was flagged as depending on itself, then we just 633 // do nothing as it means this routine was just called to add it 634 // in to the list of nodes. 635 // 636 if (edge == dependency) 637 { 638 return; 639 } 640 641 // Pick up the bit map for the requested edge 642 // 643 edgeDeps = *((m_edges) + edge); 644 645 if (edgeDeps == NULL) 646 { 647 // No edges are defined yet for this node 648 // 649 edgeDeps = new BitsetType(0); 650 *((m_edges) + edge) = edgeDeps; 651 } 652 653 // Set the bit in the bitmap that corresponds to the requested 654 // dependency. 655 // 656 edgeDeps->add(dependency); 657 658 // And we are all set 659 // 660 return; 661 662} 663 664/** 665 * Given a starting node, descend its dependent nodes (ones that it has edges 666 * to) until we find one without edges. Having found a node without edges, we have 667 * discovered the bottom of a depth first search, which we can then ascend, adding 668 * the nodes in order from the bottom, which gives us the dependency order. 669 */ 670template<class ImplTraits> 671void Topo<ImplTraits>::DFS(ANTLR_UINT32 node) 672{ 673 BitsetType* edges; 674 675 // Guard against a revisit and check for cycles 676 // 677 if (m_hasCycle == true) 678 { 679 return; // We don't do anything else if we found a cycle 680 } 681 682 if ( m_visited->isMember(node)) 683 { 684 // Check to see if we found a cycle. To do this we search the 685 // current cycle stack and see if we find this node already in the stack. 686 // 687 ANTLR_UINT32 i; 688 689 for (i=0; i< m_cycleMark; i++) 690 { 691 if ( m_cycle[i] == node) 692 { 693 // Stop! We found a cycle in the input, so rejig the cycle 694 // stack so that it only contains the cycle and set the cycle flag 695 // which will tell the caller what happened 696 // 697 ANTLR_UINT32 l; 698 699 for (l = i; l < m_cycleMark; l++) 700 { 701 m_cycle[l - i] = m_cycle[l]; // Move to zero base in the cycle list 702 } 703 704 // Recalculate the limit 705 // 706 m_cycleMark -= i; 707 708 // Signal disaster 709 // 710 m_hasCycle = true; 711 } 712 } 713 return; 714 } 715 716 // So far, no cycles have been found and we have not visited this node yet, 717 // so this node needs to go into the cycle stack before we continue 718 // then we will take it out of the stack once we have descended all its 719 // dependencies. 720 // 721 m_cycle[m_cycleMark++] = node; 722 723 // First flag that we have visited this node 724 // 725 m_visited->add(node); 726 727 // Now, if this node has edges, then we want to ensure we visit 728 // them all before we drop through and add this node into the sorted 729 // list. 730 // 731 edges = *((m_edges) + node); 732 if (edges != NULL) 733 { 734 // We have some edges, so visit each of the edge nodes 735 // that have not already been visited. 736 // 737 ANTLR_UINT32 numBits; // How many bits are in the set 738 ANTLR_UINT32 i; 739 ANTLR_UINT32 range; 740 741 numBits = edges->numBits(); 742 range = edges->size(); // Number of set bits 743 744 // Stop if we exahust the bit list or have checked the 745 // number of edges that this node refers to (so we don't 746 // check bits at the end that cannot possibly be set). 747 // 748 for (i=0; i<= numBits && range > 0; i++) 749 { 750 if (edges->isMember(i)) 751 { 752 range--; // About to check another one 753 754 // Found an edge, make sure we visit and descend it 755 // 756 this->DFS(i); 757 } 758 } 759 } 760 761 // At this point we will have visited all the dependencies 762 // of this node and they will be ordered (even if there are cycles) 763 // So we just add the node into the sorted list at the 764 // current index position. 765 // 766 m_sorted[m_limit++] = node; 767 768 // Remove this node from the cycle list if we have not detected a cycle 769 // 770 if (m_hasCycle == false) 771 { 772 m_cycleMark--; 773 } 774 775 return; 776} 777 778template<class ImplTraits> 779ANTLR_UINT32* Topo<ImplTraits>::sortToArray() 780{ 781 ANTLR_UINT32 v; 782 ANTLR_UINT32 oldLimit; 783 784 // Guard against being called with no edges defined 785 // 786 if (m_edges == NULL) 787 { 788 return 0; 789 } 790 // First we need a vector to populate with enough 791 // entries to accomodate the sorted list and another to accomodate 792 // the maximum cycle we could detect which is all nodes such as 0->1->2->3->0 793 // 794 m_sorted = AllocPolicyType::alloc( m_limit * sizeof(ANTLR_UINT32) ); 795 m_cycle = AllocPolicyType::alloc( m_limit * sizeof(ANTLR_UINT32)); 796 797 // Next we need an empty bitset to show whether we have visited a node 798 // or not. This is the bit that gives us linear time of course as we are essentially 799 // dropping through the nodes in depth first order and when we get to a node that 800 // has no edges, we pop back up the stack adding the nodes we traversed in reverse 801 // order. 802 // 803 m_visited = new BitsetType(0); 804 805 // Now traverse the nodes as if we were just going left to right, but 806 // then descend each node unless it has already been visited. 807 // 808 oldLimit = m_limit; // Number of nodes to traverse linearly 809 m_limit = 0; // Next entry in the sorted table 810 811 for (v = 0; v < oldLimit; v++) 812 { 813 // If we did not already visit this node, then descend it until we 814 // get a node without edges or arrive at a node we have already visited. 815 // 816 if (m_visited->isMember(v) == false) 817 { 818 // We have not visited this one so descend it 819 // 820 this->DFS(v); 821 } 822 823 // Break the loop if we detect a cycle as we have no need to go any 824 // further 825 // 826 if (m_hasCycle == true) 827 { 828 break; 829 } 830 } 831 832 // Reset the limit to the number we recorded as if we hit a 833 // cycle, then limit will have stopped at the node where we 834 // discovered the cycle, but in order to free the edge bitmaps 835 // we need to know how many we may have allocated and traverse them all. 836 // 837 m_limit = oldLimit; 838 839 // Having traversed all the nodes we were given, we 840 // are guaranteed to have ordered all the nodes or detected a 841 // cycle. 842 // 843 return m_sorted; 844} 845 846template<class ImplTraits> 847 template<typename DataType> 848void Topo<ImplTraits>::sortVector( typename ImplTraits::template VectorType<DataType>& v ) 849{ 850 // To sort a vector, we first perform the 851 // sort to an array, then use the results to reorder the vector 852 // we are given. This is just a convenience routine that allows you to 853 // sort the children of a tree node into topological order before or 854 // during an AST walk. This can be useful for optimizations that require 855 // dag reorders and also when the input stream defines thigns that are 856 // interdependent and you want to walk the list of the generated trees 857 // for those things in topological order so you can ignore the interdependencies 858 // at that point. 859 // 860 ANTLR_UINT32 i; 861 862 // Used as a lookup index to find the current location in the vector of 863 // the vector entry that was originally at position [0], [1], [2] etc 864 // 865 ANTLR_UINT32* vIndex; 866 867 // Sort into an array, then we can use the array that is 868 // stored in the topo 869 // 870 if (this->sortToArray() == 0) 871 { 872 return; // There were no edges 873 } 874 875 if (m_hasCycle == true) 876 { 877 return; // Do nothing if we detected a cycle 878 } 879 880 // Ensure that the vector we are sorting is at least as big as the 881 // the input sequence we were adsked to sort. It does not matter if it is 882 // bigger as thaat probably just means that nodes numbered higher than the 883 // limit had no dependencies and so can be left alone. 884 // 885 if (m_limit > v.size() ) 886 { 887 // We can only sort the entries that we have dude! The caller is 888 // responsible for ensuring the vector is the correct one and is the 889 // correct size etc. 890 // 891 m_limit = v.size(); 892 } 893 // We need to know the locations of each of the entries 894 // in the vector as we don't want to duplicate them in a new vector. We 895 // just use an indirection table to get the vector entry for a particular sequence 896 // acording to where we moved it last. Then we can just swap vector entries until 897 // we are done :-) 898 // 899 vIndex = AllocPolicyType::alloc(m_limit * sizeof(ANTLR_UINT32)); 900 901 // Start index, each vector entry is located where you think it is 902 // 903 for (i = 0; i < m_limit; i++) 904 { 905 vIndex[i] = i; 906 } 907 908 // Now we traverse the sorted array and moved the entries of 909 // the vector around according to the sort order and the indirection 910 // table we just created. The index telsl us where in the vector the 911 // original element entry n is now located via vIndex[n]. 912 // 913 for (i=0; i < m_limit; i++) 914 { 915 ANTLR_UINT32 ind; 916 917 // If the vector entry at i is already the one that it 918 // should be, then we skip moving it of course. 919 // 920 if (vIndex[m_sorted[i]] == i) 921 { 922 continue; 923 } 924 925 // The vector entry at i, should be replaced with the 926 // vector entry indicated by topo->sorted[i]. The vector entry 927 // at topo->sorted[i] may have already been swapped out though, so we 928 // find where it is now and move it from there to i. 929 // 930 ind = vIndex[m_sorted[i]]; 931 std::swap( v[i], v[ind] ); 932 933 // Update our index. The element at i is now the one we wanted 934 // to be sorted here and the element we swapped out is now the 935 // element that was at i just before we swapped it. If you are lost now 936 // don't worry about it, we are just reindexing on the fly is all. 937 // 938 vIndex[m_sorted[i]] = i; 939 vIndex[i] = ind; 940 } 941 942 // Having traversed all the entries, we have sorted the vector in place. 943 // 944 AllocPolicyType::free(vIndex); 945 return; 946} 947 948template<class ImplTraits> 949Topo<ImplTraits>::~Topo() 950{ 951 ANTLR_UINT32 i; 952 953 // Free the result vector 954 // 955 if (m_sorted != NULL) 956 { 957 AllocPolicyType::free(m_sorted); 958 } 959 960 // Free the visited map 961 // 962 if (m_visited != NULL) 963 { 964 delete m_visited; 965 } 966 967 // Free any edgemaps 968 // 969 if (m_edges != NULL) 970 { 971 Bitset<AllocPolicyType>* edgeList; 972 973 for (i=0; i<m_limit; i++) 974 { 975 edgeList = *((m_edges) + i); 976 if (edgeList != NULL) 977 { 978 delete edgeList; 979 } 980 } 981 982 AllocPolicyType::free( m_edges ); 983 } 984 m_edges = NULL; 985 986 // Free any cycle map 987 // 988 if (m_cycle != NULL) 989 { 990 AllocPolicyType::free(m_cycle); 991 } 992} 993 994 995ANTLR_END_NAMESPACE() 996