SubstringMap.java
/*
* JBoss, Home of Professional Open Source.
* Copyright 2014 Red Hat, Inc., and individual contributors
* as indicated by the @author tags.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package io.undertow.util;
import static org.wildfly.common.Assert.checkNotNullParamWithNullPointerException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* A string keyed map that can be accessed as a substring, eliminating the need to allocate a new string
* to do a key comparison against.
* <p>
* This class uses linear probing and is thread safe due to copy on write semantics. As such it is not recomended
* for data that changes frequently.
* <p>
* This class does not actually implement the map interface to avoid implementing unnecessary operations.
*
* @author Stuart Douglas
*/
public class SubstringMap<V> {
private static final int ALL_BUT_LAST_BIT = ~1;
private volatile Object[] table = new Object[16];
private int size;
public SubstringMatch<V> get(String key, int length) {
return get(key, length, false);
}
public SubstringMatch<V> get(String key) {
return get(key, key.length(), false);
}
private SubstringMatch<V> get(String key, int length, boolean exact) {
if(key.length() < length) {
throw new IllegalArgumentException();
}
Object[] table = this.table;
int hash = hash(key, length);
int pos = tablePos(table, hash);
int start = pos;
while (table[pos] != null) {
if(exact) {
if(table[pos].equals(key)) {
return (SubstringMatch<V>) table[pos + 1];
}
} else {
if (doEquals((String) table[pos], key, length)) {
return (SubstringMatch<V>) table[pos + 1];
}
}
pos += 2;
if(pos >= table.length) {
pos = 0;
}
if(pos == start) {
return null;
}
}
return null;
}
private int tablePos(Object[] table, int hash) {
return (hash & (table.length - 1)) & ALL_BUT_LAST_BIT;
}
private boolean doEquals(String s1, String s2, int length) {
if(s1.length() != length || s2.length() < length) {
return false;
}
for(int i = 0; i < length; ++i) {
if(s1.charAt(i) != s2.charAt(i)) {
return false;
}
}
return true;
}
public synchronized void put(String key, V value) {
checkNotNullParamWithNullPointerException("key", key);
Object[] newTable;
if (table.length / (double) size < 4 && table.length != Integer.MAX_VALUE) {
newTable = new Object[table.length << 1];
for (int i = 0; i < table.length; i += 2) {
if (table[i] != null) {
doPut(newTable, (String) table[i], table[i + 1]);
}
}
} else {
newTable = new Object[table.length];
System.arraycopy(table, 0, newTable, 0, table.length);
}
doPut(newTable, key, new SubstringMap.SubstringMatch<>(key, value));
this.table = newTable;
size++;
}
public synchronized V remove(String key) {
checkNotNullParamWithNullPointerException("key", key);
//we just assume it is present, and always do a copy
//for this maps intended use cases as a path matcher it won't be called when
//the value is not present anyway
V value = null;
Object[] newTable = new Object[table.length];
for (int i = 0; i < table.length; i += 2) {
if (table[i] != null && !table[i].equals(key)) {
doPut(newTable, (String) table[i], table[i + 1]);
} else if (table[i] != null) {
value = (V) table[i + 1];
size--;
}
}
this.table = newTable;
if(value == null) {
return null;
}
return ((SubstringMatch<V>)value).getValue();
}
private void doPut(Object[] newTable, String key, Object value) {
int hash = hash(key, key.length());
int pos = tablePos(newTable, hash);
while (newTable[pos] != null && !newTable[pos].equals(key)) {
pos += 2;
if (pos >= newTable.length) {
pos = 0;
}
}
newTable[pos] = key;
newTable[pos + 1] = value;
}
public Map<String, V> toMap() {
Map<String, V> map = new HashMap<>();
Object[] t = this.table;
for(int i = 0; i < t.length; i += 2) {
if(t[i] != null) {
map.put((String)t[i], ((SubstringMatch<V>)t[i+1]).value);
}
}
return map;
}
public synchronized void clear() {
size = 0;
table = new Object[16];
}
private static int hash(String value, int length) {
if (length == 0) {
return 0;
}
int h = 0;
for (int i = 0; i < length; i++) {
h = 31 * h + value.charAt(i);
}
return h;
}
public Iterable<String> keys() {
return new Iterable<String>() {
@Override
public Iterator<String> iterator() {
final Object[] tMap = table;
int i = 0;
while (i < table.length && tMap[i] == null) {
i += 2;
}
final int startPos = i;
return new Iterator<String>() {
private Object[] map = tMap;
private int pos = startPos;
@Override
public boolean hasNext() {
return pos < table.length;
}
@Override
public String next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
String ret = (String) map[pos];
pos += 2;
while (pos < table.length && tMap[pos] == null) {
pos += 2;
}
return ret;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
};
}
public static final class SubstringMatch<V> {
private final String key;
private final V value;
public SubstringMatch(String key, V value) {
this.key = key;
this.value = value;
}
public String getKey() {
return key;
}
public V getValue() {
return value;
}
}
}