neo4j/neo4j — pull request #945 by tinwelint (2013-07-09 12:31:40+00:00)
Title: Fixes problem with relationship iterator not seeing new loaded relationships

Problem manifests like this:
Calling node.getRelationships() and iterating through them might give
only a subset of all relationships the first time, compared to subsequent
calls.

Problem distilled to be:
A problem with the chained IdBlocks in RelIdArray objects. To save memory
the IdBlock kept relationship ids as int[], grouped them by the "high bits"
alongside a long containing the high bits separately. Ids <= 0xFFFFFFFF
even has got an IdBlock implementation without a high bits field.
When a new id where added its high bits signature was compared to the last
IdBlock created in the chain of IdBlocks - if matching it was added,
otherwise a new IdBlock was created with that high bits signature, its
"prev" link pointing to the IdBlock that previously was the last one and
the id added to it.
RelIdArray is capable of having three of these chains (out, in, loop).

(RelIdArray)-[:out]->(A)

==> becomes

(RelIdArray)-[:out]->(B)-[:prev]->(A)

An iterator (RelIdIterator) started from the last created IdBlock (in this
case B) going backwards, iterating through each IdBlock in its wake. After
fully depleting the iterator new relationships might get loaded lazily
(happens the first time a node visits each relationships if not cached).
Loaded ids would always be added to (B) or even a new IdBlock (C) if there was
a high bits signature mismatch, and so the iterator would be left stranded
on (A), never being able to see added ids.

Solution in this commit:
Simplify by removing the concept of chain of IdBlocks and have one
space-efficient IdBlock implementation capable of storing ids <= 0xFFFFFFFF
and another less space-efficient implementation capable of storing any id
and use the upgrade ability (upgrading from the "low" IdBlock to the
"high" IdBlock when needed). This will make sure there's only zero or one
IdBlock for any given direction (out, in, loop) and simpler code. At the
expense of slightly higher memory consumption.

Future solition:
Only have one IdBlock implementation that is capable of efficiently
storing any id, e.g. using a byte[] where each id added only consume least
necessary amount of bytes.