Incorrect handling of size in all primitive maps

[Rob Eden]

When adjusting elements in a primitive hashmap, no check is made whether the new value equals the no_entry_value. If this is the case. The entry should be removed and the size should be updated accordingly.

For example, take a simple TIntIntHashMap. Call put(1,1) and then call adjust(1,-1). The result is a map of size 1, while the value for key 1 is 0, which equals the no_entry_value. Hence, the size should be 0.

This applies also to the adjustOrPut method, the transformValues method, the forEach... methods etc. Basically, everywhere where the values array is updated, a check should be done if the result equals the no_entry_value and if so, the states array should be set to FREE and the size should be updated.

[Rob Eden]

Original SF bug

Comments...

Johan Parent:

I see the point you are making. And indeed the behaviour seems wrong in the case where no_entry_value is the default (zero). The logic does not handle this. Generally speaking the common operations are free of such additional checks for no_entry_{key|value}.

Your point is valid and illustrates a tricky aspect of the API. One could argue that the default no_entry_{key|value} should be something else. Like the MAX_VALUE of the corresponding 'primitive classes'. In that case the size() problem you raise would still occur but with other values.

Johan Parent:

Come to think of it. Scratch my previous comment.

The no_entry_XY are tokens that replace 'null' in the jdk's API. Since the trove native impl. can not handle all scenario's it allows you to specify you own 'invalid value|key'.

What can be confusing is that a no_entry_value or no_entry_key do not mean that the Map entry in itself is invalid and therefore should not be counted (i.e. included in the size())

Anonymous

I see your point as well, however, this results in an incorrect equality.

Suppose that I take two maps, in the first, I add the pair (1,1) and in the second, the pair (2,1). Then, in the first map, I adjust the value (1, -1) and in the second (2, -1). The maps now both contain one key, referring to 0, however these are different keys.

Nonetheless, the equals method returns true (assuming that the fix I reported earlier is added).

In my view, since "null" does not exist for primitive types, "null" should not be allowed as a key, nor a value in the map and hence the size should be corrected on every update.

Anonymous

It seems that the problem with equality can be solved by checking if the "that_states" array equals "FULL" as well, i.e. if you want to allow for a "null" element to be different from "0", then you should compare the states, as well as the values. The equals method then becomes (for TLongIntHashMap):

/* {@inheritDoc} /

@Override

public boolean equals( Object other ) {

if ( ! ( other instanceof TLongIntMap ) ) {

return false;

}

TLongIntMap that = ( TLongIntMap ) other;

if ( that.size() != this.size() ) {

return false;

}

int[] values = _values;

byte[] states = _states;

int this_no_entry_value = getNoEntryValue();

int that_no_entry_value = that.getNoEntryValue();

for ( int i = values.length; i-- > 0; ) {

if ( states[i] == FULL ) {

if (that.states[i] != FULL) {

return false

}

long key = _set[i];

int that_value = that.get( key );

int this_value = values[i];

if ( ( this_value != that_value ) && (

( this_value != this_no_entry_value ) ||

( that_value != that_no_entry_value ) ) ){

return false;

}

}

}

return true;

}

Rob Eden:

Hmm... thorny issue. Is this the correct behavior? I guess I can't think of anything better to do, but this doesn't seem quite right.

Anonymous:

If you allow for "null" values and hence have a no_entry_value, then you should check separately for key containment, i.e. the equality method should check if "that" contains each key and if so, if the stored value for that key is equal, or if both maps store "no_entry_value".

If you do not allow for "null" values then size should be updated on every put / adjust action and the equals can skip checking for key containment, but still needs to check if keys are equal, or if both maps store "no_entry_value".

In both cases, the equals method needs to be fixed as the current implementation is wrong either way.

Anonymous:

I think the issue here arises from the fact that no_entry_{key|value} is in primitive collections, and not in Decorators.

Primitive collections by definition are not able to store null's, and cannot return null's. I don't see any reason for a "special" value, while everything is strictly in primitives. It's need starts only when a collection is decorated.

From what I see, primitive collections nowhere treat no_entry_key in any way special (only for filling the unused part of arrays with it - i.e. irrelevant).

So I think the best solution is to move no_entry_key from primitive collections to their decorators, and handle them there.

I hope that all primitive maps and lists work the same as in trove 2, whatever no_entry_{key|value} value is?

Rob Eden:

I don't think it's a matter of different operation between Trove 2 & 3. I'm pretty sure the test case described in the original details would still be a problem in 2. Would be interesting to know if that's not the case.

Bumping up priority now that 3.0.2 is out the door.

Anonymous:

Issues 3439390 and 3432399 are basically because of the same cause, and I am not talking about of these three issues specifically.

Trove 2 didn't have no_entry_{key|value}, right?

Primitive collection shouldn't be able to store "null's", and that is the only reason for existence of no_entry_{key|value} ? (or I am missing something)

In primitive collections, I see that no_entry_{key|value} is used only in reset (list) and removeAt and equals (map).

I think if no_entry_{key|value} is moved to decorators, that would be the cleanest way to do it.

In any case, for this specific issue, even if value is null, Map is counting those in count(), why wouldn't they count?

Rob Eden

Haven't looked at it in much detail yet, but my guess is you're getting a bit too stuck on no_entry_*. They didn't exist in 2.x per se, but it was basically there and just always zero. They were put in because there was great weeping and gnashing of teeth about that being constant.

Correct, they need to be there because you need to know what to return if you say:

TObjectIntMap map = ...

int what_goes_here = map.get( "SomethingNotInMap" );

I wouldn't personally have supported the no_entry_key (yes, for decorators)... but Jeff chose to in his implementation, so it's fine with me. (Null keys are evil.)

Anyway, let me write some test cases and investigate more and I'll get back to you.

[Rob Eden]

More comments from original bug...

Rob Eden

After looking at this, I think I disagree with the bug. Here's my test case: :::java public void testAdjustToNoEntry() { TObjectIntMap<String> map = new TObjectIntHashMap<String>();

    assertEquals( 0, map.getNoEntryValue() );
    assertEquals( 0, map.get( "NotInThere" ) );

    map.put( "Value", 1 );
    assertEquals( 1, map.size() );
    assertEquals( 1, map.get( "Value" ) );
    assertTrue( map.containsKey( "Value" ) );
    assertTrue( map.containsValue( 1 ) );
    assertTrue( Arrays.equals( new int[] { 1 }, map.values() ) );

    map.adjustValue( "Value", -1 );
    assertEquals( 1, map.size() );
    assertEquals( 0, map.get( "Value" ) );
    assertTrue( map.containsKey( "Value" ) );
    assertTrue( map.containsValue( 0 ) );
    assertTrue( Arrays.equals( new int[] { 0 }, map.values() ) );
}

So, we have a result where the value stored is actually the no_entry_value, or zero. That's returned from the get() and everything appears to function correctly. Obviously, at this point the only way to tell that the value is really in the map is to use containsKey().

However, this behaves exactly like the java.util collections when null is put in a map for a value. Likewise, null would be returned from a get() so you'd only be able to tell from contains().

So, I believe this is functioning as it should. If you set a value to be the same as the marker for no value (whatever it is), then yes, things get a bit more confusing. But, I believe they're operating correctly.

I'm open to rebuttal though...

Anonymous

I agree that, if you interpret the no_entry_value to correspond to null, then you are right, i.e. the size is handled correctly and should not be updated. This behavior is indeed consistent with the java collections framework. Also, in that case, the behavior of adjustValue is correct, since it only changes the stored value. However, if that is the case, then the implementation of equality is wrong, see bug [3432399] as shown by the following code:

// initialize the int maps
TIntIntMap intMap1 = new TIntIntHashMap();
TIntIntMap intMap2 = new TIntIntHashMap();

intMap1.put(1, 1);
intMap1.put(2, 2);
intMap2.put(1, 1);
intMap2.put(2, 2);

// confirm symmetric equality
assert intMap1.equals(intMap2);
assert intMap2.equals(intMap1);

// in the second map, change value for 2 to 0 (null)
intMap2.put(2, 0);

// confirm symmetric equality
assert !intMap2.equals(intMap1);
assert !intMap1.equals(intMap2); // ERROR here

In my view, allowing for null-elements is an important design decision. Depending on the use of the maps, you may have different requirements. For example, when using a map to represent a multiset, or bag, of integers, then 0 and no_entry_value should be equal.

[Rob Eden]

I've added the test case TPrimitivePrimitiveHashMapTest.testIssue3 which runs the test described in the last comment. The comparison does not fail in the manner described, so I believe this issue was resolved.