001    /*
002     * CDDL HEADER START
003     *
004     * The contents of this file are subject to the terms of the
005     * Common Development and Distribution License, Version 1.0 only
006     * (the "License").  You may not use this file except in compliance
007     * with the License.
008     *
009     * You can obtain a copy of the license at
010     * trunk/opends/resource/legal-notices/OpenDS.LICENSE
011     * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
012     * See the License for the specific language governing permissions
013     * and limitations under the License.
014     *
015     * When distributing Covered Code, include this CDDL HEADER in each
016     * file and include the License file at
017     * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
018     * add the following below this CDDL HEADER, with the fields enclosed
019     * by brackets "[]" replaced with your own identifying information:
020     *      Portions Copyright [yyyy] [name of copyright owner]
021     *
022     * CDDL HEADER END
023     *
024     *
025     *      Copyright 2006-2008 Sun Microsystems, Inc.
026     */
027    package org.opends.server.backends.jeb;
028    
029    import static org.opends.server.loggers.debug.DebugLogger.*;
030    import org.opends.server.loggers.debug.DebugTracer;
031    import static org.opends.server.loggers.ErrorLogger.*;
032    
033    import com.sleepycat.je.*;
034    
035    import org.opends.server.types.*;
036    import org.opends.server.util.StaticUtils;
037    import org.opends.server.backends.jeb.importLDIF.IntegerImportIDSet;
038    import org.opends.server.backends.jeb.importLDIF.ImportIDSet;
039    import static org.opends.messages.JebMessages.*;
040    
041    import java.util.*;
042    
043    /**
044     * Represents an index implemented by a JE database in which each key maps to
045     * a set of entry IDs.  The key is a byte array, and is constructed from some
046     * normalized form of an attribute value (or fragment of a value) appearing
047     * in the entry.
048     */
049    public class Index extends DatabaseContainer
050    {
051      /**
052       * The tracer object for the debug logger.
053       */
054      private static final DebugTracer TRACER = getTracer();
055    
056      /**
057       * The indexer object to construct index keys from LDAP attribute values.
058       */
059      public Indexer indexer;
060    
061      /**
062       * The comparator for index keys.
063       */
064      private Comparator<byte[]> comparator;
065    
066      /**
067       * The limit on the number of entry IDs that may be indexed by one key.
068       */
069      private int indexEntryLimit;
070    
071      /**
072       * Limit on the number of entry IDs that may be retrieved by cursoring
073       * through an index.
074       */
075      private int cursorEntryLimit;
076    
077      /**
078       * Number of keys that have exceeded the entry limit since this
079       * object was created.
080       */
081      private int entryLimitExceededCount;
082    
083      /**
084       * The max number of tries to rewrite phantom records.
085       */
086      final int phantomWriteRetires = 3;
087    
088      /**
089       * Whether to maintain a count of IDs for a key once the entry limit
090       * has exceeded.
091       */
092      boolean maintainCount;
093    
094      private State state;
095    
096      /**
097       * A flag to indicate if this index should be trusted to be consistent
098       * with the entries database. If not trusted, we assume that existing
099       * entryIDSets for a key is still accurate. However, keys that do not
100       * exist are undefined instead of an empty entryIDSet. The following
101       * rules will be observed when the index is not trusted:
102       *
103       * - no entryIDs will be added to a non-existing key.
104       * - undefined entryIdSet will be returned whenever a key is not found.
105       */
106      private boolean trusted = false;
107    
108      /**
109       * A flag to indicate if a rebuild process is running on this index.
110       * During the rebuild process, we assume that no entryIDSets are
111       * accurate and return an undefined set on all read operations.
112       * However all write opeations will succeed. The rebuildRunning
113       * flag overrides all behaviours of the trusted flag.
114       */
115      private boolean rebuildRunning = false;
116    
117    
118      /**
119       * Create a new index object.
120       * @param name The name of the index database within the entryContainer.
121       * @param indexer The indexer object to construct index keys from LDAP
122       * attribute values.
123       * @param state The state database to persist index state info.
124       * @param indexEntryLimit The configured limit on the number of entry IDs
125       * that may be indexed by one key.
126       * @param cursorEntryLimit The configured limit on the number of entry IDs
127       * @param maintainCount Whether to maintain a count of IDs for a key once
128       * the entry limit has exceeded.
129       * @param env The JE Environemnt
130       * @param entryContainer The database entryContainer holding this index.
131       * @throws DatabaseException If an error occurs in the JE database.
132       */
133      public Index(String name, Indexer indexer, State state,
134            int indexEntryLimit, int cursorEntryLimit, boolean maintainCount,
135            Environment env, EntryContainer entryContainer)
136          throws DatabaseException
137      {
138        super(name, env, entryContainer);
139        this.indexer = indexer;
140        this.comparator = indexer.getComparator();
141        this.indexEntryLimit = indexEntryLimit;
142        this.cursorEntryLimit = cursorEntryLimit;
143        this.maintainCount = maintainCount;
144    
145        DatabaseConfig dbNodupsConfig = new DatabaseConfig();
146    
147        if(env.getConfig().getReadOnly())
148        {
149          dbNodupsConfig.setReadOnly(true);
150          dbNodupsConfig.setAllowCreate(false);
151          dbNodupsConfig.setTransactional(false);
152        }
153        else if(!env.getConfig().getTransactional())
154        {
155          dbNodupsConfig.setAllowCreate(true);
156          dbNodupsConfig.setTransactional(false);
157          dbNodupsConfig.setDeferredWrite(true);
158        }
159        else
160        {
161          dbNodupsConfig.setAllowCreate(true);
162          dbNodupsConfig.setTransactional(true);
163        }
164    
165        this.dbConfig = dbNodupsConfig;
166        this.dbConfig.setOverrideBtreeComparator(true);
167        this.dbConfig.setBtreeComparator(comparator.getClass());
168    
169        this.state = state;
170    
171        this.trusted = state.getIndexTrustState(null, this);
172        if(!trusted && entryContainer.getHighestEntryID().equals(new EntryID(0)))
173        {
174          // If there are no entries in the entry container then there
175          // is no reason why this index can't be upgraded to trusted.
176          setTrusted(null, true);
177        }
178    
179        // Issue warning if this index is not trusted
180        if(!trusted)
181        {
182          logError(NOTE_JEB_INDEX_ADD_REQUIRES_REBUILD.get(name));
183        }
184    
185      }
186    
187      /**
188       * Add an add entry ID operation into a index buffer.
189       *
190       * @param buffer The index buffer to insert the ID into.
191       * @param keyBytes         The index key bytes.
192       * @param entryID     The entry ID.
193       * @return True if the entry ID is inserted or ignored because the entry limit
194       *         count is exceeded. False if it already exists in the entry ID set
195       *         for the given key.
196       */
197      public boolean insertID(IndexBuffer buffer, byte[] keyBytes,
198                              EntryID entryID)
199      {
200        TreeMap<byte[], IndexBuffer.BufferedIndexValues> bufferedOperations =
201            buffer.getBufferedIndex(this);
202        IndexBuffer.BufferedIndexValues values = null;
203    
204        if(bufferedOperations == null)
205        {
206          bufferedOperations = new TreeMap<byte[],
207              IndexBuffer.BufferedIndexValues>(comparator);
208          buffer.putBufferedIndex(this, bufferedOperations);
209        }
210        else
211        {
212          values = bufferedOperations.get(keyBytes);
213        }
214    
215        if(values == null)
216        {
217          values = new IndexBuffer.BufferedIndexValues();
218          bufferedOperations.put(keyBytes, values);
219        }
220    
221        if(values.deletedIDs != null && values.deletedIDs.contains(entryID))
222        {
223          values.deletedIDs.remove(entryID);
224          return true;
225        }
226    
227        if(values.addedIDs == null)
228        {
229          values.addedIDs = new EntryIDSet(keyBytes, null);
230        }
231    
232        values.addedIDs.add(entryID);
233        return true;
234      }
235    
236      /**
237       * Insert an entry ID into the set of IDs indexed by a given key.
238       *
239       * @param txn A database transaction, or null if none is required.
240       * @param key         The index key.
241       * @param entryID     The entry ID.
242       * @return True if the entry ID is inserted or ignored because the entry limit
243       *         count is exceeded. False if it already exists in the entry ID set
244       *         for the given key.
245       * @throws DatabaseException If an error occurs in the JE database.
246       */
247      public boolean insertID(Transaction txn, DatabaseEntry key, EntryID entryID)
248           throws DatabaseException
249      {
250        OperationStatus status;
251        DatabaseEntry entryIDData = entryID.getDatabaseEntry();
252        DatabaseEntry data = new DatabaseEntry();
253        boolean success = false;
254    
255        if(maintainCount)
256        {
257          for(int i = 0; i < phantomWriteRetires; i++)
258          {
259            if(insertIDWithRMW(txn, key, data, entryIDData, entryID) ==
260                OperationStatus.SUCCESS)
261            {
262              return true;
263            }
264          }
265        }
266        else
267        {
268          status = read(txn, key, data, LockMode.READ_COMMITTED);
269          if(status == OperationStatus.SUCCESS)
270          {
271            EntryIDSet entryIDList =
272                new EntryIDSet(key.getData(), data.getData());
273    
274            if (entryIDList.isDefined())
275            {
276              for(int i = 0; i < phantomWriteRetires; i++)
277              {
278                if(insertIDWithRMW(txn, key, data, entryIDData, entryID) ==
279                    OperationStatus.SUCCESS)
280                {
281                  return true;
282                }
283              }
284            }
285          }
286          else
287          {
288            if(rebuildRunning || trusted)
289            {
290              status = insert(txn, key, entryIDData);
291              if(status == OperationStatus.KEYEXIST)
292              {
293                for(int i = 1; i < phantomWriteRetires; i++)
294                {
295                  if(insertIDWithRMW(txn, key, data, entryIDData, entryID) ==
296                      OperationStatus.SUCCESS)
297                  {
298                    return true;
299                  }
300                }
301              }
302            }
303            else
304            {
305              return true;
306            }
307          }
308        }
309    
310        return success;
311      }
312    
313    
314      /**
315       * Add the specified import ID set to the provided key. Used during
316       * substring buffer flushing.
317       *
318       * @param txn A transaction.
319       * @param key The key to add the set to.
320       * @param importIdSet The set of import IDs.
321       * @param data Database entry to reuse for read
322       * @throws DatabaseException If an database error occurs.
323       */
324      public void insert(Transaction txn, DatabaseEntry key,
325                         ImportIDSet importIdSet, DatabaseEntry data)
326      throws DatabaseException {
327    
328        OperationStatus status;
329          status = read(txn, key, data, LockMode.RMW);
330          if(status == OperationStatus.SUCCESS) {
331            ImportIDSet newImportIDSet = new IntegerImportIDSet();
332            if (newImportIDSet.merge(data.getData(), importIdSet,
333                                     indexEntryLimit, maintainCount)) {
334              entryLimitExceededCount++;
335            }
336            data.setData(newImportIDSet.toDatabase());
337          } else if(status == OperationStatus.NOTFOUND) {
338            if(!importIdSet.isDefined()) {
339              entryLimitExceededCount++;
340            }
341            data.setData(importIdSet.toDatabase());
342          } else {
343            //Should never happen during import.
344            throw new DatabaseException();
345          }
346          put(txn,key, data);
347      }
348    
349    
350      /**
351       * Add the specified import ID set to the provided keys in the keyset.
352       *
353       * @param txn  A transaction.
354       * @param importIDSet A import ID set to use.
355       * @param keySet  The set containing the keys.
356       * @param keyData A key database entry to use.
357       * @param data A database entry to use for data.
358       * @return <CODE>True</CODE> if the insert was successful.
359       * @throws DatabaseException If a database error occurs.
360       */
361      public synchronized
362      boolean insert(Transaction txn, ImportIDSet importIDSet, Set<byte[]> keySet,
363                     DatabaseEntry keyData, DatabaseEntry data)
364              throws DatabaseException {
365        for(byte[] key : keySet) {
366          keyData.setData(key);
367          insert(txn, keyData, importIDSet, data);
368        }
369        keyData.setData(null);
370        data.setData(null);
371        return true;
372      }
373    
374      private OperationStatus insertIDWithRMW(Transaction txn, DatabaseEntry key,
375                                              DatabaseEntry data,
376                                              DatabaseEntry entryIDData,
377                                              EntryID entryID)
378          throws DatabaseException
379      {
380        OperationStatus status;
381    
382        status = read(txn, key, data, LockMode.RMW);
383        if(status == OperationStatus.SUCCESS)
384        {
385          EntryIDSet entryIDList =
386              new EntryIDSet(key.getData(), data.getData());
387          if (entryIDList.isDefined() && indexEntryLimit > 0 &&
388              entryIDList.size() >= indexEntryLimit)
389          {
390            if(maintainCount)
391            {
392              entryIDList = new EntryIDSet(entryIDList.size());
393            }
394            else
395            {
396              entryIDList = new EntryIDSet();
397            }
398            entryLimitExceededCount++;
399    
400            if(debugEnabled())
401            {
402              StringBuilder builder = new StringBuilder();
403              StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
404              TRACER.debugInfo("Index entry exceeded in index %s. " +
405                  "Limit: %d. ID list size: %d.\nKey:",
406                  name, indexEntryLimit, entryIDList.size(),
407                  builder);
408    
409            }
410          }
411    
412          entryIDList.add(entryID);
413    
414          byte[] after = entryIDList.toDatabase();
415          data.setData(after);
416          return put(txn, key, data);
417        }
418        else
419        {
420          if(rebuildRunning || trusted)
421          {
422            return insert(txn, key, entryIDData);
423          }
424          else
425          {
426            return OperationStatus.SUCCESS;
427          }
428        }
429      }
430    
431      /**
432       * Update the set of entry IDs for a given key.
433       *
434       * @param txn A database transaction, or null if none is required.
435       * @param key The database key.
436       * @param deletedIDs The IDs to remove for the key.
437       * @param addedIDs the IDs to add for the key.
438       * @throws DatabaseException If a database error occurs.
439       */
440      void updateKey(Transaction txn, DatabaseEntry key,
441                     EntryIDSet deletedIDs, EntryIDSet addedIDs)
442          throws DatabaseException
443      {
444        OperationStatus status;
445        DatabaseEntry data = new DatabaseEntry();
446    
447        // Handle cases where nothing is changed early to avoid
448        // DB access.
449        if(deletedIDs != null && deletedIDs.size() == 0 &&
450            (addedIDs == null || addedIDs.size() == 0))
451        {
452          return;
453        }
454    
455        if(addedIDs != null && addedIDs.size() == 0 &&
456            (deletedIDs == null || deletedIDs.size() == 0))
457        {
458          return;
459        }
460    
461    
462        if(deletedIDs == null && addedIDs == null)
463        {
464          status = delete(txn, key);
465    
466          if(status != OperationStatus.SUCCESS)
467          {
468            if(debugEnabled())
469            {
470              StringBuilder builder = new StringBuilder();
471              StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
472              TRACER.debugError("The expected key does not exist in the " +
473                  "index %s.\nKey:%s", name, builder.toString());
474            }
475          }
476    
477          return;
478        }
479    
480        if(maintainCount)
481        {
482          for(int i = 0; i < phantomWriteRetires; i++)
483          {
484            if(updateKeyWithRMW(txn, key, data, deletedIDs, addedIDs) ==
485                OperationStatus.SUCCESS)
486            {
487              return;
488            }
489          }
490        }
491        else
492        {
493          status = read(txn, key, data, LockMode.READ_COMMITTED);
494          if(status == OperationStatus.SUCCESS)
495          {
496            EntryIDSet entryIDList =
497                new EntryIDSet(key.getData(), data.getData());
498    
499            if (entryIDList.isDefined())
500            {
501              for(int i = 0; i < phantomWriteRetires; i++)
502              {
503                if(updateKeyWithRMW(txn, key, data, deletedIDs, addedIDs) ==
504                    OperationStatus.SUCCESS)
505                {
506                  return;
507                }
508              }
509            }
510          }
511          else
512          {
513            if(rebuildRunning || trusted)
514            {
515              if(deletedIDs != null)
516              {
517                if(debugEnabled())
518                {
519                  StringBuilder builder = new StringBuilder();
520                  StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
521                  TRACER.debugError("The expected key does not exist in the " +
522                      "index %s.\nKey:%s", name, builder.toString());
523                }
524              }
525              data.setData(addedIDs.toDatabase());
526    
527              status = insert(txn, key, data);
528              if(status == OperationStatus.KEYEXIST)
529              {
530                for(int i = 1; i < phantomWriteRetires; i++)
531                {
532                  if(updateKeyWithRMW(txn, key, data, deletedIDs, addedIDs) ==
533                        OperationStatus.SUCCESS)
534                  {
535                    return;
536                  }
537                }
538              }
539            }
540          }
541        }
542      }
543    
544      private OperationStatus updateKeyWithRMW(Transaction txn,
545                                               DatabaseEntry key,
546                                               DatabaseEntry data,
547                                               EntryIDSet deletedIDs,
548                                               EntryIDSet addedIDs)
549          throws DatabaseException
550      {
551        OperationStatus status;
552    
553        status = read(txn, key, data, LockMode.RMW);
554        if(status == OperationStatus.SUCCESS)
555        {
556          EntryIDSet entryIDList =
557              new EntryIDSet(key.getData(), data.getData());
558    
559          if(addedIDs != null)
560          {
561            if(entryIDList.isDefined() && indexEntryLimit > 0)
562            {
563              long idCountDelta = addedIDs.size();
564              if(deletedIDs != null)
565              {
566                idCountDelta -= deletedIDs.size();
567              }
568              if(idCountDelta + entryIDList.size() >= indexEntryLimit)
569              {
570                if(maintainCount)
571                {
572                  entryIDList = new EntryIDSet(entryIDList.size() + idCountDelta);
573                }
574                else
575                {
576                  entryIDList = new EntryIDSet();
577                }
578                entryLimitExceededCount++;
579    
580                if(debugEnabled())
581                {
582                  StringBuilder builder = new StringBuilder();
583                  StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
584                  TRACER.debugInfo("Index entry exceeded in index %s. " +
585                      "Limit: %d. ID list size: %d.\nKey:",
586                      name, indexEntryLimit, idCountDelta + addedIDs.size(),
587                      builder);
588    
589                }
590              }
591              else
592              {
593                entryIDList.addAll(addedIDs);
594                if(deletedIDs != null)
595                {
596                  entryIDList.deleteAll(deletedIDs);
597                }
598              }
599            }
600            else
601            {
602              entryIDList.addAll(addedIDs);
603              if(deletedIDs != null)
604              {
605                entryIDList.deleteAll(deletedIDs);
606              }
607            }
608          }
609          else if(deletedIDs != null)
610          {
611            entryIDList.deleteAll(deletedIDs);
612          }
613    
614          byte[] after = entryIDList.toDatabase();
615          if (after == null)
616          {
617            // No more IDs, so remove the key. If index is not
618            // trusted then this will cause all subsequent reads
619            // for this key to return undefined set.
620            return delete(txn, key);
621          }
622          else
623          {
624            data.setData(after);
625            return put(txn, key, data);
626          }
627        }
628        else
629        {
630          if(rebuildRunning || trusted)
631          {
632            if(deletedIDs != null)
633            {
634              if(debugEnabled())
635              {
636                StringBuilder builder = new StringBuilder();
637                StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
638                TRACER.debugError("The expected key does not exist in the " +
639                    "index %s.\nKey:%s", name, builder.toString());
640              }
641            }
642            data.setData(addedIDs.toDatabase());
643            return insert(txn, key, data);
644          }
645          else
646          {
647            return OperationStatus.SUCCESS;
648          }
649        }
650      }
651    
652      /**
653       * Add an remove entry ID operation into a index buffer.
654       *
655       * @param buffer The index buffer to insert the ID into.
656       * @param keyBytes    The index key bytes.
657       * @param entryID     The entry ID.
658       * @return True if the entry ID is inserted or ignored because the entry limit
659       *         count is exceeded. False if it already exists in the entry ID set
660       *         for the given key.
661       */
662      public boolean removeID(IndexBuffer buffer, byte[] keyBytes,
663                              EntryID entryID)
664      {
665        TreeMap<byte[], IndexBuffer.BufferedIndexValues> bufferedOperations =
666            buffer.getBufferedIndex(this);
667        IndexBuffer.BufferedIndexValues values = null;
668    
669        if(bufferedOperations == null)
670        {
671          bufferedOperations = new TreeMap<byte[],
672              IndexBuffer.BufferedIndexValues>(comparator);
673          buffer.putBufferedIndex(this, bufferedOperations);
674        }
675        else
676        {
677          values = bufferedOperations.get(keyBytes);
678        }
679    
680        if(values == null)
681        {
682          values = new IndexBuffer.BufferedIndexValues();
683          bufferedOperations.put(keyBytes, values);
684        }
685    
686        if(values.addedIDs != null && values.addedIDs.contains(entryID))
687        {
688          values.addedIDs.remove(entryID);
689          return true;
690        }
691    
692        if(values.deletedIDs == null)
693        {
694          values.deletedIDs = new EntryIDSet(keyBytes, null);
695        }
696    
697        values.deletedIDs.add(entryID);
698        return true;
699      }
700    
701      /**
702       * Remove an entry ID from the set of IDs indexed by a given key.
703       *
704       * @param txn A database transaction, or null if none is required.
705       * @param key         The index key.
706       * @param entryID     The entry ID.
707       * @throws DatabaseException If an error occurs in the JE database.
708       */
709      public void removeID(Transaction txn, DatabaseEntry key, EntryID entryID)
710          throws DatabaseException
711      {
712        OperationStatus status;
713        DatabaseEntry data = new DatabaseEntry();
714    
715        if(maintainCount)
716        {
717          removeIDWithRMW(txn, key, data, entryID);
718        }
719        else
720        {
721          status = read(txn, key, data, LockMode.READ_COMMITTED);
722          if(status == OperationStatus.SUCCESS)
723          {
724            EntryIDSet entryIDList = new EntryIDSet(key.getData(), data.getData());
725            if(entryIDList.isDefined())
726            {
727              removeIDWithRMW(txn, key, data, entryID);
728            }
729          }
730          else
731          {
732            // Ignore failures if rebuild is running since a empty entryIDset
733            // will probably not be rebuilt.
734            if(trusted && !rebuildRunning)
735            {
736              setTrusted(txn, false);
737    
738              if(debugEnabled())
739              {
740                StringBuilder builder = new StringBuilder();
741                StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
742                TRACER.debugError("The expected key does not exist in the " +
743                    "index %s.\nKey:%s", name, builder.toString());
744              }
745    
746              logError(ERR_JEB_INDEX_CORRUPT_REQUIRES_REBUILD.get(name));
747            }
748          }
749        }
750      }
751    
752      /**
753       * Delete specified entry ID from all keys in the provided key set.
754       *
755       * @param txn  A Transaction.
756       * @param keySet A set of keys.
757       * @param entryID The entry ID to delete.
758       * @throws DatabaseException If a database error occurs.
759       */
760      public synchronized
761      void delete(Transaction txn, Set<byte[]> keySet, EntryID entryID)
762      throws DatabaseException {
763        setTrusted(txn, false);
764        for(byte[] key : keySet) {
765           removeIDWithRMW(txn, new DatabaseEntry(key),
766                           new DatabaseEntry(), entryID);
767        }
768        setTrusted(txn, true);
769      }
770    
771      private void removeIDWithRMW(Transaction txn, DatabaseEntry key,
772                                   DatabaseEntry data, EntryID entryID)
773          throws DatabaseException
774      {
775        OperationStatus status;
776        status = read(txn, key, data, LockMode.RMW);
777    
778        if (status == OperationStatus.SUCCESS)
779        {
780          EntryIDSet entryIDList = new EntryIDSet(key.getData(), data.getData());
781          // Ignore failures if rebuild is running since the entry ID is
782          // probably already removed.
783          if (!entryIDList.remove(entryID) && !rebuildRunning)
784          {
785            if(trusted)
786            {
787              setTrusted(txn, false);
788    
789              if(debugEnabled())
790              {
791                StringBuilder builder = new StringBuilder();
792                StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
793                TRACER.debugError("The expected entry ID does not exist in " +
794                    "the entry ID list for index %s.\nKey:%s",
795                    name, builder.toString());
796              }
797    
798              logError(ERR_JEB_INDEX_CORRUPT_REQUIRES_REBUILD.get(name));
799            }
800          }
801          else
802          {
803            byte[] after = entryIDList.toDatabase();
804            if (after == null)
805            {
806              // No more IDs, so remove the key. If index is not
807              // trusted then this will cause all subsequent reads
808              // for this key to return undefined set.
809              delete(txn, key);
810            }
811            else
812            {
813              data.setData(after);
814              put(txn, key, data);
815            }
816          }
817        }
818        else
819        {
820          // Ignore failures if rebuild is running since a empty entryIDset
821          // will probably not be rebuilt.
822          if(trusted && !rebuildRunning)
823          {
824            setTrusted(txn, false);
825    
826            if(debugEnabled())
827            {
828              StringBuilder builder = new StringBuilder();
829              StaticUtils.byteArrayToHexPlusAscii(builder, key.getData(), 4);
830              TRACER.debugError("The expected key does not exist in the " +
831                  "index %s.\nKey:%s", name, builder.toString());
832            }
833    
834            logError(ERR_JEB_INDEX_CORRUPT_REQUIRES_REBUILD.get(name));
835          }
836        }
837      }
838    
839      /**
840       * Buffered delete of a key from the JE database.
841       * @param buffer The index buffer to use to store the deleted keys
842       * @param keyBytes The index key bytes.
843       */
844      public void delete(IndexBuffer buffer, byte[] keyBytes)
845      {
846        TreeMap<byte[], IndexBuffer.BufferedIndexValues> bufferedOperations =
847            buffer.getBufferedIndex(this);
848        IndexBuffer.BufferedIndexValues values = null;
849    
850        if(bufferedOperations == null)
851        {
852          bufferedOperations = new TreeMap<byte[],
853              IndexBuffer.BufferedIndexValues>(comparator);
854          buffer.putBufferedIndex(this, bufferedOperations);
855        }
856        else
857        {
858          values = bufferedOperations.get(keyBytes);
859        }
860    
861        if(values == null)
862        {
863          values = new IndexBuffer.BufferedIndexValues();
864          bufferedOperations.put(keyBytes, values);
865        }
866      }
867    
868      /**
869       * Check if an entry ID is in the set of IDs indexed by a given key.
870       *
871       * @param txn A database transaction, or null if none is required.
872       * @param key         The index key.
873       * @param entryID     The entry ID.
874       * @return true if the entry ID is indexed by the given key,
875       *         false if it is not indexed by the given key,
876       *         undefined if the key has exceeded the entry limit.
877       * @throws DatabaseException If an error occurs in the JE database.
878       */
879      public ConditionResult containsID(Transaction txn, DatabaseEntry key,
880                                        EntryID entryID)
881           throws DatabaseException
882      {
883        if(rebuildRunning)
884        {
885          return ConditionResult.UNDEFINED;
886        }
887    
888        OperationStatus status;
889        LockMode lockMode = LockMode.DEFAULT;
890        DatabaseEntry data = new DatabaseEntry();
891    
892        status = read(txn, key, data, lockMode);
893        if (status == OperationStatus.SUCCESS)
894        {
895          EntryIDSet entryIDList =
896               new EntryIDSet(key.getData(), data.getData());
897    
898          if (!entryIDList.isDefined())
899          {
900            return ConditionResult.UNDEFINED;
901          }
902          else if (entryIDList.contains(entryID))
903          {
904            return ConditionResult.TRUE;
905          }
906          else
907          {
908            return ConditionResult.FALSE;
909          }
910        }
911        else
912        {
913          if(trusted)
914          {
915            return ConditionResult.FALSE;
916          }
917          else
918          {
919            return ConditionResult.UNDEFINED;
920          }
921        }
922      }
923    
924      /**
925       * Reads the set of entry IDs for a given key.
926       *
927       * @param key The database key.
928       * @param txn A database transaction, or null if none is required.
929       * @param lockMode The JE locking mode to be used for the database read.
930       * @return The entry IDs indexed by this key.
931       */
932      public EntryIDSet readKey(DatabaseEntry key, Transaction txn,
933                                LockMode lockMode)
934      {
935        if(rebuildRunning)
936        {
937          return new EntryIDSet();
938        }
939    
940        try
941        {
942          OperationStatus status;
943          DatabaseEntry data = new DatabaseEntry();
944          status = read( txn, key, data, lockMode);
945          if (status != OperationStatus.SUCCESS)
946          {
947            if(trusted)
948            {
949              return new EntryIDSet(key.getData(), null);
950            }
951            else
952            {
953              return new EntryIDSet();
954            }
955          }
956          return new EntryIDSet(key.getData(), data.getData());
957        }
958        catch (DatabaseException e)
959        {
960          if (debugEnabled())
961          {
962            TRACER.debugCaught(DebugLogLevel.ERROR, e);
963          }
964          return new EntryIDSet();
965        }
966      }
967    
968      /**
969       * Writes the set of entry IDs for a given key.
970       *
971       * @param key The database key.
972       * @param entryIDList The entry IDs indexed by this key.
973       * @param txn A database transaction, or null if none is required.
974       * @throws DatabaseException If an error occurs in the JE database.
975       */
976      public void writeKey(Transaction txn, DatabaseEntry key,
977                           EntryIDSet entryIDList)
978           throws DatabaseException
979      {
980        DatabaseEntry data = new DatabaseEntry();
981        byte[] after = entryIDList.toDatabase();
982        if (after == null)
983        {
984          // No more IDs, so remove the key.
985          delete(txn, key);
986        }
987        else
988        {
989          if (!entryIDList.isDefined())
990          {
991            entryLimitExceededCount++;
992          }
993          data.setData(after);
994          put(txn, key, data);
995        }
996      }
997    
998      /**
999       * Reads a range of keys and collects all their entry IDs into a
1000       * single set.
1001       *
1002       * @param lower The lower bound of the range. A 0 length byte array indicates
1003       *                      no lower bound and the range will start from the
1004       *                      smallest key.
1005       * @param upper The upper bound of the range. A 0 length byte array indicates
1006       *                      no upper bound and the range will end at the largest
1007       *                      key.
1008       * @param lowerIncluded true if a key exactly matching the lower bound
1009       *                      is included in the range, false if only keys
1010       *                      strictly greater than the lower bound are included.
1011       *                      This value is ignored if the lower bound is not
1012       *                      specified.
1013       * @param upperIncluded true if a key exactly matching the upper bound
1014       *                      is included in the range, false if only keys
1015       *                      strictly less than the upper bound are included.
1016       *                      This value is ignored if the upper bound is not
1017       *                      specified.
1018       * @return The set of entry IDs.
1019       */
1020      public EntryIDSet readRange(byte[] lower, byte[] upper,
1021                                   boolean lowerIncluded, boolean upperIncluded)
1022      {
1023        LockMode lockMode = LockMode.DEFAULT;
1024    
1025        // If this index is not trusted, then just return an undefined
1026        // id set.
1027        if(rebuildRunning || !trusted)
1028        {
1029          return new EntryIDSet();
1030        }
1031    
1032        try
1033        {
1034          // Total number of IDs found so far.
1035          int totalIDCount = 0;
1036    
1037          DatabaseEntry data = new DatabaseEntry();
1038          DatabaseEntry key;
1039    
1040          ArrayList<EntryIDSet> lists = new ArrayList<EntryIDSet>();
1041    
1042          OperationStatus status;
1043          Cursor cursor;
1044    
1045          cursor = openCursor(null, CursorConfig.READ_COMMITTED);
1046    
1047          try
1048          {
1049            // Set the lower bound if necessary.
1050            if(lower.length > 0)
1051            {
1052              key = new DatabaseEntry(lower);
1053    
1054              // Initialize the cursor to the lower bound.
1055              status = cursor.getSearchKeyRange(key, data, lockMode);
1056    
1057              // Advance past the lower bound if necessary.
1058              if (status == OperationStatus.SUCCESS && !lowerIncluded &&
1059                   comparator.compare(key.getData(), lower) == 0)
1060              {
1061                // Do not include the lower value.
1062                status = cursor.getNext(key, data, lockMode);
1063              }
1064            }
1065            else
1066            {
1067              key = new DatabaseEntry();
1068              status = cursor.getNext(key, data, lockMode);
1069            }
1070    
1071            if (status != OperationStatus.SUCCESS)
1072            {
1073              // There are no values.
1074              return new EntryIDSet(key.getData(), null);
1075            }
1076    
1077            // Step through the keys until we hit the upper bound or the last key.
1078            while (status == OperationStatus.SUCCESS)
1079            {
1080              // Check against the upper bound if necessary
1081              if(upper.length > 0)
1082              {
1083                int cmp = comparator.compare(key.getData(), upper);
1084                if ((cmp > 0) || (cmp == 0 && !upperIncluded))
1085                {
1086                  break;
1087                }
1088              }
1089              EntryIDSet list = new EntryIDSet(key.getData(), data.getData());
1090              if (!list.isDefined())
1091              {
1092                // There is no point continuing.
1093                return list;
1094              }
1095              totalIDCount += list.size();
1096              if (cursorEntryLimit > 0 && totalIDCount > cursorEntryLimit)
1097              {
1098                // There are too many. Give up and return an undefined list.
1099                return new EntryIDSet();
1100              }
1101              lists.add(list);
1102              status = cursor.getNext(key, data, LockMode.DEFAULT);
1103            }
1104    
1105            return EntryIDSet.unionOfSets(lists, false);
1106          }
1107          finally
1108          {
1109            cursor.close();
1110          }
1111        }
1112        catch (DatabaseException e)
1113        {
1114          if (debugEnabled())
1115          {
1116            TRACER.debugCaught(DebugLogLevel.ERROR, e);
1117          }
1118          return new EntryIDSet();
1119        }
1120      }
1121    
1122      /**
1123       * Get the number of keys that have exceeded the entry limit since this
1124       * object was created.
1125       * @return The number of keys that have exceeded the entry limit since this
1126       * object was created.
1127       */
1128      public int getEntryLimitExceededCount()
1129      {
1130        return entryLimitExceededCount;
1131      }
1132    
1133      /**
1134       * Increment the count of the number of keys that have exceeded the entry
1135       * limit since this object was created.
1136       */
1137      public void incEntryLimitExceededCount()
1138      {
1139        entryLimitExceededCount++;
1140      }
1141    
1142      /**
1143       * Update the index buffer for a deleted entry.
1144       *
1145       * @param buffer The index buffer to use to store the deleted keys
1146       * @param entryID     The entry ID.
1147       * @param entry       The entry to be indexed.
1148       * @return True if all the indexType keys for the entry are added. False if
1149       *         the entry ID already exists for some keys.
1150       * @throws DatabaseException If an error occurs in the JE database.
1151       * @throws DirectoryException If a Directory Server error occurs.
1152       */
1153      public boolean addEntry(IndexBuffer buffer, EntryID entryID, Entry entry)
1154           throws DatabaseException, DirectoryException
1155      {
1156        HashSet<byte[]> addKeys = new HashSet<byte[]>();
1157        boolean success = true;
1158    
1159        indexer.indexEntry(entry, addKeys);
1160    
1161        for (byte[] keyBytes : addKeys)
1162        {
1163          if(!insertID(buffer, keyBytes, entryID))
1164          {
1165            success = false;
1166          }
1167        }
1168    
1169        return success;
1170      }
1171    
1172      /**
1173       * Update the index for a new entry.
1174       *
1175       * @param txn A database transaction, or null if none is required.
1176       * @param entryID     The entry ID.
1177       * @param entry       The entry to be indexed.
1178       * @return True if all the indexType keys for the entry are added. False if
1179       *         the entry ID already exists for some keys.
1180       * @throws DatabaseException If an error occurs in the JE database.
1181       * @throws DirectoryException If a Directory Server error occurs.
1182       */
1183      public boolean addEntry(Transaction txn, EntryID entryID, Entry entry)
1184           throws DatabaseException, DirectoryException
1185      {
1186        TreeSet<byte[]> addKeys = new TreeSet<byte[]>(indexer.getComparator());
1187        boolean success = true;
1188    
1189        indexer.indexEntry(entry, addKeys);
1190    
1191        DatabaseEntry key = new DatabaseEntry();
1192        for (byte[] keyBytes : addKeys)
1193        {
1194          key.setData(keyBytes);
1195          if(!insertID(txn, key, entryID))
1196          {
1197            success = false;
1198          }
1199        }
1200    
1201        return success;
1202      }
1203    
1204      /**
1205       * Update the index buffer for a deleted entry.
1206       *
1207       * @param buffer The index buffer to use to store the deleted keys
1208       * @param entryID     The entry ID
1209       * @param entry       The contents of the deleted entry.
1210       * @throws DatabaseException If an error occurs in the JE database.
1211       * @throws DirectoryException If a Directory Server error occurs.
1212       */
1213      public void removeEntry(IndexBuffer buffer, EntryID entryID, Entry entry)
1214           throws DatabaseException, DirectoryException
1215      {
1216        HashSet<byte[]> delKeys = new HashSet<byte[]>();
1217    
1218        indexer.indexEntry(entry, delKeys);
1219    
1220        for (byte[] keyBytes : delKeys)
1221        {
1222          removeID(buffer, keyBytes, entryID);
1223        }
1224      }
1225    
1226      /**
1227       * Update the index for a deleted entry.
1228       *
1229       * @param txn A database transaction, or null if none is required.
1230       * @param entryID     The entry ID
1231       * @param entry       The contents of the deleted entry.
1232       * @throws DatabaseException If an error occurs in the JE database.
1233       * @throws DirectoryException If a Directory Server error occurs.
1234       */
1235      public void removeEntry(Transaction txn, EntryID entryID, Entry entry)
1236           throws DatabaseException, DirectoryException
1237      {
1238        TreeSet<byte[]> delKeys = new TreeSet<byte[]>(indexer.getComparator());
1239    
1240        indexer.indexEntry(entry, delKeys);
1241    
1242        DatabaseEntry key = new DatabaseEntry();
1243        for (byte[] keyBytes : delKeys)
1244        {
1245          key.setData(keyBytes);
1246          removeID(txn, key, entryID);
1247        }
1248      }
1249    
1250    
1251      /**
1252       * Update the index to reflect a sequence of modifications in a Modify
1253       * operation.
1254       *
1255       * @param txn A database transaction, or null if none is required.
1256       * @param entryID The ID of the entry that was modified.
1257       * @param oldEntry The entry before the modifications were applied.
1258       * @param newEntry The entry after the modifications were applied.
1259       * @param mods The sequence of modifications in the Modify operation.
1260       * @throws DatabaseException If an error occurs in the JE database.
1261       */
1262      public void modifyEntry(Transaction txn,
1263                              EntryID entryID,
1264                              Entry oldEntry,
1265                              Entry newEntry,
1266                              List<Modification> mods)
1267           throws DatabaseException
1268      {
1269        TreeMap<byte[], Boolean> modifiedKeys =
1270            new TreeMap<byte[], Boolean>(indexer.getComparator());
1271    
1272        indexer.modifyEntry(oldEntry, newEntry, mods, modifiedKeys);
1273    
1274        DatabaseEntry key = new DatabaseEntry();
1275        for (Map.Entry<byte[], Boolean> modifiedKey : modifiedKeys.entrySet())
1276        {
1277          key.setData(modifiedKey.getKey());
1278          if(modifiedKey.getValue())
1279          {
1280            insertID(txn, key, entryID);
1281          }
1282          else
1283          {
1284            removeID(txn, key, entryID);
1285          }
1286        }
1287      }
1288    
1289      /**
1290       * Update the index to reflect a sequence of modifications in a Modify
1291       * operation.
1292       *
1293       * @param buffer The index buffer to use to store the deleted keys
1294       * @param entryID The ID of the entry that was modified.
1295       * @param oldEntry The entry before the modifications were applied.
1296       * @param newEntry The entry after the modifications were applied.
1297       * @param mods The sequence of modifications in the Modify operation.
1298       * @throws DatabaseException If an error occurs in the JE database.
1299       */
1300      public void modifyEntry(IndexBuffer buffer,
1301                              EntryID entryID,
1302                              Entry oldEntry,
1303                              Entry newEntry,
1304                              List<Modification> mods)
1305          throws DatabaseException
1306      {
1307        HashMap<byte[], Boolean> modifiedKeys = new HashMap<byte[], Boolean>();
1308    
1309        indexer.modifyEntry(oldEntry, newEntry, mods, modifiedKeys);
1310        for (Map.Entry<byte[], Boolean> modifiedKey : modifiedKeys.entrySet())
1311        {
1312          if(modifiedKey.getValue())
1313          {
1314            insertID(buffer, modifiedKey.getKey(), entryID);
1315          }
1316          else
1317          {
1318            removeID(buffer, modifiedKey.getKey(), entryID);
1319          }
1320        }
1321      }
1322    
1323      /**
1324       * Set the index entry limit.
1325       *
1326       * @param indexEntryLimit The index entry limit to set.
1327       * @return True if a rebuild is required or false otherwise.
1328       */
1329      public boolean setIndexEntryLimit(int indexEntryLimit)
1330      {
1331        boolean rebuildRequired = false;
1332        if(this.indexEntryLimit < indexEntryLimit &&
1333            entryLimitExceededCount > 0 )
1334        {
1335          rebuildRequired = true;
1336        }
1337        this.indexEntryLimit = indexEntryLimit;
1338    
1339        return rebuildRequired;
1340      }
1341    
1342      /**
1343       * Set the indexer.
1344       *
1345       * @param indexer The indexer to set
1346       */
1347      public void setIndexer(Indexer indexer)
1348      {
1349        this.indexer = indexer;
1350      }
1351    
1352      /**
1353       * Return entry limit.
1354       *
1355       * @return The entry limit.
1356       */
1357      public int getIndexEntryLimit() {
1358        return this.indexEntryLimit;
1359      }
1360    
1361      /**
1362       * Set the index trust state.
1363       * @param txn A database transaction, or null if none is required.
1364       * @param trusted True if this index should be trusted or false
1365       *                otherwise.
1366       * @throws DatabaseException If an error occurs in the JE database.
1367       */
1368      public synchronized void setTrusted(Transaction txn, boolean trusted)
1369          throws DatabaseException
1370      {
1371        this.trusted = trusted;
1372        state.putIndexTrustState(txn, this, trusted);
1373      }
1374    
1375      /**
1376       * Return true iff this index is trusted.
1377       * @return the trusted state of this index
1378       */
1379      public synchronized boolean isTrusted()
1380      {
1381        return trusted;
1382      }
1383    
1384      /**
1385       * Set the rebuild status of this index.
1386       * @param rebuildRunning True if a rebuild process on this index
1387       *                       is running or False otherwise.
1388       */
1389      public synchronized void setRebuildStatus(boolean rebuildRunning)
1390      {
1391        this.rebuildRunning = rebuildRunning;
1392      }
1393    
1394      /**
1395       * Whether this index maintains a count of IDs for keys once the
1396       * entry limit has exceeded.
1397       * @return <code>true</code> if this index maintains court of IDs
1398       * or <code>false</code> otherwise
1399       */
1400      public boolean getMaintainCount()
1401      {
1402        return maintainCount;
1403      }
1404    }