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 java.util.ArrayList; 024 import java.util.List; 025 026 import org.apache.directory.server.i18n.I18n; 027 import org.apache.directory.server.xdbm.IndexCursor; 028 import org.apache.directory.server.xdbm.Store; 029 import org.apache.directory.server.xdbm.search.Evaluator; 030 import org.apache.directory.shared.ldap.NotImplementedException; 031 import org.apache.directory.shared.ldap.entry.ServerEntry; 032 import org.apache.directory.shared.ldap.filter.AndNode; 033 import org.apache.directory.shared.ldap.filter.ExprNode; 034 import org.apache.directory.shared.ldap.filter.NotNode; 035 import org.apache.directory.shared.ldap.filter.OrNode; 036 import org.apache.directory.shared.ldap.filter.ScopeNode; 037 import org.apache.directory.shared.ldap.filter.SearchScope; 038 039 040 /** 041 * Builds Cursors over candidates that satisfy a filter expression. 042 * 043 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 044 * @version $Rev: 927146 $ 045 */ 046 public class CursorBuilder<ID> 047 { 048 /** The database used by this builder */ 049 private Store<ServerEntry, ID> db = null; 050 051 /** Evaluator dependency on a EvaluatorBuilder */ 052 private EvaluatorBuilder<ID> evaluatorBuilder; 053 054 055 /** 056 * Creates an expression tree enumerator. 057 * 058 * @param db database used by this enumerator 059 * @param evaluatorBuilder the evaluator builder 060 */ 061 public CursorBuilder( Store<ServerEntry, ID> db, EvaluatorBuilder<ID> evaluatorBuilder ) 062 { 063 this.db = db; 064 this.evaluatorBuilder = evaluatorBuilder; 065 } 066 067 068 public <T> IndexCursor<?, ServerEntry, ID> build( ExprNode node ) throws Exception 069 { 070 switch ( node.getAssertionType() ) 071 { 072 /* ---------- LEAF NODE HANDLING ---------- */ 073 074 case APPROXIMATE: 075 return new ApproximateCursor<T, ID>( db, ( ApproximateEvaluator<T, ID> ) evaluatorBuilder.build( node ) ); 076 077 case EQUALITY: 078 return new EqualityCursor<T, ID>( db, ( EqualityEvaluator<T, ID> ) evaluatorBuilder.build( node ) ); 079 080 case GREATEREQ: 081 return new GreaterEqCursor<T, ID>( db, ( GreaterEqEvaluator<T, ID> ) evaluatorBuilder.build( node ) ); 082 083 case LESSEQ: 084 return new LessEqCursor<T, ID>( db, ( LessEqEvaluator<T, ID> ) evaluatorBuilder.build( node ) ); 085 086 case PRESENCE: 087 return new PresenceCursor<ID>( db, ( PresenceEvaluator<ID> ) evaluatorBuilder.build( node ) ); 088 089 case SCOPE: 090 if ( ( ( ScopeNode ) node ).getScope() == SearchScope.ONELEVEL ) 091 { 092 return new OneLevelScopeCursor<ID>( db, 093 ( OneLevelScopeEvaluator<ServerEntry, ID> ) evaluatorBuilder.build( node ) ); 094 } 095 else 096 { 097 return new SubtreeScopeCursor<ID>( db, ( SubtreeScopeEvaluator<ServerEntry, ID> ) evaluatorBuilder 098 .build( node ) ); 099 } 100 101 case SUBSTRING: 102 return new SubstringCursor<ID>( db, ( SubstringEvaluator<ID> ) evaluatorBuilder.build( node ) ); 103 104 /* ---------- LOGICAL OPERATORS ---------- */ 105 106 case AND: 107 return buildAndCursor( ( AndNode ) node ); 108 109 case NOT: 110 return new NotCursor<ID, ID>( db, evaluatorBuilder.build( ( ( NotNode ) node ).getFirstChild() ) ); 111 112 case OR: 113 return buildOrCursor( ( OrNode ) node ); 114 115 /* ---------- NOT IMPLEMENTED ---------- */ 116 117 case ASSERTION: 118 case EXTENSIBLE: 119 throw new NotImplementedException(); 120 121 default: 122 throw new IllegalStateException( I18n.err( I18n.ERR_260, node.getAssertionType() ) ); 123 } 124 } 125 126 127 /** 128 * Creates a OrCursor over a disjunction expression branch node. 129 * 130 * @param node the disjunction expression branch node 131 * @return Cursor over candidates satisfying disjunction expression 132 * @throws Exception on db access failures 133 */ 134 private IndexCursor<?, ServerEntry, ID> buildOrCursor( OrNode node ) throws Exception 135 { 136 List<ExprNode> children = node.getChildren(); 137 List<IndexCursor<? extends Object, ServerEntry, ID>> childCursors = new ArrayList<IndexCursor<?, ServerEntry, ID>>( 138 children.size() ); 139 List<Evaluator<? extends ExprNode, ServerEntry, ID>> childEvaluators = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>( 140 children.size() ); 141 142 // Recursively create Cursors and Evaluators for each child expression node 143 for ( ExprNode child : children ) 144 { 145 childCursors.add( build( child ) ); 146 childEvaluators.add( evaluatorBuilder.build( child ) ); 147 } 148 149 return new OrCursor( childCursors, childEvaluators ); 150 } 151 152 153 /** 154 * Creates an AndCursor over a conjunction expression branch node. 155 * 156 * @param node a conjunction expression branch node 157 * @return Cursor over the conjunction expression 158 * @throws Exception on db access failures 159 */ 160 private IndexCursor<?, ServerEntry, ID> buildAndCursor( AndNode node ) throws Exception 161 { 162 int minIndex = 0; 163 long minValue = Long.MAX_VALUE; 164 //noinspection UnusedAssignment 165 long value = Long.MAX_VALUE; 166 167 /* 168 * We scan the child nodes of a branch node searching for the child 169 * expression node with the smallest scan count. This is the child 170 * we will use for iteration by creating a Cursor over its expression. 171 */ 172 final List<ExprNode> children = node.getChildren(); 173 174 for ( int ii = 0; ii < children.size(); ii++ ) 175 { 176 ExprNode child = children.get( ii ); 177 Object count = child.get( "count" ); 178 if ( count == null ) 179 { 180 continue; 181 } 182 value = ( Long ) count; 183 minValue = Math.min( minValue, value ); 184 185 if ( minValue == value ) 186 { 187 minIndex = ii; 188 } 189 } 190 191 // Once found we build the child Evaluators minus the one for the minChild 192 ExprNode minChild = children.get( minIndex ); 193 List<Evaluator<? extends ExprNode, ServerEntry, ID>> childEvaluators = new ArrayList<Evaluator<? extends ExprNode, ServerEntry, ID>>( 194 children.size() - 1 ); 195 for ( ExprNode child : children ) 196 { 197 if ( child == minChild ) 198 { 199 continue; 200 } 201 202 childEvaluators.add( evaluatorBuilder.build( child ) ); 203 } 204 205 // Do recursive call to build min child Cursor then create AndCursor 206 IndexCursor<?, ServerEntry, ID> childCursor = build( minChild ); 207 return new AndCursor( childCursor, childEvaluators ); 208 } 209 }