I'm looking for feedback on my URLEncoder implementation, which is a drop-in replacement for Apache Tomcat's URLEncoder. It was completely ignored by the project committers (and I got no feedback why) and I'm curious if it's just that bad, or I failed to communicate why it's better than the original one.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You 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 org.apache.catalina.util;
import java.nio.Buffer;
import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.charset.Charset;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.CoderResult;
import java.nio.charset.CodingErrorAction;
import java.util.BitSet;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
/**
*
*/
public class URLEncoder {
/**
* This constant determines how many characters
* the encoder can process at once
*/
private static final int CHAR_BUFFER_SIZE = 8;
/**
* On one hand, the output buffer should be large
* enough to avoid most overflow conditions when
* possible. On the other hand too large buffer
* is a waste of space
*/
private static final int BYTE_BUFFER_SIZE = CHAR_BUFFER_SIZE * 2;
/**
* How many encoding entries should be cached in each pool
*/
private static final int DEFAULT_POOL_CAPACITY = 16;
/**
* Do not cache StringBuilders with larger capacity because it's a
* waste of heap space
*/
private static final int MAX_STRING_BUILDER_CAPACITY = 1024;
/**
* The initial capacity of the newly allocated StringBuilders.
*/
private static final int INITIAL_STRING_BUILDER_CAPACITY = 64;
/**
* Mask for extracting the lower four bits of a byte
*/
private static final int MASK_LOW = 0x0f;
/**
* Mask for extracting the higher four bits of a byte
*/
private static final int MASK_HIGH = 0xf0;
/**
* Each encoded byte must be prefixed with the percent sign
*/
private static final char PERCENT = '%';
/**
* The hexadecimal alphabet
*/
private static final char[] HEXADECIMAL = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
};
/**
* This class is to hold together all objects
* needed for an encoding operation, in order
* to use a single pool instead of several
*/
private static class PoolEntry {
CharsetEncoder charsetEncoder;
CharBuffer charBuffer;
ByteBuffer byteBuffer;
StringBuilder stringBuilder;
}
/**
* Efficiently remember which characters should not be encoded
*/
protected final BitSet safeCharacters = new BitSet(256);
/**
* Cache the already created encoders and buffers
* in order to avoid excessive memory allocation
*
* The more pools there are, the less lock contention
* there will be. The number of pools must be a power
* of two, in order to be able to quickly choose
* the pool index.
*/
private final BlockingQueue<PoolEntry>[] pools;
/**
* The pool index is calculated by INTEGER & (NUMBER_OF_POOLS - 1) == POOL INDEX.
* This is actually a very fast modulus division, but works only for
* number of pools that is a power of two
*/
private final int maskPoolIndex;
/**
* A default instance with number of pools equal to the number of available processors
* and with the default pool capacity
*/
public static final URLEncoder DEFAULT = new URLEncoder();
static {
DEFAULT.addSafeCharacter('~');
DEFAULT.addSafeCharacter('-');
DEFAULT.addSafeCharacter('_');
DEFAULT.addSafeCharacter('.');
DEFAULT.addSafeCharacter('*');
DEFAULT.addSafeCharacter('/');
}
/**
* Create a new encoder instance with the
* ASCII alphanumeric characters added to the
* safe characters list and number of pools
* equal to the nearest power of two that is
* bigger than or equal to the number of
* available processors
*/
public URLEncoder() {
this(getNumberOfProcessors(), DEFAULT_POOL_CAPACITY);
}
private static int getNumberOfProcessors() {
return Runtime.getRuntime().availableProcessors();
}
/**
* Create a new encoder instance with the
* ASCII alphanumeric characters added to the
* safe characters list and number of pools equal
* to the nearest power of two that is bigger
* than or equal to <code>numberOfPools</code>
*
* @param numberOfPools How many object pools to create
* @param poolCapacity The capacity of each pool
*/
public URLEncoder(int numberOfPools, int poolCapacity) {
if (numberOfPools <= 0) {
throw new IllegalArgumentException("The number of pools must be > 0, but the requested number is: " + numberOfPools);
}
final int actualNumberOfPools = nextPowerOfTwo(numberOfPools);
pools = new BlockingQueue[actualNumberOfPools];
for (int i = 0; i < pools.length; i++) {
pools[i] = new ArrayBlockingQueue<PoolEntry>(poolCapacity);
}
maskPoolIndex = actualNumberOfPools - 1;
for (char i = 'a'; i <= 'z'; i++) {
addSafeCharacter(i);
}
for (char i = 'A'; i <= 'Z'; i++) {
addSafeCharacter(i);
}
for (char i = '0'; i <= '9'; i++) {
addSafeCharacter(i);
}
}
/**
* Calculate the nearest power of two bigger or equal to <code>v</code>
*
* @return the nearest power of two bigger or equal to <code>v</code>
*/
private static int nextPowerOfTwo(int v) {
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return v + 1;
}
/**
* Add a character to the safe list. Those characters
* will not be encoded. This method is not thread safe
* and must not be called while an encoding operation
* is in progress
*
* @param c The character to add
*/
public void addSafeCharacter(char c) {
/*
The older encoder was not thread safe as well,
if there is a chance that this method might be
called during encode(), then a ReadWriteLock
should set in place
*/
safeCharacters.set(c);
}
/**
* URL encode the given string using the UTF-8 charset
* <p>
* This method is deprecated. Either encode(String, String)
* or encode()String, Charset) should be used instead.
*
* @param string The String to encode
* @return The encoded string
*/
@Deprecated
public String encode(String string) {
//Or better java.nio.charset.StandardCharsets.UTF_8 in java >= 7
return encode(string, Charset.forName("UTF-8"));
}
/**
* URL encode the given string using the selected charset
* <p>
* This method is deprecated. Either encode(String, String)
* or encode()String, Charset) should be used instead.
*
* @param string The String to encode
* @param charset The name of the charset which will be used to convert the string to bytes
* @return The encoded string
* @throws java.nio.charset.IllegalCharsetNameException If the given charset name is illegal
* @throws IllegalArgumentException If the given charset name is null
* @throws java.nio.charset.UnsupportedCharsetException If there is no support for the given charset
* in this instance of the JVM
*/
public String encode(String string, String charset) {
return encode(string, Charset.forName(charset));
}
/**
* URL encode the given string using the selected charset
* <p>
* This method is deprecated. Either encode(String, String)
* or encode()String, Charset) should be used instead.
*
* @param string The String to encode
* @param charset The charset which will be used to convert the strings to byes
* @return The encoded string
*/
public String encode(String string, Charset charset) {
final PoolEntry poolEntry = retrievePoolEntryForCharset(charset);
final CharsetEncoder encoder = poolEntry.charsetEncoder;
final CharBuffer inputBuffer = poolEntry.charBuffer;
final ByteBuffer outputBuffer = poolEntry.byteBuffer;
final StringBuilder result = poolEntry.stringBuilder;
for (int nextCharacterIndex = 0; nextCharacterIndex < string.length(); ) {
final char character = string.charAt(nextCharacterIndex);
if (safeCharacters.get(character)) {
result.append(character);
nextCharacterIndex++;
} else {
/*
* Recycle the char buffer, because the last fillInputBuffer()
* call may have flipped an empty buffer, hence making the
* position and limit equal to 0. No need to recycle the
* byte buffer, as flushOutputBuffer() always recycles it
*/
recycle(inputBuffer);
int charsRead;
while ((charsRead = fillInputBuffer(string, inputBuffer, nextCharacterIndex)) != 0) {
nextCharacterIndex += charsRead;
CoderResult encodingResult;
do {
final boolean endOfInput = isEndOfInput(string, nextCharacterIndex, inputBuffer);
encodingResult = encoder.encode(inputBuffer, outputBuffer, endOfInput);
requireCorrectEncodingResult(encodingResult, string, charsRead, nextCharacterIndex);
flushOutputBuffer(outputBuffer, result);
} while (encodingResult.isOverflow());
/*
* If the buffer has any remaining unprocessed characters
* they must be preserved for the next encoding operation.
*/
inputBuffer.compact();
}
//Make sure that everything has been encoded and written to the output buffer
CoderResult flushResult;
do {
flushResult = encoder.flush(outputBuffer);
requireCorrectEncodingResult(flushResult, string, charsRead, nextCharacterIndex);
flushOutputBuffer(outputBuffer, result);
} while (flushResult.isOverflow());
//Prepare the encoder for the next set of encode() operations if any
encoder.reset();
}
}
final String encodedString = result.toString();
returnToPool(poolEntry);
return encodedString;
}
/**
* Fill in the character buffer with the characters to be encoded.
* This method flips the char buffer and prepares it for reading.
*
* @param source The original string that is to be encoded
* @param dest The CharBuffer to fill with unsafe characters
* @param readFrom The index of the first unsafe character
* @return The number of read consecutive, unsafe characters.
*/
private int fillInputBuffer(String source, CharBuffer dest, int readFrom) {
int charsRead = 0;
if (source.length() > readFrom) {
for (int i = readFrom; dest.hasRemaining() & i < source.length(); i++) {
final char c = source.charAt(i);
if (safeCharacters.get(c)) {
break;
}
dest.put(c);
charsRead++;
}
}
dest.flip();
return charsRead;
}
/**
* Peek one character ahead to check if there is
* more input waiting to be encoded
*
* @param string The string argument passed to teh encode() method
* @param nextIndex The index of the first unprocessed character
* @param inputBuffer The input buffer
* @return true if there is an unsafe character at nextIndex
*/
private boolean isEndOfInput(String string, int nextIndex, CharBuffer inputBuffer) {
//If the buffer is not full, it means that we've met safe character
if (inputBuffer.limit() < inputBuffer.capacity()) {
return true;
}
//Even if it's full, we might have reached the end of the string
if (nextIndex >= string.length()) {
return true;
}
//The buffer is full and we are not at the end of the string -> check for next unsafe character
final char nextCharacter = string.charAt(nextIndex);
return safeCharacters.get(nextCharacter);
}
/**
* Write the content of the ByteBuffer to
* the StringBuilder as percent encoded
* hexadecimal string representation.
* <p>
* This method flips the ByteBuffer to prepares it for reading
* and recycles it in order to prepare it for writing
*
* @param source The buffer containing the data to be written
* @param dest The buffer that will store the result of the encoding operation
*/
private void flushOutputBuffer(ByteBuffer source, StringBuilder dest) {
source.flip();
while (source.hasRemaining()) {
final byte toEncode = source.get();
final int low = toEncode & MASK_LOW;
final int high = (toEncode & MASK_HIGH) >> 4;
dest.append(PERCENT);
dest.append(HEXADECIMAL[high]);
dest.append(HEXADECIMAL[low]);
}
recycle(source);
}
private void requireCorrectEncodingResult(CoderResult result, String source, int charsRead, int nextCharIndex) {
if (result.isError()) {
final String errorDetails = "\tSource: '" + source + "'" +
"\tNext character index: '" + nextCharIndex + "'" +
"\tChars read: '" + charsRead + "'" +
"\tCoder result: '" + result + "'";
if (result.isUnmappable()) {
throw new IllegalArgumentException("Non mappable input. " + errorDetails);
} else if (result.isMalformed()) {
throw new IllegalArgumentException("Malformed input." + errorDetails);
} else {
throw new IllegalStateException("Unknown coder state. " + errorDetails);
}
}
}
/**
* Recycle the buffer. Set the limit to the capacity,
* discard the mark and set the position to zero
*
* @param buffer The buffer to be recycled
* @return The given buffer
*/
private <T extends Buffer> T recycle(T buffer) {
buffer.rewind();
buffer.limit(buffer.capacity());
return buffer;
}
/**
* Either take from the pool or create a new pool entry.
*
* @param charset The charset of teh encoder
* @return The retrieved PoolEntry
*/
private PoolEntry retrievePoolEntryForCharset(Charset charset) {
final int poolIndex = getPoolIndex();
PoolEntry poolEntry = pools[poolIndex].poll();
if (null == poolEntry) {
poolEntry = createPoolEntryForCharset(charset);
} else {
poolEntry = recyclePoolEntryForCharset(poolEntry, charset);
}
return poolEntry;
}
private PoolEntry createPoolEntryForCharset(Charset charset) {
PoolEntry poolEntry = new PoolEntry();
poolEntry.charsetEncoder = createCharsetEncoder(charset);
poolEntry.charBuffer = CharBuffer.allocate(CHAR_BUFFER_SIZE);
poolEntry.byteBuffer = ByteBuffer.allocate(BYTE_BUFFER_SIZE);
poolEntry.stringBuilder = new StringBuilder(INITIAL_STRING_BUILDER_CAPACITY);
return poolEntry;
}
private PoolEntry recyclePoolEntryForCharset(PoolEntry poolEntry, Charset charset) {
/*
The cached encoder might be for different than the requested charset.
If that's the case, just get rid of the old charset. At the moment of this writing
teh encoder is used only with one charset.
*/
if (!poolEntry.charsetEncoder.charset().equals(charset)) {
poolEntry.charsetEncoder = createCharsetEncoder(charset);
} else {
poolEntry.charsetEncoder.reset();
}
/*
If the string builder was too large, it might have been discarded
*/
if (null == poolEntry.stringBuilder) {
poolEntry.stringBuilder = new StringBuilder(INITIAL_STRING_BUILDER_CAPACITY);
} else {
poolEntry.stringBuilder.setLength(0);
}
recycle(poolEntry.charBuffer);
recycle(poolEntry.byteBuffer);
return poolEntry;
}
private CharsetEncoder createCharsetEncoder(Charset charset) {
final CharsetEncoder charsetEncoder = charset.newEncoder();
/*
* Preserve the behaviour of the old URLEncoder
*/
charsetEncoder.onMalformedInput(CodingErrorAction.REPLACE);
charsetEncoder.onUnmappableCharacter(CodingErrorAction.REPLACE);
return charsetEncoder;
}
private void returnToPool(PoolEntry poolEntry) {
if (poolEntry.stringBuilder.capacity() > MAX_STRING_BUILDER_CAPACITY) {
poolEntry.stringBuilder = null;
}
final int poolIndex = getPoolIndex();
pools[poolIndex].offer(poolEntry);
}
private int getPoolIndex() {
final long threadId = Thread.currentThread().getId();
return (int) (threadId & maskPoolIndex);
}
}
It's a lot more complicated than the current encoder, but encodes 2-5 times faster and has an almost zero allocation rate (which is the actual reason I wrote it).
