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