Concurrency problem with arrays (Java)

For an algorithm I'm working on I tried to develop a blacklisting mechanism that can blacklist arrays in a specific way: If "1, 2, 3" is blacklisted "1, 2, 3, 4, 5" is also considered blacklisted.

I'm quite happy with the solution I've come up with so far. But there seem to be some serious problems when I access a blacklist from multiple threads. The method "contains" (see code below) sometimes returns true, even if an array is not blacklisted. This problem does not occur if I only use one thread, so it most likely is a concurrency problem.

I've tried adding some synchronization, but it didn't change anything. I also tried some slightly different implementations using java.util.concurrent classes. Any ideas on how to fix this?

public class Blacklist {

private static final int ARRAY_GROWTH = 10;

private final Node root = new Node();

private static class Node{

    private volatile Node[] childNodes = new Node[ARRAY_GROWTH];

    private volatile boolean blacklisted = false;

    public void blacklist(){
        this.blacklisted = true;
        this.childNodes = null;
    }
}

public void add(final int[] array){

    synchronized (root) {

        Node currentNode = this.root;

        for(final int edge : array){
      开发者_Python百科      if(currentNode.blacklisted)
                return;

            else if(currentNode.childNodes.length <= edge) {
                currentNode.childNodes = Arrays.copyOf(currentNode.childNodes, edge + ARRAY_GROWTH);
            }

            if(currentNode.childNodes[edge] == null) {
                currentNode.childNodes[edge] = new Node();
            }

            currentNode = currentNode.childNodes[edge];
        }

        currentNode.blacklist();
    }


}

public boolean contains(final int[] array){

    synchronized (root) {

        Node currentNode = this.root;

        for(final int edge : array){
            if(currentNode.blacklisted)
                return true;

            else if(currentNode.childNodes.length <= edge || currentNode.childNodes[edge] == null)
                return false;

            currentNode = currentNode.childNodes[edge];
        }

        return currentNode.blacklisted;

    }

}

}

Edit: I ran your code through a test suite with ten threads adding and comparing thousands of patterns, but I could find nothing wrong with your implementation. I believe you are misinterpreting your data. For example, in a threaded environment this will sometimes return false:

// sometimes this can be false
blacklist.contains(pattern) == blacklist.contains(pattern);

Another thread altered the blacklist between after the first call, but before the second call. This is normal behaviour and the class itself can't do anything to stop it. If this isn't the behaviour you want, you can synchronize it from outside of the class:

synchronized (blacklist) {
    // this will always be true
    blacklist.contains(pattern) == blacklist.contains(pattern);
}

Original response:
You synchronize the root node, but this does not synchronize any of its children. All you have to do to make your class bulletproof is synchronize the add(int[]) and contains(int[]) methods and then don't leak any references. This ensures that only one thread can ever be using a Blacklist object at one time.

I fiddled with your code while trying to make sense of it, so you might as well have it:

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Blacklist {
    private final Node root = new Node(Integer.MIN_VALUE, false);

    public synchronized void add(int[] array) {
        if (array == null) return;
        Node next, cur = root;

        for(int i = 0; i < array.length-1 && !cur.isLeaf(); i++) {
            next = cur.getChild(array[i]);

            if (next == null) { 
                next = new Node(array[i], false);
                cur.addChild(next);
            }

            cur = next;
        }

        if (!cur.isLeaf()) {
            next = cur.getChild(array[array.length-1]); 
            if (next == null || !next.isLeaf())
                cur.addChild(new Node(array[array.length-1], true));
        }
    }

    public synchronized boolean contains(int[] array) {
        if (array == null) return false;
        Node cur = root;

        for (int i = 0; i < array.length; i++) {
            cur = cur.getChild(array[i]);
            if (cur == null) return false;
            if (cur.isLeaf()) return true;
        }

        return false;
    }

    private static class Node {
        private final Map<Integer, Node> children; 
        private final int value;

        public Node(int _value, boolean leaf) { 
            children = (leaf?null:new HashMap<Integer, Node>());
            value = _value;
        }

        public void addChild(Node child) { children.put(child.value, child); }
        public Node getChild(int value) { return children.get(value); }
        public boolean isLeaf() { return (children == null); }

    }
}

The Collections framework can make things a lot easier for you. You're not doing yourself any favors by reimplementing ArrayList.

Here I use a HashMap so that you don't have to allocate over 9000 references for a something like this:

blacklist.add(new int[] {1, 2000, 3000, 4000});