Concurrency issue with arrays (Java)

Question

For the algorithm I'm working on, I tried to develop a blacklist mechanism that can blacklist arrays in a certain way: if "1, 2, 3" is blacklisted, "1, 2, 3, 4, 5" is also considered blacklisted list.
I am pleased with the solution that I have come up with so far. But there seem to be some serious issues when I access the blacklist from multiple threads. The "contains" method (see code below) sometimes returns true, even if the array is not blacklisted. This problem does not occur if I use only one thread, so this is most likely a concurrency problem.
I tried to add some synchronization but didn't change anything. I also tried several slightly different implementations using the 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){ 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; } } 

}

Answer 1

Edit: I led your code through a ten-thread test suite, adding and comparing thousands of templates, but I could not find anything wrong with your implementation. I believe that you are misinterpreting your data. For example, in a streaming environment, this sometimes returns false:

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

Another thread changed the blacklist between the first call, but before the second call. This is normal behavior, and the class itself cannot do anything to stop it. If this is not the behavior you want, you can synchronize it outside the class:

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

Original answer:
You are synchronizing the root of the node, but this does not synchronize any of its children. All you need to do to make your bulletproof class synchronize the add(int[]) and contains(int[]) methods and then not leak any links. This ensures that only one thread can ever use a Blacklist object.

I was looking for your code trying to figure it out, so you can also use 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); } } } 

Collection structure can make you a lot easier. You do not make any benefits by overriding ArrayList.

Here I use HashMap, so you do not need to allocate more than 9000 links for something like this:

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