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;
21
22
23 import java.io.IOException;
24 import java.net.URI;
25
26 import org.apache.directory.api.ldap.model.cursor.Cursor;
27 import org.apache.directory.api.ldap.model.exception.LdapException;
28 import org.apache.directory.api.ldap.model.schema.AttributeType;
29 import org.apache.directory.server.core.api.partition.PartitionTxn;
30
31
32 /**
33 * An index used to retrieve elements into the master table. Each stored element that is
34 * indexed has a unique identifier (ID). We may have more than one element associated with
35 * a value (K). We may cache the retrieved element (O). <br>
36 * Cursors over indices can also be gotten to traverse the
37 * values of the index.
38 *
39 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
40 * @param <K> The Indexed value type, used to retrieve an element
41 * @param <E> The unique identifier type in the master table
42 */
43 public interface Index<K, E>
44 {
45 /** The default cache size (ie, the number of elements we stored in the cache) */
46 int DEFAULT_INDEX_CACHE_SIZE = 100;
47
48 // -----------------------------------------------------------------------
49 // C O N F I G U R A T I O N M E T H O D S
50 // -----------------------------------------------------------------------
51
52 /**
53 * Gets the attribute identifier set at configuration time for this index which may not
54 * be the OID but an alias name for the attributeType associated with this Index
55 *
56 * @return configured attribute oid or alias name
57 */
58 String getAttributeId();
59
60
61 /**
62 * Sets the attribute identifier set at configuration time for this index which may not
63 * be the OID but an alias name for the attributeType associated with this Index
64 *
65 * @param attributeId configured attribute oid or alias name
66 */
67 void setAttributeId( String attributeId );
68
69
70 /**
71 * Gets the size of the index cache in terms of the number of index entries to be cached.
72 *
73 * @return the size of the index cache
74 */
75 int getCacheSize();
76
77
78 /**
79 * Sets the size of the index cache in terms of the number of index entries to be cached.
80 *
81 * @param cacheSize the size of the index cache
82 */
83 void setCacheSize( int cacheSize );
84
85
86 /**
87 * Sets the working directory path to something other than the default. Sometimes more
88 * performance is gained by locating indices on separate disk spindles.
89 *
90 * @param wkDirPath optional working directory path
91 */
92 void setWkDirPath( URI wkDirPath );
93
94
95 /**
96 * Gets the working directory path to something other than the default. Sometimes more
97 * performance is gained by locating indices on separate disk spindles.
98 *
99 * @return optional working directory path
100 */
101 URI getWkDirPath();
102
103
104 // -----------------------------------------------------------------------
105 // E N D C O N F I G U R A T I O N M E T H O D S
106 // -----------------------------------------------------------------------
107
108 /**
109 * Gets the attribute this Index is built upon.
110 *
111 * @return the id of the Index's attribute
112 */
113 AttributeType getAttribute();
114
115
116 /**
117 * Gets the total scan count for this index.
118 *
119 * @param partitionTxn The transaction to use
120 * @return the number of key/value pairs in this index
121 * @throws LdapException on failure to access index db files
122 */
123 long count( PartitionTxn partitionTxn ) throws LdapException;
124
125
126 /**
127 * Gets the scan count for the occurrence of a specific attribute value
128 * within the index.
129 *
130 * @param partitionTxn The transaction to use
131 * @param attrVal the value of the attribute to get a scan count for
132 * @return the number of key/value pairs in this index with the value value
133 * @throws LdapException on failure to access index db files
134 */
135 long count( PartitionTxn partitionTxn, K attrVal ) throws LdapException;
136
137
138 /**
139 * Find the number of element in a tree above a given key
140 *
141 * @param partitionTxn The transaction to use
142 * @param attrVal The key
143 * @return The number of element above the key
144 * @throws LdapException If the operation failed
145 */
146 long greaterThanCount( PartitionTxn partitionTxn, K attrVal ) throws LdapException;
147
148
149 /**
150 * Find the number of element in a tree below a given key
151 *
152 * @param partitionTxn The transaction to use
153 * @param attrVal The key
154 * @return The number of element below the key
155 * @throws LdapException If the operation failed
156 */
157 long lessThanCount( PartitionTxn partitionTxn, K attrVal ) throws LdapException;
158
159
160 /**
161 * Search for a value using the Forward table
162 *
163 * @param partitionTxn The transaction to use
164 * @param attrVal The key to retrieve
165 * @return The found value
166 * @throws LdapException If the operation failed
167 */
168 E forwardLookup( PartitionTxn partitionTxn, K attrVal ) throws LdapException;
169
170
171 /**
172 * Search for a value using the Reverse table
173 *
174 * @param partitionTxn The transaction to use
175 * @param element The key to retrieve
176 * @return The found value
177 * @throws LdapException If the operation failed
178 */
179 K reverseLookup( PartitionTxn partitionTxn, E element ) throws LdapException;
180
181
182 /**
183 * Add an entry into the index, associated with the element E. The added
184 * value is the key to retrieve the element having the given ID.
185 *
186 * @param partitionTxn The transaction to use
187 * @param attrVal The added value
188 * @param entryId The entry ID pointed by the added value
189 * @throws LdapException If the addition can't be done
190 */
191 void add( PartitionTxn partitionTxn, K attrVal, E entryId ) throws LdapException;
192
193
194 /**
195 * Remove all the reference to an entry from the index.
196 * <br>
197 * As an entry might be referenced more than once in the forward index,
198 * depending on which index we are dealing with, we need to iterate
199 * over all the values contained into the reverse index for this entryId.
200 * <br>
201 * For instance, considering the ObjectClass index for an entry having
202 * three ObjectClasses (top, person, inetOrgPerson), then the reverse
203 * index will contain :
204 * <pre>
205 * [entryId, [top, person, inetOrgPerson]]
206 * </pre>
207 * and the forward index will contain many entries like :
208 * <pre>
209 * [top, [..., entryId, ...]]
210 * [person, [..., entryId, ...]]
211 * [inetOrgPerson, [..., entryId, ...]]
212 * </pre>
213 * So dropping the entryId means that we must first get all the values from
214 * the reverse index (and we will get [top, person, inetOrgPerson]) then to
215 * iterate through all those values to remove entryId from the associated
216 * list of entryIds.
217 *
218 * @param partitionTxn The transaction to use
219 * @param entryId The master table entryId to remove
220 * @throws LdapException if we can't drop the element from the index
221 */
222 void drop( PartitionTxn partitionTxn, E entryId ) throws LdapException;
223
224
225 /**
226 * Remove the pair <K,ID> from the index for the given value and id.
227 *
228 * @param partitionTxn The transaction to use
229 * @param attrVal The value we want to remove from the index
230 * @param entryId The associated ID
231 * @throws LdapException If the removal can't be done
232 */
233 void drop( PartitionTxn partitionTxn, K attrVal, E entryId ) throws LdapException;
234
235
236 /**
237 * Builds a Cursor on the Forward index
238 *
239 * @param partitionTxn The transaction to use
240 * @return The created Cursor
241 * @throws LdapException If the cursor can't be created
242 */
243 Cursor<IndexEntry<K, E>> forwardCursor( PartitionTxn partitionTxn ) throws LdapException;
244
245
246 /**
247 * Builds a Cursor on the Forward index, starting at a specific key
248 *
249 * @param partitionTxn The transaction to use
250 * @param key The key to start from
251 * @return The created Cursor
252 * @throws LdapException If the cursor can't be created
253 */
254 Cursor<IndexEntry<K, E>> forwardCursor( PartitionTxn partitionTxn, K key ) throws LdapException;
255
256
257 /**
258 * Builds a Cursor on the Reverse index, starting at a specific entry Id
259 *
260 * @param partitionTxn The transaction to use
261 * @param entryId The entry ID to start from
262 * @return The created Cursor
263 * @throws LdapException If the cursor can't be created
264 */
265 Cursor<K> reverseValueCursor( PartitionTxn partitionTxn, E entryId ) throws LdapException;
266
267
268 /**
269 * Builds a Cursor on the Forward index, starting at a specific key
270 *
271 * @param partitionTxn The transaction to use
272 * @param key The key to start from
273 * @return The created Cursor
274 * @throws LdapException If the cursor can't be created
275 */
276 Cursor<E> forwardValueCursor( PartitionTxn partitionTxn, K key ) throws LdapException;
277
278
279 /**
280 * Try to move forward in the index
281 *
282 * @param partitionTxn The transaction to use
283 * @param attrVal The key we want to start with
284 * @return <tt>true</tt> if we can move forward
285 * @throws LdapException If we had an issue moving forward
286 */
287 boolean forward( PartitionTxn partitionTxn, K attrVal ) throws LdapException;
288
289
290 /**
291 * Try to move forward in the index
292 *
293 * @param partitionTxn The transaction to use
294 * @param attrVal The key we want to start with
295 * @param entryId The entry ID to start from
296 * @return <tt>true</tt> if we can move forward
297 * @throws LdapException If we had an issue moving forward
298 */
299 boolean forward( PartitionTxn partitionTxn, K attrVal, E entryId ) throws LdapException;
300
301
302 /**
303 * Try to move backward in the index
304 *
305 * @param partitionTxn The transaction to use
306 * @param entryId The entry we want to start with
307 * @return <tt>true</tt> if we can move backward
308 * @throws LdapException If we had an issue moving backward
309 */
310 boolean reverse( PartitionTxn partitionTxn, E entryId ) throws LdapException;
311
312
313 /**
314 * Try to move backward in the index
315 *
316 * @param partitionTxn The transaction to use
317 * @param entryId The entry ID to start from
318 * @param attrVal The key we want to start with
319 * @return <tt>true</tt> if we can move backward
320 * @throws LdapException If we had an issue moving backward
321 */
322 boolean reverse( PartitionTxn partitionTxn, E entryId, K attrVal ) throws LdapException;
323
324
325 /**
326 * Close and index
327 *
328 * @param partitionTxn The transaction to use
329 * @throws LdapException If we weren't able to close the index
330 * @throws IOException If we had an issue with the index file
331 */
332 void close( PartitionTxn partitionTxn ) throws LdapException, IOException;
333
334
335 /**
336 * tells whether the Index implementation supports storing duplicate keys
337 *
338 * @return true if duplicate keys are allowed false otherwise
339 */
340 boolean isDupsEnabled();
341
342
343 /**
344 * Tells if the index has a reverse table or not
345 * @return true if the index has a reverse table
346 */
347 boolean hasReverse();
348 }