001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.xdbm.search.impl; 021 022 023 import org.apache.directory.shared.ldap.entry.ServerEntry; 024 import org.apache.directory.shared.ldap.filter.OrNode; 025 import org.apache.directory.shared.ldap.filter.ExprNode; 026 import org.apache.directory.server.xdbm.IndexEntry; 027 import org.apache.directory.server.xdbm.search.Evaluator; 028 029 import java.util.List; 030 import java.util.ArrayList; 031 import java.util.Collections; 032 import java.util.Comparator; 033 034 035 /** 036 * An Evaluator for logical disjunction (OR) expressions. 037 * 038 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 039 * @version $$Rev$$ 040 */ 041 public class OrEvaluator<ID> implements Evaluator<OrNode, ServerEntry, ID> 042 { 043 private final List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators; 044 045 private final OrNode node; 046 047 048 public OrEvaluator( OrNode node, List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators ) 049 { 050 this.node = node; 051 this.evaluators = optimize( evaluators ); 052 } 053 054 055 /** 056 * Takes a set of Evaluators and copies then sorts them in a new list with 057 * decreasing scan counts on their expression nodes. This is done to have 058 * the Evaluators with the greatest scan counts which have the highest 059 * probability of accepting a candidate first. That will increase the 060 * chance of shorting the checks on evaluators early so extra lookups and 061 * comparisons are avoided. 062 * 063 * @param unoptimized the unoptimized list of Evaluators 064 * @return optimized Evaluator list with decreasing scan count ordering 065 */ 066 private List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimize( 067 List<Evaluator<? extends ExprNode, ServerEntry, ID>> unoptimized ) 068 { 069 List<Evaluator<? extends ExprNode, ServerEntry, ID>> optimized = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>( 070 unoptimized.size() ); 071 optimized.addAll( unoptimized ); 072 Collections.sort( optimized, new Comparator<Evaluator<? extends ExprNode, ServerEntry, ID>>() 073 { 074 public int compare( Evaluator<? extends ExprNode, ServerEntry, ID> e1, 075 Evaluator<? extends ExprNode, ServerEntry, ID> e2 ) 076 { 077 long scanCount1 = ( Long ) e1.getExpression().get( "count" ); 078 long scanCount2 = ( Long ) e2.getExpression().get( "count" ); 079 080 if ( scanCount1 == scanCount2 ) 081 { 082 return 0; 083 } 084 085 /* 086 * We want the Evaluator with the largest scan count first 087 * since this node has the highest probability of accepting, 088 * or rather the least probability of failing. That way we 089 * can short the sub-expression evaluation process. 090 */ 091 if ( scanCount1 < scanCount2 ) 092 { 093 return 1; 094 } 095 096 return -1; 097 } 098 } ); 099 100 return optimized; 101 } 102 103 104 public boolean evaluate( IndexEntry<?, ServerEntry, ID> indexEntry ) throws Exception 105 { 106 for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators ) 107 { 108 if ( evaluator.evaluate( indexEntry ) ) 109 { 110 return true; 111 } 112 } 113 114 return false; 115 } 116 117 118 public boolean evaluateId( ID id ) throws Exception 119 { 120 for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators ) 121 { 122 if ( evaluator.evaluateId( id ) ) 123 { 124 return true; 125 } 126 } 127 128 return false; 129 } 130 131 132 public boolean evaluateEntry( ServerEntry entry ) throws Exception 133 { 134 for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators ) 135 { 136 if ( evaluator.evaluateEntry( entry ) ) 137 { 138 return true; 139 } 140 } 141 142 return false; 143 } 144 145 146 public OrNode getExpression() 147 { 148 return node; 149 } 150 }