Glynn Clements wrote:
Markus Metz wrote:
That thing branch[i].child is a pointer to the next node in the tree, if
I understand the code correctly.
It's either a pointer to the child or, at the lowest level (where
there are no children), an integer ("tid").
Hmmm. What when RTreeInsertRect() is called by RTreeDeleteRect() during
reinsertion? For internal nodes, tmp_nptr->b.child was a pointer to a
node, but now it is cast to an integer, and this integer gets stuffed
back into tmp_nptr->b.child?
This is a standard tree design, not
only of RTrees, but of many search trees. So your condition #2 would be
violated, because a pointer is passed as an integer to RTreeInsertRect().
Not if the "pointer" is actually an integer which was stuffed into the
field, which is exactly what index.c:119 does:
b.child = (struct Node *)tid;
That's not the problem and works. The problem is if b.child is really a
pointer to a node. b.child was originally stuffed with an integer only
for level 0, not for higher levels.
In case of root split
b.child = *root; /* old root node */
and
b.child = newnode; /* new node just below root */
No integer is stuffed in there.
During insertion, a node somewhere between root and level 0 may need to
be splitted. Then it says
b.child = n2; /* n2: pointer to node */
No integer is stuffed in there.
/* */ comments by me.
The bulk of the nodes in reInsertList are probably internal nodes, not
end nodes, i.e. tmp_nptr->branch[i].child is a pointer to a node, an
integer was not stuffed in there.
I believe the compile warning was there for a reason.
The compiler complains because, on a 64-bit architecture, casting a
pointer to an "int" results in truncation. The compiler has no way of
knowing whether the "pointer" is just an integer which was stuffed
into the field.
If the code used a union of an int and a "struct Node *", instead of
just a "struct Node *", the resulting machine code would be identical,
but the compiler wouldn't complain because the code would "explain
itself" to the compiler's satisfaction.
During deletion, (int)tmp_nptr->branch[i].child is done. I think the
idea is to get both a node pointer if tmp_nptr is an internal node and
the tid if tmp_nptr is on level 0.
During reinsertion I would really like to pass a pointer if b.child is a
pointer to the next node. If tmp_nptr->branch[i].child is cast to an
integer, and we want to keep that behaviour, we would need to use off_t
and LFS for the rtree library. I can't judge if a union would work in
this case without off_t usage: (off_t)tmp_nptr->branch[i].child, because
the address of tmp_nptr->branch[i].child is needed for internal nodes.
The branch structure holds the rectangle (bounding box) and a pointer to
a node. The rectangle is what the spatial index is really after,
therefore I decided to put the feature id in the branch structure, next
to the rectangle. I gave all internal nodes a feature id of 0, in the
hope that e.g. line numbers start with 1 and not with 0. I'm sure there
is a more elegant solution, but with this you could build in some more
safety checks.
This solution is LFS-independent, but increases the size of the branch
structure, thus requiring more memory. The required changes to the code
are still minimal.
To me it seems that the solution interfering the least with the current
code would be to make use of off_t (only some replacements of int with
off_t) and adjust the Makefile for rtree accordingly. Somehow this
appears to me more dangerous than my solution with an additional int id,
but I can't give precise reasons why. Maybe because higher-level code
would have to be adjusted too, at least everything using a
SearchHitCallback with RTreeSearch().
As I said, I understand the concept better than the code. At least, I
think that passing around pointer addresses as integer is not good
coding practise.
In short, I think even when using a union of an int and a "struct Node
*", additional changes are required. You want to give it a try?
BTW, I think it is possible that this is also the reason in the new
ticket #494.
_______________________________________________
grass-dev mailing list
[email protected]
http://lists.osgeo.org/mailman/listinfo/grass-dev
