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.HashSet; 025 import java.util.List; 026 import java.util.Set; 027 028 import org.apache.directory.server.i18n.I18n; 029 import org.apache.directory.server.xdbm.IndexEntry; 030 import org.apache.directory.server.xdbm.AbstractIndexCursor; 031 import org.apache.directory.server.xdbm.IndexCursor; 032 import org.apache.directory.server.xdbm.search.Evaluator; 033 import org.apache.directory.shared.ldap.cursor.Cursor; 034 import org.apache.directory.shared.ldap.cursor.InvalidCursorPositionException; 035 import org.apache.directory.shared.ldap.entry.ServerEntry; 036 import org.apache.directory.shared.ldap.filter.ExprNode; 037 038 039 /** 040 * A Cursor returning candidates satisfying a logical disjunction expression. 041 * 042 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 043 * @version $Rev$ 044 */ 045 public class OrCursor<V, ID> extends AbstractIndexCursor<V, ServerEntry, ID> 046 { 047 private static final String UNSUPPORTED_MSG = I18n.err( I18n.ERR_722 ); 048 private final List<IndexCursor<V, ServerEntry, ID>> cursors; 049 private final List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators; 050 private final List<Set<ID>> blacklists; 051 private int cursorIndex = -1; 052 private boolean available = false; 053 054 055 // TODO - do same evaluator fail fast optimization that we do in AndCursor 056 public OrCursor( List<IndexCursor<V, ServerEntry, ID>> cursors, 057 List<Evaluator<? extends ExprNode, ServerEntry, ID>> evaluators ) 058 { 059 if ( cursors.size() <= 1 ) 060 { 061 throw new IllegalArgumentException( I18n.err( I18n.ERR_723 ) ); 062 } 063 064 this.cursors = cursors; 065 this.evaluators = evaluators; 066 this.blacklists = new ArrayList<Set<ID>>(); 067 068 for ( int ii = 0; ii < cursors.size(); ii++ ) 069 { 070 this.blacklists.add( new HashSet<ID>() ); 071 } 072 this.cursorIndex = 0; 073 } 074 075 076 public boolean available() 077 { 078 return available; 079 } 080 081 082 public void before( IndexEntry<V, ServerEntry, ID> element ) throws Exception 083 { 084 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 085 } 086 087 088 public void after( IndexEntry<V, ServerEntry, ID> element ) throws Exception 089 { 090 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 091 } 092 093 094 public void beforeValue( ID id, V value ) throws Exception 095 { 096 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 097 } 098 099 100 public void afterValue( ID id, V value ) throws Exception 101 { 102 throw new UnsupportedOperationException( UNSUPPORTED_MSG ); 103 } 104 105 106 public void beforeFirst() throws Exception 107 { 108 checkNotClosed( "beforeFirst()" ); 109 cursorIndex = 0; 110 cursors.get( cursorIndex ).beforeFirst(); 111 available = false; 112 } 113 114 115 public void afterLast() throws Exception 116 { 117 checkNotClosed( "afterLast()" ); 118 cursorIndex = cursors.size() - 1; 119 cursors.get( cursorIndex ).afterLast(); 120 available = false; 121 } 122 123 124 public boolean first() throws Exception 125 { 126 beforeFirst(); 127 return available = next(); 128 } 129 130 131 public boolean last() throws Exception 132 { 133 afterLast(); 134 return available = previous(); 135 } 136 137 138 private boolean isBlackListed( ID id ) 139 { 140 return blacklists.get( cursorIndex ).contains( id ); 141 } 142 143 144 /** 145 * The first sub-expression Cursor to advance to an entry adds the entry 146 * to the blacklists of other Cursors that might return that entry. 147 * 148 * @param indexEntry the index entry to blacklist 149 * @throws Exception if there are problems accessing underlying db 150 */ 151 private void blackListIfDuplicate( IndexEntry<?, ServerEntry, ID> indexEntry ) throws Exception 152 { 153 for ( int ii = 0; ii < evaluators.size(); ii++ ) 154 { 155 if ( ii == cursorIndex ) 156 { 157 continue; 158 } 159 160 if ( evaluators.get( ii ).evaluate( indexEntry ) ) 161 { 162 blacklists.get( ii ).add( indexEntry.getId() ); 163 } 164 } 165 } 166 167 168 public boolean previous() throws Exception 169 { 170 while ( cursors.get( cursorIndex ).previous() ) 171 { 172 checkNotClosed( "previous()" ); 173 IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get(); 174 if ( !isBlackListed( candidate.getId() ) ) 175 { 176 blackListIfDuplicate( candidate ); 177 return available = true; 178 } 179 } 180 181 while ( cursorIndex > 0 ) 182 { 183 checkNotClosed( "previous()" ); 184 cursorIndex--; 185 cursors.get( cursorIndex ).afterLast(); 186 187 while ( cursors.get( cursorIndex ).previous() ) 188 { 189 checkNotClosed( "previous()" ); 190 IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get(); 191 if ( !isBlackListed( candidate.getId() ) ) 192 { 193 blackListIfDuplicate( candidate ); 194 return available = true; 195 } 196 } 197 } 198 199 return available = false; 200 } 201 202 203 public boolean next() throws Exception 204 { 205 while ( cursors.get( cursorIndex ).next() ) 206 { 207 checkNotClosed( "next()" ); 208 IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get(); 209 if ( !isBlackListed( candidate.getId() ) ) 210 { 211 blackListIfDuplicate( candidate ); 212 return available = true; 213 } 214 } 215 216 while ( cursorIndex < cursors.size() - 1 ) 217 { 218 checkNotClosed( "previous()" ); 219 cursorIndex++; 220 cursors.get( cursorIndex ).beforeFirst(); 221 222 while ( cursors.get( cursorIndex ).next() ) 223 { 224 checkNotClosed( "previous()" ); 225 IndexEntry<?, ServerEntry, ID> candidate = cursors.get( cursorIndex ).get(); 226 if ( !isBlackListed( candidate.getId() ) ) 227 { 228 blackListIfDuplicate( candidate ); 229 return available = true; 230 } 231 } 232 } 233 234 return available = false; 235 } 236 237 238 public IndexEntry<V, ServerEntry, ID> get() throws Exception 239 { 240 checkNotClosed( "get()" ); 241 if ( available ) 242 { 243 return cursors.get( cursorIndex ).get(); 244 } 245 246 throw new InvalidCursorPositionException( I18n.err( I18n.ERR_708 ) ); 247 } 248 249 250 public boolean isElementReused() 251 { 252 return cursors.get( cursorIndex ).isElementReused(); 253 } 254 255 256 public void close() throws Exception 257 { 258 super.close(); 259 for ( Cursor<?> cursor : cursors ) 260 { 261 cursor.close(); 262 } 263 } 264 }