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 */ 020package org.apache.directory.server.xdbm.search.evaluator; 021 022 023import java.util.ArrayList; 024import java.util.Collections; 025import java.util.List; 026 027import org.apache.directory.api.ldap.model.entry.Entry; 028import org.apache.directory.api.ldap.model.exception.LdapException; 029import org.apache.directory.api.ldap.model.filter.AndNode; 030import org.apache.directory.api.ldap.model.filter.ExprNode; 031import org.apache.directory.server.core.api.partition.PartitionTxn; 032import org.apache.directory.server.xdbm.IndexEntry; 033import org.apache.directory.server.xdbm.search.Evaluator; 034import org.apache.directory.server.xdbm.search.impl.ScanCountComparator; 035 036 037/** 038 * An Evaluator for logical conjunction (AND) expressions. 039 * 040 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 041 */ 042public class AndEvaluator implements Evaluator<AndNode> 043{ 044 /** The list of evaluators associated with each of the children */ 045 private final List<Evaluator<? extends ExprNode>> evaluators; 046 047 /** The AndNode */ 048 private final AndNode node; 049 050 051 /** 052 * Creates an instance of AndEvaluator 053 * @param node The And Node 054 * @param evaluators The list of evaluators for all the contaned nodes 055 */ 056 public AndEvaluator( AndNode node, List<Evaluator<? extends ExprNode>> evaluators ) 057 { 058 this.node = node; 059 this.evaluators = optimize( evaluators ); 060 } 061 062 063 /** 064 * Takes a set of Evaluators and copies then sorts them in a new list with 065 * increasing scan counts on their expression nodes. This is done to have 066 * the Evaluators with the least scan count which have the highest 067 * probability of rejecting a candidate first. That will increase the 068 * chance of shorting the checks on evaluators early so extra lookups and 069 * comparisons are avoided. 070 * 071 * @param unoptimized the unoptimized list of Evaluators 072 * @return optimized Evaluator list with increasing scan count ordering 073 */ 074 private List<Evaluator<? extends ExprNode>> optimize( 075 List<Evaluator<? extends ExprNode>> unoptimized ) 076 { 077 switch ( unoptimized.size() ) 078 { 079 case 0 : 080 case 1 : 081 return unoptimized; 082 083 case 2 : 084 Object count1 = unoptimized.get( 0 ).getExpression().get( "count" ); 085 Object count2 = unoptimized.get( 1 ).getExpression().get( "count" ); 086 087 if ( count1 == null ) 088 { 089 if ( count2 != null ) 090 { 091 unoptimized.add( unoptimized.remove( 0 ) ); 092 } 093 } 094 else 095 { 096 if ( ( count2 != null ) && ( ( Long ) count1 > ( Long ) count2 ) ) 097 { 098 unoptimized.add( unoptimized.remove( 0 ) ); 099 } 100 } 101 102 return unoptimized; 103 104 default : 105 List<Evaluator<? extends ExprNode>> optimized = new ArrayList<>( 106 unoptimized.size() ); 107 optimized.addAll( unoptimized ); 108 109 Collections.sort( optimized, new ScanCountComparator() ); 110 111 return optimized; 112 } 113 114 /* Potential speed up, for when we do'nt care about the evaluation itself. 115 private List<Evaluator<? extends ExprNode>> optimize( 116 List<Evaluator<? extends ExprNode>> evaluators ) 117 { 118 long minCount = Long.MAX_VALUE; 119 int pos = 0; 120 int minPos = 0; 121 122 for ( Evaluator<? extends ExprNode> evaluator : evaluators ) 123 { 124 long count = ( Long ) evaluator.getExpression().get( "count" ); 125 126 if ( count < minCount ) 127 { 128 minCount = count; 129 minPos = pos; 130 } 131 132 pos++; 133 } 134 135 if ( minPos > 0 ) 136 { 137 Evaluator<? extends ExprNode> minEvaluator = evaluators.remove( minPos ); 138 evaluators.set( 0, minEvaluator ); 139 140 } 141 142 return evaluators; 143 } 144 145 */ 146 } 147 148 149 /** 150 * {@inheritDoc} 151 */ 152 public boolean evaluate( Entry entry ) throws LdapException 153 { 154 for ( Evaluator<?> evaluator : evaluators ) 155 { 156 if ( !evaluator.evaluate( entry ) ) 157 { 158 return false; 159 } 160 } 161 162 return true; 163 } 164 165 166 /** 167 * {@inheritDoc} 168 */ 169 public boolean evaluate( PartitionTxn partitionTxn, IndexEntry<?, String> indexEntry ) throws LdapException 170 { 171 for ( Evaluator<?> evaluator : evaluators ) 172 { 173 if ( !evaluator.evaluate( partitionTxn, indexEntry ) ) 174 { 175 return false; 176 } 177 } 178 179 return true; 180 } 181 182 183 /** 184 * {@inheritDoc} 185 */ 186 public AndNode getExpression() 187 { 188 return node; 189 } 190 191 192 /** 193 * Dumps the evaluators 194 */ 195 private String dumpEvaluators( String tabs ) 196 { 197 StringBuilder sb = new StringBuilder(); 198 199 for ( Evaluator<? extends ExprNode> evaluator : evaluators ) 200 { 201 sb.append( evaluator.toString( tabs + " " ) ); 202 } 203 204 return sb.toString(); 205 } 206 207 208 /** 209 * @see Object#toString() 210 */ 211 public String toString( String tabs ) 212 { 213 StringBuilder sb = new StringBuilder(); 214 215 sb.append( tabs ).append( "AndEvaluator : " ).append( node ).append( "\n" ); 216 217 if ( ( evaluators != null ) && !evaluators.isEmpty() ) 218 { 219 sb.append( dumpEvaluators( tabs + " " ) ).append( "\n" ); 220 } 221 222 return sb.toString(); 223 } 224 225 226 /** 227 * @see Object#toString() 228 */ 229 public String toString() 230 { 231 return toString( "" ); 232 } 233}