View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.server.xdbm.search.impl;
21  
22  
23  import org.apache.directory.server.core.cursor.Cursor;
24  import org.apache.directory.server.core.cursor.InvalidCursorPositionException;
25  import org.apache.directory.server.core.entry.ServerEntry;
26  import org.apache.directory.server.xdbm.IndexEntry;
27  import org.apache.directory.server.xdbm.AbstractIndexCursor;
28  import org.apache.directory.server.xdbm.IndexCursor;
29  import org.apache.directory.server.xdbm.search.Evaluator;
30  import org.apache.directory.shared.ldap.filter.ExprNode;
31  
32  import java.util.*;
33  
34  
35  /**
36   * A Cursor returning candidates satisfying a logical disjunction expression.
37   *
38   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
39   * @version $Rev$
40   */
41  public class OrCursor<V> extends AbstractIndexCursor<V, ServerEntry>
42  {
43      private static final String UNSUPPORTED_MSG =
44          "OrCursors are not ordered and do not support positioning by element.";
45      private final List<IndexCursor<V,ServerEntry>> cursors;
46      private final List<Evaluator<? extends ExprNode,ServerEntry>> evaluators;
47      private final List<Set<Long>> blacklists;
48      private int cursorIndex = -1;
49      private boolean available = false;
50  
51  
52      // TODO - do same evaluator fail fast optimization that we do in AndCursor
53      public OrCursor( List<IndexCursor<V, ServerEntry>> cursors, List<Evaluator<? extends ExprNode,ServerEntry>> evaluators )
54      {
55          if ( cursors.size() <= 1 )
56          {
57              throw new IllegalArgumentException(
58                  "Must have 2 or more sub-expression Cursors for a disjunction" );
59          }
60  
61          this.cursors = cursors;
62          this.evaluators = evaluators;
63          this.blacklists = new ArrayList<Set<Long>>();
64  
65          for ( int ii = 0; ii < cursors.size(); ii++ )
66          {
67              this.blacklists.add( new HashSet<Long>() );
68          }
69          this.cursorIndex = 0;
70      }
71  
72  
73      public boolean available()
74      {
75          return available;
76      }
77  
78  
79      public void before( IndexEntry<V, ServerEntry> element ) throws Exception
80      {
81          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
82      }
83  
84  
85      public void after( IndexEntry<V, ServerEntry> element ) throws Exception
86      {
87          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
88      }
89  
90  
91      public void beforeValue( Long id, V value ) throws Exception
92      {
93          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
94      }
95  
96  
97      public void afterValue( Long id, V value ) throws Exception
98      {
99          throw new UnsupportedOperationException( UNSUPPORTED_MSG );
100     }
101 
102 
103     public void beforeFirst() throws Exception
104     {
105         checkNotClosed( "beforeFirst()" );
106         cursorIndex = 0;
107         cursors.get( cursorIndex ).beforeFirst();
108         available = false;
109     }
110 
111 
112     public void afterLast() throws Exception
113     {
114         checkNotClosed( "afterLast()" );
115         cursorIndex = cursors.size() - 1;
116         cursors.get( cursorIndex ).afterLast();
117         available = false;
118     }
119 
120 
121     public boolean first() throws Exception
122     {
123         beforeFirst();
124         return available = next();
125     }
126 
127 
128     public boolean last() throws Exception
129     {
130         afterLast();
131         return available = previous();
132     }
133 
134 
135     private boolean isBlackListed( Long id )
136     {
137         return blacklists.get( cursorIndex ).contains( id );
138     }
139 
140 
141     /**
142      * The first sub-expression Cursor to advance to an entry adds the entry
143      * to the blacklists of other Cursors that might return that entry.
144      *
145      * @param indexEntry the index entry to blacklist
146      * @throws Exception if there are problems accessing underlying db
147      */
148     private void blackListIfDuplicate( IndexEntry<?, ServerEntry> indexEntry ) throws Exception
149     {
150         for ( int ii = 0; ii < evaluators.size(); ii++ )
151         {
152             if ( ii == cursorIndex )
153             {
154                 continue;
155             }
156 
157             if ( evaluators.get( ii ).evaluate( indexEntry ) )
158             {
159                 blacklists.get( ii ).add( indexEntry.getId() );
160             }
161         }
162     }
163 
164 
165     public boolean previous() throws Exception
166     {
167         while ( cursors.get( cursorIndex ).previous() )
168         {
169             checkNotClosed( "previous()" );
170             IndexEntry<?,ServerEntry> candidate = cursors.get( cursorIndex ).get();
171             if ( ! isBlackListed( candidate.getId() ) )
172             {
173                 blackListIfDuplicate( candidate );
174                 return available = true;
175             }
176         }
177 
178         while ( cursorIndex > 0 )
179         {
180             checkNotClosed( "previous()" );
181             cursorIndex--;
182             cursors.get( cursorIndex ).afterLast();
183 
184             while ( cursors.get( cursorIndex ).previous() )
185             {
186                 checkNotClosed( "previous()" );
187                 IndexEntry<?,ServerEntry> candidate = cursors.get( cursorIndex ).get();
188                 if ( ! isBlackListed( candidate.getId() ) )
189                 {
190                     blackListIfDuplicate( candidate );
191                     return available = true;
192                 }
193             }
194         }
195 
196         return available = false;
197     }
198 
199 
200     public boolean next() throws Exception
201     {
202         while ( cursors.get( cursorIndex ).next() )
203         {
204             checkNotClosed( "next()" );
205             IndexEntry<?,ServerEntry> candidate = cursors.get( cursorIndex ).get();
206             if ( ! isBlackListed( candidate.getId() ) )
207             {
208                 blackListIfDuplicate( candidate );
209                 return available = true;
210             }
211         }
212 
213         while ( cursorIndex < cursors.size() - 1 )
214         {
215             checkNotClosed( "previous()" );
216             cursorIndex++;
217             cursors.get( cursorIndex ).beforeFirst();
218 
219             while ( cursors.get( cursorIndex ).next() )
220             {
221                 checkNotClosed( "previous()" );
222                 IndexEntry<?,ServerEntry> candidate = cursors.get( cursorIndex ).get();
223                 if ( ! isBlackListed( candidate.getId() ) )
224                 {
225                     blackListIfDuplicate( candidate );
226                     return available = true;
227                 }
228             }
229         }
230 
231         return available = false;
232     }
233 
234 
235     public IndexEntry<V, ServerEntry> get() throws Exception
236     {
237         checkNotClosed( "get()" );
238         if ( available )
239         {
240             return cursors.get( cursorIndex ).get();
241         }
242 
243         throw new InvalidCursorPositionException( "Cursor has not been positioned yet." );
244     }
245 
246 
247     public boolean isElementReused()
248     {
249         return cursors.get( cursorIndex ).isElementReused();
250     }
251 
252 
253     public void close() throws Exception
254     {
255         super.close();
256         for ( Cursor<?> cursor : cursors )
257         {
258             cursor.close();
259         }
260     }
261 }