/*
* 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 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) {
if (
key == null) {
throw new
NullPointerException();
}
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) {
if (
key == null) {
throw new
NullPointerException();
}
//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;
}
}
}