Chapter 5: Case Studies I
5.1 Case Study 1
5.1.1 The program
The purpose of the case studies in this book is to demonstrate the use of some of the concepts presented in the preceding chapters. The defects analyzed are the actual mistakes made by the author when developing this software. Different people are prone to make different mistakes. Focus on the method used in debugging, rather than the particular error in question.
The algorithms implemented in the case studies for this book were chosen based on the following criteria:
-
There is a published design in pseudocode for the algorithm accessible in the computer science literature.
-
The implementation should follow the original design relatively closely so that it is easy to compare it with the design.
-
The algorithm computes a useful result. Toy programs do not make interesting examples.
-
The algorithm has excellent computational complexity. Toy programs do not make convincing examples.
-
The algorithm is complicated enough that some bugs would likely occur in implementing it.
The program we debug in this section is a heap sort that works on linked list structures. Heap sorts are usually explained in an undergraduate course in data structures. The data-structure books we reviewed for this example present heap sorts of integer data stored in arrays. See Algorithms in C++ (3rd ed.) [Se98] for an excellent analysis of array-based heap sorts. This example presents a heap sort that works on linked lists, written in C++.
The data-structure books present array-based heap sorts because they can be coded very concisely. The linked-list heap sort requires a great deal more code. Some people say that if you want to sort a linked list, you should copy it into an array, sort the array, and then copy it back into another linked list. This approach works fine for small linked lists. The cost of copying data and allocating storage, as well as the extra memory required, make this approach prohibitive for large lists or small memory systems.
The first step in a heap sort is to insert all of the elements to be sorted into a heap structure. A common way to represent a heap is with a complete binary tree. A complete binary tree is created by appending nodes to the tree from left to right on a given level of the tree and starting a new level only when the current level is full.
If we create a binary tree such that the keys of the nodes satisfy the heap condition, we have represented a heap with a binary tree. The heap condition is the following: The key in each node is greater than or equal to the keys in any of its children. The largest key is stored in the root node of the tree.
After the heap is constructed, the sort loops as many times as there are elements. Each iteration of the loop removes the largest element from the heap and restructures the heap so that it retains the heap property.
The code for the original program is listed as follows:
#ifndef _Heap_h_ #define _Heap_h_ class Heap { public: // constructors and destructors Heap(int, int); Heap(int, int *); // accessors inline int getKey() { return _key; } inline int getID() { return _id; } inline Heap * getLeft() { return _left; } inline Heap * getRight() { return _right; } inline Heap * getParent() { return _parent; } inline Heap * getPred() { return _pred; } inline Heap * getSucc() { return _succ; } inline Heap * getRoot() { return _root; } inline Heap * getActive() { return _active; } inline Heap * getLast() { return _last; } inline Heap * getFrontier() { return _frontier; } inline int getPower() { return _power; } // mutators inline void setKey(int x) { _key= x; } inline void setID(int x) { _id= x; } inline void setLeft(Heap * x) { _left= x; } inline void setRight(Heap * x) { _right= x; } inline void setParent(Heap * x) { _parent= x; } inline void setPred(Heap * x) { _pred= x; } inline void setSucc(Heap * x) { _succ= x; } inline void setRoot(Heap *x) { _root= x; } inline void setActive(Heap *x) { _active= x; } inline void setLast(Heap *x) { _last= x; } inline void setFrontier(Heap *x) { _frontier= x; } inline void setPower(int x) { _power= x; } // workers void insert(); void movedown(); void moveup(); Heap * remove(); void replace(Heap *); Heap * sort(); void print(); private: static Heap * _root; static Heap * _active; static Heap * _last; static Heap * _frontier; static int _power; int _key; int _id; Heap * _left; Heap * _right; Heap * _parent; Heap * _pred; Heap * _succ; }; void list(Heap *); void draw(Heap *); #endif ________________________________________________________ #include <stdio.h> #include <stdlib.h> #include <assert.h> #include “Heap.h” //----------------------------------------------------- // static variables //----------------------------------------------------- Heap * Heap::_root; Heap * Heap::_active; Heap * Heap::_last; Heap * Heap::_frontier; int Heap::_power; //----------------------------------------------------- // construct an individual heap node //----------------------------------------------------- Heap::Heap(int x, int y) { _key= x; _id= y; _left= 0; _right= 0; _parent= 0; _pred= 0; _succ= 0; } //----------------------------------------------------- // construct a heap from the provided data // the node returned is located somewhere on the heap // to get the root: // Heap *n= new Heap(count,values); // Heap *root= n->getRoot(); //----------------------------------------------------- Heap::Heap(int n, int *x ) { _key= x[0]; _id= 1; _left= 0; _right= 0; _parent= 0; _pred= 0; _succ= 0; _root= this; _active= this; _last= 0; _frontier= 0; _power= 2; for( int i= 1; i < n; ++i ) { Heap *node= new Heap(x[i], i+1); node->insert(); node->moveup(); } } //----------------------------------------------------- // insert a Heap node at the end of the heap //----------------------------------------------------- void Heap::insert() { this->setPred(0); this->setSucc(0); if( _active->getLeft() == 0 ) { _active->setLeft(this); this->setParent(_active); if ( this->getID() == _power ) { _frontier= this; _power *= 2; } _last= this; } else if( _active->getRight() == 0 ) { _active->setRight(this); this->setParent(_active); _last->setSucc(this); this->setPred(_last); if ( this->getID() == _power-1 ) { _active= _frontier; } _last= this; } else { _active= _last->getParent()->getSucc(); if( _active == 0 ) { _active= _frontier; } else { _active->setLeft(this); this->setParent(_active); } _last->setSucc(this); this->setPred(_last); _last= this; } } //----------------------------------------------------- // re-arrange the heap after appending a node at the // end of the binary tree so that the heap property // is preserved //----------------------------------------------------- void Heap::moveup() { Heap *temp; while( true ) { Heap * parent= this->getParent(); if( !parent || parent->getKey() >= this->getKey() ) { break; } // swap ID numbers int swap= parent->getID(); parent->setID(this->getID()); this->setID(swap); // swap incoming vertical pointers Heap * grand= parent->getParent(); if( grand != 0 ) { if( parent == grand->getLeft() ) { grand->setLeft(this); } else if( parent == grand->getRight() ) { grand->setRight(this); } } // swap outgoing vertical pointers parent->setParent(this); this->setParent(grand); if( this == parent->getLeft() ) { if( this->getLeft() != 0 ) { this->getLeft()->setParent(parent); } parent->setLeft(this->getLeft()); this->setLeft(parent); if( this->getRight() != 0 ) { if( parent->getRight() != 0 ) { temp= parent->getRight() ->getParent(); parent->getRight()->setParent(this-> getRight()->getParent()); this->getRight()->setParent(temp); } else { this->getRight()->setParent(0); } } else { if( parent->getRight() != 0 ) { parent->getRight()->setParent(0); } } temp= this->getRight(); this->setRight(parent->getRight()); parent->setRight(temp); } else if( this == parent->getRight() ) { if( this->getRight() != 0 ) { this->getRight()->setParent(parent); } parent->setRight(this->getRight()); this->setRight(parent); if( this->getLeft() != 0 ) { if( parent->getLeft() != 0 ) { temp= parent->getLeft()->getParent(); parent->getLeft()->setParent(this-> getLeft()->getParent()); this->getLeft()->setParent(temp); } else { this->getLeft()->setParent(0); } } else { if( parent->getLeft() != 0 ) { parent->getLeft()->setParent(0); } } temp= this->getLeft(); this->setLeft(parent->getLeft()); parent->setLeft(temp); } else { assert(0); } // swap incoming horizontal pointers if( this->getPred() != 0 ) { if( parent->getPred() != 0 ) { temp= parent->getPred()->getSucc(); parent->getPred()->setSucc( this->getPred() ->getSucc()); this->getPred()->setSucc(temp); } else { this->getPred()->setSucc(0); } } else { if( parent->getPred() != 0 ) { parent->getPred()->setSucc(0); } } if( this->getSucc() != 0 ) { if( parent->getSucc() != 0 ) { temp= parent->getSucc()->getPred(); parent->getSucc()->setPred( this->getSucc() ->getPred()); this->getSucc()->setPred(temp); } else { this->getSucc()->setPred(0); } } else { if( parent->getSucc() != 0 ) { parent->getSucc()->setPred(0); } } // swap outgoing horizontal pointers temp= parent->getPred(); parent->setPred(this->getPred()); this->setPred(temp); temp= parent->getSucc(); parent->setSucc(this->getSucc()); this->setSucc(temp); // update variables _active= _last->getParent(); if( _root == parent ) { _root= this; } _last= parent; _active= this; if ( _root == parent ) { _root= this; } } } //----------------------------------------------------- // re-arrange the heap after inserting a new root node // in the binary tree so that the heap property // is preserved //----------------------------------------------------- void Heap::movedown() { Heap *temp, *child; while( true ) { Heap * left= this->getLeft(); Heap * right= this->getRight(); if( left != 0 && right != 0 ) { if( left->getKey() <= this->getKey() && right->getKey() <= this->getKey() ) { break; } else { child= (left->getKey() >= right->getKey()) ? left : right; } } else if ( left != 0 ) { if( left->getKey() <= this->getKey() ) { break; } else { child= left; } } else { break; } // swap ID numbers int swap= this->getID(); this->setID(child->getID()); child->setID(swap); // swap incoming vertical pointers Heap * grand= this->getParent(); if( grand != 0 ) { if( this == grand->getLeft() ) { grand->setLeft(child); } else if( this == grand->getRight() ) { grand->setRight(child); } } // swap outgoing vertical pointers this->setParent(child); child->setParent(grand); if( child == this->getLeft() ) { if( child->getLeft() != 0 ) { child->getLeft()->setParent(this); } this->setLeft(child->getLeft()); child->setLeft(this); if( child->getRight() != 0 ) { if( this->getRight() != 0 ) { temp= this->getRight()->getParent(); this->getRight()->setParent(child-> getRight()->getParent()); child->getRight()->setParent(temp); } else { child->getRight()->setParent(0); } } else { if( this->getRight() != 0 ) { this->getRight()->setParent(child); } } temp= child->getRight(); child->setRight(this->getRight()); this->setRight(temp); } else if( child == this->getRight() ) { if( child->getRight() != 0 ) { child->getRight()->setParent(this); } this->setRight(child->getRight()); child->setRight(this); if( child->getLeft() != 0 ) { if( this->getLeft() != 0 ) { temp= this->getLeft()->getParent(); this->getLeft()->setParent(child-> getLeft()->getParent()); child->getLeft()->setParent(temp); } else { child->getLeft()->setParent(0); } } else { if( this->getLeft() != 0 ) { this->getLeft()->setParent(child); } } temp= child->getLeft(); child->setLeft(this->getLeft()); this->setLeft(temp); } else { assert(0); } // swap incoming horizontal pointers if( child->getPred() != 0 ) { if( this->getPred() != 0 ) { temp= this->getPred()->getSucc(); this->getPred()->setSucc( child->getPred() ->getSucc()); child->getPred()->setSucc(temp); } else { child->getPred()->setSucc(this); } } else { if( this->getPred() != 0 ) { this->getPred()->setSucc(child); } } if( child->getSucc() != 0 ) { if( this->getSucc() != 0 ) { temp= this->getSucc()->getPred(); this->getSucc()->setPred( child->getSucc() ->getPred()); child->getSucc()->setPred(temp); } else { child->getSucc()->setPred(this); } } else { if( this->getSucc() != 0 ) { this->getSucc()->setPred(child); } } // swap outgoing horizontal pointers temp= this->getPred(); this->setPred(child->getPred()); child->setPred(temp); temp= this->getSucc(); this->setSucc(child->getSucc()); child->setSucc(temp); // update variables _active= _last->getParent(); if( _root == this ) { _root= child; } } } //----------------------------------------------------- // display the contents of one Heap node //----------------------------------------------------- void Heap::print() { fprintf(stderr,”%2d(%x) L %x R %x P %x S %x ^ %x\n”, this->getKey(), this, this->getLeft(), this->getRight(), this->getPred(), this->getSucc(), this->getParent()); } //----------------------------------------------------- // remove the root node //----------------------------------------------------- Heap * Heap::remove() { // unlink last node _last->getPred()->setSucc(0); if( _last == _last->getParent()->getLeft() ) { _last->getParent()->setLeft(0); } else { _last->getParent()->setRight(0); } // link last node in as root _last->setLeft(_root->getLeft()); _last->setRight(_root->getRight()); _last->setParent(_root->getParent()); _last->setSucc(_root->getSucc()); _last->setPred(_root->getPred()); _last->setID(_root->getID()); Heap * node= _root; _root= _last; // unlink root node->setLeft(0); node->setRight(0); node->setParent(0); node->setSucc(0); node->setPred(0); node->setID(0); movedown(); return node; } //----------------------------------------------------- // Heap sort integer array //----------------------------------------------------- Heap * Heap::sort() { Heap *head; Heap *last= 0; do { Heap * next= this->remove(); if( last == 0 ) { head= next; next->setPred(0); last->setSucc(next); } else { next->setPred(last); last->setSucc(next); } last= next; } while ( _root != 0 ); _root= head; _last= last; _active= 0; _frontier= 0; return head; }
5.1.2 Bug 1
5.1.2.1 The evidence
The first debugging session began by running the application standalone. The test input and test driver are shown as follows:
// sorted up, power of 2 length int t01[8]= { 1,2,3,4,5,6,7,8 }; // sorted up, non-power of 2 length int t02[9]= { 2,3,5,7,11,13,17,19,23 }; int main() { fprintf(stderr,”test 1:8\n”); testBuild(new Heap(8, t01)); fprintf(stderr,”test 2:9\n”); testBuild(new Heap(9, t02)); } void testBuild(Heap *node) { draw(node->getRoot()); fprintf(stderr,”\n”); } int indent= 0; void draw(Heap * n) { int i; indent += 4; if( n != 0 ) { for( i=0; i<indent; ++i ) { fputc(‘ ‘,stderr); } fprintf(stderr,”%d\n”,n->getKey()); draw(n->getRight()); draw(n->getLeft()); } indent -= 4; } The results of executing this test are shown below. test 1:8 5 3 2 1 test 2:9 11 5 3 2
5.1.2.2 The investigation
It is obvious that this output is faulty—over half of the key values are not even represented. The first thing we would like to do is generate a standard with which to compare the actual output. There many potential valid heap representations of the inputs of these test cases. We will construct one that is representative.
test 1:8 8 6 5 2 7 3 4 1 test 2:9 23 13 11 3 19 5 17 7 2
We observe that at least half of the key values are missing, and that those missing do not come from consecutive positions in the original input stream. We need more data to work with. We decide to insert a call to a function that will list the details of the data structure. We insert this call at the end of each execution of the insert function. We also insert an output statement at the beginning of the insert function that tells us the key value of the node being inserted. This is what the output looks like. We have decided that since the first two test cases fail similarly, we will focus on the first for now.
test 1:8 insert 2 1(804b9f0) L 804ba10 R 0 P 0 S 0 ^ 0 2(804ba10) L 0 R 0 P 0 S 0 ^ 804b9f0 insert 3 2(804ba10) L 804b9f0 R 804ba30 P 0 S 0 ^ 0 3(804ba30) L 0 R 0 P 804b9f0 S 0 ^ 804ba10 1(804b9f0) L 0 R 0 P 0 S 804ba30 ^ 804ba10 insert 4 3(804ba30) L 804b9f0 R 804ba10 P 0 S 0 ^ 0 2(804ba10) L 0 R 0 P 804b9f0 S 804ba50 ^ 804ba30 1(804b9f0) L 0 R 0 P 0 S 0 ^ 0 insert 5 3(804ba30) L 804b9f0 R 804ba10 P 0 S 0 ^ 0 2(804ba10) L 804ba70 R 0 P 804b9f0 S 804ba50 ^ 804ba30 5(804ba70) L 0 R 0 P 0 S 0 ^ 804ba10 1(804b9f0) L 0 R 0 P 0 S 0 ^ 0 insert 6 5(804ba70) L 804b9f0 R 804ba30 P 0 S 0 ^ 0 3(804ba30) L 804ba10 R 0 P 804b9f0 S 804ba90 ^ 804ba70 2(804ba10) L 0 R 0 P 0 S 0 ^ 0 1(804b9f0) L 0 R 0 P 0 S 0 ^ 804ba70 insert 7 5(804ba70) L 804b9f0 R 804ba30 P 0 S 0 ^ 0 3(804ba30) L 804ba10 R 0 P 804b9f0 S 804ba90 ^ 804ba70 2(804ba10) L 804bab0 R 0 P 0 S 0 ^ 0 7(804bab0) L 0 R 0 P 0 S 0 ^ 804ba10 1(804b9f0) L 0 R 0 P 0 S 0 ^ 804ba70 insert 8 5(804ba70) L 804b9f0 R 804ba30 P 0 S 0 ^ 0 3(804ba30) L 804ba10 R 0 P 804b9f0 S 804ba90 ^ 804ba70 2(804ba10) L 0 R 0 P 0 S 804bad0 ^ 804bab0 1(804b9f0) L 0 R 0 P 0 S 0 ^ 804ba70 5 3 2 1
Each row of the display shows
-
The node key
-
The node address
-
The left child pointer (“L”)
-
The right child pointer (“R”)
-
The predecessor pointer (“P”)
-
The successor pointer (“S”)
-
The parent pointer (“^”)
Indentation shows the parental relationship between nodes graphically as well.
We can see that the data structure is invalid by the time the call to insert the node with key “4” has completed. We need more data to work with. We decide to step through the execution of the insert function in the debugger. We set a breakpoint at the beginning of the function and continue execution when the breakpoint is reached, until the call that inserts the node with key “4” is reached.
We observe that there are three cases in this function and that the third case is the one selected for processing this node. We step through this case one statement at a time. Control flows through the true branch of an if-then-else. It becomes clear that no statement is executed that sets the left child of some node to point to the current node, nor does any statement set the parent pointer of the current node to anything. Since this is the fundamental operation of inserting a node in a tree, it is not surprising that the node with key “4” fails to show up when we list the contents of the tree.
5.1.2.3 The fault and correction
We make three changes to correct the problems we have observed.
First, we attach the node being processed to the data structure by inserting the following statements:
_active->setLeft(this); this->setParent(_active);
Second, we move statements that were being unconditionally executed in the case we observed to be executed only under the else clause. It makes no sense to try to set the predecessor pointer when a node is at the left edge of a row and has no predecessors.
_last->setSucc(this); this->setPred(_last);
Finally, we observe that since the case being handled is the left edge, we should be updating the variable that is supposed to be tracking that same left edge. We insert the following statement to cover this:
_frontier= this;
In this round of debugging, we applied the following methods from Chapter 2:
-
Pay attention to unusual details.
-
Gather facts before hypothesizing.
We found two defects that had the following root causes, explained in Chapter 11:
-
Missing operations—missing statements
-
Control-flow problems—statements controlled by the wrong control condition
5.1.3 Bug 2
5.1.3.1 The evidence
The second debugging session began by running the application standalone. We use the same test input and test driver as in the previous test. The results of executing this test are shown below.
test 1:8 8 3 2 7
We definitely fixed problems in the previous session. Unfortunately, while the output of this run is different, it still is not correct.
5.1.3.2 The investigation
We turn on the same diagnostic output that we used before. This is what the output looks like:
test 1:8 insert 2 1(804bad0) L 804baf0 R 0 P 0 S 0 ^ 0 2(804baf0) L 0 R 0 P 0 S 0 ^ 804bad0 insert 3 2(804baf0) L 804bad0 R 804bb10 P 0 S 0 ^ 0 3(804bb10) L 0 R 0 P 804bad0 S 0 ^ 804baf0 1(804bad0) L 0 R 0 P 0 S 804bb10 ^ 804baf0 insert 4 3(804bb10) L 804bad0 R 804baf0 P 0 S 0 ^ 0 2(804baf0) L 804bb30 R 0 P 804bad0 S 0 ^ 804bb10 4(804bb30) L 0 R 0 P 0 S 0 ^ 804baf0 1(804bad0) L 0 R 0 P 0 S 0 ^ 0 insert 5 4(804bb30) L 804bb50 R 804bb10 P 0 S 0 ^ 0 3(804bb10) L 804baf0 R 0 P 804bad0 S 0 ^ 804bb30 2(804baf0) L 0 R 0 P 0 S 0 ^ 0 5(804bb50) L 0 R 0 P 0 S 0 ^ 804bb30 insert 6 5(804bb50) L 804bb70 R 804bb10 P 0 S 0 ^ 0 3(804bb10) L 804baf0 R 0 P 804bad0 S 0 ^ 0 2(804baf0) L 0 R 0 P 0 S 0 ^ 0 6(804bb70) L 0 R 0 P 0 S 0 ^ 804bb50 insert 7 6(804bb70) L 804bb90 R 804bb10 P 0 S 0 ^ 0 3(804bb10) L 804baf0 R 0 P 804bad0 S 0 ^ 0 2(804baf0) L 0 R 0 P 0 S 0 ^ 0 7(804bb90) L 0 R 0 P 0 S 0 ^ 804bb70 insert 8 7(804bb90) L 804bbb0 R 804bb10 P 0 S 0 ^ 0 3(804bb10) L 804baf0 R 0 P 804bad0 S 0 ^ 0 2(804baf0) L 0 R 0 P 0 S 0 ^ 0 8(804bbb0) L 0 R 0 P 0 S 0 ^ 804bb90 8 3 2 7
All of the nodes that are missing from the output appear briefly in the data structure after they are inserted, but then disappear after other nodes are inserted. We decide that the actions of the moveup function may be masking a problem in the insert function. We modify the test case by commenting out the call to moveup and try the same case again. We have elided all but the last listing of the data-structure details in the interest of saving space.
test 1:8 insert 2 insert 3 insert 4 insert 5 insert 6 insert 7 insert 8 1(804ba10) L ba30 R 804ba50 P 0 S 0 ^ 0 3(804ba50) L 804bab0 R 804bad0 P 804ba30 S 0 ^ 804ba10 7(804bad0) L 0 R 0 P 804bab0 S 0 ^ 804ba50 6(804bab0) L 0 R 0 P 804ba90 S 804bad0 ^ 804ba50 2(804ba30) L 804ba70 R 804ba90 P 0 S 804ba50 ^ 804ba10 5(804ba90) L 0 R 0 P 804ba70 S 804bab0 ^ 804ba30 4(804ba70) L 804baf0 R 0 P 0 S 804ba90 ^ 804ba30 8(804baf0) L 0 R 0 P 0 S 0 ^ 804ba70 1 3 7 6 2 5 4 8
We are quite pleased with the results, but cautiously optimistic, since the test case has keys in strict ascending order. We check over all the pointers in the data structure, and they are all correct. Just to make sure, we reverse the order of the keys in the input and try again. Here is the result:
test 1:8 insert 7 insert 6 insert 5 insert 4 insert 3 insert 2 insert 1 8(804ba30) L 804ba50 R 804ba70 P 0 S 0 ^ 0 6(804ba70) L 804bad0 R 804baf0 P 804ba50 S 0 ^ 804ba30 2(804baf0) L 0 R 0 P 804bad0 S 0 ^ 804ba70 3(804bad0) L 0 R 0 P 804bab0 S 804baf0 ^ 804ba70 7(804ba50) L 804ba90 R 804bab0 P 0 S 804ba70 ^ 804ba30 4(804bab0) L 0 R 0 P 804ba90 S 804bad0 ^ 804ba50 5(804ba90) L 804bb10 R 0 P 0 S 804bab0 ^ 804ba50 1(804bb10) L 0 R 0 P 0 S 0 ^ 804ba90 8 6 2 3 7 4 5 1
Now we have greater confidence in the insert function, so we focus our attention on the moveup function. After staring at the output for a while,
we remember that the input of the moveup function includes not only the data structure as displayed, but also a small set of static variables that capture key values used during the process.
We plan our investigation as follows:
-
Problem: Nodes are disappearing from the data structure at random after they are inserted when moveup is used.
-
Hypothesis: Static variables are not getting set properly on input to moveup.
-
Experiment: Run test case 1 with detailed debugging output of the data structure displayed after each execution of the moveup function. Also display the static variables used by both functions.
When we run the experiment, we get the following results, with some of the detailed output omitted in the interest of saving space:
test 1:8 insert 2 *** moveup *** _last= 804bb40, _active= 804bb20, _frontier= 804bb40 1(804bb20) L 804bb40 R 0 P 0 S 0 ^ 0 2(804bb40) L 0 R 0 P 0 S 0 ^ 804bb20 ### moveup ### _last= 804bb20, _active= 804bb40, _frontier= 804bb40 2(804bb40) L 804bb20 R 0 P 0 S 0 ^ 0 1(804bb20) L 0 R 0 P 0 S 0 ^ 804bb40 insert 3 *** moveup *** _last= 804bb60, _active= 804bb40, _frontier= 804bb40 2(804bb40) L 804bb20 R 804bb60 P 0 S 0 ^ 0 3(804bb60) L 0 R 0 P 804bb20 S 0 ^ 804bb40 1(804bb20) L 0 R 0 P 0 S 804bb60 ^ 804bb40 ### moveup ### _last= 804bb40, _active= 804bb60, _frontier= 804bb40 3(804bb60) L 804bb20 R 804bb40 P 0 S 0 ^ 0 2(804bb40) L 0 R 0 P 804bb20 S 0 ^ 804bb60 1(804bb20) L 0 R 0 P 0 S 0 ^ 0 insert 4 *** moveup *** _last= 804bb80, _active= 804bb40, _frontier= 804bb80 3(804bb60) L 804bb20 R 804bb40 P 0 S 0 ^ 0 2(804bb40) L 804bb80 R 0 P 804bb20 S 0 ^ 804bb60 4(804bb80) L 0 R 0 P 0 S 0 ^ 804bb40 1(804bb20) L 0 R 0 P 0 S 0 ^ 0 ### moveup ### _last= 804bb60, _active= 804bb80, _frontier= 804bb80 4(804bb80) L 804bb20 R 804bb60 P 0 S 0 ^ 0 3(804bb60) L 804bb40 R 0 P 804bb20 S 0 ^ 804bb80 2(804bb40) L 0 R 0 P 0 S 0 ^ 0 1(804bb20) L 0 R 0 P 0 S 0 ^ 804bb80 insert 5 *** moveup *** _last= 804bba0, _active= 804bb80, _frontier= 804bba0 4(804bb80) L 804bba0 R 804bb60 P 0 S 0 ^ 0 3(804bb60) L 804bb40 R 0 P 804bb20 S 0 ^ 804bb80 2(804bb40) L 0 R 0 P 0 S 0 ^ 0 5(804bba0) L 0 R 0 P 0 S 0 ^ 804bb80 ### moveup ### _last= 804bb80, _active= 804bba0, _frontier= 804bba0 5(804bba0) L 804bb80 R 804bb60 P 0 S 0 ^ 0 3(804bb60) L 804bb40 R 0 P 804bb20 S 0 ^ 0 2(804bb40) L 0 R 0 P 0 S 0 ^ 0 4(804bb80) L 0 R 0 P 0 S 0 ^ 804bba0 insert 6 *** moveup *** _last= 804bbc0, _active= 804bba0, _frontier= 804bbc0 5(804bba0) L 804bbc0 R 804bb60 P 0 S 0 ^ 0 3(804bb60) L 804bb40 R 0 P 804bb20 S 0 ^ 0 2(804bb40) L 0 R 0 P 0 S 0 ^ 0 6(804bbc0) L 0 R 0 P 0 S 0 ^ 804bba0 ### moveup ### _last= 804bba0, _active= 804bbc0, _frontier= 804bbc0 6(804bbc0) L 804bba0 R 804bb60 P 0 S 0 ^ 0 3(804bb60) L 804bb40 R 0 P 804bb20 S 0 ^ 0 2(804bb40) L 0 R 0 P 0 S 0 ^ 0 5(804bba0) L 0 R 0 P 0 S 0 ^ 804bbc0 insert 7 *** moveup *** ### moveup ### insert 8 *** moveup *** ### moveup ### 8 3 2 7
The values of these static variables are not what they should be.
5.1.3.3 The fault and correction
We insert the following code and rerun the test:
Heap * parent= this->getParent(); if( this->getKey() > parent->getKey() ) { // update variables if ( _frontier == this ) { _frontier= parent; } _last= parent; _active= this; } The values of the static variables are correct on input to the movedown function. The values are incorrect on exit from the movedown function, and nodes are still disappearing. Still, we are making progress.
In this round of debugging, we applied the following methods from Chapter 2:
-
Pay attention to unusual details.
-
Gather facts before hypothesizing.
We found two defects that had the following root causes, explained in Chapter 11:
-
Missing operations—missing statements
-
Reference errors—variable not assigned
5.1.4 Bug 3
5.1.4.1 The evidence
The third debugging session began by running the application standalone again. The test input and test driver are still the same. The results of executing this test are shown as follows:
test 1:8 insert 2 *** moveup *** _last= 804bb60, _active= 804bb80, _frontier= 804bb60 1(804bb60) L 804bb80 R 0 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 0 S 0 ^ 804bb60 ### moveup ### _last= 804bb60, _active= 804bb80, _frontier= 804bb60 2(804bb80) L 804bb60 R 0 P 0 S 0 ^ 0 1(804bb60) L 0 R 0 P 0 S 0 ^ 804bb80 insert 3 *** moveup *** _last= 804bb80, _active= 804bba0, _frontier= 804bb60 2(804bb80) L 804bb60 R 804bba0 P 0 S 0 ^ 0 3(804bba0) L 0 R 0 P 804bb60 S 0 ^ 804bb80 1(804bb60) L 0 R 0 P 0 S 804bba0 ^ 804bb80 ### moveup ### _last= 804bb80, _active= 804bba0, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 0 insert 4 *** moveup *** _last= 804bb60, _active= 804bbc0, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 804bbc0 R 0 P 0 S 0 ^ 0 4(804bbc0) L 0 R 0 P 0 S 0 ^ 804bb60 ### moveup ### _last= 804bb60, _active= 804bbc0, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 804bbc0 insert 5 *** moveup *** _last= 804bbc0, _active= 804bbe0, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 804bbe0 ^ 804bbc0 ### moveup ### _last= 804bbc0, _active= 804bbe0, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 0 insert 6 *** moveup *** _last= 804bb60, _active= 804bc00, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 804bc00 R 0 P 0 S 0 ^ 0 6(804bc00) L 0 R 0 P 0 S 0 ^ 804bb60 ### moveup ### _last= 804bb60, _active= 804bc00, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 804bc00 insert 7 *** moveup *** _last= 804bc00, _active= 804bc20, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 804bc20 ^ 804bc00 ### moveup ### _last= 804bc00, _active= 804bc20, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 0 insert 8 *** moveup *** _last= 804bb60, _active= 804bc40, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 804bc40 R 0 P 0 S 0 ^ 0 8(804bc40) L 0 R 0 P 0 S 0 ^ 804bb60 ### moveup ### _last= 804bb60, _active= 804bc40, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 804bc40 3 2 1
5.1.4.2 The investigation
The data structure has become defective by the end of the moveup function processing for the node with key “4.” That node has disappeared, and the node with key “1” has a pointer to a parent that does not exist, which happens to be the address of the missing node.
We decide that we should run the application under the debugger, set breakpoints at key sections of the code, and dump the data structure at those points. The results of this experiment are listed as follows:
(gdb) Breakpoint 1 at 0x8048bc8: file Heap.c, line 144. Breakpoint 2 at 0x8048d78: file Heap.c, line 168. Breakpoint 3 at 0x8048f40: file Heap.c, line 197. Breakpoint 4 at 0x804911b: file Heap.c, line 225. (gdb) run test 1:8 insert 2 *** moveup *** _last= 804bb60, _active= 804bb80, _frontier= 804bb60 1(804bb60) L 804bb80 R 0 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 0 S 0 ^ 804bb60 ... ### moveup ### _last= 804bb60, _active= 804bb80, _frontier= 804bb60 2(804bb80) L 804bb60 R 0 P 0 S 0 ^ 0 1(804bb60) L 0 R 0 P 0 S 0 ^ 804bb80 insert 3 *** moveup *** _last= 804bb80, _active= 804bba0, _frontier= 804bb60 2(804bb80) L 804bb60 R 804bba0 P 0 S 0 ^ 0 3(804bba0) L 0 R 0 P 804bb60 S 0 ^ 804bb80 1(804bb60) L 0 R 0 P 0 S 804bba0 ^ 804bb80 ... ### moveup ### _last= 804bb80, _active= 804bba0, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 0 insert 4 *** moveup *** _last= 804bb60, _active= 804bbc0, _frontier= 804bb60 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 804bbc0 R 0 P 0 S 0 ^ 0 4(804bbc0) L 0 R 0 P 0 S 0 ^ 804bb60 Breakpoint 1, moveup__4Heap (this=0x804bbc0) at Heap.c:144 144 if( this == parent->getLeft() ) { 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 804bbc0 R 0 P 0 S 0 ^ 804bbc0 4(804bbc0) L 0 R 0 P 0 S 0 ^ 0 Breakpoint 3, moveup__4Heap (this=0x804bbc0) at Heap.c:197 197 if( this->getPred() != 0 ) { 3(804bba0) L 804bb60 R 804bb80 P 0 S 0 ^ 0 2(804bb80) L 0 R 0 P 804bb60 S 0 ^ 804bba0 1(804bb60) L 0 R 0 P 0 S 0 ^ 804bbc0 The results from the first set of breakpoints show us that the data structure is valid at line 144 and invalid at line 197. This eliminates the code outside of these bounds. The node with key “4” has disappeared by the end-point of this segment.
Having eliminated a large part of the code as a source of possible causes, we move on to a manual inspection of these lines. We are looking for code that would cause an existing node to become unlinked from the data structure. To unlink something is to make its pointer null.
5.1.4.3 The fault and correction
As we review the code, we find two statements in our zone of suspicion that are setting pointers to null when they should be setting them to this, and two that should be setting them to the parent of the node, and yet two more that should be setting pointers to this.
parent->getRight()->setParent(0); parent->getLeft()->setParent(0); this->getPred()->setSucc(0); this->getSucc()->setPred(0); parent->getPred()->setSucc(0); parent->getSucc()->setPred(0);
We change the arguments to this and parent as appropriate.
In this round of debugging, we applied the following methods from Chapter 2:
-
Start by observing.
-
Eliminate impossible causes.
We found two defects that had the following root causes, explained in Chapter 11:
-
Reference errors—wrong variable referenced
-
Reference errors—wrong constant referenced
5.1.5 Bug 4
5.1.5.1 The evidence
The next debugging session began by running the application as before. The test input and test driver are still the same. The results of executing this test are shown as follows:
test 1:8 8 2 7 6 5 4 3 1
We are making some progress. We are now getting all of the nodes inserted into the data structure. Unfortunately, the structure is still invalid.
5.1.5.2 The investigation
We start our investigation by turning on the detailed display of the data structure and rerunning the application. We get the following results:
test 1:8 insert 2 *** moveup *** _last= 804bc20, _active= 804bc40, _frontier= 804bc20 1(804bc20) L 804bc40 R 0 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 0 S 0 ^ 804bc20 ### moveup ### _last= 804bc20, _active= 804bc40, _frontier= 804bc20 2(804bc40) L 804bc20 R 0 P 0 S 0 ^ 0 1(804bc20) L 0 R 0 P 0 S 0 ^ 804bc40 insert 3 *** moveup *** _last= 804bc40, _active= 804bc60, _frontier= 804bc20 2(804bc40) L 804bc20 R 804bc60 P 0 S 0 ^ 0 3(804bc60) L 0 R 0 P 804bc20 S 0 ^ 804bc40 1(804bc20) L 0 R 0 P 0 S 804bc60 ^ 804bc40 ### moveup ### _last= 804bc40, _active= 804bc60, _frontier= 804bc20 3(804bc60) L 804bc20 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bc20 S 0 ^ 804bc60 1(804bc20) L 0 R 0 P 0 S 804bc40 ^ 804bc60 insert 4 *** moveup *** _last= 804bc20, _active= 804bc80, _frontier= 804bc20 3(804bc60) L 804bc20 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bc20 S 0 ^ 804bc60 1(804bc20) L 804bc80 R 0 P 0 S 804bc40 ^ 804bc60 4(804bc80) L 0 R 0 P 0 S 0 ^ 804bc20 ### moveup ### _last= 804bc60, _active= 804bc80, _frontier= 804bc20 4(804bc80) L 804bc60 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bc60 S 0 ^ 804bc80 3(804bc60) L 804bc20 R 0 P 0 S 804bc40 ^ 804bc80 1(804bc20) L 0 R 0 P 0 S 0 ^ 804bc60 insert 5 *** moveup *** _last= 804bc20, _active= 804bca0, _frontier= 804bc20 4(804bc80) L 804bc60 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bc60 S 0 ^ 804bc80 3(804bc60) L 804bc20 R 0 P 0 S 804bc40 ^ 804bc80 1(804bc20) L 804bca0 R 0 P 0 S 0 ^ 804bc60 5(804bca0) L 0 R 0 P 0 S 0 ^ 804bc20 ### moveup ### _last= 804bc80, _active= 804bca0, _frontier= 804bc20 5(804bca0) L 804bc80 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bc80 S 0 ^ 804bca0 4(804bc80) L 804bc60 R 0 P 0 S 804bc40 ^ 804bca0 3(804bc60) L 804bc20 R 0 P 0 S 0 ^ 804bc80 1(804bc20) L 0 R 0 P 0 S 0 ^ 804bc60 insert 6 *** moveup *** _last= 804bc20, _active= 804bcc0, _frontier= 804bc20 5(804bca0) L 804bc80 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bc80 S 0 ^ 804bca0 4(804bc80) L 804bc60 R 0 P 0 S 804bc40 ^ 804bca0 3(804bc60) L 804bc20 R 0 P 0 S 0 ^ 804bc80 1(804bc20) L 804bcc0 R 0 P 0 S 0 ^ 804bc60 6(804bcc0) L 0 R 0 P 0 S 0 ^ 804bc20 ### moveup ### _last= 804bca0, _active= 804bcc0, _frontier= 804bc20 6(804bcc0) L 804bca0 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bca0 S 0 ^ 804bcc0 5(804bca0) L 804bc80 R 0 P 0 S 804bc40 ^ 804bcc0 4(804bc80) L 804bc60 R 0 P 0 S 0 ^ 804bca0 3(804bc60) L 804bc20 R 0 P 0 S 0 ^ 804bc80 1(804bc20) L 0 R 0 P 0 S 0 ^ 804bc60 insert 7 *** moveup *** _last= 804bc20, _active= 804bce0, _frontier= 804bc20 6(804bcc0) L 804bca0 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bca0 S 0 ^ 804bcc0 5(804bca0) L 804bc80 R 0 P 0 S 804bc40 ^ 804bcc0 4(804bc80) L 804bc60 R 0 P 0 S 0 ^ 804bca0 3(804bc60) L 804bc20 R 0 P 0 S 0 ^ 804bc80 1(804bc20) L 804bce0 R 0 P 0 S 0 ^ 804bc60 7(804bce0) L 0 R 0 P 0 S 0 ^ 804bc20 ### moveup ### _last= 804bcc0, _active= 804bce0, _frontier= 804bc20 7(804bce0) L 804bcc0 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bcc0 S 0 ^ 804bce0 6(804bcc0) L 804bca0 R 0 P 0 S 804bc40 ^ 804bce0 5(804bca0) L 804bc80 R 0 P 0 S 0 ^ 804bcc0 4(804bc80) L 804bc60 R 0 P 0 S 0 ^ 804bca0 3(804bc60) L 804bc20 R 0 P 0 S 0 ^ 804bc80 1(804bc20) L 0 R 0 P 0 S 0 ^ 804bc60 insert 8 *** moveup *** _last= 804bc20, _active= 804bd00, _frontier= 804bc20 7(804bce0) L 804bcc0 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bcc0 S 0 ^ 804bce0 6(804bcc0) L 804bca0 R 0 P 0 S 804bc40 ^ 804bce0 5(804bca0) L 804bc80 R 0 P 0 S 0 ^ 804bcc0 4(804bc80) L 804bc60 R 0 P 0 S 0 ^ 804bca0 3(804bc60) L 804bc20 R 0 P 0 S 0 ^ 804bc80 1(804bc20) L 804bd00 R 0 P 0 S 0 ^ 804bc60 8(804bd00) L 0 R 0 P 0 S 0 ^ 804bc20 ### moveup ### _last= 804bce0, _active= 804bd00, _frontier= 804bc20 8(804bd00) L 804bce0 R 804bc40 P 0 S 0 ^ 0 2(804bc40) L 0 R 0 P 804bce0 S 0 ^ 804bd00 7(804bce0) L 804bcc0 R 0 P 0 S 804bc40 ^ 804bd00 6(804bcc0) L 804bca0 R 0 P 0 S 0 ^ 804bce0 5(804bca0) L 804bc80 R 0 P 0 S 0 ^ 804bcc0 4(804bc80) L 804bc60 R 0 P 0 S 0 ^ 804bca0 3(804bc60) L 804bc20 R 0 P 0 S 0 ^ 804bc80 1(804bc20) L 0 R 0 P 0 S 0 ^ 804bc60 8 2 7 6 5 4 3 1
We notice that the data structure goes bad after the node with key “5” is inserted. It is no longer a complete binary tree. The node with key “3” should have two children, “1” and “5,” not one child with key “1” and one grandchild with key “5.” Unlike the previous error, this one manifests itself at the beginning of the moveup function.
Three possibilities would lead to problems coming out of the insert function:
-
The code is incorrect, and the data being passed from moveup is incorrect.
-
The code is incorrect, even though the data being passed from moveup is correct.
-
The code is correct, but the data being passed from moveup is incorrect.
We need to determine which data might be at fault. We reason backward as follows: The symptom of the problem is that a node is being inserted as the left child of another node, instead of as its sibling (the right child of the parent). Three places in the insert function have the following sequence:
X->setLeft(Y) Y->setParent(X)
If the data that controls the execution of one of these statements allows it to execute at the wrong time, the manifest problem would result.
The next step is to execute the application in the debugger and find out which of these sets of statements is performing the invalid insertion. This will enable us to determine whether the variables that control them are incorrect.
We find that the statements that are making the bad insertion are controlled by the following statements:
_active= _last->getParent()->getSucc(); if( _active == 0 ) { ... } The value of the _last variable is clearly wrong. We must identify the statement that assigned the value to it. This is easy, since the function previously executed was moveup and at the very end of that function, there are assignments to both _last and _active.
We consider the values being assigned and cannot come up with a good reason why these statements are in this function. We decide to comment them out, so that we can observe the values they are masking. We rebuild and restart the debugger. After setting a breakpoint on the statement we know is causing the problem, we rerun the program.
It stops once before the problem and then not again until several more nodes are inserted. Once we regain control, we display the data structure and are delighted to find that everything has been built correctly.
5.1.5.3 The fault and correction
To correct the problem, we delete the following code at the end of the moveup function:
_last= parent; _active= this;
In this round of debugging, we applied the following methods from Chapter 2:
-
Eliminate impossible causes.
-
Gather facts before hypothesizing.
-
Pay attention to unusual details.
We found two defects that had the following root cause, explained in Chapter 11:
-
Extra operations—extra statements
Since we believe that we have the insert and moveup functions working properly, we subject them to a larger set of tests.
// sorted up, power of 2 length int t01[8]= { 1,2,3,4,5,6,7,8 }; // sorted up, non-power of 2 length int t02[9]= { 2,3,5,7,11,13,17,19,23 }; // sorted down, power of 2 length int t03[16]= { 32,30,28,26,24,22,20,18,16,14,12,10,8,6,4,2 }; // sorted down, non-power of 2 length int t04[14]= { 27,25,23,21,19,17,15,13,11,9,7,5,3,1 }; // “V” pattern, power of 2 length int t05[16]= { 2, 5, 11, 17, 29, 37, 47, 57, 61, 53, 41, 31, 23, 13, 7, 3 }; // “V” pattern, non-power of 2 length int t06[11]= { 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3 }; // inverse “V” pattern, power of 2 length int t07[32]= { 109, 103, 97, 87, 79, 71, 61, 57, 47, 41, 31, 23, 17, 11, 5, 2, 3, 7, 13, 19, 29, 37, 43, 53, 59, 67, 73, 83, 89, 101, 107, 111 }; // inverse “V” pattern, non-power of 2 length int t08[31]= { 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 }; // random values, power of 2 length int t09[16]= { 2, 3, 43, 47, 5, 7, 37, 41, 11, 13, 29, 31, 17, 23, 53, 57 }; // random values, non-power of 2 length int t10[20]= { 2, 71, 3, 67, 5, 61, 7, 59, 11, 57, 13, 53, 17, 47, 23, 43, 29, 41, 31, 37 }; int main() { fprintf(stderr,”test 1:8\n”); testBuild(new Heap(8, t01)); fprintf(stderr,”test 2:9\n”); testBuild(new Heap(9, t02)); fprintf(stderr,”test 3:16\n”); testBuild(new Heap(16, t03)); fprintf(stderr,”test 4:14\n”); testBuild(new Heap(14, t04)); fprintf(stderr,”test 5:16\n”); testBuild(new Heap(16, t05)); fprintf(stderr,”test 6:11\n”); testBuild(new Heap(11, t06)); fprintf(stderr,”test 7:32\n”); testBuild(new Heap(32, t07)); fprintf(stderr,”test 8:31\n”); testBuild(new Heap(31, t08)); fprintf(stderr,”test 9:16\n”); testBuild(new Heap(16, t09)); fprintf(stderr,”test 10:20\n”); testBuild(new Heap(20, t10)); } void testBuild(Heap *node) { draw(node->getRoot()); fprintf(stderr,”\n”); } //----------------------------------------------------- int indent= 0; void draw(Heap * n) { int i; indent += 4; if( n != 0 ) { for( i=0; i<indent; ++i ) { fputc(‘ ‘,stderr); } fprintf(stderr,”%d\n”,n->getKey()); draw(n->getRight()); draw(n->getLeft()); } indent -= 4; } The results of running these tests are listed as follows:
test 1:8 8 6 5 2 7 3 4 1 test 2:9 23 13 11 3 19 5 17 7 2 test 3:16 32 28 20 4 6 22 8 10 30 24 12 14 26 16 18 2 test 4:14 27 23 15 1 17 3 5 25 19 7 9 21 11 13 test 5:16 61 37 29 7 13 31 23 5 57 53 41 11 47 17 3 2 test 6:11 12 11 10 4 9 6 3 5 8 7 2 test 7:32 111 107 101 97 89 5 83 61 11 73 71 67 17 59 53 23 109 79 43 37 31 41 29 19 103 47 13 7 87 3 57 2 test 8:31 32 31 29 28 27 2 25 20 4 23 22 21 8 19 17 10 30 24 15 13 12 14 11 9 26 16 7 5 18 3 1 test 9:16 57 47 37 23 7 31 17 3 53 29 13 5 43 11 41 2 test 10:20 71 61 47 23 7 53 17 3 67 57 13 37 5 59 41 31 11 43 29 2
At this point, the functions insert and moveup have undergone quite a bit of revision, but they seem to be working, so we list their sources as follows:
//----------------------------------------------------- // insert a Heap node at the end of the heap //----------------------------------------------------- void Heap::insert() { this->setPred(0); this->setSucc(0); if( _active->getLeft() == 0 ) { _active->setLeft(this); this->setParent(_active); if ( this->getID() == _power ) { _frontier= this; _power *= 2; } _last= this; } else if( _active->getRight() == 0 ) { _active->setRight(this); this->setParent(_active); _last->setSucc(this); this->setPred(_last); if ( this->getID() == _power-1 ) { _active= _frontier; } _last= this; } else { _active= _last->getParent()->getSucc(); if( _active == 0 ) { _active= _frontier; _active->setLeft(this); this->setParent(_active); _frontier= this; } else { _active->setLeft(this); this->setParent(_active); _last->setSucc(this); this->setPred(_last); } _last= this; } Heap * parent= this->getParent(); if( this->getKey() > parent->getKey() ) { // update variables if ( _frontier == this ) { _frontier= parent; } _last= parent; _active= this; } } //----------------------------------------------------- // re-arrange the heap after appending a node at the // end of the binary tree so that the heap property // is preserved //----------------------------------------------------- void Heap::moveup() { Heap *temp; while( true ) { Heap * parent= this->getParent(); if( !parent || parent->getKey() >= this->getKey() ) { break; } // swap ID numbers int swap= parent->getID(); parent->setID(this->getID()); this->setID(swap); // swap incoming vertical pointers Heap * grand= parent->getParent(); if( grand != 0 ) { if( parent == grand->getLeft() ) { grand->setLeft(this); } else if( parent == grand->getRight() ) { grand->setRight(this); } } // swap outgoing vertical pointers parent->setParent(this); this->setParent(grand); if( this == parent->getLeft() ) { if( this->getLeft() != 0 ) { this->getLeft()->setParent(parent); } parent->setLeft(this->getLeft()); this->setLeft(parent); if( this->getRight() != 0 ) { if( parent->getRight() != 0 ) { temp= parent->getRight() ->getParent(); parent->getRight()->setParent(this-> getRight()->getParent()); this->getRight()->setParent(temp); } else { this->getRight()->setParent(0); } } else { if( parent->getRight() != 0 ) { parent->getRight()->setParent(this); } } temp= this->getRight(); this->setRight(parent->getRight()); parent->setRight(temp); } else if( this == parent->getRight() ) { if( this->getRight() != 0 ) { this->getRight()->setParent(parent); } parent->setRight(this->getRight()); this->setRight(parent); if( this->getLeft() != 0 ) { if( parent->getLeft() != 0 ) { temp= parent->getLeft()->getParent(); parent->getLeft()->setParent(this-> getLeft()->getParent()); this->getLeft()->setParent(temp); } else { this->getLeft()->setParent(0); } } else { if( parent->getLeft() != 0 ) { parent->getLeft()->setParent(this); } } temp= this->getLeft(); this->setLeft(parent->getLeft()); parent->setLeft(temp); } else { assert(0); } // swap incoming horizontal pointers if( this->getPred() != 0 ) { if( parent->getPred() != 0 ) { temp= parent->getPred()->getSucc(); parent->getPred()->setSucc(this-> getPred()->getSucc()); this->getPred()->setSucc(temp); } else { this->getPred()->setSucc(parent); } } else { if( parent->getPred() != 0 ) { parent->getPred()->setSucc(this); } } if( this->getSucc() != 0 ) { if( parent->getSucc() != 0 ) { temp= parent->getSucc()->getPred(); parent->getSucc()->setPred(this-> getSucc()->getPred()); this->getSucc()->setPred(temp); } else { this->getSucc()->setPred(parent); } } else { if( parent->getSucc() != 0 ) { parent->getSucc()->setPred(this); } } // swap outgoing horizontal pointers temp= parent->getPred(); parent->setPred(this->getPred()); this->setPred(temp); temp= parent->getSucc(); parent->setSucc(this->getSucc()); this->setSucc(temp); // update variables _active= _last->getParent(); if( _root == parent ) { _root= this; } } }
5.1.6 Bug 5
5.1.6.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). The test input and test driver are listed as follows:
void testSort(Heap *); // sorted up, power of 2 length int t01[8]= { 1,2,3,4,5,6,7,8 }; int main() { Heap *node, *first; fprintf(stderr,”test 1:8\n”); testSort(new Heap(8, t01)); } void testSort(Heap *in) { Heap * node= in->sort(); for( ; node != 0; node= node->getSucc() ) { fprintf(stderr,”%d “, node->getKey()); } fprintf(stderr,”\n”); } The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/h.exe test 1:8 Program received signal SIGSEGV, Segmentation fault. 0x0804a585 in setSucc__4HeapP4Heap (this=0x0, x=0x0) at Heap.h:34 34 inline void setSucc(Heap * x) { _succ= x; } (gdb) bt #0 0x0804a585 in setSucc__4HeapP4Heap (this=0x0, x=0x0) at Heap.h:34 #1 0x080499f1 in remove__4Heap (this=0x804c038) at Heap.c:396 #2 0x08049be3 in sort__4Heap (this=0x804c038) at Heap.c:441 #3 0x0804a25d in testSort__FP4Heap (in=0x804c038) at HeapTest.c:110 ...
5.1.6.2 The investigation
We observe that the immediate cause of the failure is that this does not point to a valid heap object, but rather has the null pointer value. We use one of our most basic tools, enumerating and eliminating possibilities.
-
The variable should always have a null value.
-
The variable should never have a null value.
-
The variable should sometimes have a null value.
-
The statement should never be executed.
-
The statement should sometimes be executed.
-
The statement should always be executed.
-
Possibility 1 means that the pointer is useless, so we immediately eliminate it. The pointer in question is a predecessor. It is correct for the predecessor pointer to be null when the node is the leftmost node on a row. This eliminates possibility 2.
The problem was a result of the variable sometimes having a null value, and the statement always being executed, so we can reject possibility 3c. Possibility 3a means the code is meaningless, which we know isn’t true, so we reject it. We reconsider the purpose of the original statement. When a node is removed from the data structure, all pointers to it should be removed. Since the statement is removing one of those pointers, the only logical possibility is that the statement should be executed only when the intermediate pointer has a nonnull value.
While we are eliminating logical impossibilities, we exercise some curiosity and review the code that will be executed later. In the sort function, we find a problem that is the converse of the one we just analyzed. We have a conditional statement guarding some pointer references that guarantees that one of the pointers is null. This statement can never be correctly executed under this condition.
In this round of debugging, we applied the following methods from Chapter 3:
-
Enumerate possibilities.
-
Exercise curiosity.
We found two defects that both had the following root cause, explained in Chapter 11:
-
Control-flow problem—statement controlled by wrong control-flow condition.
5.1.6.3 The fault and correction
In this round of debugging, we found two problems. The remove function makes an unguarded reference thus:
_last->getPred()->setSucc(0);
We must guard it with a test for the value of the intermediate pointer:
if ( _last->getPred() != 0 ) { _last->getPred()->setSucc(0); } The sort function makes a reference through a pointer that is known to be null, as a result of a careless symmetrical coding of cases that were not actually symmetric. The original code looked like the following:
if ( last == 0 ) { head= next; next->setPred(0); last->setSucc(next); } else { next->setPred(last); last->setSucc(next); } The modified code removed the unnecessary operation.
if ( last == 0 ) { head= next; next->setPred(0); } else { next->setPred(last); last->setSucc(next); }
5.1.7 Bug 6
5.1.7.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). We use the same test data and driver as in the previous session. We inserted the following line of code into the sort function, after the call to remove, to observe the progress of the sort:
fprintf(stderr,”remove %d\n”,next->getKey());
The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/h.exe test 1:8 remove 8 remove 7 remove 6 remove 5 remove 4 Program received signal SIGSEGV, Segmentation fault. 0x0804a512 in getLeft__4Heap (this=0x0) at Heap.h:15 15 inline Heap * getLeft() { return _left; } (gdb) bt #0 0x0804a512 in getLeft__4Heap (this=0x0) at Heap.h:15 #1 0x08049a24 in remove__4Heap (this=0x804c080) at Heap.c:399 #2 0x08049bfb in sort__4Heap (this=0x804c080) at Heap.c:443 #3 0x0804a28d in testSort__FP4Heap (in=0x804c080) at HeapTest.c:110 ...
5.1.7.2 The investigation
We start the program under the debugger and set a breakpoint at the statement that is failing. Each time the statement is encountered, we print the value of the pointer variable in question. The statement executes four times before we encounter the problem.
We notice that the offending statement is another that contains multiple pointer dereferences. The question comes to mind, are there nodes that legitimately have a null pointer for a parent? The answer is yes, just one—the root. We print the value of the _root and _last variables and see that they are identical.
After correcting the problem, we run the code again under the debugger. It immediately goes into an endless loop. We start reading the code looking for a faulty termination condition. We do not find any termination condition at all.
In this round of debugging, we applied the following methods from Chapter 3:
-
Show how something could be done.
-
Exercise curiosity.
We found two defects that had the following root causes, explained in Chapter 11:
-
Control-flow problem—statement controlled by wrong control-flow condition
-
Control-flow problem—loop never terminates
5.1.7.3 The fault and correction
In this round of debugging, we found two problems. The remove function makes an unguarded reference thus:
if ( _last == _last->getParent()->getLeft() ) { _last->getParent()->setLeft(0); } else { _last->getParent()->setRight(0); } The node pointed at by the _last variable has a null pointer for its parent. Thus, we must guard it with a test for the value of the intermediate pointer:
if( _last->getParent() != 0 ) { if ( _last == _last->getParent()->getLeft() ) { _last->getParent()->setLeft(0); } else { _last->getParent()->setRight(0); } } The remove function has a more serious flaw. It does not check for a termination condition. The removal process is finished when the node pointed at by the _last variable is the same node pointed at by the _root variable. We capture the value of the pointer in a local variable _root to perform the removal of links in the proper order. When the termination condition is detected, both the _root and _last variables are set to null to ensure that no further processing will occur.
Heap * node= _root; if( _last != _root ) { // original function body inserted here _root= _last; movedown(); } else { _last= 0; _root= 0; }
5.1.8 Bug 7
5.1.8.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). We use the same test data and driver as in the first and second sessions. The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/h.exe test 1:8 remove 8 remove 7 remove 6 remove 5 remove 4 remove 1 8 7 6 5 4 1 Program exited normally.
5.1.8.2 The investigation
We begin by listing the facts that we can observe:
-
The program terminated normally.
-
The items that were removed were processed in the correct order.
-
Not all of the items were processed.
-
The items that were not processed were both of the immediate children of the root.
These observations are suggestive, but we need more data. We add a function to list all of the fields of each node in the data structure.
int indent= 0; void list(Heap * n) { indent += 4; if( n != 0 ) { for( int i=0; i<indent; ++i ) { fputc(‘ ‘,stderr); } fprintf(stderr,”%2d(%x)[%d] L %x R %x P %x S %x ^ %x\n”, n->getKey(), n, n->getID(), n->getLeft(), n->getRight(), n->getPred(), n->getSucc(), n->getParent()); list(n->getRight()); list(n->getLeft()); } indent -= 4; } We set a breakpoint at the entry of the remove function and display the details of the data structure each time the breakpoint is hit.
The output is shown as follows. The first time the function is entered, all the pointers point to the right node. The second time is also okay. The third time, we notice that the tree is no longer a complete binary tree. The correct node was removed, but the structure was not restored properly afterward.
(gdb) run Starting program: /home/metzger/h.exe Breakpoint 1 at 0x80499d6: file Heap.c, line 395. test 1:8 Breakpoint 1, remove__4Heap (this=0x804ba80) at Heap.c:395 395 Heap * node= _root; 8(804bb60) L 804bb40 R 804bb20 P 0 S 0 ^ 0 6(804bb20) L 804baa0 R 804bb00 P 804bb40 S 0 ^ 804bb60 5(804bb00) L 0 R 0 P 804baa0 S 0 ^ 804bb20 2(804baa0) L 0 R 0 P 804bac0 S 804bb00 ^ 804bb20 7(804bb40) L 804bae0 R 804bac0 P 0 S 804bb20 ^ 804bb60 3(804bac0) L 0 R 0 P 804bae0 S 804baa0 ^ 804bb40 4(804bae0) L 804ba80 R 0 P 0 S 804bac0 ^ 804bb40 1(804ba80) L 0 R 0 P 0 S 0 ^ 804bae0 $1 = void remove 8 Breakpoint 1, remove__4Heap (this=0x804ba80) at Heap.c:395 395 Heap * node= _root; 7(804bb40) L 804bae0 R 804bb20 P 0 S 0 ^ 0 6(804bb20) L 804baa0 R 804bb00 P 804bae0 S 0 ^ 804bb40 5(804bb00) L 0 R 0 P 804baa0 S 0 ^ 804bb20 2(804baa0) L 0 R 0 P 804bac0 S 804bb00 ^ 804bb20 4(804bae0) L 804ba80 R 804bac0 P 0 S 804bb20 ^ 804bb40 3(804bac0) L 0 R 0 P 804ba80 S 804baa0 ^ 804bae0 1(804ba80) L 0 R 0 P 0 S 804bac0 ^ 804bae0 $2 = void remove 7 Breakpoint 1, remove__4Heap (this=0x804ba80) at Heap.c:395 395 Heap * node= _root; 6(804bb20) L 804bae0 R 804bb00 P 0 S 0 ^ 0 5(804bb00) L 804baa0 R 804ba80 P 804bae0 S 0 ^ 804bb20 1(804ba80) L 0 R 0 P 804baa0 S 0 ^ 804bb00 2(804baa0) L 0 R 0 P 804bac0 S 804ba80 ^ 804bb00 4(804bae0) L 0 R 804bac0 P 0 S 804bb00 ^ 804bb20 3(804bac0) L 0 R 0 P 804ba80 S 804baa0 ^ 804bae0 $3 = void remove 6
We carefully inspect the pointers in the output. The first and second displays are correct. In the third display, the node with key value of “3” has a predecessor pointer of “804ba80,” even though it is the leftmost node at that level and has no logical predecessor.
We reason backward from effect to cause to find the source of the problem. When the root node is removed, the rightmost node on the lowest level is supposed to be inserted as the new root node and then moved down the tree until the data structure meets the heap criteria. The first time a node was removed, the rightmost node (with key “1”) was inserted as the root and moved to an appropriate location. The next time a node was removed, the leftmost node (with key “1”) was inserted as the root and moved down. This left the tree in an invalid state.
The variable _last identifies the variable that will be moved up. We look for the relevant assignment to this variable to determine why it is getting the wrong value. We find none and determine that the lack of an update is the problem.
In this round of debugging, we applied the following methods from Chapter 3:
-
Reason based on facts.
-
Use the power of logic.
We found a defect that had the following root cause, explained in Chapter 11:
-
Reference error—variable was not assigned
5.1.8.3 The fault and correction
The problem is that the remove function is not updating the _last variable. We determine that the right thing to do is save the back pointer that the last node has to the penultimate node, move the last node, and then record the address of the penultimate node for future processing. This results in the following significant rewrite of this function:
Heap * Heap::remove() { Heap * node= _root; if( _last != _root ) { // unlink last node Heap * penult= _last->getPred(); if( penult != 0 ) { penult->setSucc(0); } Heap * parent= _last->getParent(); if( _last == parent->getLeft() ) { parent->setLeft(0); } else { parent->setRight(0); } // link last node in as root if( _root->getLeft() != 0 ) { _root->getLeft()->setParent(_last); } if( _root->getRight() != 0 ) { _root->getRight()->setParent(_last); } _last->setLeft(_root->getLeft()); _last->setRight(_root->getRight()); _last->setParent(_root->getParent()); _last->setSucc(_root->getSucc()); _last->setPred(_root->getPred()); _last->setID(_root->getID()); _root= _last; _last= penult; movedown(); } else { _last= 0; _root= 0; } // unlink removed node node->setLeft(0); node->setRight(0); node->setParent(0); node->setSucc(0); node->setPred(0); node->setID(0); return node; }
5.1.9 Bug 8
5.1.9.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). To have confidence in the input to the sorting process, we inserted a function to draw the tree using ASCII characters and indentation to show the structure. We also inserted calls at the start and end of the movedown function to show the tree data structure after each move.
The test input and test driver are listed as follows:
void draw(Heap *); void testBuild(Heap *); void testSort(Heap *); // sorted up, power of 2 length int t01[8]= { 1,2,3,4,5,6,7,8 }; int main() { Heap *node, *first; fprintf(stderr,”test 1:8\n”); node= new Heap(8, t01); testBuild(node); testSort(node); } void testBuild(Heap *node) { draw(node->getRoot()); fprintf(stderr,”\n”); } void testSort(Heap *in) { Heap * node= in->sort(); for( ; node != 0; node= node->getSucc() ) { fprintf(stderr,”%d “, node->getKey()); } fprintf(stderr,”\n”); } int indent= 0; void draw(Heap * n) { int i; indent += 4; if( n != 0 ) { for( i=0; i<indent; ++i ) { fputc(‘ ‘,stderr); } fprintf(stderr,”%d\n”,n->getKey()); draw(n->getRight()); draw(n->getLeft()); } indent -= 4; } The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/h.exe test 1:8 8 6 5 2 7 3 4 1 *** movedown *** 1(804bb00) L 804bbc0 R 804bba0 P 0 S 0 ^ 0 6(804bba0) L 804bb20 R 804bb80 P 804bbc0 S 0 ^ 804bb00 5(804bb80) L 0 R 0 P 804bb20 S 0 ^ 804bba0 2(804bb20) L 0 R 0 P 804bb40 S 804bb80 ^ 804bba0 7(804bbc0) L 804bb60 R 804bb40 P 0 S 804bba0 ^ 804bb00 3(804bb40) L 0 R 0 P 804bb60 S 804bb20 ^ 804bbc0 4(804bb60) L 0 R 0 P 0 S 804bb40 ^ 804bbc0 Program received signal SIGSEGV, Segmentation fault. 0x0804a0f2 in getParent__4Heap (this=0x0) at Heap.h:17 17 inline Heap * getParent() { return _parent; } (gdb) bt #0 0x0804a0f2 in getParent__4Heap (this=0x0) at Heap.h:17 #1 0x0804994c in movedown__4Heap (this=0x804bb00) at Heap.c:375 #2 0x08049ba9 in remove__4Heap (this=0x804bb00) at Heap.c:426 #3 0x08049c4f in sort__4Heap (this=0x804bb00) at Heap.c:457 #4 0x08049e51 in testSort__FP4Heap (in=0x804bb00) at HeapTest.c:114 ...
5.1.9.2 The investigation
After displaying the stack trace, we display the value of the pointer being referenced in the movedown function. The statement is
_active= _last->getParent();
and the _last variable has a null pointer. Since we just finished changing the statements that modify this variable, the logical thing to do is to review them for possible problems. We have been making a copy of the source for this program each time we make a significant change.
We use the UNIX™ diff program to compare the current source to the previous source. We quickly find the lines we recently modified.
There are only two interesting places where this variable is assigned, so we set a breakpoint at each of them. On the first try, we find that this variable is being assigned a null pointer from the penultimate pointer we had saved earlier.
Is there ever a condition under which the penultimate pointer will be null? The answer is yes: When the node is the leftmost node on a level, the predecessor pointer will be null, and this will be stored for this assignment.
In this round of debugging, we applied the following methods from Chapter 4:
-
Look for domestic drift.
-
Tail thyself.
We found defects that had the following root causes, explained in Chapter 11:
-
Reference error—variable not assigned
-
Control-flow problem—statement controlled by wrong control-flow condition
5.1.9.3 The fault and correction
It is clear that we need a more sophisticated way of backing up through the tree than just using the predecessor pointers. The natural solution is to use the same mechanism that we used in building the tree. When we built the tree, we relied on the fact that if we number the nodes in a complete binary tree successively from 1 as they are inserted, the number of nodes on the right-hand edge of each level will be a power of 2. This means that the numbers of the nodes on the right-hand side will be 1 less than a power of 2.
When we hop levels as we remove nodes, we must remember the parent as the frontier of the next level up. When we are about to save a null pointer into the variable that caused the original problem, we must instead save this pointer to the upper frontier.
After we get the parent of the node that we are going to move down the tree, we check its ID number. If it indicates that we are on the edge, we retain the parent for later use. The code looks like this:
if( _last->getID() == _power-1 ) { _frontier= parent; } Later in the function, we test the penultimate pointer to determine what to assign to the _last variable. The code looks as follows:
if ( penult != 0 ) { _last= penult; } else { _last= _frontier; }
5.1.10 Bug 9
5.1.10.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). We ran the same test case with the same test driver. We modified the movedown function to display the data structure at the beginning and end of the execution of the function. These displays are marked with
-
*** movedown ***
-
and
-
### movedown ###
-
respectively.
The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/h.exe test 1:8 8 6 5 2 7 3 4 1 remove 8 *** movedown *** 1(804bb38) L 804bbf8 R 804bbd8 P 0 S 0 ^ 0 6(804bbd8) L 804bb58 R 804bbb8 P 804bbf8 S 0 ^ 804bb38 5(804bbb8) L 0 R 0 P 804bb58 S 0 ^ 804bbd8 2(804bb58) L 0 R 0 P 804bb78 S 804bbb8 ^ 804bbd8 7(804bbf8) L 804bb98 R 804bb78 P 0 S 804bbd8 ^ 804bb38 3(804bb78) L 0 R 0 P 804bb98 S 804bb58 ^ 804bbf8 4(804bb98) L 0 R 0 P 0 S 804bb78 ^ 804bbf8 ### movedown ### 7(804bbf8) L 804bb98 R 804bbd8 P 0 S 0 ^ 0 6(804bbd8) L 804bb58 R 804bbb8 P 804bb98 S 0 ^ 804bbf8 5(804bbb8) L 0 R 0 P 804bb58 S 0 ^ 804bbd8 2(804bb58) L 0 R 0 P 804bb78 S 804bbb8 ^ 804bbd8 4(804bb98) L 804bb38 R 804bb78 P 0 S 804bbd8 ^ 804bbf8 3(804bb78) L 0 R 0 P 804bb38 S 804bb58 ^ 804bb98 1(804bb38) L 0 R 0 P 0 S 804bb78 ^ 804bb98 remove 7 *** movedown *** 1(804bb38) L 804bb98 R 804bbd8 P 0 S 0 ^ 0 6(804bbd8) L 804bb58 R 804bbb8 P 804bb98 S 0 ^ 804bb38 5(804bbb8) L 0 R 0 P 804bb58 S 0 ^ 804bbd8 2(804bb58) L 0 R 0 P 804bb78 S 804bbb8 ^ 804bbd8 4(804bb98) L 0 R 804bb78 P 0 S 804bbd8 ^ 804bb38 3(804bb78) L 0 R 0 P 804bb38 S 804bb58 ^ 804bb98 ### movedown ### 6(804bbd8) L 804bb98 R 804bbb8 P 0 S 0 ^ 0 5(804bbb8) L 804bb58 R 804bb38 P 804bb98 S 0 ^ 804bbd8 1(804bb38) L 0 R 0 P 804bb58 S 0 ^ 804bbb8 2(804bb58) L 0 R 0 P 804bb78 S 804bb38 ^ 804bbb8 4(804bb98) L 0 R 804bb78 P 0 S 804bbb8 ^ 804bbd8 3(804bb78) L 0 R 0 P 804bb38 S 804bb58 ^ 804bb98 remove 6 *** movedown *** 1(804bb38) L 804bb98 R 804bbb8 P 0 S 0 ^ 0 5(804bbb8) L 804bb58 R 0 P 804bb98 S 0 ^ 804bb38 2(804bb58) L 0 R 0 P 804bb78 S 0 ^ 804bbb8 4(804bb98) L 0 R 804bb78 P 0 S 804bbb8 ^ 804bb38 3(804bb78) L 0 R 0 P 804bb38 S 804bb58 ^ 804bb98 ### movedown ### 5(804bbb8) L 804bb98 R 804bb58 P 0 S 0 ^ 0 2(804bb58) L 804bb38 R 0 P 804bb98 S 0 ^ 804bbb8 1(804bb38) L 0 R 0 P 804bb78 S 0 ^ 804bb58 4(804bb98) L 0 R 804bb78 P 0 S 804bb58 ^ 804bbb8 3(804bb78) L 0 R 0 P 804bb38 S 804bb38 ^ 804bb98 remove 5 *** movedown *** 2(804bb58) L 804bb98 R 0 P 0 S 0 ^ 0 4(804bb98) L 0 R 804bb78 P 0 S 0 ^ 804bb58 3(804bb78) L 0 R 0 P 804bb38 S 804bb38 ^ 804bb98 ### movedown ### 2(804bb58) L 804bb98 R 0 P 0 S 0 ^ 0 4(804bb98) L 0 R 804bb78 P 0 S 0 ^ 804bb58 3(804bb78) L 0 R 0 P 804bb38 S 804bb38 ^ 804bb98 remove 2 *** movedown *** 4(804bb98) L 0 R 0 P 0 S 0 ^ 0 ### movedown ### 4(804bb98) L 0 R 0 P 0 S 0 ^ 0 remove 4 Program received signal SIGSEGV, Segmentation fault. 0x0804a102 in getLeft__4Heap (this=0x0) at Heap.h:15 15 inline Heap * getLeft() { return _left; } (gdb) bt #0 0x0804a102 in getLeft__4Heap (this=0x0) at Heap.h:15 #1 0x08049a5b in remove__4Heap (this=0x804bb38) at Heap.c:405 #2 0x08049c7b in sort__4Heap (this=0x804bb38) at Heap.c:464 #3 0x08049e7d in testSort__FP4Heap (in=0x804bb38) at HeapTest.c:114
5.1.10.2 The investigation
We have encountered another null pointer. We review the output and notice that the data structure has lost the character of a complete binary tree by the time the movedown function enters the second time. Since the structure is valid at the first exit and invalid on the second entry, the problem is likely with the processing that occurred in between.
What occurs between these calls is the execution of the remove function, so we focus our attention here. We saw the same symptom in the previous session, so it appears that our change may not have been sufficient.
Since we have had several instances of statements being executed under the wrong control-flow conditions, we decide to watch the execution of the statements that assign the _frontier variable. There is only one such statement in the remove function, so we add a command list that prints the values used to control the expression each time the breakpoint is encountered. The results of running this test are shown as follows:
(gdb) b Heap.c:402 (gdb) commands p Heap::_last->getID() p Heap::_power-1 end (gdb) run Starting program: /home/metzger/h.exe Breakpoint 1 at 0x8049a2b: file Heap.c, line 402. test 1:8 8 6 5 2 7 3 4 1 remove 8 Breakpoint 1, remove__4Heap (this=0x804bb38) at Heap.c:402 402 if ( _last->getID() == _power-1 ) { $1 = 8 $2 = 3 remove 7 Breakpoint 1, remove__4Heap (this=0x804bb38) at Heap.c:402 402 if ( _last->getID() == _power-1 ) { $3 = 4 $4 = 3 (gdb) c remove 6 Breakpoint 1, remove__4Heap (this=0x804bb38) at Heap.c:402 402 if ( _last->getID() == _power-1 ) { $5 = 7 $6 = 3 (gdb) c remove 5 Breakpoint 1, remove__4Heap (this=0x804bb38) at Heap.c:402 402 if ( _last->getID() == _power-1 ) { $7 = 3 $8 = 3 (gdb) c Breakpoint 1, remove__4Heap (this=0x804bb38) at Heap.c:402 402 if ( _last->getID() == _power-1 ) { $9 = 2 $10 = 3 (gdb) c Continuing. remove 4 Breakpoint 1, remove__4Heap (this=0x804bb38) at Heap.c:402 402 if ( _last->getID() == _power-1 ) { $11 = 0 $12 = 3 (gdb) c Program received signal SIGSEGV, Segmentation fault. 0x0804a102 in getLeft__4Heap (this=0x0) at Heap.h:15 We decide that we need to use a system for organizing our investigation. We choose the observation-hypothesis-experiment method.
Observation 1: The _power variable starts with the value 4 when it should be 8.
Hypothesis 1: The process of building the data structure is not correctly updating the variable.
Experiment 1: Watch the variable during the construction process.
Observation 2: The value of the _power variable never changes.
Hypothesis 2: There is a missing statement in the remove function.
Experiment 2: Search the text for a statement that reduces the variable’s value.
The results of running our first experiment are listed as follows:
Hardware watchpoint 1: Heap::_power test 1:8 Hardware watchpoint 1: Heap::_power Hardware watchpoint 1: Heap::_power Hardware watchpoint 1: Heap::_power Hardware watchpoint 1: Heap::_power Hardware watchpoint 1: Heap::_power Old value = 0 New value = 2 __4HeapiPi (this=0x804bb38, n=8, x=0x804b340) at Heap.c:44 Hardware watchpoint 1: Heap::_power Old value = 2 New value = 4 insert__4Heap (this=0x804bb58) at Heap.c:66 (gdb) c remove 8 remove 7 remove 6 remove 5 remove 2 remove 4 Program received signal SIGSEGV, Segmentation fault. 0x0804a102 in getLeft__4Heap (this=0x0) at Heap.h:15 15 inline Heap * getLeft() { return _left; } Observation 3: The variable _power is assigned twice during the construction of the binary tree. It is initialized to 2. Later it is multiplied by 2 in the code that handles insertion of the initial left branch. It is never modified by the sections of code that handle insertion of left and right children after the initial special case.
Hypothesis 3: The variable should be multiplied by 2 in the code that handles insertion of left branches after the first one.
Experiment 3: Add the code and run the test case again.
In this round of debugging, we applied the following methods from Chapter 3:
-
Eliminate impossible causes.
-
Use a system for organizing facts.
We found defects that had the following root causes, which are explained in Chapter 11:
-
Missing operation—missing statement
-
Invalid expression—extra term
5.1.10.3 The fault and correction
After a great deal of work, we decide that the following changes are necessary. We insert the following statement into the insert function in the code that handles inserting left children when the child starts a new level:
_power *= 2;
We change the code that detects the edge of a level to the following:
if( _last->getID() == _power ) { We insert a statement under the control of this statement, which reduces the _power variable when a level is detected:
_power /= 2;
5.1.11 Bug 10
5.1.11.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). We tested using the same test input and test driver as the previous case. The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/h.exe test 1:8 8 6 5 2 7 3 4 1 remove 8 last: 4 *** movedown *** 1(804bbc0) L 804bc80 R 804bc60 P 0 S 0 ^ 0 6(804bc60) L 804bbe0 R 804bc40 P 804bc80 S 0 ^ 804bbc0 5(804bc40) L 0 R 0 P 804bbe0 S 0 ^ 804bc60 2(804bbe0) L 0 R 0 P 804bc00 S 804bc40 ^ 804bc60 7(804bc80) L 804bc20 R 804bc00 P 0 S 804bc60 ^ 804bbc0 3(804bc00) L 0 R 0 P 804bc20 S 804bbe0 ^ 804bc80 4(804bc20) L 0 R 0 P 0 S 804bc00 ^ 804bc80 ### movedown ### 7(804bc80) L 804bc20 R 804bc60 P 0 S 0 ^ 0 6(804bc60) L 804bbe0 R 804bc40 P 804bc20 S 0 ^ 804bc80 5(804bc40) L 0 R 0 P 804bbe0 S 0 ^ 804bc60 2(804bbe0) L 0 R 0 P 804bc00 S 804bc40 ^ 804bc60 4(804bc20) L 804bbc0 R 804bc00 P 0 S 804bc60 ^ 804bc80 3(804bc00) L 0 R 0 P 804bbc0 S 804bbe0 ^ 804bc20 1(804bbc0) L 0 R 0 P 0 S 804bc00 ^ 804bc20 remove 7 last: 4 *** movedown *** 4(804bc20) L 0 R 804bc60 P 0 S 0 ^ 0 6(804bc60) L 804bbe0 R 804bc40 P 804bc20 S 0 ^ 804bc20 5(804bc40) L 0 R 0 P 804bbe0 S 0 ^ 804bc60 2(804bbe0) L 0 R 0 P 804bc00 S 804bc40 ^ 804bc60 ### movedown ### 4(804bc20) L 0 R 804bc60 P 0 S 0 ^ 0 6(804bc60) L 804bbe0 R 804bc40 P 804bc20 S 0 ^ 804bc20 5(804bc40) L 0 R 0 P 804bbe0 S 0 ^ 804bc60 2(804bbe0) L 0 R 0 P 804bc00 S 804bc40 ^ 804bc60 remove 4 8 7 4 Program exited normally.
5.1.11.2 The investigation
Our initial observation is that the data structure has lost the complete binary tree property after the item with key “7” has been removed. The tree display at the second entry to the movedown function has a null left child pointer. This can only occur when the root is the only node in the tree.
We also observe that the wrong node was inserted as the new root when the node with the key “7” was removed. The rightmost node on the lowest level should have been used. This was the item with key “5.” Instead the leftmost node on the level above was used. This was the item with the key “4.”
The candidate for next removal is identified by the variable _last.
The first course of action is to observe the values assigned to this variable. There are three places in the remove function where it is assigned. One of them always assigns a null pointer, and since this is not our problem, we can exclude it. We set a breakpoint at the remaining two assignments to watch the flow of values into this variable. On the first execution of the statement that assigns the value of the _frontier variable to the _last variable, the value is incorrect. The node with the key “4” is assigned, when it should be the node with key “5.” Suspicion now falls on the _frontier variable. We delete our breakpoints and set a new one to observe the flow of values into this variable. It is only assigned once, and the value it receives is the address of the node with the key “4.” We have found the culprit, but why is it getting this value?
After some consideration, we realize that we have overloaded the meaning of the variable. During both insertion and removal of nodes, this variable is intended to track the edge where nodes will next be inserted or removed. In the case of insertion, we track the left edge. In the case of removal, we track the right edge.
We have created the converse of an alibi. Instead of having multiple names for one value, we have one name for multiple values. Since the name covers both cases, and the phases are independent, perhaps this is not so bad. We must, however, use different means to identify the values that are assigned to this variable during these two phases.
In this round of debugging, we applied the following methods from Chapter 3:
-
Use alibis as clues.
-
Eliminate impossible causes.
We also applied the following method from Chapter 4:
-
The eureka zone
We found a defect that had the following root causes, explained in Chapter 11:
-
Missing operations—statements are missing
-
Reference errors—variable not assigned
5.1.11.3 The fault and correction
The original code that assigned the _frontier variable looked like the following. It is invoked when an edge is detected.
if ( _last->getID() == _power ) { _frontier= parent; _power /= 2; } To get the rightmost edge, we must walk the list of successors until we find a node that does not have a successor. This is the right edge.
if ( _last->getID() == _power ) { for ( curr= parent; curr != 0 ; curr= curr->getSucc() ) { prev= curr; } _frontier= prev; _power /= 2; }
5.1.12 Bug 11
5.1.12.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). We use the same test driver and input as the previous session. The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/h.exe test 1:8 8 6 5 2 7 3 4 1 remove 8 *** movedown *** 1(804bb78) L 804bc38 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 804bb98 R 804bbf8 P 804bc38 S 0 ^ 804bb78 5(804bbf8) L 0 R 0 P 804bb98 S 0 ^ 804bc18 2(804bb98) L 0 R 0 P 804bbb8 S 804bbf8 ^ 804bc18 7(804bc38) L 804bbd8 R 804bbb8 P 0 S 804bc18 ^ 804bb78 3(804bbb8) L 0 R 0 P 804bbd8 S 804bb98 ^ 804bc38 4(804bbd8) L 0 R 0 P 0 S 804bbb8 ^ 804bc38 ### movedown ### 7(804bc38) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 804bb98 R 804bbf8 P 804bbd8 S 0 ^ 804bc38 5(804bbf8) L 0 R 0 P 804bb98 S 0 ^ 804bc18 2(804bb98) L 0 R 0 P 804bbb8 S 804bbf8 ^ 804bc18 4(804bbd8) L 804bb78 R 804bbb8 P 0 S 804bc18 ^ 804bc38 3(804bbb8) L 0 R 0 P 804bb78 S 804bb98 ^ 804bbd8 1(804bb78) L 0 R 0 P 0 S 804bbb8 ^ 804bbd8 remove 7 *** movedown *** 5(804bbf8) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 804bb98 R 0 P 804bbd8 S 0 ^ 804bbf8 2(804bb98) L 0 R 0 P 804bbb8 S 0 ^ 804bc18 4(804bbd8) L 804bb78 R 804bbb8 P 0 S 804bc18 ^ 804bbf8 3(804bbb8) L 0 R 0 P 804bb78 S 804bb98 ^ 804bbd8 1(804bb78) L 0 R 0 P 0 S 804bbb8 ^ 804bbd8 ### movedown ### 5(804bbf8) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 804bb98 R 0 P 804bbd8 S 0 ^ 804bbf8 2(804bb98) L 0 R 0 P 804bbb8 S 0 ^ 804bc18 4(804bbd8) L 804bb78 R 804bbb8 P 0 S 804bc18 ^ 804bbf8 3(804bbb8) L 0 R 0 P 804bb78 S 804bb98 ^ 804bbd8 1(804bb78) L 0 R 0 P 0 S 804bbb8 ^ 804bbd8 remove 5 *** movedown *** 2(804bb98) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 0 R 0 P 804bbd8 S 0 ^ 804bb98 4(804bbd8) L 804bb78 R 804bbb8 P 0 S 804bc18 ^ 804bb98 3(804bbb8) L 0 R 0 P 804bb78 S 0 ^ 804bbd8 1(804bb78) L 0 R 0 P 0 S 804bbb8 ^ 804bbd8 ### movedown ### 2(804bb98) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 0 R 0 P 804bbd8 S 0 ^ 804bb98 4(804bbd8) L 804bb78 R 804bbb8 P 0 S 804bc18 ^ 804bb98 3(804bbb8) L 0 R 0 P 804bb78 S 0 ^ 804bbd8 1(804bb78) L 0 R 0 P 0 S 804bbb8 ^ 804bbd8 remove 2 *** movedown *** 3(804bbb8) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 0 R 0 P 804bbd8 S 0 ^ 804bbb8 4(804bbd8) L 804bb78 R 0 P 0 S 804bc18 ^ 804bbb8 1(804bb78) L 0 R 0 P 0 S 0 ^ 804bbd8 ### movedown ### 3(804bbb8) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 0 R 0 P 804bbd8 S 0 ^ 804bbb8 4(804bbd8) L 804bb78 R 0 P 0 S 804bc18 ^ 804bbb8 1(804bb78) L 0 R 0 P 0 S 0 ^ 804bbd8 remove 3 *** movedown *** 1(804bb78) L 804bbd8 R 804bc18 P 0 S 0 ^ 0 6(804bc18) L 0 R 0 P 804bbd8 S 0 ^ 804bb78 4(804bbd8) L 0 R 0 P 0 S 804bc18 ^ 804bb78 ### movedown ### 6(804bc18) L 804bbd8 R 804bb78 P 0 S 0 ^ 0 1(804bb78) L 0 R 0 P 804bbd8 S 0 ^ 804bc18 4(804bbd8) L 0 R 0 P 0 S 804bb78 ^ 804bc18 remove 6 8 7 5 2 3 6 Program exited normally.
5.1.12.2 The investigation
Our initial observation is that the data structure has lost the heap property after the node with key “7” is removed and the corresponding call to movedown has been completed. The node with key “5” is the parent of the node with key “6,” and that is not permissible. We will focus our attention on the movedown function.
Since the body of this function iterates until it determines that a node has moved into the right place, we decide to insert a statement at the top of the loop that prints the node being processed. This will enable us to trace the behavior of the loop. We also turn off the printing of the entire data structure, since we already know where it goes bad.
test 1:8 remove 8 this 1, left 804bc20, right 804bc00 this 1, left 804bbc0, right 804bba0 this 1, left 0, right 0 remove 7 this 1, left 0, right 0 remove 5 this 1, left 0, right 0 remove 2 this 1, left 0, right 0 remove 3 this 1, left 804bbc0, right 804bc00 this 1, left 0, right 0 remove 6 8 7 5 2 3 6
As we stare at the output, looking for a pattern, it hits us all at once—we have been using the this variable to refer both to the structure as a whole and to one node being moved in particular. The reason the process seemed to work is that for this particular data set, the node pointed to by this was the correct one to move, at least initially.
In this round of debugging, we applied the following method from Chapter 3:
-
Use gestalt understanding.
In this round of debugging, we also applied the following method from Chapter 4:
-
You are looking right at it.
We found a defect that had the following root cause, explained in Chapter 11:
-
Reference errors—wrong variable referenced
5.1.12.3 The fault and correction
The changes required for this correction are pervasive. Every reference to this in the function movedown has to be changed to a new variable move. This variable is initialized with the current root, which is the place where we always start moving a node. Since this function has changed so drastically, we have reproduced the new version here to facilitate discussion of the remaining bugs.
void Heap::movedown() { Heap *temp, *child, *move; move= _root; while ( true ) { Heap * left= move->getLeft(); Heap * right= move->getRight(); if ( left != 0 && right != 0 ) { if ( left->getKey() <= move->getKey() && right->getKey() <= move->getKey() ) { break; } else { child= (left->getKey() >= right->getKey()) ? left : right; } } else if ( left != 0 ) { if ( left->getKey() <= move->getKey() ) { break; } else { child= left; } } else { break; } // swap ID numbers int swap= move->getID(); move->setID(child->getID()); child->setID(swap); // swap incoming vertical pointers Heap * grand= move->getParent(); if ( grand != 0 ) { if ( move == grand->getLeft() ) { grand->setLeft(child); } else if ( move == grand->getRight() ) { grand->setRight(child); } } // swap outgoing vertical pointers move->setParent(child); child->setParent(grand); if ( child == move->getLeft() ) { if ( child->getLeft() != 0 ) { child->getLeft()->setParent(move); } move->setLeft(child->getLeft()); child->setLeft(move); if ( child->getRight() != 0 ) { if ( move->getRight() != 0 ) { temp= move->getRight()->getParent(); move->getRight()->setParent(child-> getRight()->getParent()); child->getRight()->setParent(temp); } else { child->getRight()->setParent(0); } } else { if ( move->getRight() != 0 ) { move->getRight()->setParent(child); } } temp= child->getRight(); child->setRight(move->getRight()); move->setRight(temp); } else if ( child == move->getRight() ) { if ( child->getRight() != 0 ) { child->getRight()->setParent(move); } move->setRight(child->getRight()); child->setRight(move); if ( child->getLeft() != 0 ) { if ( move->getLeft() != 0 ) { temp= move->getLeft()->getParent(); move->getLeft()->setParent(child-> getLeft()->getParent()); child->getLeft()->setParent(temp); } else { child->getLeft()->setParent(0); } } else { if ( move->getLeft() != 0 ) { move->getLeft()->setParent(child); } } temp= child->getLeft(); child->setLeft(move->getLeft()); move->setLeft(temp); } else { assert(0); } // swap incoming horizontal pointers if ( child->getPred() != 0 ) { if ( move->getPred() != 0 ) { temp= move->getPred()->getSucc(); move->getPred()->setSucc(child-> getPred()->getSucc()); child->getPred()->setSucc(temp); } else { child->getPred()->setSucc(move); } } else { if ( move->getPred() != 0 ) { move->getPred()->setSucc(child); } } if ( child->getSucc() != 0 ) { if ( move->getSucc() != 0 ) { temp= move->getSucc()->getPred(); move->getSucc()->setPred(child-> getSucc()->getPred()); child->getSucc()->setPred(temp); } else { child->getSucc()->setPred(move); } } else { if ( move->getSucc() != 0 ) { move->getSucc()->setPred(child); } } // swap outgoing horizontal pointers temp= move->getPred(); move->setPred(child->getPred()); child->setPred(temp); temp= move->getSucc(); move->setSucc(child->getSucc()); child->setSucc(temp); // update variables _active= _last->getParent(); if ( _root == move ) { _root= child; } } }
5.1.13 Bug 12
5.1.13.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). We are still using the same test input and test driver. The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/src/sort/save11/h.exe test 1:8 8 6 5 2 7 3 4 1 remove 8 remove 7 remove 6 remove 5 remove 4 remove 3 remove 2 remove 1 Program received signal SIGSEGV, Segmentation fault. 0x0804a772 in getLeft__4Heap (this=0x0) at Heap.h:15 15 inline Heap * getLeft() { return _left; } (gdb) bt #0 0x0804a772 in getLeft__4Heap (this=0x0) at Heap.h:15 #1 0x08049a87 in remove__4Heap (this=0x804c290) at Heap.c:414 #2 0x08049cb7 in sort__4Heap (this=0x804c290) at Heap.c:474 #3 0x0804a4f5 in testSort__FP4Heap (in=0x804c290) at HeapTest.c:131 ...
5.1.13.2 The investigation
Once again, we find a null pointer being dereferenced. At least we have the satisfaction of seeing all items being removed from the heap in the correct order. The exception occurs as we try to remove the final element. Perhaps we are getting close to the end.
We do not have a good idea to start, so we look over our records of what we have done. Back in the discussion of Bug 4, we said that we were going to add a statement into the insert function in the code that handles inserting left children when the child starts a new level. When we look in this code, we do not see an assignment to the _power variable, as we expected.
In this round of debugging, we applied the following methods from Chapter 4:
-
Tail thyself.
-
Look once, look well.
We found a defect that had the following root cause, explained in Chapter 11:
-
Missing operations—statements missing
5.1.13.3 The fault and correction
The change required to fix this problem is rather small. The following code is inserted as we had previously promised:
if ( this->getID() == _power ) { _power *= 2; }
5.1.14 Bug 13
5.1.14.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). Since our code seems to be getting more reliable, we decide to add some more tests. The test input and test driver are listed as follows:
// sorted up, power of 2 length int t01[8]= { 1,2,3,4,5,6,7,8 }; // sorted up, non-power of 2 length int t02[9]= { 2,3,5,7,11,13,17,19,23 }; // sorted down, power of 2 length int t03[16]= { 32,30,28,26,24,22,20,18,16,14,12,10,8,6,4,2 }; // sorted down, non-power of 2 length int t04[14]= { 27,25,23,21,19,17,15,13,11,9,7,5,3,1 }; // “V” pattern, power of 2 length int t05[16]= { 2, 5, 11, 17, 29, 37, 47, 57, 61, 53, 41, 31, 23, 13, 7, 3 }; // “V” pattern, non-power of 2 length int t06[11]= { 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3 }; // inverse “V” pattern, power of 2 length int t07[32]= { 109, 103, 97, 87, 79, 71, 61, 57, 47, 41, 31, 23, 17, 11, 5, 2, 3, 7, 13, 19, 29, 37, 43, 53, 59, 67, 73, 83, 89, 101, 107, 111 }; // inverse “V” pattern, non-power of 2 length int t08[31]= { 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31 }; // random values, power of 2 length int t09[16]= { 2, 3, 43, 47, 5, 7, 37, 41, 11, 13, 29, 31, 17, 23, 53, 57 }; // random values, non-power of 2 length int t10[20]= { 2, 71, 3, 67, 5, 61, 7, 59, 11, 57, 13, 53, 17, 47, 23, 43, 29, 41, 31, 37 }; //----------------------------------------------------- int main() { Heap *node, *first; fprintf(stderr,”test 1:8\n”); node= new Heap(8, t01); testBuild(node); testSort(node); fprintf(stderr,”test 2:9\n”); node= new Heap(9, t02); testBuild(node); testSort(node); fprintf(stderr,”test 3:16\n”); node= new Heap(16, t03); testBuild(node); testSort(node); fprintf(stderr,”test 4:14\n”); node= new Heap(14, t04); testBuild(node); testSort(node); fprintf(stderr,”test 5:16\n”); node= new Heap(16, t05); testBuild(node); testSort(node); fprintf(stderr,”test 6:11\n”); node= new Heap(11, t06); testBuild(node); testSort(node); fprintf(stderr,”test 7:32\n”); node= new Heap(32, t07); testBuild(node); testSort(node); fprintf(stderr,”test 8:31\n”); node= new Heap(31, t08); testBuild(node); testSort(node); } void testBuild(Heap *node) { draw(node->getRoot()); fprintf(stderr,”\n”); } void testSort(Heap *in) { Heap * node= in->sort(); for( ; node != 0; node= node->getSucc() ) { fprintf(stderr,”%d “, node->getKey()); } fprintf(stderr,”\n”); } The results of running this test are shown as follows. In the interest of
conserving space, we show only the results from the first six tests.
test 1:8 8 6 5 2 7 3 4 1 remove 8 remove 7 remove 6 remove 5 remove 4 8 7 6 5 4 test 2:9 23 13 11 3 19 5 17 7 2 remove 23 remove 19 remove 17 remove 13 remove 11 remove 7 23 19 17 13 11 7 test 3:16 32 28 20 4 6 22 8 10 30 24 12 14 26 16 18 2 remove 32 remove 30 remove 28 remove 26 remove 24 remove 22 remove 20 remove 18 remove 16 remove 14 remove 12 remove 2 32 30 28 26 24 22 20 18 16 14 12 2 test 4:14 27 23 15 1 17 3 5 25 19 7 9 21 11 13 remove 27 remove 25 remove 23 remove 21 remove 19 remove 13 27 25 23 21 19 13 test 5:16 61 37 29 7 13 31 23 5 57 53 41 11 47 17 3 2 remove 61 remove 57 remove 53 remove 47 remove 41 remove 37 remove 31 remove 29 remove 23 remove 17 remove 13 remove 11 remove 2 61 57 53 47 41 37 31 29 23 17 13 11 2 test 6:11 12 11 10 4 9 6 3 5 8 7 2 remove 12 remove 11 remove 10 remove 9 remove 8 remove 7 remove 2 12 11 10 9 8 7 2
5.1.14.2 The investigation
In each case, all of the items removed are in the proper order. Anywhere from two to six items are missing. Sometimes the node with the smallest key is removed, but sometimes it is not.
We are getting a little tired, so we decide to go after “the usual suspects” and look a little closer at the changes we just made. In this case, we insert some statements to generate a trace of important values in the insert function.
To make our life simpler, we go back to running just the first test case. We put four separate statements into the insert statement to print an identification, together with the key and sequential ID number of the node being sorted. We suspect that something is wrong with the variable that tracks the power of 2 that corresponds to the ID number of the complete binary tree nodes, so we print it as well. The results of the trace are listed as follows:
test 1:8 insert 1 key= 2, ID= 2 insert 2 key= 3, ID= 3 insert 3 key= 4, ID= 4 insert 2 key= 5, ID= 5 insert 4 key= 6, ID= 6 insert 2 key= 7, ID= 7 insert 3 key= 8, ID= 8 8 6 5 2 7 3 4 1 remove 8 remove 7 remove 6 remove 5 remove 4 8 7 6 5 4
We observe that the value of the _power variable is given a final adjustment at the end of building the complete binary tree. Unfortunately, the adjustment is in the wrong direction. While inserting nodes, the variable tracks forward motion and leads the actual values referenced, except when the threshold is reached. When removing nodes, the variable tracks backward motion and trails the actual values referenced, except when the threshold is reached. We were right to put a final adjustment of the variable, but we adjusted it the wrong way.
In this round of debugging, we applied the following methods from Chapter 4:
-
You are looking right at it.
-
Look for domestic drift.
We found a defect that had the following root cause, explained in Chapter 11:
-
Invalid expression—wrong arithmetic operator is used
5.1.14.3 The fault and correction
This correction is fairly easy. We change the final adjustment of the _power variable from
_power *= 2;
to
_power /= 2;
5.1.15 Bug 14
5.1.15.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). The test input and test driver are the same as the previous session. The results of running this test are listed as follows:
(gdb) run Starting program: /home/metzger/src/sort/save14/h.exe test 1:8 8 6 5 2 7 3 4 1 remove 8 remove 7 remove 6 remove 5 remove 4 remove 3 remove 2 remove 1 Program received signal SIGSEGV, Segmentation fault. 0x0804a152 in getLeft__4Heap (this=0x0) at Heap.h:15 15 inline Heap * getLeft() { return _left; } (gdb) bt #0 0x0804a152 in getLeft__4Heap (this=0x0) at Heap.h:15 #1 0x08049a9b in remove__4Heap (this=0x804bb58) at Heap.c:422 #2 0x08049ccb in sort__4Heap (this=0x804bb58) at Heap.c:482 #3 0x08049ed1 in testSort__FP4Heap (in=0x804bb58) at HeapTest.c:133 ... (gdb) q
5.1.15.2 The investigation
We are back to removing all the nodes in the correct order. This is the same result we had during session 8. We are once again dereferencing a null pointer. This pointer points to the parent of the node we are currently removing. Is there any case in which a node will have a null pointer for a parent? The answer is yes, when the node is the root of the tree. Either the node is the root, or it is not, and if it is, there is a great deal of processing in the remove function that is completely unnecessary. The sort function will terminate if the _root variable is a null pointer, so all we need to do when removing the final node is copy the value of the root pointer, set the root pointer to null, and return the copy. The calling function will see that it is done and terminate processing.
In this round of debugging, we applied the following method from Chapter 4:
-
Use the power of logic.
We found defects that had the following root causes, which are explained in Chapter 11:
-
Missing operations—statements are missing
-
Control-flow problems—statement controlled by wrong control-flow condition
5.1.15.3 The fault and correction
The correction is straightforward. We put the majority of the body of the remove function under the control of the following statement:
if ( parent != 0 ) { This eliminates the exception.
5.1.16 Bug 15
5.1.16.1 The evidence
The next debugging session began by running the application under the GNU debugger (gdb). We are using the same test case and test input as in the previous session.
The results of running this test are shown as follows:
(gdb) run Starting program: /home/metzger/src/sort/save15/h.exe test 1:8 8 6 5 2 7 3 4 1 remove _root 8; _last 1 last: 5 ### movedown ### 7(804c3d8) L 804c378 R 804c3b8 P 0 S 0 ^ 0 6(804c3b8) L 804c338 R 804c398 P 804c378 S 0 ^ 804c3d8 5(804c398) L 0 R 0 P 804c338 S 0 ^ 804c3b8 2(804c338) L 0 R 0 P 804c358 S 804c398 ^ 804c3b8 4(804c378) L 804c318 R 804c358 P 0 S 804c3b8 ^ 804c3d8 3(804c358) L 0 R 0 P 804c318 S 804c338 ^ 804c378 1(804c318) L 0 R 0 P 0 S 804c358 ^ 804c378 remove _root 7; _last 5 last= 2 ### movedown ### 6(804c3b8) L 804c378 R 804c398 P 0 S 0 ^ 0 5(804c398) L 804c338 R 0 P 804c378 S 0 ^ 804c3b8 2(804c338) L 0 R 0 P 804c358 S 0 ^ 804c398 4(804c378) L 804c318 R 804c358 P 0 S 804c398 ^ 804c3b8 3(804c358) L 0 R 0 P 804c318 S 804c338 ^ 804c378 1(804c318) L 0 R 0 P 0 S 804c358 ^ 804c378 remove _root 6; _last 2 last= 3 ### movedown ### 5(804c398) L 804c378 R 804c338 P 0 S 0 ^ 0 2(804c338) L 0 R 0 P 804c378 S 0 ^ 804c398 4(804c378) L 804c318 R 804c358 P 0 S 804c338 ^ 804c398 3(804c358) L 0 R 0 P 804c318 S 0 ^ 804c378 1(804c318) L 0 R 0 P 0 S 804c358 ^ 804c378 remove _root 5; _last 3 last= 1 ### movedown ### 4(804c378) L 804c358 R 804c338 P 0 S 0 ^ 0 2(804c338) L 0 R 0 P 804c358 S 0 ^ 804c378 3(804c358) L 804c318 R 0 P 0 S 804c338 ^ 804c378 1(804c318) L 0 R 0 P 0 S 0 ^ 804c358 remove _root 4; _last 1 last: 2 ### movedown ### 3(804c358) L 804c318 R 804c338 P 0 S 0 ^ 0 2(804c338) L 0 R 0 P 804c318 S 0 ^ 804c358 1(804c318) L 0 R 0 P 0 S 804c338 ^ 804c358 remove _root 3; _last 2 last= 1 ### movedown ### 2(804c338) L 804c318 R 0 P 0 S 0 ^ 0 1(804c318) L 0 R 0 P 0 S 0 ^ 804c338 remove _root 2; _last 1 last: 2 ### movedown ### 1(804c318) L 0 R 0 P 0 S 0 ^ 0 remove _root 1; _last 2 last= 3 ### movedown ### 1(804c318) L 0 R 0 P 0 S 0 ^ 0 remove _root 1; _last 3 last= 4 ### movedown ### 1(804c318) L 0 R 0 P 804c338 S 0 ^ 0 remove _root 1; _last 4 last= 5 ### movedown ### 1(804c318) L 0 R 0 P 804c318 S 804c318 ^ 0 remove _root 1; _last 5 last= 6 ### movedown ### 1(804c318) L 0 R 0 P 804c318 S 804c318 ^ 0 remove _root 1; _last 6 last= 7 ### movedown ### 1(804c318) L 0 R 0 P 804c318 S 804c318 ^ 0 remove _root 1; _last 7 last= 8 ### movedown ### 1(804c318) L 0 R 0 P 804c318 S 804c318 ^ 0 remove _root 1; _last 8 // infinite loop
5.1.16.2 The investigation
The obvious thing we notice is that while the _root variable converges to the node with the key of “1,” as it should, the _last variable seems to cycle through nodes that have already been processed. It appears that it is referring to storage that is no longer connected to the tree. Is there somewhere that this variable should be updated? We look through the source for instances where _root is updated, but _last is not. We quickly find one at the end of the movedown function, where after the pointers internal to the nodes are updated, several static variables are also updated.
This will fix the problem with the pattern of values in the _last variable, but does not address the infinite loop.
We look again at the condition controlling normal processing in the remove function. What we want to detect is the situation where exactly one node exists in the tree, and that has no connections. The current test does not consider the connections, so we need an alternative.
In this round of debugging, we applied the following methods from Chapter 4:
-
Exercise curiosity.
-
Show how something could be done.
We found a defect that had the following root causes, explained in Chapter 11:
-
Missing operations—statements are missing
-
Control-flow problems—statement controlled by wrong control-flow condition
5.1.16.3 The fault and correction
We correct the lack of an update to the _last variable by including it in the swapping activity that is going on between the node pointed to by move and the one pointed to by child.
if( _last == child ) { _last= move; } We correct the condition guarding normal processing in the remove function by replacing it with the following test:
if( _root != 0 && _root->getLeft() != 0 ) { This ensures that there is one node, no connections, and it tests the existence of the root pointer before dereferencing it.
To make sure that we have fixed the last problem, we run the program one more time with all test cases and minimal debugging output. The results are shown as follows:
test 1:8 8 7 6 5 4 3 2 1 test 2:9 23 19 17 13 11 7 5 3 2 test 3:16 32 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 test 4:14 27 25 23 21 19 17 15 13 11 9 7 5 3 1 test 5:16 61 57 53 47 41 37 31 29 23 17 13 11 7 5 3 2 test 6:11 12 11 10 9 8 7 6 5 4 3 2 test 7:32 111 109 107 103 101 97 89 87 83 79 73 71 67 61 59 57 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2 test 8:31 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 5 4 3 2 1 test 9:16 57 53 47 43 41 37 31 29 23 17 13 11 7 5 3 2 test 10:20 71 67 61 59 57 53 47 43 41 37 31 29 23 17 13 11 7 5 3 2
The code for the final program is listed below.
#ifndef _Heap_h_ #define _Heap_h_ class Heap { public: // constructors and destructors Heap(int, int); Heap(int, int *); // accessors inline int getKey() { return _key; } inline int getID() { return _id; } inline Heap * getLeft() { return _left; } inline Heap * getRight() { return _right; } inline Heap * getParent() { return _parent; } inline Heap * getPred() { return _pred; } inline Heap * getSucc() { return _succ; } inline Heap * getRoot() { return _root; } inline Heap * getActive() { return _active; } inline Heap * getLast() { return _last; } inline Heap * getFrontier() { return _frontier; } inline int getPower() { return _power; } // mutators inline void setKey(int x) { _key= x; } inline void setID(int x) { _id= x; } inline void setLeft(Heap * x) { _left= x; } inline void setRight(Heap * x) { _right= x; } inline void setParent(Heap * x) { _parent= x; } inline void setPred(Heap * x) { _pred= x; } inline void setSucc(Heap * x) { _succ= x; } inline void setRoot(Heap *x) { _root= x; } inline void setActive(Heap *x) { _active= x; } inline void setLast(Heap *x) { _last= x; } inline void setFrontier(Heap *x) { _frontier= x; } inline void setPower(int x) { _power= x; } // workers void insert(); void movedown(); void moveup(); Heap * remove(); void replace(Heap *); Heap * sort(); void print(); void moveFrontier(); private: static Heap * _root; // tree root static Heap * _active; // node currently // receiving children static Heap * _last; // node with highest ID // on current level static Heap * _frontier; // node on the edge of // the last full level static int _power; // ID value of leftmost node // on each level int _key; // key value int _id; // successive integer assigned to nodes struct Heap * _left; // left child node struct Heap * _right; // right child node struct Heap * _parent; // parent node struct Heap * _pred; // predecessor node on this level struct Heap * _succ; // successor node on this level }; void list(Heap *); void draw(Heap *); #endif ________________________________________________________ #include <stdio.h> #include <stdlib.h> #include <assert.h> #include “Heap.h” //----------------------------------------------------- // static variables //----------------------------------------------------- Heap * Heap::_root; Heap * Heap::_active; Heap * Heap::_last; Heap * Heap::_frontier; int Heap::_power; //----------------------------------------------------- // construct an individual heap node //----------------------------------------------------- Heap::Heap(int x, int y) { _key= x; _id= y; _left= 0; _right= 0; _parent= 0; _pred= 0; _succ= 0; } //----------------------------------------------------- // construct a heap from the provided data // the node returned is located somewhere on the heap // to get the root: // Heap *n= new Heap(count,values); // Heap *root= n->getRoot(); //----------------------------------------------------- Heap::Heap(int n, int *x ) { _key= x[0]; _id= 1; _left= 0; _right= 0; _parent= 0; _pred= 0; _succ= 0; _root= this; _active= this; _last= 0; _frontier= 0; _power= 2; for ( int i= 1; i < n; ++i ) { Heap *node= new Heap(x[i], i+1); node->insert(); node->moveup(); } _power /= 2; } //----------------------------------------------------- // insert a Heap node at the end of the heap //----------------------------------------------------- void Heap::insert() { this->setPred(0); this->setSucc(0); if ( _active->getLeft() == 0 ) { _active->setLeft(this); this->setParent(_active); if ( this->getID() == _power ) { _frontier= this; _power *= 2; } _last= this; } else if ( _active->getRight() == 0 ) { _active->setRight(this); this->setParent(_active); _last->setSucc(this); this->setPred(_last); if ( this->getID() == _power-1 ) { _active= _frontier; } _last= this; } else { _active= _last->getParent()->getSucc(); if ( _active == 0 ) { _active= _frontier; _active->setLeft(this); this->setParent(_active); _frontier= this; } else { _active->setLeft(this); this->setParent(_active); _last->setSucc(this); this->setPred(_last); } if ( this->getID() == _power ) { _power *= 2; } _last= this; } Heap * parent= this->getParent(); if ( this->getKey() > parent->getKey() ) { // update variables if ( _frontier == this ) { _frontier= parent; } _last= parent; _active= this; } } //----------------------------------------------------- // re-arrange the heap after appending a node at the // end of the binary tree so that the heap property // is preserved //----------------------------------------------------- void Heap::moveup() { Heap *temp; while ( true ) { Heap * parent= this->getParent(); if ( !parent || parent->getKey() >= this->getKey() ) { break; } // swap ID numbers int swap= parent->getID(); parent->setID(this->getID()); this->setID(swap); // swap incoming vertical pointers Heap * grand= parent->getParent(); if ( grand != 0 ) { if ( parent == grand->getLeft() ) { grand->setLeft(this); } else if ( parent == grand->getRight() ) { grand->setRight(this); } } // swap outgoing vertical pointers parent->setParent(this); this->setParent(grand); if ( this == parent->getLeft() ) { if ( this->getLeft() != 0 ) { this->getLeft()->setParent(parent); } parent->setLeft(this->getLeft()); this->setLeft(parent); if ( this->getRight() != 0 ) { if ( parent->getRight() != 0 ) { temp= parent->getRight() ->getParent(); parent->getRight()->setParent( this->getRight() ->getParent()); this->getRight()->setParent(temp); } else { this->getRight()->setParent(0); } } else { if ( parent->getRight() != 0 ) { parent->getRight()->setParent(this); } } temp= this->getRight(); this->setRight(parent->getRight()); parent->setRight(temp); } else if ( this == parent->getRight() ) { if ( this->getRight() != 0 ) { this->getRight()->setParent(parent); } parent->setRight(this->getRight()); this->setRight(parent); if ( this->getLeft() != 0 ) { if ( parent->getLeft() != 0 ) { temp= parent->getLeft()->getParent(); parent->getLeft()->setParent( this->getLeft() ->getParent()); this->getLeft()->setParent(temp); } else { this->getLeft()->setParent(0); } } else { if ( parent->getLeft() != 0 ) { parent->getLeft()->setParent(this); } } temp= this->getLeft(); this->setLeft(parent->getLeft()); parent->setLeft(temp); } else { assert(0); } // swap incoming horizontal pointers if ( this->getPred() != 0 ) { if ( parent->getPred() != 0 ) { temp= parent->getPred()->getSucc(); parent->getPred()->setSucc( this->getPred() ->getSucc()); this->getPred()->setSucc(temp); } else { this->getPred()->setSucc(parent); } } else { if ( parent->getPred() != 0 ) { parent->getPred()->setSucc(this); } } if ( this->getSucc() != 0 ) { if ( parent->getSucc() != 0 ) { temp= parent->getSucc()->getPred(); parent->getSucc()->setPred( this->getSucc() ->getPred()); this->getSucc()->setPred(temp); } else { this->getSucc()->setPred(parent); } } else { if ( parent->getSucc() != 0 ) { parent->getSucc()->setPred(this); } } // swap outgoing horizontal pointers temp= parent->getPred(); parent->setPred(this->getPred()); this->setPred(temp); temp= parent->getSucc(); parent->setSucc(this->getSucc()); this->setSucc(temp); // update variables _active= _last->getParent(); if ( _root == parent ) { _root= this; } } } //----------------------------------------------------- // re-arrange the heap after inserting a new root node // in the binary tree so that the heap property is // preserved //----------------------------------------------------- void Heap::movedown() { Heap *temp, *child, *move; move= _root; while ( true ) { Heap * left= move->getLeft(); Heap * right= move->getRight(); if ( left != 0 && right != 0 ) { if ( left->getKey() <= move->getKey() && right->getKey() <= move->getKey() ) { break; } else { child= (left->getKey() >= right->getKey()) ? left : right; } } else if ( left != 0 ) { if ( left->getKey() <= move->getKey() ) { break; } else { child= left; } } else { break; } // swap ID numbers int swap= move->getID(); move->setID(child->getID()); child->setID(swap); // swap incoming vertical pointers Heap * grand= move->getParent(); if ( grand != 0 ) { if ( move == grand->getLeft() ) { grand->setLeft(child); } else if ( move == grand->getRight() ) { grand->setRight(child); } } // swap outgoing vertical pointers move->setParent(child); child->setParent(grand); if ( child == move->getLeft() ) { if ( child->getLeft() != 0 ) { child->getLeft()->setParent(move); } move->setLeft(child->getLeft()); child->setLeft(move); if ( child->getRight() != 0 ) { if ( move->getRight() != 0 ) { temp= move->getRight()->getParent(); move->getRight()->setParent( child->getRight() ->getParent()); child->getRight()->setParent(temp); } else { child->getRight()->setParent(0); } } else { if ( move->getRight() != 0 ) { move->getRight()->setParent(child); } } temp= child->getRight(); child->setRight(move->getRight()); move->setRight(temp); } else if ( child == move->getRight() ) { if ( child->getRight() != 0 ) { child->getRight()->setParent(move); } move->setRight(child->getRight()); child->setRight(move); if ( child->getLeft() != 0 ) { if ( move->getLeft() != 0 ) { temp= move->getLeft()->getParent(); move->getLeft()->setParent( child->getLeft() ->getParent()); child->getLeft()->setParent(temp); } else { child->getLeft()->setParent(0); } } else { if ( move->getLeft() != 0 ) { move->getLeft()->setParent(child); } } temp= child->getLeft(); child->setLeft(move->getLeft()); move->setLeft(temp); } else { assert(0); } // swap incoming horizontal pointers if ( child->getPred() != 0 ) { if ( move->getPred() != 0 ) { temp= move->getPred()->getSucc(); move->getPred()->setSucc( child->getPred() ->getSucc()); child->getPred()->setSucc(temp); } else { child->getPred()->setSucc(move); } } else { if ( move->getPred() != 0 ) { move->getPred()->setSucc(child); } } if ( child->getSucc() != 0 ) { if ( move->getSucc() != 0 ) { temp= move->getSucc()->getPred(); move->getSucc()->setPred( child->getSucc() ->getPred()); child->getSucc()->setPred(temp); } else { child->getSucc()->setPred(move); } } else { if ( move->getSucc() != 0 ) { move->getSucc()->setPred(child); } } // swap outgoing horizontal pointers temp= move->getPred(); move->setPred(child->getPred()); child->setPred(temp); temp= move->getSucc(); move->setSucc(child->getSucc()); child->setSucc(temp); // update variables _active= _last->getParent(); if ( _root == move ) { _root= child; } if ( _last == child ) { _last= move; } } } //----------------------------------------------------- // remove the largest element from the heap and // restore the structure to have the heap properties //----------------------------------------------------- Heap * Heap::remove() { Heap * node= _root; Heap * curr, * prev; if ( _root == 0 ) { return 0; } if ( _root != 0 && _root->getLeft() != 0 ) { // unlink last node Heap * penult= _last->getPred(); if ( penult != 0 ) { penult->setSucc(0); } Heap * parent= _last->getParent(); if ( _last->getID() == _power ) { for ( curr= parent; curr != 0 ; curr= curr->getSucc() ) { prev= curr; } _frontier= prev; _power /= 2; } if ( parent != 0 ) { if ( _last == parent->getLeft() ) { parent->setLeft(0); } else { parent->setRight(0); } // link last node in as root if ( _root->getLeft() != 0 ) { _root->getLeft()->setParent(_last); } if ( _root->getRight() != 0 ) { _root->getRight()->setParent(_last); } _last->setLeft(_root->getLeft()); _last->setRight(_root->getRight()); _last->setParent(0); _last->setSucc(0); _last->setPred(0); _last->setID(_root->getID()); _root= _last; } if ( penult != 0 ) { _last= penult; } else { _last= _frontier; } movedown(); } else { _last= 0; _root= 0; _frontier= 0; } // unlink removed node node->setLeft(0); node->setRight(0); node->setParent(0); node->setSucc(0); node->setPred(0); node->setID(0); return node; } //----------------------------------------------------- // heap sort a linked list //----------------------------------------------------- Heap * Heap::sort() { Heap * head; Heap * last= 0; Heap * next= 0; while( _root != 0 ) { next= this->remove(); if ( next == 0 ) { break; } if ( last == 0 ) { head= next; next->setPred(0); } else { next->setPred(last); last->setSucc(next); } last= next; } _root= head; _last= last; _active= 0; _frontier= 0; return head; } 
EAN: 2147483647
Pages: 172
- Challenging the Unpredictable: Changeable Order Management Systems
- The Effects of an Enterprise Resource Planning System (ERP) Implementation on Job Characteristics – A Study using the Hackman and Oldham Job Characteristics Model
- Healthcare Information: From Administrative to Practice Databases
- Relevance and Micro-Relevance for the Professional as Determinants of IT-Diffusion and IT-Use in Healthcare
- Development of Interactive Web Sites to Enhance Police/Community Relations