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.AndNode; 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 conjunction (AND) expressions. 037 * 038 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 039 * @version $$Rev$$ 040 */ 041 public class AndEvaluator<ID> implements Evaluator<AndNode, ServerEntry, ID> 042 { 043 private final List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators; 044 045 private final AndNode node; 046 047 048 public AndEvaluator( AndNode 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 * increasing scan counts on their expression nodes. This is done to have 058 * the Evaluators with the least scan count which have the highest 059 * probability of rejecting 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 increasing 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<?, ServerEntry, ID>>() 073 { 074 public int compare( Evaluator<?, ServerEntry, ID> e1, Evaluator<?, ServerEntry, ID> e2 ) 075 { 076 long scanCount1 = ( Long ) e1.getExpression().get( "count" ); 077 long scanCount2 = ( Long ) e2.getExpression().get( "count" ); 078 079 if ( scanCount1 == scanCount2 ) 080 { 081 return 0; 082 } 083 084 /* 085 * We want the Evaluator with the smallest scan count first 086 * since this node has the highest probability of failing, or 087 * rather the least probability of succeeding. That way we 088 * can short the sub-expression evaluation process. 089 */ 090 if ( scanCount1 < scanCount2 ) 091 { 092 return -1; 093 } 094 095 return 1; 096 } 097 } ); 098 099 return optimized; 100 } 101 102 103 public boolean evaluateId( ID id ) throws Exception 104 { 105 for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators ) 106 { 107 if ( !evaluator.evaluateId( id ) ) 108 { 109 return false; 110 } 111 } 112 113 return true; 114 } 115 116 117 public boolean evaluateEntry( ServerEntry entry ) throws Exception 118 { 119 for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators ) 120 { 121 if ( !evaluator.evaluateEntry( entry ) ) 122 { 123 return false; 124 } 125 } 126 127 return true; 128 } 129 130 131 public boolean evaluate( IndexEntry<?, ServerEntry, ID> indexEntry ) throws Exception 132 { 133 for ( Evaluator<?, ServerEntry, ID> evaluator : evaluators ) 134 { 135 if ( !evaluator.evaluate( indexEntry ) ) 136 { 137 return false; 138 } 139 } 140 141 return true; 142 } 143 144 145 public AndNode getExpression() 146 { 147 return node; 148 } 149 }