Pointer association and red-black trees

[Simon_Geard]

I'm trying to implement a red-black tree in Fortran. Rather than starting from scratch I'm translating some c-code I found on the internet. Both the original code and my Fortran versions are attached together with a Makefile; the c version works as I expect.

The problem I'm having is that line 373

            newn%parent => oldn%parent

seems to corrupt the contents of oldn but not on the first invocation. Tested with 14.0.1.139.

Is this a compiler bug, a typo in my code or something else. I've been thinking about this all afternoon and just can't see what the problem is. Any help greatly appreciated.

Simon

[Simon_Geard]

Sorry, an old version othe the archive was attached in my first post.

[IanH]

Its been a few days - but did you ever get to the bottom of this?

In case you didn't - I think you have an issue with unintended aliasing.  In the C code there are pointers to objects being passed by value - after it has been passed the value of such a pointer can only be changed by operations directly on the pointer argument inside the C function.  That is not the case with the Fortran code - if you change another pointer that is associated with a pointer argument - you also change the pointer argument (the pointer arguments are being passed by reference).

I think the details is that in the Fortran case `newn%parent` is aliased with `oldn`, so `newn%parent` => `oldn%parent` changes what `oldn` points to.  `oldn` hasn't been corrupted, it is just pointing at a different object.

There was a question on stackoverflow a week or so ago, with a similar cause identified by others, that prompted me to go looking for this sort of issue here.

You may need to make copies of your pointer arguments when a procedure is entered to emulate the C behaviour.  Alternatively it may be more productive to recast the source in a more Fortran friendly manner - get rid of the pointer result functions and reduce the number of pointer arguments.

Edit to note that another possibility is to wrap the pointer references in a derived type - for example:

type rbtree_node_ref
  type(rbtree_node_t), pointer :: item => NULL()
end type rbtree_node_ref

type rbtree_node_t
  ...
  type(rbtree_node_ref) :: left
  type(rbtree_node_ref) :: right
  type(rbtree_node_ref) :: parent
end type rbtree_node_t

You end up with a heap of %item's scattered throughout your low level functions, but in addition to the aliasing issue above, this wrapper approach can help to avoid issues such as accidentally using normal assignment rather than pointer assignment. 

(When F2008 support is complete, there's also the potential (only potential - other considerations may prevent this or make it not worth pursuing) that the left and right components could become allocatables - that is the parent owns its children - which might also help with the robustness of the code.)

[Simon_Geard]

I haven't yet got to the bottom of this but I have logged a support call with Premier Support. They are getting different behaviour between Windows and Linux, and in addition to the problem above I get a different (later) error on Linux according to the level of optimization.

The subtleties of pointer aliasing of procedure arguments are something that I was worried about because I don't think I understand them properly. I will think about what you've said - I like your derived-type idea. I will also investigate giving the 'value' attribute to the pointer arguments.

I will post the conclusion of Premier Support when I have it.
 

[IanH · Accepted solution]

I think the output from the attached matches that of your C code.  See the *_arg dummy arguments and use of a temporary pointer to emulate the semantics of C passing of pointers in rotate_* and replace_node.  I have a variation on this using a _ref derived type that I'll post later, but its gone a bit ... dotty.

[Simon_Geard]

Yes thank you  - that works beautifully. Now I can test my new understanding by translating the delete_node routines.

I tried the 'value' attribute but there is a language constraint that disallows it. I don't understand why that should be, particularly because the additional isolation association which you've added to make the code behave correctly could be the defined behaviour for 'pointer, value' arguments.

[IanH]

Here's my dotty (I like user defined operators, perhaps a bit too much) node_ref variant.  I'm in two minds as to whether this approach was worthwhile.

I've also "parameterised" (include + use rename hack) out the value and key types so that they are known at compile time - which will result in more efficient code.  Unfortunately this may mean that you can't use a bare integer type as the key, but reverting back to default integer shouldn't be too big a change.

I think there was a memory leak in the original C code - insertion of an object where the key already existed in the tree still malloc'd a node to be inserted, but then never did anything with that node - because there was already a matching node in the tree it just copied the new value into that existing node.

[jimdempseyatthecove]

>>I think there was a memory leak in the original C code - insertion of an object where the key already existed in the tree still malloc'd a node to be inserted, but then never did anything with that node - because there was already a matching node in the tree it just copied the new value into that existing node.

And that leads to the design question as to the protocol for handling duplicate keys as well as other design considerations: Are duplicate keys permitted or not? Is the internal node allocated by the caller and passed into the tree .OR. does the caller pass in a packet and the insert function performs the copy if duplicate or allocate and copy if unique (leaving the caller's arguments alone). Does the find return a reference to the internal node or return a newly allocated copy of the node? etc...

Jim Dempsey