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.core.partition.impl.btree.jdbm;
21
22
23 import jdbm.RecordManager;
24 import jdbm.helper.MRU;
25 import jdbm.recman.BaseRecordManager;
26 import jdbm.recman.CacheRecordManager;
27 import org.apache.directory.server.core.partition.impl.btree.*;
28 import org.apache.directory.server.core.cursor.Cursor;
29 import org.apache.directory.server.schema.SerializableComparator;
30 import org.apache.directory.server.xdbm.Index;
31 import org.apache.directory.server.xdbm.Tuple;
32 import org.apache.directory.server.xdbm.IndexCursor;
33 import org.apache.directory.shared.ldap.schema.AttributeType;
34 import org.apache.directory.shared.ldap.util.SynchronizedLRUMap;
35
36 import javax.naming.NamingException;
37 import java.io.File;
38 import java.io.IOException;
39
40
41 /**
42 * A Jdbm based index implementation.
43 *
44 * @org.apache.xbean.XBean
45 *
46 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
47 * @version $Rev: 689396 $
48 */
49 public class JdbmIndex<K,O> implements Index<K,O>
50 {
51 /**
52 * default duplicate limit before duplicate keys switch to using a btree for values
53 */
54 public static final int DEFAULT_DUPLICATE_LIMIT = 512;
55
56 /** the key used for the forward btree name */
57 public static final String FORWARD_BTREE = "_forward";
58 /** the key used for the reverse btree name */
59 public static final String REVERSE_BTREE = "_reverse";
60
61 /** the attribute type resolved for this JdbmIndex */
62 private AttributeType attribute;
63 /**
64 * the forward btree where the btree key is the value of the indexed attribute and
65 * the value of the btree is the entry id of the entry containing an attribute with
66 * that value
67 */
68 protected JdbmTable<K, Long> forward;
69 /**
70 * the reverse btree where the btree key is the entry id of the entry containing a
71 * value for the indexed attribute, and the btree value is the value of the indexed
72 * attribute
73 */
74 protected JdbmTable<Long,K> reverse;
75 /**
76 * the JDBM record manager for the file containing this index
77 */
78 protected RecordManager recMan;
79 /**
80 * the normalized value cache for this index
81 * @todo I don't think the keyCache is required anymore since the normalizer
82 * will cache values for us.
83 */
84 protected SynchronizedLRUMap keyCache;
85 /** the size (number of index entries) for the cache */
86 protected int cacheSize = DEFAULT_INDEX_CACHE_SIZE;
87 /**
88 * duplicate limit before duplicate keys switch to using a btree for values
89 */
90 protected int numDupLimit = DEFAULT_DUPLICATE_LIMIT;
91 /**
92 * the attribute identifier set at configuration time for this index which may not
93 * be the OID but an alias name for the attributeType associated with this Index
94 */
95 private String attributeId;
96 /** whether or not this index has been initialized */
97 protected boolean initialized;
98 /** a customm working directory path when specified in configuration */
99 protected File wkDirPath;
100
101
102 /*
103 * NOTE: Duplicate Key Limit
104 *
105 * Jdbm cannot store duplicate keys: meaning it cannot have more than one value
106 * for the same key in the btree. Thus as a workaround we stuff values for the
107 * same key into a TreeSet. This is only effective up to some threshold after
108 * which we run into problems with serialization on and off disk. A threshold
109 * is used to determine when to switch from using a TreeSet to start using another
110 * btree in the same index file just for the values. This value only btree just
111 * has keys populated without a value for it's btree entries. When the switch
112 * occurs the value for the key in the index btree contains a pointer to the
113 * btree containing it's values.
114 *
115 * This numDupLimit is the threshold at which we switch from using in memory
116 * containers for values of the same key to using a btree for those values
117 * instead with indirection.
118 */
119
120 // ------------------------------------------------------------------------
121 // C O N S T R U C T O R S
122 // ----------------------------------------------------------------------
123
124 public JdbmIndex()
125 {
126 initialized = false;
127 }
128
129
130 public JdbmIndex( String attributeId )
131 {
132 initialized = false;
133 setAttributeId( attributeId );
134 }
135
136
137 public void init( AttributeType attributeType, File wkDirPath ) throws IOException
138 {
139 this.keyCache = new SynchronizedLRUMap( cacheSize );
140 this.attribute = attributeType;
141
142 if ( attributeId == null )
143 {
144 setAttributeId( attribute.getName() );
145 }
146
147 if ( this.wkDirPath == null )
148 {
149 this.wkDirPath = wkDirPath;
150 }
151
152 File file = new File( this.wkDirPath.getPath() + File.separator + attribute.getName() );
153 String path = file.getAbsolutePath();
154 BaseRecordManager base = new BaseRecordManager( path );
155 base.disableTransactions();
156 this.recMan = new CacheRecordManager( base, new MRU( cacheSize ) );
157
158 initTables();
159 initialized = true;
160 }
161
162
163 /**
164 * Initializes the forward and reverse tables used by this Index.
165 *
166 * @throws IOException if we cannot initialize the forward and reverse
167 * tables
168 */
169 private void initTables() throws IOException
170 {
171 SerializableComparator<K> comp;
172
173 try
174 {
175 comp = new SerializableComparator<K>( attribute.getEquality().getOid() );
176 }
177 catch ( NamingException e )
178 {
179 IOException ioe = new IOException( "Failed to find an equality matching rule for attribute type" );
180 ioe.initCause( e );
181 throw ioe;
182 }
183
184 /*
185 * The forward key/value map stores attribute values to master table
186 * primary keys. A value for an attribute can occur several times in
187 * different entries so the forward map can have more than one value.
188 */
189 forward = new JdbmTable<K, Long>(
190 attribute.getName() + FORWARD_BTREE,
191 numDupLimit,
192 recMan,
193 comp, LongComparator.INSTANCE,
194 null, LongSerializer.INSTANCE );
195
196 /*
197 * Now the reverse map stores the primary key into the master table as
198 * the key and the values of attributes as the value. If an attribute
199 * is single valued according to its specification based on a schema
200 * then duplicate keys should not be allowed within the reverse table.
201 */
202 if ( attribute.isSingleValue() )
203 {
204 reverse = new JdbmTable<Long,K>(
205 attribute.getName() + REVERSE_BTREE,
206 recMan,
207 LongComparator.INSTANCE,
208 LongSerializer.INSTANCE,
209 null );
210 }
211 else
212 {
213 reverse = new JdbmTable<Long,K>(
214 attribute.getName() + REVERSE_BTREE,
215 numDupLimit,
216 recMan,
217 LongComparator.INSTANCE, comp,
218 LongSerializer.INSTANCE, null );
219 }
220 }
221
222
223 /**
224 * @see org.apache.directory.server.xdbm.Index#getAttribute()
225 */
226 public AttributeType getAttribute()
227 {
228 return attribute;
229 }
230
231
232 // ------------------------------------------------------------------------
233 // C O N F I G U R A T I O N M E T H O D S
234 // ------------------------------------------------------------------------
235
236 /**
237 * Protects configuration properties from being set after initialization.
238 *
239 * @param property the property to protect
240 */
241 private void protect( String property )
242 {
243 if ( initialized )
244 {
245 throw new IllegalStateException( "The " + property
246 + " property for an index cannot be set after it has been initialized." );
247 }
248 }
249
250
251 public boolean isCountExact()
252 {
253 return false;
254 }
255
256
257 /**
258 * Gets the attribute identifier set at configuration time for this index which may not
259 * be the OID but an alias name for the attributeType associated with this Index
260 *
261 * @return configured attribute oid or alias name
262 */
263 public String getAttributeId()
264 {
265 return attributeId;
266 }
267
268
269 /**
270 * Sets the attribute identifier set at configuration time for this index which may not
271 * be the OID but an alias name for the attributeType associated with this Index
272 *
273 * @param attributeId configured attribute oid or alias name
274 */
275 public void setAttributeId( String attributeId )
276 {
277 protect( "attributeId" );
278 this.attributeId = attributeId;
279 }
280
281
282 /**
283 * Gets the threshold at which point duplicate keys use btree indirection to store
284 * their values.
285 *
286 * @return the threshold for storing a keys values in another btree
287 */
288 public int getNumDupLimit()
289 {
290 return numDupLimit;
291 }
292
293
294 /**
295 * Sets the threshold at which point duplicate keys use btree indirection to store
296 * their values.
297 *
298 * @param numDupLimit the threshold for storing a keys values in another btree
299 */
300 public void setNumDupLimit( int numDupLimit )
301 {
302 protect( "numDupLimit" );
303 this.numDupLimit = numDupLimit;
304 }
305
306
307 /**
308 * Gets the size of the index cache in terms of the number of index entries to be cached.
309 *
310 * @return the size of the index cache
311 */
312 public int getCacheSize()
313 {
314 return cacheSize;
315 }
316
317
318 /**
319 * Sets the size of the index cache in terms of the number of index entries to be cached.
320 *
321 * @param cacheSize the size of the index cache
322 */
323 public void setCacheSize( int cacheSize )
324 {
325 protect( "cacheSize" );
326 this.cacheSize = cacheSize;
327 }
328
329
330 /**
331 * Sets the working directory path to something other than the default. Sometimes more
332 * performance is gained by locating indices on separate disk spindles.
333 *
334 * @param wkDirPath optional working directory path
335 */
336 public void setWkDirPath( File wkDirPath )
337 {
338 protect( "wkDirPath" );
339 this.wkDirPath = wkDirPath;
340 }
341
342
343 /**
344 * Gets the working directory path to something other than the default. Sometimes more
345 * performance is gained by locating indices on separate disk spindles.
346 *
347 * @return optional working directory path
348 */
349 public File getWkDirPath()
350 {
351 return wkDirPath;
352 }
353
354
355 // ------------------------------------------------------------------------
356 // Scan Count Methods
357 // ------------------------------------------------------------------------
358
359
360 /**
361 * @see org.apache.directory.server.xdbm.Index#count()
362 */
363 public int count() throws IOException
364 {
365 return forward.count();
366 }
367
368
369 /**
370 * @see Index#count(java.lang.Object)
371 */
372 public int count( K attrVal ) throws Exception
373 {
374 return forward.count( getNormalized( attrVal ) );
375 }
376
377
378 public int greaterThanCount( K attrVal ) throws Exception
379 {
380 return forward.greaterThanCount( getNormalized( attrVal ) );
381 }
382
383
384 /**
385 * @see org.apache.directory.server.xdbm.Index#lessThanCount(java.lang.Object)
386 */
387 public int lessThanCount( K attrVal ) throws Exception
388 {
389 return forward.lessThanCount( getNormalized( attrVal ) );
390 }
391
392
393 // ------------------------------------------------------------------------
394 // Forward and Reverse Lookups
395 // ------------------------------------------------------------------------
396
397
398 /**
399 * @see Index#forwardLookup(java.lang.Object)
400 */
401 public Long forwardLookup( K attrVal ) throws Exception
402 {
403 return forward.get( getNormalized( attrVal ) );
404 }
405
406
407 /**
408 * @see org.apache.directory.server.xdbm.Index#reverseLookup(Long)
409 */
410 public K reverseLookup( Long id ) throws Exception
411 {
412 return reverse.get( id );
413 }
414
415
416 // ------------------------------------------------------------------------
417 // Add/Drop Methods
418 // ------------------------------------------------------------------------
419
420
421 /**
422 * @see Index#add(Object, Long)
423 */
424 public synchronized void add( K attrVal, Long id ) throws Exception
425 {
426 forward.put( getNormalized( attrVal ), id );
427 reverse.put( id, getNormalized( attrVal ) );
428 }
429
430
431 /**
432 * @see Index#drop(Object,Long)
433 */
434 public synchronized void drop( K attrVal, Long id ) throws Exception
435 {
436 forward.remove( getNormalized( attrVal ), id );
437 reverse.remove( id, getNormalized( attrVal ) );
438 }
439
440
441 /**
442 * @see Index#drop(Long)
443 */
444 public void drop( Long id ) throws Exception
445 {
446 Cursor<Tuple<Long,K>> values = reverse.cursor();
447 Tuple<Long,K> tuple = new Tuple<Long,K>( id, null );
448 values.before( tuple );
449
450 while ( values.next() )
451 {
452 forward.remove( values.get().getValue(), id );
453 }
454
455 reverse.remove( id );
456 }
457
458
459 // ------------------------------------------------------------------------
460 // Index Cursor Operations
461 // ------------------------------------------------------------------------
462
463
464 @SuppressWarnings("unchecked")
465 public IndexCursor<K, O> reverseCursor() throws Exception
466 {
467 return new IndexCursorAdaptor<K, O>( ( Cursor ) reverse.cursor(), false );
468 }
469
470
471 @SuppressWarnings("unchecked")
472 public IndexCursor<K, O> forwardCursor() throws Exception
473 {
474 return new IndexCursorAdaptor<K, O>( ( Cursor ) forward.cursor(), true );
475 }
476
477
478 @SuppressWarnings("unchecked")
479 public IndexCursor<K, O> reverseCursor( Long id ) throws Exception
480 {
481 return new IndexCursorAdaptor<K, O>( ( Cursor ) reverse.cursor( id ), false );
482 }
483
484
485 @SuppressWarnings("unchecked")
486 public IndexCursor<K, O> forwardCursor( K key ) throws Exception
487 {
488 return new IndexCursorAdaptor<K, O>( ( Cursor ) forward.cursor( key ), true );
489 }
490
491
492 public Cursor<K> reverseValueCursor( Long id ) throws Exception
493 {
494 return reverse.valueCursor( id );
495 }
496
497
498 public Cursor<Long> forwardValueCursor( K key ) throws Exception
499 {
500 return forward.valueCursor( key );
501 }
502
503
504 // ------------------------------------------------------------------------
505 // Value Assertion (a.k.a Index Lookup) Methods //
506 // ------------------------------------------------------------------------
507
508
509 /**
510 * @see Index#forward(Object)
511 */
512 public boolean forward( K attrVal ) throws Exception
513 {
514 return forward.has( getNormalized( attrVal ) );
515 }
516
517
518 /**
519 * @see Index#forward(Object,Long)
520 */
521 public boolean forward( K attrVal, Long id ) throws Exception
522 {
523 return forward.has( getNormalized( attrVal ), id );
524 }
525
526 /**
527 * @see Index#reverse(Long)
528 */
529 public boolean reverse( Long id ) throws Exception
530 {
531 return reverse.has( id );
532 }
533
534
535 /**
536 * @see Index#reverse(Long,Object)
537 */
538 public boolean reverse( Long id, K attrVal ) throws Exception
539 {
540 return forward.has( getNormalized( attrVal ), id );
541 }
542
543
544 /**
545 * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object)
546 */
547 public boolean forwardGreaterOrEq( K attrVal ) throws Exception
548 {
549 return forward.hasGreaterOrEqual( getNormalized( attrVal ) );
550 }
551
552
553 /**
554 * @see org.apache.directory.server.xdbm.Index#forwardGreaterOrEq(Object, Long)
555 */
556 public boolean forwardGreaterOrEq( K attrVal, Long id ) throws Exception
557 {
558 return forward.hasGreaterOrEqual( getNormalized( attrVal ), id );
559 }
560
561
562 /**
563 * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object)
564 */
565 public boolean forwardLessOrEq( K attrVal ) throws Exception
566 {
567 return forward.hasLessOrEqual( getNormalized( attrVal ) );
568 }
569
570
571 /**
572 * @see org.apache.directory.server.xdbm.Index#forwardLessOrEq(Object, Long)
573 */
574 public boolean forwardLessOrEq( K attrVal, Long id ) throws Exception
575 {
576 return forward.hasLessOrEqual( getNormalized( attrVal ), id );
577 }
578
579
580 /**
581 * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long)
582 */
583 public boolean reverseGreaterOrEq( Long id ) throws Exception
584 {
585 return reverse.hasGreaterOrEqual( id );
586 }
587
588
589 /**
590 * @see org.apache.directory.server.xdbm.Index#reverseGreaterOrEq(Long,Object)
591 */
592 public boolean reverseGreaterOrEq( Long id, K attrVal ) throws Exception
593 {
594 return reverse.hasGreaterOrEqual( id, getNormalized( attrVal ) );
595 }
596
597
598 /**
599 * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long)
600 */
601 public boolean reverseLessOrEq( Long id ) throws Exception
602 {
603 return reverse.hasLessOrEqual( id );
604 }
605
606
607 /**
608 * @see org.apache.directory.server.xdbm.Index#reverseLessOrEq(Long,Object)
609 */
610 public boolean reverseLessOrEq( Long id, K attrVal ) throws Exception
611 {
612 return reverse.hasLessOrEqual( id, getNormalized( attrVal ) );
613 }
614
615
616 // ------------------------------------------------------------------------
617 // Maintenance Methods
618 // ------------------------------------------------------------------------
619
620
621 /**
622 * @see org.apache.directory.server.xdbm.Index#close()
623 */
624 public synchronized void close() throws IOException
625 {
626 forward.close();
627 reverse.close();
628 recMan.commit();
629 recMan.close();
630 }
631
632
633 /**
634 * @see Index#sync()
635 */
636 public synchronized void sync() throws IOException
637 {
638 recMan.commit();
639 }
640
641
642 /**
643 * TODO I don't think the keyCache is required anymore since the normalizer
644 * will cache values for us.
645 */
646 @SuppressWarnings("unchecked")
647 public K getNormalized( K attrVal ) throws Exception
648 {
649 if ( attrVal instanceof Long )
650 {
651 return attrVal;
652 }
653
654 K normalized = ( K ) keyCache.get( attrVal );
655
656 if ( null == normalized )
657 {
658 normalized = ( K ) attribute.getEquality().getNormalizer().normalize( attrVal );
659
660 // Double map it so if we use an already normalized
661 // value we can get back the same normalized value.
662 // and not have to regenerate a second time.
663 keyCache.put( attrVal, normalized );
664 keyCache.put( normalized, normalized );
665 }
666
667 return normalized;
668 }
669
670
671 /**
672 * @see Object#toString()
673 */
674 public String toString()
675 {
676 return "Index<" + attributeId +">";
677 }
678 }