Misunderstanding, silly error, or compiler bug?
Regan Heath
regan at netmail.co.nz
Fri Aug 10 06:28:44 PDT 2007
Peter C. Chapin wrote:
> I'm new to D and I'm having some trouble with an access violation error
> that I can't figure out. Either I'm misunderstanding something basic
> about D's semantics (which is very possible) or perhaps there is a
> compiler bug.
>
> I'm using dmd v1.020 and I'm trying to write a simple binary tree
> template as an exercise. The problem is in the insert method. The full
> text of tree.d is below. My complete test program, named tree_driver.d, is:
>
> ---> tree_driver.d <---
> import tree;
>
> int main( )
> {
> Tree!(int) my_tree = new Tree!(int);
>
> my_tree.insert( 5 );
> my_tree.insert( 3 );
> return( 0 );
> }
> ---> end <---
>
> I compile this with the command
>
> dmd tree_driver.d
>
> There are no errors or warnings during compilation. When I execute this
> program I get the following output:
>
> A: new_item = 5
> B:
> A: new_item = 3
> C:
> D: current.data = 5
> Error: Access Violation
>
> The first two trace points (A and B) are when the root node is created.
> That is handled as a special case. When the three is inserted, there is
> an access violation between point D and the upcoming point E (see tree.d
> below). It seems like the critical statement is:
>
> if( new_item < current.data ) current = current.left;
>
> The values of new_item and current.data appear to be correct. Thus the
> condition is true. The reference current points at the root node (at
> this time) and thus current.left should be null because of the way the
> root node was initialized earlier. In that case the while loop should
> end normally and "E:" should be printed.
>
> Any suggestions as to where the problem might be?
>
> Thanks!
>
> Peter
>
> ---> tree.d <---
> import std.stdio;
>
> class Tree(T) {
> private {
>
> // Nodes are handled by reference.
> class Node {
> public:
> Node left;
> Node right;
> Node parent;
> T data;
> };
>
> Node root;
> uint count;
> }
>
> this( )
> {
> root = null;
> count = 0;
> }
>
> // Adds a copy of the new_item to the tree.
> void insert( T new_item )
> {
> Node fresh = new Node;
> fresh.data = new_item;
> fresh.left = null;
> fresh.right = null;
>
> writefln("A: new_item = %d", new_item);
> if( count == 0 ) {
> writefln("B:");
> root = fresh;
> fresh.parent = null;
> count = 1;
> }
> else {
> Node current = root;
> Node previous;
> writefln("C:");
> while( current != null ) {
> previous = current;
> writefln("D: current.data = %d", current.data);
> if( new_item < current.data ) current = current.left;
> else if( new_item > current.data ) current = current.right;
> else return;
> }
> writefln("E:");
> fresh.parent = previous;
> if( new_item < previous.data ) previous.left = fresh;
> else if( new_item > previous.data ) previous.right = fresh;
> ++count;
> writefln("F: count = %d", count);
> }
> }
> }
>
The problem is the line:
while( current != null ) {
this is an equality comparrison and therefore calls:
current.opEquals
and as current is null that's a null dereference.
What you want is:
while( current !is null ) {
which does an 'identity' comparrison on the reference against null.
Regan
More information about the Digitalmars-d-learn
mailing list