[FELIX-4811] Optimize ConfigurationManager#listConfigurations
git-svn-id: https://svn.apache.org/repos/asf/felix/trunk@1663369 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/configadmin/src/main/java/org/apache/felix/cm/impl/CachingPersistenceManagerProxy.java b/configadmin/src/main/java/org/apache/felix/cm/impl/CachingPersistenceManagerProxy.java
index 7f3225f..997ddd7 100644
--- a/configadmin/src/main/java/org/apache/felix/cm/impl/CachingPersistenceManagerProxy.java
+++ b/configadmin/src/main/java/org/apache/felix/cm/impl/CachingPersistenceManagerProxy.java
@@ -20,12 +20,9 @@
import java.io.IOException;
-import java.util.ArrayList;
import java.util.Dictionary;
import java.util.Enumeration;
import java.util.Hashtable;
-import java.util.Iterator;
-import java.util.Map;
import java.util.Vector;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
@@ -47,7 +44,7 @@
private final PersistenceManager pm;
/** cached dictionaries */
- private final Hashtable cache;
+ private final Hashtable<String, CaseInsensitiveDictionary> cache;
/** protecting lock */
private final ReadWriteLock globalLock = new ReentrantReadWriteLock();
@@ -67,7 +64,7 @@
public CachingPersistenceManagerProxy( final PersistenceManager pm )
{
this.pm = pm;
- this.cache = new Hashtable();
+ this.cache = new Hashtable<String, CaseInsensitiveDictionary>();
}
@@ -118,6 +115,11 @@
*/
public Enumeration getDictionaries() throws IOException
{
+ return getDictionaries( null );
+ }
+
+ public Enumeration getDictionaries( SimpleFilter filter ) throws IOException
+ {
Lock lock = globalLock.readLock();
try {
lock.lock();
@@ -137,7 +139,7 @@
String pid = (String) next.get(Constants.SERVICE_PID);
if (pid != null)
{
- cache.put(pid, next);
+ cache.put(pid, copy( next ) );
}
}
fullyLoaded = true;
@@ -145,10 +147,14 @@
}
// Deep copy the configuration to avoid any threading issue
- Vector configs = new Vector();
+ Vector<Dictionary> configs = new Vector<Dictionary>();
for (Object o : cache.values())
{
- configs.add( copy( ( Dictionary ) o ) );
+ Dictionary d = (Dictionary) o;
+ if ( filter == null || filter.matches( d ) )
+ {
+ configs.add( copy( d ) );
+ }
}
return configs.elements();
} finally {
@@ -172,17 +178,17 @@
Lock lock = globalLock.readLock();
try {
lock.lock();
- Dictionary loaded = ( Dictionary ) cache.get( pid );
+ Dictionary loaded = cache.get( pid );
if ( loaded == null && !fullyLoaded )
{
lock.unlock();
lock = globalLock.writeLock();
lock.lock();
- loaded = ( Dictionary ) cache.get( pid );
+ loaded = cache.get( pid );
if ( loaded == null )
{
loaded = pm.load(pid);
- cache.put(pid, loaded);
+ cache.put(pid, copy( loaded ) );
}
}
return copy( loaded );
@@ -219,22 +225,8 @@
* copies all entries from the source dictionary to the newly created
* target.
*/
- Dictionary copy( final Dictionary source )
+ CaseInsensitiveDictionary copy( final Dictionary source )
{
- Hashtable copy = new Hashtable();
- if ( source instanceof Map )
- {
- copy.putAll( ( Map ) source );
- }
- else
- {
- Enumeration keys = source.keys();
- while ( keys.hasMoreElements() )
- {
- Object key = keys.nextElement();
- copy.put( key, source.get( key ) );
- }
- }
- return copy;
+ return new CaseInsensitiveDictionary( source );
}
}
diff --git a/configadmin/src/main/java/org/apache/felix/cm/impl/CaseInsensitiveDictionary.java b/configadmin/src/main/java/org/apache/felix/cm/impl/CaseInsensitiveDictionary.java
index f05ff44..6c318a5 100644
--- a/configadmin/src/main/java/org/apache/felix/cm/impl/CaseInsensitiveDictionary.java
+++ b/configadmin/src/main/java/org/apache/felix/cm/impl/CaseInsensitiveDictionary.java
@@ -21,14 +21,17 @@
import java.lang.reflect.Array;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
import java.util.Dictionary;
import java.util.Enumeration;
-import java.util.Hashtable;
-import java.util.Iterator;
-import java.util.Locale;
+import java.util.HashSet;
import java.util.Map;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.TreeMap;
import java.util.Vector;
@@ -38,45 +41,39 @@
* out by the Configuration Admin Service Specification requiring the property
* names to keep case but to ignore case when accessing the properties.
*/
-public class CaseInsensitiveDictionary extends Dictionary
+public class CaseInsensitiveDictionary extends Dictionary<String, Object>
{
/**
* The backend dictionary with lower case keys.
*/
- private Hashtable internalMap;
-
- /**
- * Mapping of lower case keys to original case keys as last used to set a
- * property value.
- */
- private Hashtable originalKeys;
-
+ private SortedMap<String, Object> internalMap;
public CaseInsensitiveDictionary()
{
- internalMap = new Hashtable();
- originalKeys = new Hashtable();
+ internalMap = new TreeMap<String, Object>( CASE_INSENSITIVE_ORDER );
}
public CaseInsensitiveDictionary( Dictionary props )
{
- this();
-
- if ( props != null )
+ if ( props instanceof CaseInsensitiveDictionary)
{
+ internalMap = new TreeMap<String, Object>( ((CaseInsensitiveDictionary) props).internalMap );
+ }
+ else if ( props != null )
+ {
+ internalMap = new TreeMap<String, Object>( CASE_INSENSITIVE_ORDER );
Enumeration keys = props.keys();
while ( keys.hasMoreElements() )
{
Object key = keys.nextElement();
// check the correct syntax of the key
- checkKey( key );
+ String k = checkKey( key );
// check uniqueness of key
- String lowerCase = toLowerCase( key );
- if ( internalMap.containsKey( lowerCase ) )
+ if ( internalMap.containsKey( k ) )
{
throw new IllegalArgumentException( "Key [" + key + "] already present in different case" );
}
@@ -86,22 +83,23 @@
value = checkValue( value );
// add the key/value pair
- internalMap.put( lowerCase, value );
- originalKeys.put( lowerCase, key );
+ internalMap.put( k, value );
}
}
+ else
+ {
+ internalMap = new TreeMap<String, Object>( CASE_INSENSITIVE_ORDER );
+ }
}
CaseInsensitiveDictionary( CaseInsensitiveDictionary props, boolean deepCopy )
{
- Hashtable tmp = new Hashtable( Math.max( 2 * props.internalMap.size(), 11 ), 0.75f );
if ( deepCopy )
{
- Iterator entries = props.internalMap.entrySet().iterator();
- while ( entries.hasNext() )
+ internalMap = new TreeMap<String, Object>( CASE_INSENSITIVE_ORDER );
+ for( Map.Entry<String, Object> entry : props.internalMap.entrySet() )
{
- Map.Entry entry = ( Map.Entry ) entries.next();
Object value = entry.getValue();
if ( value.getClass().isArray() )
{
@@ -119,18 +117,15 @@
// Vector. And even though we accept Collection nowadays
// there might be clients out there still written against
// R4 and R4.1 spec expecting Vector
- value = new Vector( ( Collection ) value );
+ value = new Vector<Object>( ( Collection ) value );
}
- tmp.put( entry.getKey(), value );
+ internalMap.put( entry.getKey(), value );
}
}
else
{
- tmp.putAll( props.internalMap );
+ internalMap = new TreeMap<String, Object>( props.internalMap );
}
-
- internalMap = tmp;
- originalKeys = new Hashtable( props.originalKeys );
}
@@ -139,7 +134,7 @@
*
* @see java.util.Dictionary#elements()
*/
- public Enumeration elements()
+ public Enumeration<Object> elements()
{
return Collections.enumeration( internalMap.values() );
}
@@ -157,7 +152,7 @@
throw new NullPointerException( "key" );
}
- return internalMap.get( toLowerCase( key ) );
+ return internalMap.get( key );
}
@@ -177,18 +172,18 @@
*
* @see java.util.Dictionary#keys()
*/
- public Enumeration keys()
+ public Enumeration<String> keys()
{
- return Collections.enumeration( originalKeys.values() );
+ return Collections.enumeration( internalMap.keySet() );
}
/*
* (non-Javadoc)
*
- * @see java.util.Dictionary#put(java.lang.Object, java.lang.Object)
+ * @see java.util.Dictionary#put(java.lang.String, java.lang.Object)
*/
- public Object put( Object key, Object value )
+ public Object put( String key, Object value )
{
if ( key == null || value == null )
{
@@ -198,9 +193,7 @@
checkKey( key );
value = checkValue( value );
- String lowerCase = toLowerCase( key );
- originalKeys.put( lowerCase, key );
- return internalMap.put( lowerCase, value );
+ return internalMap.put( key, value );
}
@@ -216,9 +209,7 @@
throw new NullPointerException( "key" );
}
- String lowerCase = toLowerCase( key );
- originalKeys.remove( lowerCase );
- return internalMap.remove( lowerCase );
+ return internalMap.remove( key );
}
@@ -250,12 +241,12 @@
* If the key does not comply an <code>IllegalArgumentException</code> is
* thrown.
*
- * @param key
+ * @param keyObject
* The configuration property key to check.
* @throws IllegalArgumentException
* if the key does not comply with the symbolic-name production.
*/
- static void checkKey( Object keyObject )
+ static String checkKey( Object keyObject )
{
// check for wrong type or null key
if ( !( keyObject instanceof String ) )
@@ -270,26 +261,32 @@
{
throw new IllegalArgumentException( "Key [" + key + "] must not be an empty string" );
}
+
+ return key;
}
- static final String toLowerCase( Object keyObject )
- {
- final String key = ( String ) keyObject;
- return key.toLowerCase( Locale.ENGLISH );
- }
-
+ private static final Set<Class> KNOWN = new HashSet<Class>(Arrays.<Class>asList(
+ String.class, Integer.class, Long.class, Float.class,
+ Double.class, Byte.class, Short.class, Character.class,
+ Boolean.class));
static Object checkValue( Object value )
{
- Class type;
if ( value == null )
{
// null is illegal
throw new IllegalArgumentException( "Value must not be null" );
}
- else if ( value.getClass().isArray() )
+
+ Class type = value.getClass();
+ // Fast check for simple types
+ if ( KNOWN.contains( type ) )
+ {
+ return value;
+ }
+ else if ( type.isArray() )
{
// check simple or primitive
type = value.getClass().getComponentType();
@@ -312,11 +309,10 @@
}
// ensure all elements have the same type and to internal list
- Collection internalValue = new ArrayList( collection.size() );
+ Collection<Object> internalValue = new ArrayList<Object>( collection.size() );
type = null;
- for ( Iterator ci = collection.iterator(); ci.hasNext(); )
+ for ( Object el : collection )
{
- Object el = ci.next();
if ( el == null )
{
throw new IllegalArgumentException( "Collection must not contain null elements" );
@@ -341,9 +337,7 @@
}
// check for simple type
- if ( type == String.class || type == Integer.class || type == Long.class || type == Float.class
- || type == Double.class || type == Byte.class || type == Short.class || type == Character.class
- || type == Boolean.class )
+ if ( KNOWN.contains( type ) )
{
return value;
}
@@ -360,4 +354,56 @@
return internalMap.toString();
}
+ public static final Comparator<String> CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator();
+
+ private static class CaseInsensitiveComparator implements Comparator<String>
+ {
+
+ public int compare(String s1, String s2)
+ {
+ int n1 = s1.length();
+ int n2 = s2.length();
+ int min = n1 < n2 ? n1 : n2;
+ for ( int i = 0; i < min; i++ )
+ {
+ char c1 = s1.charAt( i );
+ char c2 = s2.charAt( i );
+ if ( c1 != c2 )
+ {
+ // Fast check for simple ascii codes
+ if ( c1 <= 128 && c2 <= 128 )
+ {
+ c1 = toLowerCaseFast(c1);
+ c2 = toLowerCaseFast(c2);
+ if ( c1 != c2 )
+ {
+ return c1 - c2;
+ }
+ }
+ else
+ {
+ c1 = Character.toUpperCase( c1 );
+ c2 = Character.toUpperCase( c2 );
+ if ( c1 != c2 )
+ {
+ c1 = Character.toLowerCase( c1 );
+ c2 = Character.toLowerCase( c2 );
+ if ( c1 != c2 )
+ {
+ // No overflow because of numeric promotion
+ return c1 - c2;
+ }
+ }
+ }
+ }
+ }
+ return n1 - n2;
+ }
+ }
+
+ private static char toLowerCaseFast( char ch )
+ {
+ return ( ch >= 'A' && ch <= 'Z' ) ? ( char ) ( ch + 'a' - 'A' ) : ch;
+ }
+
}
diff --git a/configadmin/src/main/java/org/apache/felix/cm/impl/ConfigurationManager.java b/configadmin/src/main/java/org/apache/felix/cm/impl/ConfigurationManager.java
index 12dd0de..c1b80a5 100644
--- a/configadmin/src/main/java/org/apache/felix/cm/impl/ConfigurationManager.java
+++ b/configadmin/src/main/java/org/apache/felix/cm/impl/ConfigurationManager.java
@@ -46,7 +46,6 @@
import org.osgi.framework.BundleEvent;
import org.osgi.framework.BundleListener;
import org.osgi.framework.Constants;
-import org.osgi.framework.Filter;
import org.osgi.framework.InvalidSyntaxException;
import org.osgi.framework.ServiceReference;
import org.osgi.framework.ServiceRegistration;
@@ -163,7 +162,7 @@
* {@link #persistenceManagerMap}, which is ordered according to the
* {@link RankingComparator}.
*/
- private PersistenceManager[] persistenceManagers;
+ private CachingPersistenceManagerProxy[] persistenceManagers;
// the persistenceManagerTracker.getTrackingCount when the
// persistenceManagers were last got
@@ -642,10 +641,10 @@
ConfigurationImpl[] listConfigurations( ConfigurationAdminImpl configurationAdmin, String filterString )
throws IOException, InvalidSyntaxException
{
- Filter filter = null;
+ SimpleFilter filter = null;
if ( filterString != null )
{
- filter = bundleContext.createFilter( filterString );
+ filter = SimpleFilter.parse( filterString );
}
log( LogService.LOG_DEBUG, "Listing configurations matching {0}", new Object[]
@@ -653,10 +652,10 @@
List configList = new ArrayList();
- PersistenceManager[] pmList = getPersistenceManagers();
+ CachingPersistenceManagerProxy[] pmList = getPersistenceManagers();
for ( int i = 0; i < pmList.length; i++ )
{
- Enumeration configs = pmList[i].getDictionaries();
+ Enumeration configs = pmList[i].getDictionaries( filter );
while ( configs.hasMoreElements() )
{
final Dictionary config = ( Dictionary ) configs.nextElement();
@@ -681,30 +680,23 @@
continue;
}
- // check filter
- if ( filter == null || filter.match( config ) )
+ // ensure the service.pid and returned a cached config if available
+ ConfigurationImpl cfg = getCachedConfiguration( pid );
+ if ( cfg == null )
{
- // ensure the service.pid and returned a cached config if available
- ConfigurationImpl cfg = getCachedConfiguration( pid );
- if ( cfg == null )
- {
- cfg = new ConfigurationImpl( this, pmList[i], config );
- }
+ cfg = new ConfigurationImpl( this, pmList[i], config );
+ }
- // FELIX-611: Ignore configuration objects without props
- if ( !cfg.isNew() )
- {
- log( LogService.LOG_DEBUG, "Adding configuration {0}", new Object[]
- { pid } );
- configList.add( cfg );
- }
- else
- {
- log( LogService.LOG_DEBUG, "Omitting configuration {0}: Is new", new Object[]
- { pid } );
- }
- } else {
- log( LogService.LOG_DEBUG, "Omitting configuration {0}: Does not match filter", new Object[]
+ // FELIX-611: Ignore configuration objects without props
+ if ( !cfg.isNew() )
+ {
+ log( LogService.LOG_DEBUG, "Adding configuration {0}", new Object[]
+ { pid } );
+ configList.add( cfg );
+ }
+ else
+ {
+ log( LogService.LOG_DEBUG, "Omitting configuration {0}: Is new", new Object[]
{ pid } );
}
}
@@ -813,19 +805,19 @@
// ---------- internal -----------------------------------------------------
- private PersistenceManager[] getPersistenceManagers()
+ private CachingPersistenceManagerProxy[] getPersistenceManagers()
{
int currentPmtCount = persistenceManagerTracker.getTrackingCount();
if ( persistenceManagers == null || currentPmtCount > pmtCount )
{
List pmList = new ArrayList();
- PersistenceManager[] pm;
+ CachingPersistenceManagerProxy[] pm;
ServiceReference[] refs = persistenceManagerTracker.getServiceReferences();
if ( refs == null || refs.length == 0 )
{
- pm = new PersistenceManager[0];
+ pm = new CachingPersistenceManagerProxy[0];
}
else
{
@@ -845,7 +837,7 @@
}
}
- pm = ( PersistenceManager[] ) pmList.toArray( new PersistenceManager[pmList.size()] );
+ pm = ( CachingPersistenceManagerProxy[] ) pmList.toArray( new CachingPersistenceManagerProxy[pmList.size()] );
}
pmtCount = currentPmtCount;
diff --git a/configadmin/src/main/java/org/apache/felix/cm/impl/Factory.java b/configadmin/src/main/java/org/apache/felix/cm/impl/Factory.java
index b3564ac..77b3c99 100644
--- a/configadmin/src/main/java/org/apache/felix/cm/impl/Factory.java
+++ b/configadmin/src/main/java/org/apache/felix/cm/impl/Factory.java
@@ -133,7 +133,7 @@
}
else
{
- props.put( FACTORY_PID, this.getFactoryPid() );
+ props.put( FACTORY_PID, this.getFactoryPid().toString() );
getPersistenceManager().store( id, props );
}
}
diff --git a/configadmin/src/main/java/org/apache/felix/cm/impl/SimpleFilter.java b/configadmin/src/main/java/org/apache/felix/cm/impl/SimpleFilter.java
new file mode 100644
index 0000000..0305e08
--- /dev/null
+++ b/configadmin/src/main/java/org/apache/felix/cm/impl/SimpleFilter.java
@@ -0,0 +1,863 @@
+/*
+ * 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.felix.cm.impl;
+
+import java.lang.reflect.Array;
+import java.lang.reflect.Constructor;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Dictionary;
+import java.util.Iterator;
+import java.util.List;
+
+public class SimpleFilter
+{
+ public static final int MATCH_ALL = 0;
+ public static final int AND = 1;
+ public static final int OR = 2;
+ public static final int NOT = 3;
+ public static final int EQ = 4;
+ public static final int LTE = 5;
+ public static final int GTE = 6;
+ public static final int SUBSTRING = 7;
+ public static final int PRESENT = 8;
+ public static final int APPROX = 9;
+
+ private final String m_name;
+ private final Object m_value;
+ private final int m_op;
+
+ public SimpleFilter(String attr, Object value, int op)
+ {
+ m_name = attr;
+ m_value = value;
+ m_op = op;
+ }
+
+ public String getName()
+ {
+ return m_name;
+ }
+
+ public Object getValue()
+ {
+ return m_value;
+ }
+
+ public int getOperation()
+ {
+ return m_op;
+ }
+
+ public String toString()
+ {
+ StringBuilder sb = new StringBuilder();
+ toString(sb);
+ return sb.toString();
+ }
+
+ private void toString(StringBuilder sb)
+ {
+ switch (m_op)
+ {
+ case AND:
+ sb.append("(&");
+ toString(sb, (List) m_value);
+ sb.append(")");
+ break;
+ case OR:
+ sb.append("(|");
+ toString(sb, (List) m_value);
+ sb.append(")");
+ break;
+ case NOT:
+ sb.append("(!");
+ toString(sb, (List) m_value);
+ sb.append(")");
+ break;
+ case EQ:
+ sb.append("(")
+ .append(m_name)
+ .append("=");
+ toEncodedString(sb, m_value);
+ sb.append(")");
+ break;
+ case LTE:
+ sb.append("(")
+ .append(m_name)
+ .append("<=");
+ toEncodedString(sb, m_value);
+ sb.append(")");
+ break;
+ case GTE:
+ sb.append("(")
+ .append(m_name)
+ .append(">=");
+ toEncodedString(sb, m_value);
+ sb.append(")");
+ break;
+ case SUBSTRING:
+ sb.append("(").append(m_name).append("=");
+ unparseSubstring(sb, (List) m_value);
+ sb.append(")");
+ break;
+ case PRESENT:
+ sb.append("(").append(m_name).append("=*)");
+ break;
+ case APPROX:
+ sb.append("(").append(m_name).append("~=");
+ toEncodedString(sb, m_value);
+ sb.append(")");
+ break;
+ case MATCH_ALL:
+ sb.append("(*)");
+ break;
+ }
+ }
+
+ private static void toString(StringBuilder sb, List list)
+ {
+ for (Object o : list)
+ {
+ SimpleFilter sf = (SimpleFilter) o;
+ sf.toString(sb);
+ }
+ }
+
+ private static String toDecodedString(String s, int startIdx, int endIdx)
+ {
+ StringBuilder sb = new StringBuilder(endIdx - startIdx);
+ boolean escaped = false;
+ for (int i = 0; i < (endIdx - startIdx); i++)
+ {
+ char c = s.charAt(startIdx + i);
+ if (!escaped && (c == '\\'))
+ {
+ escaped = true;
+ }
+ else
+ {
+ escaped = false;
+ sb.append(c);
+ }
+ }
+
+ return sb.toString();
+ }
+
+ private static void toEncodedString(StringBuilder sb, Object o)
+ {
+ if (o instanceof String)
+ {
+ String s = (String) o;
+ for (int i = 0; i < s.length(); i++)
+ {
+ char c = s.charAt(i);
+ if ((c == '\\') || (c == '(') || (c == ')') || (c == '*'))
+ {
+ sb.append('\\');
+ }
+ sb.append(c);
+ }
+ }
+ else
+ {
+ sb.append(o);
+ }
+ }
+
+ public static SimpleFilter parse(String filter)
+ {
+ int idx = skipWhitespace(filter, 0);
+
+ if ((filter == null) || (filter.length() == 0) || (idx >= filter.length()))
+ {
+ throw new IllegalArgumentException("Null or empty filter.");
+ }
+ else if (filter.charAt(idx) != '(')
+ {
+ throw new IllegalArgumentException("Missing opening parenthesis: " + filter);
+ }
+
+ SimpleFilter sf = null;
+ List<Object> stack = new ArrayList<Object>();
+ boolean isEscaped = false;
+ while (idx < filter.length())
+ {
+ if (sf != null)
+ {
+ throw new IllegalArgumentException(
+ "Only one top-level operation allowed: " + filter);
+ }
+
+ if (!isEscaped && (filter.charAt(idx) == '('))
+ {
+ // Skip paren and following whitespace.
+ idx = skipWhitespace(filter, idx + 1);
+
+ if (filter.charAt(idx) == '&')
+ {
+ int peek = skipWhitespace(filter, idx + 1);
+ if (filter.charAt(peek) == '(')
+ {
+ idx = peek - 1;
+ stack.add(0, new SimpleFilter(null, new ArrayList(), SimpleFilter.AND));
+ }
+ else
+ {
+ stack.add(0, idx);
+ }
+ }
+ else if (filter.charAt(idx) == '|')
+ {
+ int peek = skipWhitespace(filter, idx + 1);
+ if (filter.charAt(peek) == '(')
+ {
+ idx = peek - 1;
+ stack.add(0, new SimpleFilter(null, new ArrayList(), SimpleFilter.OR));
+ }
+ else
+ {
+ stack.add(0, idx);
+ }
+ }
+ else if (filter.charAt(idx) == '!')
+ {
+ int peek = skipWhitespace(filter, idx + 1);
+ if (filter.charAt(peek) == '(')
+ {
+ idx = peek - 1;
+ stack.add(0, new SimpleFilter(null, new ArrayList(), SimpleFilter.NOT));
+ }
+ else
+ {
+ stack.add(0, idx);
+ }
+ }
+ else
+ {
+ stack.add(0, idx);
+ }
+ }
+ else if (!isEscaped && (filter.charAt(idx) == ')'))
+ {
+ Object top = stack.remove(0);
+ if (top instanceof SimpleFilter)
+ {
+ if (!stack.isEmpty() && (stack.get(0) instanceof SimpleFilter))
+ {
+ ((List) ((SimpleFilter) stack.get(0)).m_value).add(top);
+ }
+ else
+ {
+ sf = (SimpleFilter) top;
+ }
+ }
+ else if (!stack.isEmpty() && (stack.get(0) instanceof SimpleFilter))
+ {
+ ((List) ((SimpleFilter) stack.get(0)).m_value).add(
+ SimpleFilter.subfilter(filter, (Integer) top, idx));
+ }
+ else
+ {
+ sf = SimpleFilter.subfilter(filter, (Integer) top, idx);
+ }
+ }
+ else if (!isEscaped && (filter.charAt(idx) == '\\'))
+ {
+ isEscaped = true;
+ }
+ else
+ {
+ isEscaped = false;
+ }
+
+ idx = skipWhitespace(filter, idx + 1);
+ }
+
+ if (sf == null)
+ {
+ throw new IllegalArgumentException("Missing closing parenthesis: " + filter);
+ }
+
+ return sf;
+ }
+
+ private static SimpleFilter subfilter(String filter, int startIdx, int endIdx)
+ {
+ final String opChars = "=<>~";
+
+ // Determine the ending index of the attribute name.
+ int attrEndIdx = startIdx;
+ for (int i = 0; i < (endIdx - startIdx); i++)
+ {
+ char c = filter.charAt(startIdx + i);
+ if (opChars.indexOf(c) >= 0)
+ {
+ break;
+ }
+ else if (!Character.isWhitespace(c))
+ {
+ attrEndIdx = startIdx + i + 1;
+ }
+ }
+ if (attrEndIdx == startIdx)
+ {
+ throw new IllegalArgumentException(
+ "Missing attribute name: " + filter.substring(startIdx, endIdx));
+ }
+ String attr = filter.substring(startIdx, attrEndIdx);
+
+ // Skip the attribute name and any following whitespace.
+ startIdx = skipWhitespace(filter, attrEndIdx);
+
+ // Determine the operator type.
+ int op;
+ switch (filter.charAt(startIdx))
+ {
+ case '=':
+ op = EQ;
+ startIdx++;
+ break;
+ case '<':
+ if (filter.charAt(startIdx + 1) != '=')
+ {
+ throw new IllegalArgumentException(
+ "Unknown operator: " + filter.substring(startIdx, endIdx));
+ }
+ op = LTE;
+ startIdx += 2;
+ break;
+ case '>':
+ if (filter.charAt(startIdx + 1) != '=')
+ {
+ throw new IllegalArgumentException(
+ "Unknown operator: " + filter.substring(startIdx, endIdx));
+ }
+ op = GTE;
+ startIdx += 2;
+ break;
+ case '~':
+ if (filter.charAt(startIdx + 1) != '=')
+ {
+ throw new IllegalArgumentException(
+ "Unknown operator: " + filter.substring(startIdx, endIdx));
+ }
+ op = APPROX;
+ startIdx += 2;
+ break;
+ default:
+ throw new IllegalArgumentException(
+ "Unknown operator: " + filter.substring(startIdx, endIdx));
+ }
+
+ // Parse value.
+ Object value = toDecodedString(filter, startIdx, endIdx);
+
+ // Check if the equality comparison is actually a substring
+ // or present operation.
+ if (op == EQ)
+ {
+ String valueStr = filter.substring(startIdx, endIdx);
+ List<String> values = parseSubstring(valueStr);
+ if ((values.size() == 2)
+ && (values.get(0).length() == 0)
+ && (values.get(1).length() == 0))
+ {
+ op = PRESENT;
+ }
+ else if (values.size() > 1)
+ {
+ op = SUBSTRING;
+ value = values;
+ }
+ }
+
+ return new SimpleFilter(attr, value, op);
+ }
+
+ public static List<String> parseSubstring(String value)
+ {
+ List<String> pieces = new ArrayList<String>();
+ StringBuilder ss = new StringBuilder();
+ // int kind = SIMPLE; // assume until proven otherwise
+ boolean wasStar = false; // indicates last piece was a star
+ boolean leftstar = false; // track if the initial piece is a star
+ boolean rightstar = false; // track if the final piece is a star
+
+ int idx = 0;
+
+ // We assume (sub)strings can contain leading and trailing blanks
+ boolean escaped = false;
+ loop: for (;;)
+ {
+ if (idx >= value.length())
+ {
+ if (wasStar)
+ {
+ // insert last piece as "" to handle trailing star
+ rightstar = true;
+ }
+ else
+ {
+ pieces.add(ss.toString());
+ // accumulate the last piece
+ // note that in the case of
+ // (cn=); this might be
+ // the string "" (!=null)
+ }
+ ss.setLength(0);
+ break loop;
+ }
+
+ // Read the next character and account for escapes.
+ char c = value.charAt(idx++);
+ if (!escaped && (c == '*'))
+ {
+ // If we have successive '*' characters, then we can
+ // effectively collapse them by ignoring succeeding ones.
+ if (!wasStar)
+ {
+ if (ss.length() > 0)
+ {
+ pieces.add(ss.toString()); // accumulate the pieces
+ // between '*' occurrences
+ }
+ ss.setLength(0);
+ // if this is a leading star, then track it
+ if (pieces.isEmpty())
+ {
+ leftstar = true;
+ }
+ wasStar = true;
+ }
+ }
+ else if (!escaped && (c == '\\'))
+ {
+ escaped = true;
+ }
+ else
+ {
+ escaped = false;
+ wasStar = false;
+ ss.append(c);
+ }
+ }
+ if (leftstar || rightstar || pieces.size() > 1)
+ {
+ // insert leading and/or trailing "" to anchor ends
+ if (rightstar)
+ {
+ pieces.add("");
+ }
+ if (leftstar)
+ {
+ pieces.add(0, "");
+ }
+ }
+ return pieces;
+ }
+
+ public static void unparseSubstring(StringBuilder sb, List<String> pieces)
+ {
+ for (int i = 0; i < pieces.size(); i++)
+ {
+ if (i > 0)
+ {
+ sb.append("*");
+ }
+ toEncodedString(sb, pieces.get(i));
+ }
+ }
+
+ public static boolean compareSubstring(List<String> pieces, String s)
+ {
+ // Walk the pieces to match the string
+ // There are implicit stars between each piece,
+ // and the first and last pieces might be "" to anchor the match.
+ // assert (pieces.length > 1)
+ // minimal case is <string>*<string>
+
+ boolean result = true;
+ int len = pieces.size();
+
+ // Special case, if there is only one piece, then
+ // we must perform an equality test.
+ if (len == 1)
+ {
+ return s.equals(pieces.get(0));
+ }
+
+ // Otherwise, check whether the pieces match
+ // the specified string.
+
+ int index = 0;
+
+ loop: for (int i = 0; i < len; i++)
+ {
+ String piece = pieces.get(i);
+
+ // If this is the first piece, then make sure the
+ // string starts with it.
+ if (i == 0)
+ {
+ if (!s.startsWith(piece))
+ {
+ result = false;
+ break loop;
+ }
+ }
+
+ // If this is the last piece, then make sure the
+ // string ends with it.
+ if (i == (len - 1))
+ {
+ if (s.endsWith(piece) && (s.length() >= (index + piece.length())))
+ {
+ result = true;
+ }
+ else
+ {
+ result = false;
+ }
+ break loop;
+ }
+
+ // If this is neither the first or last piece, then
+ // make sure the string contains it.
+ if ((i > 0) && (i < (len - 1)))
+ {
+ index = s.indexOf(piece, index);
+ if (index < 0)
+ {
+ result = false;
+ break loop;
+ }
+ }
+
+ // Move string index beyond the matching piece.
+ index += piece.length();
+ }
+
+ return result;
+ }
+
+ private static int skipWhitespace(String s, int startIdx)
+ {
+ int len = s.length();
+ while ((startIdx < len) && Character.isWhitespace(s.charAt(startIdx)))
+ {
+ startIdx++;
+ }
+ return startIdx;
+ }
+
+ public boolean matches(Dictionary dict)
+ {
+ boolean matched = true;
+
+ if (getOperation() == SimpleFilter.MATCH_ALL)
+ {
+ matched = true;
+ }
+ else if (getOperation() == SimpleFilter.AND)
+ {
+ // Evaluate each subfilter against the remaining capabilities.
+ // For AND we calculate the intersection of each subfilter.
+ // We can short-circuit the AND operation if there are no
+ // remaining capabilities.
+ List<SimpleFilter> sfs = (List<SimpleFilter>) getValue();
+ for (int i = 0; matched && (i < sfs.size()); i++)
+ {
+ matched = sfs.get(i).matches(dict);
+ }
+ }
+ else if (getOperation() == SimpleFilter.OR)
+ {
+ // Evaluate each subfilter against the remaining capabilities.
+ // For OR we calculate the union of each subfilter.
+ matched = false;
+ List<SimpleFilter> sfs = (List<SimpleFilter>) getValue();
+ for (int i = 0; !matched && (i < sfs.size()); i++)
+ {
+ matched = sfs.get(i).matches(dict);
+ }
+ }
+ else if (getOperation() == SimpleFilter.NOT)
+ {
+ // Evaluate each subfilter against the remaining capabilities.
+ // For OR we calculate the union of each subfilter.
+ List<SimpleFilter> sfs = (List<SimpleFilter>) getValue();
+ for (int i = 0; i < sfs.size(); i++)
+ {
+ matched = !sfs.get(i).matches(dict);
+ }
+ }
+ else
+ {
+ matched = false;
+ Object lhs = dict.get( getName() );
+ if (lhs != null)
+ {
+ matched = compare(lhs, getValue(), getOperation());
+ }
+ }
+
+ return matched;
+ }
+
+ private static final Class<?>[] STRING_CLASS = new Class[] { String.class };
+
+ private static boolean compare(Object lhs, Object rhsUnknown, int op)
+ {
+ if (lhs == null)
+ {
+ return false;
+ }
+
+ // If this is a PRESENT operation, then just return true immediately
+ // since we wouldn't be here if the attribute wasn't present.
+ if (op == SimpleFilter.PRESENT)
+ {
+ return true;
+ }
+
+ // If the type is comparable, then we can just return the
+ // result immediately.
+ if (lhs instanceof Comparable)
+ {
+ // Spec says SUBSTRING is false for all types other than string.
+ if ((op == SimpleFilter.SUBSTRING) && !(lhs instanceof String))
+ {
+ return false;
+ }
+
+ Object rhs;
+ if (op == SimpleFilter.SUBSTRING)
+ {
+ rhs = rhsUnknown;
+ }
+ else
+ {
+ try
+ {
+ rhs = coerceType(lhs, (String) rhsUnknown);
+ }
+ catch (Exception ex)
+ {
+ return false;
+ }
+ }
+
+ switch (op)
+ {
+ case SimpleFilter.EQ :
+ try
+ {
+ return (((Comparable) lhs).compareTo(rhs) == 0);
+ }
+ catch (Exception ex)
+ {
+ return false;
+ }
+ case SimpleFilter.GTE :
+ try
+ {
+ return (((Comparable) lhs).compareTo(rhs) >= 0);
+ }
+ catch (Exception ex)
+ {
+ return false;
+ }
+ case SimpleFilter.LTE :
+ try
+ {
+ return (((Comparable) lhs).compareTo(rhs) <= 0);
+ }
+ catch (Exception ex)
+ {
+ return false;
+ }
+ case SimpleFilter.APPROX :
+ return compareApproximate(((Comparable) lhs), rhs);
+ case SimpleFilter.SUBSTRING :
+ return SimpleFilter.compareSubstring((List<String>) rhs, (String) lhs);
+ default:
+ throw new RuntimeException(
+ "Unknown comparison operator: " + op);
+ }
+ }
+ // Booleans do not implement comparable, so special case them.
+ else if (lhs instanceof Boolean)
+ {
+ Object rhs;
+ try
+ {
+ rhs = coerceType(lhs, (String) rhsUnknown);
+ }
+ catch (Exception ex)
+ {
+ return false;
+ }
+
+ switch (op)
+ {
+ case SimpleFilter.EQ :
+ case SimpleFilter.GTE :
+ case SimpleFilter.LTE :
+ case SimpleFilter.APPROX :
+ return (lhs.equals(rhs));
+ default:
+ throw new RuntimeException(
+ "Unknown comparison operator: " + op);
+ }
+ }
+
+ // If the LHS is not a comparable or boolean, check if it is an
+ // array. If so, convert it to a list so we can treat it as a
+ // collection.
+ if (lhs.getClass().isArray())
+ {
+ lhs = convertArrayToList(lhs);
+ }
+
+ // If LHS is a collection, then call compare() on each element
+ // of the collection until a match is found.
+ if (lhs instanceof Collection)
+ {
+ for (Iterator iter = ((Collection) lhs).iterator(); iter.hasNext(); )
+ {
+ if (compare(iter.next(), rhsUnknown, op))
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ // Spec says SUBSTRING is false for all types other than string.
+ if ((op == SimpleFilter.SUBSTRING) && !(lhs instanceof String))
+ {
+ return false;
+ }
+
+ // Since we cannot identify the LHS type, then we can only perform
+ // equality comparison.
+ try
+ {
+ return lhs.equals(coerceType(lhs, (String) rhsUnknown));
+ }
+ catch (Exception ex)
+ {
+ return false;
+ }
+ }
+
+ private static boolean compareApproximate(Object lhs, Object rhs)
+ {
+ if (rhs instanceof String)
+ {
+ return removeWhitespace((String) lhs)
+ .equalsIgnoreCase(removeWhitespace((String) rhs));
+ }
+ else if (rhs instanceof Character)
+ {
+ return Character.toLowerCase(((Character) lhs))
+ == Character.toLowerCase(((Character) rhs));
+ }
+ return lhs.equals(rhs);
+ }
+
+ private static String removeWhitespace(String s)
+ {
+ StringBuilder sb = new StringBuilder(s.length());
+ for (int i = 0; i < s.length(); i++)
+ {
+ if (!Character.isWhitespace(s.charAt(i)))
+ {
+ sb.append(s.charAt(i));
+ }
+ }
+ return sb.toString();
+ }
+
+ private static Object coerceType(Object lhs, String rhsString) throws Exception
+ {
+ // If the LHS expects a string, then we can just return
+ // the RHS since it is a string.
+ if (lhs.getClass() == rhsString.getClass())
+ {
+ return rhsString;
+ }
+
+ // Try to convert the RHS type to the LHS type by using
+ // the string constructor of the LHS class, if it has one.
+ Object rhs = null;
+ try
+ {
+ // The Character class is a special case, since its constructor
+ // does not take a string, so handle it separately.
+ if (lhs instanceof Character)
+ {
+ rhs = rhsString.charAt(0);
+ }
+ else
+ {
+ // Spec says we should trim number types.
+ if ((lhs instanceof Number) || (lhs instanceof Boolean))
+ {
+ rhsString = rhsString.trim();
+ }
+ Constructor ctor = lhs.getClass().getConstructor(STRING_CLASS);
+ ctor.setAccessible(true);
+ rhs = ctor.newInstance(rhsString);
+ }
+ }
+ catch (Exception ex)
+ {
+ throw new Exception(
+ "Could not instantiate class "
+ + lhs.getClass().getName()
+ + " from string constructor with argument '"
+ + rhsString + "' because " + ex);
+ }
+
+ return rhs;
+ }
+
+ /**
+ * This is an ugly utility method to convert an array of primitives
+ * to an array of primitive wrapper objects. This method simplifies
+ * processing LDAP filters since the special case of primitive arrays
+ * can be ignored.
+ * @param array An array of primitive types.
+ * @return An corresponding array using pritive wrapper objects.
+ **/
+ private static List convertArrayToList(Object array)
+ {
+ int len = Array.getLength(array);
+ List<Object> list = new ArrayList<Object>(len);
+ for (int i = 0; i < len; i++)
+ {
+ list.add(Array.get(array, i));
+ }
+ return list;
+ }
+}