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){
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;
}
}
}
