Posible array out of bounds in QNode

[ng-dmc]

Hi,

I believe it's possible to get OOB if values.length == 0 here:

tinspin-indexes/src/main/java/org/tinspin/index/qthypercube2/QNode.java

Lines 116 to 123 in fc9e7fd

	private void addValue(PointEntry<T> e, int maxNodeSize) {
	//Allow overflow over max node size (for example for lots of identical values in node)
	int maxLen = nValues >= maxNodeSize ? nValues * 2 : maxNodeSize;
	if (nValues >= getValues().length) {
	values = Arrays.copyOf(getValues(), Math.min(nValues * 3, maxLen));
	}
	getValues()[nValues++] = e;
	}

And the empty array could be created here:

tinspin-indexes/src/main/java/org/tinspin/index/qthypercube2/QNode.java

Line 335 in fc9e7fd

values = new PointEntry[nTotal];

[tzaeschke]

@ng-dmc Thanks, I will have a look. Do you happen to have a test case?

[ng-dmc]

Here it is:

package com.example;

import java.util.Arrays;
import org.tinspin.index.qthypercube2.QuadTreeKD2;

public class Main {

    static void test(double[][] data) {
        QuadTreeKD2<Integer> tree = QuadTreeKD2.create(2);
        for (int i = 0; i < data.length; i++) {
            if (data[i][3] == 0) {
                tree.insert(Arrays.copyOf(data[i], 2), (int)data[i][2]);
            } else {
                tree.remove(Arrays.copyOf(data[i], 2), (int)data[i][2]);
            }
        }
    }
    public static void main(String[] args) {
        double[][] data = new double[][] {
            new double[]{-49.0949020385742, -2.05027413368225, 819588127, 0},
            new double[]{-49.0949020385742, -2.05027389526367, 819588127, 0},
            new double[]{-45.6938514709473, 32.9847145080566, -2056090140, 0},
            new double[]{-45.6938514709473, 32.9847145080566, -2056090140, 0},
            new double[]{-1.7595032453537, 112.097793579102, -267989921, 0},
            new double[]{-1.75950336456299, 112.097793579102, -267989921, 0},
            new double[]{45.6938438415527, 32.9847145080566, 1591613824, 0},
            new double[]{45.6938438415527, 32.9847145080566, 1591613824, 0},
            new double[]{49.0948944091797, -2.05027413368225, 14481734, 0},
            new double[]{49.0948944091797, -2.05027389526367, 14481734, 0},
            new double[]{-49.0949020385742, -2.05027413368225, 819588127, 1},
            new double[]{-49.0949020385742, -2.05027389526367, 819588127, 1},
            new double[]{-49.0949020385742, -2.05027413368225, 916603126, 0},
        };
        test(data);
    }
}

[tzaeschke]

@ng-dmc Thanks, excellent test!

I found at least two problems, a logical one and a precision problem.

I fill first fix the logical problem (should be easy enough) and then, in a separate patch, fix the precision problem. This may take a few days to resolve.

As a workaround I can suggest using the PH-tree instead (which doesn't have precision problems like quadtrees do).

Alternatively if you want to use the qt2 index, you could

• first insert a key at [0,0] (this will create a center for the tree),
• then a key at [64,64] (or some other power of two, ideally larger than your data space), this will resize the root node,
• then add you data,
• then remove [0,0] and [64,64]

[tzaeschke]

Also, in case you are using the PH-Tree, and in case you want to store duplicate points (as in the unit test), make sure to use the PointMultiMap version.

[tzaeschke]

@ng-dmc I just merged #41 which should fix the array out of bounds issue. Feel free to try it out (from master).

The precision problem (that I mentioned above) is tracked in #42. It will not cause any exception and I don't think it can cause any correctness problems.

[ng-dmc]

Thanks! I will check it out.

[tzaeschke]

I'll close the issue. Let me know if the problem occurs again.