Lines Matching refs:we
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
144 /* Now we seed the root node with the index being the
145 * highest left most bit we want to test, which limits the
151 /* And as we have nothing in here yet, we set both child pointers
159 * we use calloc() to initialise it.
172 /* the nodes are all gone now, so we need only free the memory
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
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
200 /* While we are descending the tree nodes...
210 * in the key we are searching for. The new next node is the
223 /* Here we have reached a node where the bitMap index is lower than
227 * we wanted, or if that key is not in the trie it is another key
242 return NULL; /* That key is not in the trie (note that we set the pointer to -1 if no payload) */
274 nextNode = m_root->get_leftN(); /* And assume we start to the left */
277 * key we are being asked to insert.
294 /* Bit at the required index was 0, so we traverse to the left
299 /* Here we have located the only node that can be reached by the
301 * we need to use to insert the new key.
305 /* We have located an exact match, but we will only append to the bucket chain
310 /* Yes, we are accepting duplicates
315 …* added as duplicate keys. We might need to revise this opinion if we end up having many duplicate…
330 /* We found the key is already there and we are not allowed duplicates in this
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
343 …xorKey = (key ^ nextNode->get_key() ); /* Gives 1 bits only where they differ then we find the l…
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
406 …* at bit 3, then we have the "skipped" bit case. But if that chain was Bit 4, Bit 2 and they diffe…
407 * then we have the easy bit <pun>.
410 * according to whether we skip the bit that differs or not.
431 /* Bit at the required index was 0, so we traverse to the left
437 /* We have located the correct insert point for this new key, so we need
467 /* Finally, we need to change the pointers at the node we located
514 * we need to descend any right nodes that are not back pointers
523 /* Now all the children are dealt with, we can destroy
538 /* The bucket entry is now gone, so we can free the memory for
602 // First see if we have enough room in the edges array to add the edge?
610 // Set the limit to what we have now
620 // Initialize the new bitmaps to ;indicate we have no edges defined yet
627 // Set the limit to what we have now
632 // If the edge was flagged as depending on itself, then we just
658 // And we are all set
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
679 return; // We don't do anything else if we found a cycle
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.
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
723 // First flag that we have visited this node
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
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
754 // Found an edge, make sure we visit and descend it
761 // At this point we will have visited all the dependencies
763 // So we just add the node into the sorted list at the
768 // Remove this node from the cycle list if we have not detected a cycle
790 // First we need a vector to populate with enough
792 // the maximum cycle we could detect which is all nodes such as 0->1->2->3->0
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
805 // Now traverse the nodes as if we were just going left to right, but
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.
823 // Break the loop if we detect a cycle as we have no need to go any
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
835 // we need to know how many we may have allocated and traverse them all.
839 // Having traversed all the nodes we were given, we
850 // To sort a vector, we first perform the
852 // we are given. This is just a convenience routine that allows you to
867 // Sort into an array, then we can use the array that is
877 return; // Do nothing if we detected a cycle
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
887 // We can only sort the entries that we have dude! The caller is
894 // in the vector as we don't want to duplicate them in a new vector. We
896 // acording to where we moved it last. Then we can just swap vector entries until
897 // we are done :-)
908 // Now we traverse the sorted array and moved the entries of
910 // table we just created. The index telsl us where in the vector the
918 // should be, then we skip moving it of course.
927 // at topo->sorted[i] may have already been swapped out though, so we
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.
942 // Having traversed all the entries, we have sorted the vector in place.