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    import org.opends.messages.Message;
029    
030    import com.sleepycat.je.*;
031    import org.opends.server.loggers.debug.DebugTracer;
032    import static org.opends.server.loggers.debug.DebugLogger.getTracer;
033    import static org.opends.server.loggers.ErrorLogger.*;
034    import org.opends.server.types.*;
035    import org.opends.server.admin.std.server.LocalDBVLVIndexCfg;
036    import org.opends.server.admin.server.ConfigurationChangeListener;
037    import org.opends.server.core.DirectoryServer;
038    import org.opends.server.core.SearchOperation;
039    import static org.opends.messages.JebMessages.
040        NOTE_JEB_INDEX_ADD_REQUIRES_REBUILD;
041    import static org.opends.messages.JebMessages.
042        ERR_ENTRYIDSORTER_NEGATIVE_START_POS;
043    import static org.opends.messages.JebMessages.
044        ERR_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
045    import static org.opends.messages.JebMessages.
046        ERR_JEB_CONFIG_VLV_INDEX_BAD_FILTER;
047    
048    
049    import static org.opends.server.loggers.debug.DebugLogger.*;
050    import org.opends.server.util.StaticUtils;
051    import static org.opends.server.util.StaticUtils.stackTraceToSingleLineString;
052    import org.opends.server.api.OrderingMatchingRule;
053    import org.opends.server.config.ConfigException;
054    import org.opends.server.protocols.asn1.ASN1Element;
055    import org.opends.server.protocols.asn1.ASN1OctetString;
056    import org.opends.server.protocols.ldap.LDAPResultCode;
057    import org.opends.server.controls.VLVRequestControl;
058    import org.opends.server.controls.VLVResponseControl;
059    import org.opends.server.controls.ServerSideSortRequestControl;
060    
061    import java.util.*;
062    import java.util.concurrent.atomic.AtomicInteger;
063    
064    /**
065     * This class represents a VLV index. Each database record is a sorted list
066     * of entry IDs followed by sets of attribute values used to sort the entries.
067     * The entire set of entry IDs are broken up into sorted subsets to decrease
068     * the number of database retrivals needed for a range lookup. The records are
069     * keyed by the last entry's first sort attribute value. The list of entries
070     * in a particular database record maintains the property where the first sort
071     * attribute value is bigger then the previous key but smaller or equal
072     * to its own key.
073     */
074    public class VLVIndex extends DatabaseContainer
075        implements ConfigurationChangeListener<LocalDBVLVIndexCfg>
076    {
077      /**
078       * The tracer object for the debug logger.
079       */
080      private static final DebugTracer TRACER = getTracer();
081    
082      /**
083       * The comparator for vlvIndex keys.
084       */
085      public VLVKeyComparator comparator;
086    
087      /**
088       * The limit on the number of entry IDs that may be indexed by one key.
089       */
090      private int sortedSetCapacity = 4000;
091    
092      /**
093       * The cached count of entries in this index.
094       */
095      private AtomicInteger count;
096    
097      private State state;
098    
099      /**
100       * A flag to indicate if this vlvIndex should be trusted to be consistent
101       * with the entries database.
102       */
103      private boolean trusted = false;
104    
105      /**
106       * A flag to indicate if a rebuild process is running on this vlvIndex.
107       */
108      private boolean rebuildRunning = false;
109    
110      /**
111       * The VLV vlvIndex configuration.
112       */
113      private LocalDBVLVIndexCfg config;
114    
115      private ID2Entry id2entry;
116    
117      private DN baseDN;
118    
119      private SearchFilter filter;
120    
121      private SearchScope scope;
122    
123      /**
124       * The SortOrder in use by this VLV index to sort the entries.
125       */
126      public SortOrder sortOrder;
127    
128    
129      /**
130       * Create a new VLV vlvIndex object.
131       *
132       * @param config           The VLV index config object to use for this VLV
133       *                         index.
134       * @param state            The state database to persist vlvIndex state info.
135       * @param env              The JE Environemnt
136       * @param entryContainer   The database entryContainer holding this vlvIndex.
137       * @throws com.sleepycat.je.DatabaseException
138       *          If an error occurs in the JE database.
139       * @throws ConfigException if a error occurs while reading the VLV index
140       * configuration
141       */
142      public VLVIndex(LocalDBVLVIndexCfg config, State state, Environment env,
143                      EntryContainer entryContainer)
144          throws DatabaseException, ConfigException
145      {
146        super(entryContainer.getDatabasePrefix()+"_vlv."+config.getName(),
147              env, entryContainer);
148    
149        this.config = config;
150        this.baseDN = config.getBaseDN();
151        this.scope = SearchScope.valueOf(config.getScope().name());
152        this.sortedSetCapacity = config.getMaxBlockSize();
153        this.id2entry = entryContainer.getID2Entry();
154    
155        try
156        {
157          this.filter =
158              SearchFilter.createFilterFromString(config.getFilter());
159        }
160        catch(Exception e)
161        {
162          Message msg = ERR_JEB_CONFIG_VLV_INDEX_BAD_FILTER.get(
163              config.getFilter(), name, stackTraceToSingleLineString(e));
164          throw new ConfigException(msg);
165        }
166    
167        String[] sortAttrs = config.getSortOrder().split(" ");
168        SortKey[] sortKeys = new SortKey[sortAttrs.length];
169        OrderingMatchingRule[] orderingRules =
170            new OrderingMatchingRule[sortAttrs.length];
171        boolean[] ascending = new boolean[sortAttrs.length];
172        for(int i = 0; i < sortAttrs.length; i++)
173        {
174          try
175          {
176            if(sortAttrs[i].startsWith("-"))
177            {
178              ascending[i] = false;
179              sortAttrs[i] = sortAttrs[i].substring(1);
180            }
181            else
182            {
183              ascending[i] = true;
184              if(sortAttrs[i].startsWith("+"))
185              {
186                sortAttrs[i] = sortAttrs[i].substring(1);
187              }
188            }
189          }
190          catch(Exception e)
191          {
192            Message msg =
193                ERR_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(
194                        String.valueOf(sortKeys[i]), name);
195            throw new ConfigException(msg);
196          }
197    
198          AttributeType attrType =
199              DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
200          if(attrType == null)
201          {
202            Message msg =
203                ERR_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortAttrs[i], name);
204            throw new ConfigException(msg);
205          }
206          sortKeys[i] = new SortKey(attrType, ascending[i]);
207          orderingRules[i] = attrType.getOrderingMatchingRule();
208        }
209    
210        this.sortOrder = new SortOrder(sortKeys);
211        this.comparator = new VLVKeyComparator(orderingRules, ascending);
212    
213        DatabaseConfig dbNodupsConfig = new DatabaseConfig();
214    
215        if(env.getConfig().getReadOnly())
216        {
217          dbNodupsConfig.setReadOnly(true);
218          dbNodupsConfig.setAllowCreate(false);
219          dbNodupsConfig.setTransactional(false);
220        }
221        else if(!env.getConfig().getTransactional())
222        {
223          dbNodupsConfig.setAllowCreate(true);
224          dbNodupsConfig.setTransactional(false);
225          dbNodupsConfig.setDeferredWrite(true);
226        }
227        else
228        {
229          dbNodupsConfig.setAllowCreate(true);
230          dbNodupsConfig.setTransactional(true);
231        }
232    
233        this.dbConfig = dbNodupsConfig;
234        this.dbConfig.setOverrideBtreeComparator(true);
235        this.dbConfig.setBtreeComparator(this.comparator);
236    
237        this.state = state;
238    
239        this.trusted = state.getIndexTrustState(null, this);
240        if(!trusted && entryContainer.getHighestEntryID().equals(new EntryID(0)))
241        {
242          // If there are no entries in the entry container then there
243          // is no reason why this vlvIndex can't be upgraded to trusted.
244          setTrusted(null, true);
245        }
246    
247        // Issue warning if this vlvIndex is not trusted
248        if(!trusted)
249        {
250          logError(NOTE_JEB_INDEX_ADD_REQUIRES_REBUILD.get(name));
251        }
252    
253        this.count = new AtomicInteger(0);
254        this.config.addChangeListener(this);
255      }
256    
257      /**
258       * {@inheritDoc}
259       */
260      public void open() throws DatabaseException
261      {
262        super.open();
263    
264        DatabaseEntry key = new DatabaseEntry();
265        OperationStatus status;
266        LockMode lockMode = LockMode.RMW;
267        DatabaseEntry data = new DatabaseEntry();
268    
269        Cursor cursor = openCursor(null, CursorConfig.READ_COMMITTED);
270    
271        try
272        {
273          status = cursor.getFirst(key, data,lockMode);
274          while(status == OperationStatus.SUCCESS)
275          {
276            count.getAndAdd(SortValuesSet.getEncodedSize(data.getData(), 0));
277            status = cursor.getNext(key, data, lockMode);
278          }
279        }
280        finally
281        {
282          cursor.close();
283        }
284      }
285    
286      /**
287       * Close the VLV index.
288       *
289       * @throws DatabaseException if a JE database error occurs while
290       * closing the index.
291       */
292      public void close() throws DatabaseException
293      {
294        super.close();
295        this.config.removeChangeListener(this);
296      }
297    
298      /**
299       * Update the vlvIndex for a new entry.
300       *
301       * @param txn A database transaction, or null if none is required.
302       * @param entryID     The entry ID.
303       * @param entry       The entry to be indexed.
304       * @return True if the entry ID for the entry are added. False if
305       *         the entry ID already exists.
306       * @throws DatabaseException If an error occurs in the JE database.
307       * @throws org.opends.server.types.DirectoryException If a Directory Server
308       * error occurs.
309       * @throws JebException If an error occurs in the JE backend.
310       */
311      public boolean addEntry(Transaction txn, EntryID entryID, Entry entry)
312          throws DatabaseException, DirectoryException, JebException
313      {
314        DN entryDN = entry.getDN();
315        if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
316        {
317          return insertValues(txn, entryID.longValue(), entry);
318        }
319        return false;
320      }
321    
322      /**
323       * Update the vlvIndex for a new entry.
324       *
325       * @param buffer      The index buffer to buffer the changes.
326       * @param entryID     The entry ID.
327       * @param entry       The entry to be indexed.
328       * @return True if the entry ID for the entry are added. False if
329       *         the entry ID already exists.
330       * @throws DirectoryException If a Directory Server
331       * error occurs.
332       */
333      public boolean addEntry(IndexBuffer buffer, EntryID entryID, Entry entry)
334          throws DirectoryException
335      {
336        DN entryDN = entry.getDN();
337        if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
338        {
339          SortValues sortValues = new SortValues(entryID, entry, sortOrder);
340    
341          IndexBuffer.BufferedVLVValues bufferedValues =
342              buffer.getVLVIndex(this);
343          if(bufferedValues == null)
344          {
345            bufferedValues = new IndexBuffer.BufferedVLVValues();
346            buffer.putBufferedVLVIndex(this, bufferedValues);
347          }
348    
349          if(bufferedValues.deletedValues != null &&
350              bufferedValues.deletedValues.contains(sortValues))
351          {
352            bufferedValues.deletedValues.remove(sortValues);
353            return true;
354          }
355    
356          TreeSet<SortValues> bufferedAddedValues = bufferedValues.addedValues;
357          if(bufferedAddedValues == null)
358          {
359            bufferedAddedValues = new TreeSet<SortValues>();
360            bufferedValues.addedValues = bufferedAddedValues;
361          }
362          bufferedAddedValues.add(sortValues);
363          return true;
364        }
365        return false;
366      }
367    
368    
369      /**
370       * Update the vlvIndex for a deleted entry.
371       *
372       * @param txn         The database transaction to be used for the deletions
373       * @param entryID     The entry ID
374       * @param entry       The contents of the deleted entry.
375       * @return True if the entry was successfully removed from this VLV index
376       * or False otherwise.
377       * @throws DatabaseException If an error occurs in the JE database.
378       * @throws DirectoryException If a Directory Server error occurs.
379       * @throws JebException If an error occurs in the JE backend.
380       */
381      public boolean removeEntry(Transaction txn, EntryID entryID, Entry entry)
382          throws DatabaseException, DirectoryException, JebException
383      {
384        DN entryDN = entry.getDN();
385        if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
386        {
387          return removeValues(txn, entryID.longValue(), entry);
388        }
389        return false;
390      }
391    
392      /**
393       * Update the vlvIndex for a deleted entry.
394       *
395       * @param buffer      The database transaction to be used for the deletions
396       * @param entryID     The entry ID
397       * @param entry       The contents of the deleted entry.
398       * @return True if the entry was successfully removed from this VLV index
399       * or False otherwise.
400       * @throws DirectoryException If a Directory Server error occurs.
401       */
402      public boolean removeEntry(IndexBuffer buffer, EntryID entryID, Entry entry)
403          throws DirectoryException
404      {
405        DN entryDN = entry.getDN();
406        if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
407        {
408          SortValues sortValues = new SortValues(entryID, entry, sortOrder);
409    
410          IndexBuffer.BufferedVLVValues bufferedValues =
411              buffer.getVLVIndex(this);
412          if(bufferedValues == null)
413          {
414            bufferedValues = new IndexBuffer.BufferedVLVValues();
415            buffer.putBufferedVLVIndex(this, bufferedValues);
416          }
417    
418          if(bufferedValues.addedValues != null &&
419              bufferedValues.addedValues.contains(sortValues))
420          {
421            bufferedValues.addedValues.remove(sortValues);
422            return true;
423          }
424    
425          TreeSet<SortValues> bufferedDeletedValues = bufferedValues.deletedValues;
426          if(bufferedDeletedValues == null)
427          {
428            bufferedDeletedValues = new TreeSet<SortValues>();
429            bufferedValues.deletedValues = bufferedDeletedValues;
430          }
431          bufferedDeletedValues.add(sortValues);
432          return true;
433        }
434        return false;
435    
436      }
437    
438      /**
439       * Update the vlvIndex to reflect a sequence of modifications in a Modify
440       * operation.
441       *
442       * @param txn The JE transaction to use for database updates.
443       * @param entryID The ID of the entry that was modified.
444       * @param oldEntry The entry before the modifications were applied.
445       * @param newEntry The entry after the modifications were applied.
446       * @param mods The sequence of modifications in the Modify operation.
447       * @return True if the modification was successfully processed or False
448       * otherwise.
449       * @throws JebException If an error occurs during an operation on a
450       * JE database.
451       * @throws DatabaseException If an error occurs during an operation on a
452       * JE database.
453       * @throws DirectoryException If a Directory Server error occurs.
454       */
455      public boolean modifyEntry(Transaction txn,
456                              EntryID entryID,
457                              Entry oldEntry,
458                              Entry newEntry,
459                              List<Modification> mods)
460           throws DatabaseException, DirectoryException, JebException
461      {
462        DN oldEntryDN = oldEntry.getDN();
463        DN newEntryDN = newEntry.getDN();
464        if(oldEntryDN.matchesBaseAndScope(baseDN, scope) &&
465            filter.matchesEntry(oldEntry))
466        {
467          if(newEntryDN.matchesBaseAndScope(baseDN, scope) &&
468              filter.matchesEntry(newEntry))
469          {
470            // The entry should still be indexed. See if any sorted attributes are
471            // changed.
472            boolean sortAttributeModified = false;
473            SortKey[] sortKeys = sortOrder.getSortKeys();
474            for(SortKey sortKey : sortKeys)
475            {
476              AttributeType attributeType = sortKey.getAttributeType();
477              Iterable<AttributeType> subTypes =
478                  DirectoryServer.getSchema().getSubTypes(attributeType);
479              for(Modification mod : mods)
480              {
481                AttributeType modAttrType = mod.getAttribute().getAttributeType();
482                if(modAttrType.equals(attributeType))
483                {
484                  sortAttributeModified = true;
485                  break;
486                }
487                for(AttributeType subType : subTypes)
488                {
489                  if(modAttrType.equals(subType))
490                  {
491                    sortAttributeModified = true;
492                    break;
493                  }
494                }
495              }
496              if(sortAttributeModified)
497              {
498                break;
499              }
500            }
501            if(sortAttributeModified)
502            {
503              boolean success;
504              // Sorted attributes have changed. Reindex the entry;
505              success = removeValues(txn, entryID.longValue(), oldEntry);
506              success &= insertValues(txn, entryID.longValue(), newEntry);
507              return success;
508            }
509          }
510          else
511          {
512            // The modifications caused the new entry to be unindexed. Remove from
513            // vlvIndex.
514            return removeValues(txn, entryID.longValue(), oldEntry);
515          }
516        }
517        else
518        {
519          if(newEntryDN.matchesBaseAndScope(baseDN, scope) &&
520              filter.matchesEntry(newEntry))
521          {
522            // The modifications caused the new entry to be indexed. Add to
523            // vlvIndex.
524            return insertValues(txn, entryID.longValue(), newEntry);
525          }
526        }
527    
528        // The modifications does not affect this vlvIndex
529        return true;
530      }
531    
532      /**
533       * Update the vlvIndex to reflect a sequence of modifications in a Modify
534       * operation.
535       *
536       * @param buffer The database transaction to be used for the deletions
537       * @param entryID The ID of the entry that was modified.
538       * @param oldEntry The entry before the modifications were applied.
539       * @param newEntry The entry after the modifications were applied.
540       * @param mods The sequence of modifications in the Modify operation.
541       * @return True if the modification was successfully processed or False
542       * otherwise.
543       * @throws JebException If an error occurs during an operation on a
544       * JE database.
545       * @throws DatabaseException If an error occurs during an operation on a
546       * JE database.
547       * @throws DirectoryException If a Directory Server error occurs.
548       */
549      public boolean modifyEntry(IndexBuffer buffer,
550                              EntryID entryID,
551                              Entry oldEntry,
552                              Entry newEntry,
553                              List<Modification> mods)
554           throws DatabaseException, DirectoryException, JebException
555      {
556        DN oldEntryDN = oldEntry.getDN();
557        DN newEntryDN = newEntry.getDN();
558        if(oldEntryDN.matchesBaseAndScope(baseDN, scope) &&
559            filter.matchesEntry(oldEntry))
560        {
561          if(newEntryDN.matchesBaseAndScope(baseDN, scope) &&
562              filter.matchesEntry(newEntry))
563          {
564            // The entry should still be indexed. See if any sorted attributes are
565            // changed.
566            boolean sortAttributeModified = false;
567            SortKey[] sortKeys = sortOrder.getSortKeys();
568            for(SortKey sortKey : sortKeys)
569            {
570              AttributeType attributeType = sortKey.getAttributeType();
571              Iterable<AttributeType> subTypes =
572                  DirectoryServer.getSchema().getSubTypes(attributeType);
573              for(Modification mod : mods)
574              {
575                AttributeType modAttrType = mod.getAttribute().getAttributeType();
576                if(modAttrType.equals(attributeType))
577                {
578                  sortAttributeModified = true;
579                  break;
580                }
581                for(AttributeType subType : subTypes)
582                {
583                  if(modAttrType.equals(subType))
584                  {
585                    sortAttributeModified = true;
586                    break;
587                  }
588                }
589              }
590              if(sortAttributeModified)
591              {
592                break;
593              }
594            }
595            if(sortAttributeModified)
596            {
597              boolean success;
598              // Sorted attributes have changed. Reindex the entry;
599              success = removeEntry(buffer, entryID, oldEntry);
600              success &= addEntry(buffer, entryID, newEntry);
601              return success;
602            }
603          }
604          else
605          {
606            // The modifications caused the new entry to be unindexed. Remove from
607            // vlvIndex.
608            return removeEntry(buffer, entryID, oldEntry);
609          }
610        }
611        else
612        {
613          if(newEntryDN.matchesBaseAndScope(baseDN, scope) &&
614              filter.matchesEntry(newEntry))
615          {
616            // The modifications caused the new entry to be indexed. Add to
617            // vlvIndex.
618            return addEntry(buffer, entryID, newEntry);
619          }
620        }
621    
622        // The modifications does not affect this vlvIndex
623        return true;
624      }
625    
626      /**
627       * Put a sort values set in this VLV index.
628       *
629       * @param txn The transaction to use when retriving the set or NULL if it is
630       *            not required.
631       * @param sortValuesSet The SortValuesSet to put.
632       * @return True if the sortValuesSet was put successfully or False otherwise.
633       * @throws JebException If an error occurs during an operation on a
634       * JE database.
635       * @throws DatabaseException If an error occurs during an operation on a
636       * JE database.
637       * @throws DirectoryException If a Directory Server error occurs.
638       */
639      public boolean putSortValuesSet(Transaction txn, SortValuesSet sortValuesSet)
640          throws JebException, DatabaseException, DirectoryException
641      {
642        DatabaseEntry key = new DatabaseEntry();
643        DatabaseEntry data = new DatabaseEntry();
644    
645        byte[] after = sortValuesSet.toDatabase();
646        key.setData(sortValuesSet.getKeyBytes());
647        data.setData(after);
648        return put(txn, key, data) == OperationStatus.SUCCESS;
649      }
650    
651      /**
652       * Get a sorted values set that should contain the entry with the given
653       * information.
654       *
655       * @param txn The transaction to use when retriving the set or NULL if it is
656       *            not required.
657       * @param entryID The entry ID to use.
658       * @param values The values to use.
659       * @return The SortValuesSet that should contain the entry with the given
660       *         information.
661       * @throws DatabaseException If an error occurs during an operation on a
662       * JE database.
663       * @throws DirectoryException If a Directory Server error occurs.
664       */
665      public SortValuesSet getSortValuesSet(Transaction txn, long entryID,
666                                            AttributeValue[] values)
667          throws DatabaseException, DirectoryException
668      {
669        SortValuesSet sortValuesSet = null;
670        DatabaseEntry key = new DatabaseEntry();
671        OperationStatus status;
672        LockMode lockMode = LockMode.DEFAULT;
673        DatabaseEntry data = new DatabaseEntry();
674    
675        Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
676    
677        try
678        {
679          key.setData(encodeKey(entryID, values));
680          status = cursor.getSearchKeyRange(key, data,lockMode);
681    
682          if(status != OperationStatus.SUCCESS)
683          {
684            // There are no records in the database
685            if(debugEnabled())
686            {
687              TRACER.debugVerbose("No sort values set exist in VLV vlvIndex %s. " +
688                  "Creating unbound set.", config.getName());
689            }
690            sortValuesSet = new SortValuesSet(this);
691          }
692          else
693          {
694            if(debugEnabled())
695            {
696              StringBuilder searchKeyHex = new StringBuilder();
697              StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
698              StringBuilder foundKeyHex = new StringBuilder();
699              StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
700              TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
701                  "%s\nSearch Key:%s\nFound Key:%s\n",
702                                  config.getName(),
703                                  searchKeyHex,
704                                  foundKeyHex);
705            }
706            sortValuesSet = new SortValuesSet(key.getData(), data.getData(),
707                                              this);
708          }
709        }
710        finally
711        {
712          cursor.close();
713        }
714    
715        return sortValuesSet;
716      }
717    
718      /**
719       * Search for entries matching the entry ID and attribute values and
720       * return its entry ID.
721       *
722       * @param txn The JE transaction to use for database updates.
723       * @param entryID The entry ID to search for.
724       * @param values The values to search for.
725       * @return The index of the entry ID matching the values or -1 if its not
726       * found.
727       * @throws DatabaseException If an error occurs during an operation on a
728       * JE database.
729       * @throws JebException If an error occurs during an operation on a
730       * JE database.
731       * @throws DirectoryException If a Directory Server error occurs.
732       */
733      public boolean containsValues(Transaction txn, long entryID,
734                                 AttributeValue[] values)
735          throws JebException, DatabaseException, DirectoryException
736      {
737        SortValuesSet valuesSet = getSortValuesSet(txn, entryID, values);
738        int pos = valuesSet.binarySearch(entryID, values);
739        if(pos < 0)
740        {
741          return false;
742        }
743        return true;
744      }
745    
746      private boolean insertValues(Transaction txn, long entryID, Entry entry)
747          throws JebException, DatabaseException, DirectoryException
748      {
749        SortValuesSet sortValuesSet;
750        AttributeValue[] values = getSortValues(entry);
751        DatabaseEntry key = new DatabaseEntry();
752        OperationStatus status;
753        LockMode lockMode = LockMode.RMW;
754        DatabaseEntry data = new DatabaseEntry();
755        boolean success = true;
756    
757        Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
758    
759        try
760        {
761          key.setData(encodeKey(entryID, values));
762          status = cursor.getSearchKeyRange(key, data,lockMode);
763        }
764        finally
765        {
766          cursor.close();
767        }
768    
769        if(status != OperationStatus.SUCCESS)
770        {
771          // There are no records in the database
772          if(debugEnabled())
773          {
774            TRACER.debugVerbose("No sort values set exist in VLV vlvIndex %s. " +
775                "Creating unbound set.", config.getName());
776          }
777          sortValuesSet = new SortValuesSet(this);
778          key.setData(new byte[0]);
779        }
780        else
781        {
782          if(debugEnabled())
783          {
784            StringBuilder searchKeyHex = new StringBuilder();
785            StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
786            StringBuilder foundKeyHex = new StringBuilder();
787            StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
788            TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
789                "%s\nSearch Key:%s\nFound Key:%s\n",
790                                config.getName(),
791                                searchKeyHex,
792                                foundKeyHex);
793          }
794          sortValuesSet = new SortValuesSet(key.getData(), data.getData(),
795                                            this);
796        }
797    
798    
799    
800    
801        success = sortValuesSet.add(entryID, values);
802    
803        int newSize = sortValuesSet.size();
804        if(newSize >= sortedSetCapacity)
805        {
806          SortValuesSet splitSortValuesSet = sortValuesSet.split(newSize / 2);
807          byte[] splitAfter = splitSortValuesSet.toDatabase();
808          key.setData(splitSortValuesSet.getKeyBytes());
809          data.setData(splitAfter);
810          put(txn, key, data);
811          byte[] after = sortValuesSet.toDatabase();
812          key.setData(sortValuesSet.getKeyBytes());
813          data.setData(after);
814          put(txn, key, data);
815    
816          if(debugEnabled())
817          {
818            TRACER.debugInfo("SortValuesSet with key %s has reached" +
819                " the entry size of %d. Spliting into two sets with " +
820                " keys %s and %s.", splitSortValuesSet.getKeySortValues(),
821                                    newSize, sortValuesSet.getKeySortValues(),
822                                    splitSortValuesSet.getKeySortValues());
823          }
824        }
825        else
826        {
827          byte[] after = sortValuesSet.toDatabase();
828          data.setData(after);
829          put(txn, key, data);
830          // TODO: What about phantoms?
831        }
832    
833        if(success)
834        {
835          count.getAndIncrement();
836        }
837    
838        return success;
839      }
840    
841      private boolean removeValues(Transaction txn, long entryID, Entry entry)
842          throws JebException, DatabaseException, DirectoryException
843      {
844        SortValuesSet sortValuesSet;
845        AttributeValue[] values = getSortValues(entry);
846        DatabaseEntry key = new DatabaseEntry();
847        OperationStatus status;
848        LockMode lockMode = LockMode.RMW;
849        DatabaseEntry data = new DatabaseEntry();
850    
851        Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
852    
853        try
854        {
855          key.setData(encodeKey(entryID, values));
856          status = cursor.getSearchKeyRange(key, data,lockMode);
857        }
858        finally
859        {
860          cursor.close();
861        }
862    
863        if(status == OperationStatus.SUCCESS)
864        {
865          if(debugEnabled())
866          {
867            StringBuilder searchKeyHex = new StringBuilder();
868            StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
869            StringBuilder foundKeyHex = new StringBuilder();
870            StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
871            TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
872                "%s\nSearch Key:%s\nFound Key:%s\n",
873                                config.getName(),
874                                searchKeyHex,
875                                foundKeyHex);
876          }
877          sortValuesSet = new SortValuesSet(key.getData(), data.getData(),
878                                            this);
879          boolean success = sortValuesSet.remove(entryID, values);
880          byte[] after = sortValuesSet.toDatabase();
881    
882          if(after == null)
883          {
884            delete(txn, key);
885          }
886          else
887          {
888            data.setData(after);
889            put(txn, key, data);
890          }
891    
892          if(success)
893          {
894            count.getAndDecrement();
895          }
896    
897          return success;
898        }
899        else
900        {
901          return false;
902        }
903      }
904    
905      /**
906       * Update the vlvIndex with the specified values to add and delete.
907       *
908       * @param txn A database transaction, or null if none is required.
909       * @param addedValues The values to add to the VLV index.
910       * @param deletedValues The values to delete from the VLV index.
911       * @throws DatabaseException If an error occurs in the JE database.
912       * @throws DirectoryException If a Directory Server
913       * error occurs.
914       * @throws JebException If an error occurs in the JE backend.
915       */
916      public void updateIndex(Transaction txn,
917                              TreeSet<SortValues> addedValues,
918                              TreeSet<SortValues> deletedValues)
919          throws DirectoryException, DatabaseException, JebException
920      {
921        // Handle cases where nothing is changed early to avoid
922        // DB access.
923        if((addedValues == null || addedValues.size() == 0) &&
924            (deletedValues == null || deletedValues.size() == 0))
925        {
926          return;
927        }
928    
929        DatabaseEntry key = new DatabaseEntry();
930        OperationStatus status;
931        LockMode lockMode = LockMode.RMW;
932        DatabaseEntry data = new DatabaseEntry();
933        SortValuesSet sortValuesSet;
934        Iterator<SortValues> aValues = null;
935        Iterator<SortValues> dValues = null;
936        SortValues av = null;
937        SortValues dv = null;
938    
939        if(addedValues != null)
940        {
941          aValues = addedValues.iterator();
942          av = aValues.next();
943        }
944        if(deletedValues != null)
945        {
946          dValues = deletedValues.iterator();
947          dv = dValues.next();
948        }
949    
950        while(true)
951        {
952          if(av != null)
953          {
954            if(dv != null)
955            {
956              // Start from the smallest values from either set.
957              if(av.compareTo(dv) < 0)
958              {
959                key.setData(encodeKey(av.getEntryID(), av.getValues()));
960              }
961              else
962              {
963                key.setData(encodeKey(dv.getEntryID(), dv.getValues()));
964              }
965            }
966            else
967            {
968              key.setData(encodeKey(av.getEntryID(), av.getValues()));
969            }
970          }
971          else if(dv != null)
972          {
973            key.setData(encodeKey(dv.getEntryID(), dv.getValues()));
974          }
975          else
976          {
977            break;
978          }
979    
980          Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
981    
982          try
983          {
984            status = cursor.getSearchKeyRange(key, data,lockMode);
985          }
986          finally
987          {
988            cursor.close();
989          }
990    
991          if(status != OperationStatus.SUCCESS)
992          {
993            // There are no records in the database
994            if(debugEnabled())
995            {
996              TRACER.debugVerbose("No sort values set exist in VLV vlvIndex %s. " +
997                  "Creating unbound set.", config.getName());
998            }
999            sortValuesSet = new SortValuesSet(this);
1000            key.setData(new byte[0]);
1001          }
1002          else
1003          {
1004            if(debugEnabled())
1005            {
1006              StringBuilder searchKeyHex = new StringBuilder();
1007              StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
1008              StringBuilder foundKeyHex = new StringBuilder();
1009              StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
1010              TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
1011                  "%s\nSearch Key:%s\nFound Key:%s\n",
1012                  config.getName(),
1013                  searchKeyHex,
1014                  foundKeyHex);
1015            }
1016            sortValuesSet = new SortValuesSet(key.getData(), data.getData(),
1017                this);
1018          }
1019    
1020          int oldSize = sortValuesSet.size();
1021          if(key.getData().length == 0)
1022          {
1023            // This is the last unbounded set.
1024            while(av != null)
1025            {
1026              sortValuesSet.add(av.getEntryID(), av.getValues());
1027              aValues.remove();
1028              if(aValues.hasNext())
1029              {
1030                av = aValues.next();
1031              }
1032              else
1033              {
1034                av = null;
1035              }
1036            }
1037    
1038            while(dv != null)
1039            {
1040              sortValuesSet.remove(dv.getEntryID(), dv.getValues());
1041              dValues.remove();
1042              if(dValues.hasNext())
1043              {
1044                dv = dValues.next();
1045              }
1046              else
1047              {
1048                dv = null;
1049              }
1050            }
1051          }
1052          else
1053          {
1054            SortValues maxValues = decodeKey(sortValuesSet.getKeyBytes());
1055    
1056            while(av != null && av.compareTo(maxValues) <= 0)
1057            {
1058              sortValuesSet.add(av.getEntryID(), av.getValues());
1059              aValues.remove();
1060              if(aValues.hasNext())
1061              {
1062                av = aValues.next();
1063              }
1064              else
1065              {
1066                av = null;
1067              }
1068            }
1069    
1070            while(dv != null && dv.compareTo(maxValues) <= 0)
1071            {
1072              sortValuesSet.remove(dv.getEntryID(), dv.getValues());
1073              dValues.remove();
1074              if(dValues.hasNext())
1075              {
1076                dv = dValues.next();
1077              }
1078              else
1079              {
1080                dv = null;
1081              }
1082            }
1083          }
1084    
1085          int newSize = sortValuesSet.size();
1086          if(newSize >= sortedSetCapacity)
1087          {
1088            SortValuesSet splitSortValuesSet = sortValuesSet.split(newSize / 2);
1089            byte[] splitAfter = splitSortValuesSet.toDatabase();
1090            key.setData(splitSortValuesSet.getKeyBytes());
1091            data.setData(splitAfter);
1092            put(txn, key, data);
1093            byte[] after = sortValuesSet.toDatabase();
1094            key.setData(sortValuesSet.getKeyBytes());
1095            data.setData(after);
1096            put(txn, key, data);
1097    
1098            if(debugEnabled())
1099            {
1100              TRACER.debugInfo("SortValuesSet with key %s has reached" +
1101                  " the entry size of %d. Spliting into two sets with " +
1102                  " keys %s and %s.", splitSortValuesSet.getKeySortValues(),
1103                  newSize, sortValuesSet.getKeySortValues(),
1104                  splitSortValuesSet.getKeySortValues());
1105            }
1106          }
1107          else if(newSize == 0)
1108          {
1109            delete(txn, key);
1110          }
1111          else
1112          {
1113            byte[] after = sortValuesSet.toDatabase();
1114            data.setData(after);
1115            put(txn, key, data);
1116          }
1117    
1118          count.getAndAdd(newSize - oldSize);
1119        }
1120      }
1121    
1122      /**
1123       * Evaluate a search with sort control using this VLV index.
1124       *
1125       * @param txn The transaction to used when reading the index or NULL if it is
1126       *            not required.
1127       * @param searchOperation The search operation to evaluate.
1128       * @param sortControl The sort request control to evaluate.
1129       * @param vlvRequest The VLV request control to evaluate or NULL if VLV is not
1130       *                   requested.
1131       * @param debugBuilder If not null, a diagnostic string will be written
1132       *                     which will help determine how this index contributed
1133       *                     to this search.
1134       * @return The sorted EntryIDSet containing the entry IDs that match the
1135       *         search criteria.
1136       * @throws DirectoryException If a Directory Server error occurs.
1137       * @throws DatabaseException If an error occurs in the JE database.
1138       * @throws JebException If an error occurs in the JE database.
1139       */
1140      public EntryIDSet evaluate(Transaction txn,
1141                                 SearchOperation searchOperation,
1142                                 ServerSideSortRequestControl sortControl,
1143                                 VLVRequestControl vlvRequest,
1144                                 StringBuilder debugBuilder)
1145          throws DirectoryException, DatabaseException, JebException
1146      {
1147        if(!trusted || rebuildRunning)
1148        {
1149          return null;
1150        }
1151        if(!searchOperation.getBaseDN().equals(baseDN))
1152        {
1153          return null;
1154        }
1155        if(!searchOperation.getScope().equals(scope))
1156        {
1157          return null;
1158        }
1159        if(!searchOperation.getFilter().equals(filter))
1160        {
1161          return null;
1162        }
1163        if(!sortControl.getSortOrder().equals(this.sortOrder))
1164        {
1165          return null;
1166        }
1167    
1168        if (debugBuilder != null)
1169        {
1170          debugBuilder.append("vlv=");
1171          debugBuilder.append("[INDEX:");
1172          debugBuilder.append(name.replace(entryContainer.getDatabasePrefix() + "_",
1173                                           ""));
1174          debugBuilder.append("]");
1175        }
1176    
1177        long[] selectedIDs = new long[0];
1178        if(vlvRequest != null)
1179        {
1180          int currentCount = count.get();
1181          int beforeCount = vlvRequest.getBeforeCount();
1182          int afterCount  = vlvRequest.getAfterCount();
1183    
1184          if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET)
1185          {
1186            int targetOffset = vlvRequest.getOffset();
1187            if (targetOffset < 0)
1188            {
1189              // The client specified a negative target offset.  This should never
1190              // be allowed.
1191              searchOperation.addResponseControl(
1192                  new VLVResponseControl(targetOffset, currentCount,
1193                                         LDAPResultCode.OFFSET_RANGE_ERROR));
1194    
1195              Message message = ERR_ENTRYIDSORTER_NEGATIVE_START_POS.get();
1196              throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR,
1197                                           message);
1198            }
1199            else if (targetOffset == 0)
1200            {
1201              // This is an easy mistake to make, since VLV offsets start at 1
1202              // instead of 0.  We'll assume the client meant to use 1.
1203              targetOffset = 1;
1204            }
1205            int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0.
1206            int startPos = listOffset - beforeCount;
1207            if (startPos < 0)
1208            {
1209              // This can happen if beforeCount >= offset, and in this case we'll
1210              // just adjust the start position to ignore the range of beforeCount
1211              // that doesn't exist.
1212              startPos    = 0;
1213              beforeCount = listOffset;
1214            }
1215            else if(startPos >= currentCount)
1216            {
1217              // The start position is beyond the end of the list.  In this case,
1218              // we'll assume that the start position was one greater than the
1219              // size of the list and will only return the beforeCount entries.
1220              // The start position is beyond the end of the list.  In this case,
1221              // we'll assume that the start position was one greater than the
1222              // size of the list and will only return the beforeCount entries.
1223              targetOffset = currentCount + 1;
1224              listOffset   = currentCount;
1225              startPos     = listOffset - beforeCount;
1226              afterCount   = 0;
1227            }
1228    
1229            int count = 1 + beforeCount + afterCount;
1230            selectedIDs = new long[count];
1231    
1232            DatabaseEntry key = new DatabaseEntry();
1233            OperationStatus status;
1234            LockMode lockMode = LockMode.DEFAULT;
1235            DatabaseEntry data = new DatabaseEntry();
1236    
1237            Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
1238    
1239            try
1240            {
1241              //Locate the set that contains the target entry.
1242              int cursorCount = 0;
1243              int selectedPos = 0;
1244              status = cursor.getFirst(key, data,lockMode);
1245              while(status == OperationStatus.SUCCESS)
1246              {
1247                if(debugEnabled())
1248                {
1249                  StringBuilder searchKeyHex = new StringBuilder();
1250                  StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(),
1251                                                      4);
1252                  StringBuilder foundKeyHex = new StringBuilder();
1253                  StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(),
1254                                                      4);
1255                  TRACER.debugVerbose("Retrieved a sort values set in VLV " +
1256                      "vlvIndex %s\nSearch Key:%s\nFound Key:%s\n",
1257                                      config.getName(),
1258                                      searchKeyHex,
1259                                      foundKeyHex);
1260                }
1261                long[] IDs = SortValuesSet.getEncodedIDs(data.getData(), 0);
1262                for(int i = startPos + selectedPos - cursorCount;
1263                    i < IDs.length && selectedPos < count;
1264                    i++, selectedPos++)
1265                {
1266                  selectedIDs[selectedPos] = IDs[i];
1267                }
1268                cursorCount += IDs.length;
1269                status = cursor.getNext(key, data,lockMode);
1270              }
1271    
1272              if (selectedPos < count)
1273              {
1274                // We don't have enough entries in the set to meet the requested
1275                // page size, so we'll need to shorten the array.
1276                long[] newIDArray = new long[selectedPos];
1277                System.arraycopy(selectedIDs, 0, newIDArray, 0, selectedPos);
1278                selectedIDs = newIDArray;
1279              }
1280    
1281              searchOperation.addResponseControl(
1282                  new VLVResponseControl(targetOffset, currentCount,
1283                                         LDAPResultCode.SUCCESS));
1284    
1285              if(debugBuilder != null)
1286              {
1287                debugBuilder.append("[COUNT:");
1288                debugBuilder.append(cursorCount);
1289                debugBuilder.append("]");
1290              }
1291            }
1292            finally
1293            {
1294              cursor.close();
1295            }
1296          }
1297          else
1298          {
1299            int targetOffset = 0;
1300            int includedBeforeCount = 0;
1301            int includedAfterCount  = 0;
1302            LinkedList<EntryID> idList = new LinkedList<EntryID>();
1303            DatabaseEntry key = new DatabaseEntry();
1304            OperationStatus status;
1305            LockMode lockMode = LockMode.DEFAULT;
1306            DatabaseEntry data = new DatabaseEntry();
1307    
1308            Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
1309    
1310            try
1311            {
1312              byte[] vBytes = vlvRequest.getGreaterThanOrEqualAssertion().value();
1313              byte[] vLength = ASN1Element.encodeLength(vBytes.length);
1314              byte[] keyBytes = new byte[vBytes.length + vLength.length];
1315              System.arraycopy(vLength, 0, keyBytes, 0, vLength.length);
1316              System.arraycopy(vBytes, 0, keyBytes, vLength.length, vBytes.length);
1317    
1318              key.setData(keyBytes);
1319              status = cursor.getSearchKeyRange(key, data, lockMode);
1320              if(status == OperationStatus.SUCCESS)
1321              {
1322                if(debugEnabled())
1323                {
1324                  StringBuilder searchKeyHex = new StringBuilder();
1325                  StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(),
1326                                                      4);
1327                  StringBuilder foundKeyHex = new StringBuilder();
1328                  StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(),
1329                                                      4);
1330                  TRACER.debugVerbose("Retrieved a sort values set in VLV " +
1331                      "vlvIndex %s\nSearch Key:%s\nFound Key:%s\n",
1332                                      config.getName(),
1333                                      searchKeyHex,
1334                                      foundKeyHex);
1335                }
1336                SortValuesSet sortValuesSet =
1337                    new SortValuesSet(key.getData(), data.getData(), this);
1338                AttributeValue[] assertionValue = new AttributeValue[1];
1339                assertionValue[0] =
1340                    new AttributeValue(
1341                        sortOrder.getSortKeys()[0].getAttributeType(),
1342                        vlvRequest.getGreaterThanOrEqualAssertion());
1343    
1344                int adjustedTargetOffset =
1345                    sortValuesSet.binarySearch(-1, assertionValue);
1346                if(adjustedTargetOffset < 0)
1347                {
1348                  // For a negative return value r, the vlvIndex -(r+1) gives the
1349                  // array index of the ID that is greater then the assertion value.
1350                  adjustedTargetOffset = -(adjustedTargetOffset+1);
1351                }
1352    
1353                targetOffset = adjustedTargetOffset;
1354    
1355                // Iterate through all the sort values sets before this one to find
1356                // the target offset in the index.
1357                int lastOffset = adjustedTargetOffset - 1;
1358                long[] lastIDs = sortValuesSet.getEntryIDs();
1359                while(true)
1360                {
1361                  for(int i = lastOffset;
1362                      i >= 0 && includedBeforeCount < beforeCount; i--)
1363                  {
1364                    idList.addFirst(new EntryID(lastIDs[i]));
1365                    includedBeforeCount++;
1366                  }
1367    
1368                  status = cursor.getPrev(key, data, lockMode);
1369    
1370                  if(status != OperationStatus.SUCCESS)
1371                  {
1372                    break;
1373                  }
1374    
1375                  if(includedBeforeCount < beforeCount)
1376                  {
1377                    lastIDs =
1378                        SortValuesSet.getEncodedIDs(data.getData(), 0);
1379                    lastOffset = lastIDs.length - 1;
1380                    targetOffset += lastIDs.length;
1381                  }
1382                  else
1383                  {
1384                    targetOffset += SortValuesSet.getEncodedSize(data.getData(), 0);
1385                  }
1386                }
1387    
1388    
1389                // Set the cursor back to the position of the target entry set
1390                key.setData(sortValuesSet.getKeyBytes());
1391                cursor.getSearchKey(key, data, lockMode);
1392    
1393                // Add the target and after count entries if the target was found.
1394                lastOffset = adjustedTargetOffset;
1395                lastIDs = sortValuesSet.getEntryIDs();
1396                int afterIDCount = 0;
1397                while(true)
1398                {
1399                  for(int i = lastOffset;
1400                      i < lastIDs.length && includedAfterCount < afterCount + 1;
1401                      i++)
1402                  {
1403                    idList.addLast(new EntryID(lastIDs[i]));
1404                    includedAfterCount++;
1405                  }
1406    
1407                  if(includedAfterCount >= afterCount + 1)
1408                  {
1409                    break;
1410                  }
1411    
1412                  status = cursor.getNext(key, data, lockMode);
1413    
1414                  if(status != OperationStatus.SUCCESS)
1415                  {
1416                    break;
1417                  }
1418    
1419                  lastIDs =
1420                      SortValuesSet.getEncodedIDs(data.getData(), 0);
1421                  lastOffset = 0;
1422                  afterIDCount += lastIDs.length;
1423                }
1424    
1425                selectedIDs = new long[idList.size()];
1426                Iterator<EntryID> idIterator = idList.iterator();
1427                for (int i=0; i < selectedIDs.length; i++)
1428                {
1429                  selectedIDs[i] = idIterator.next().longValue();
1430                }
1431    
1432                searchOperation.addResponseControl(
1433                    new VLVResponseControl(targetOffset + 1, currentCount,
1434                                           LDAPResultCode.SUCCESS));
1435    
1436                if(debugBuilder != null)
1437                {
1438                  debugBuilder.append("[COUNT:");
1439                  debugBuilder.append(targetOffset + afterIDCount + 1);
1440                  debugBuilder.append("]");
1441                }
1442              }
1443            }
1444            finally
1445            {
1446              cursor.close();
1447            }
1448          }
1449        }
1450        else
1451        {
1452          LinkedList<long[]> idSets = new LinkedList<long[]>();
1453          int currentCount = 0;
1454          DatabaseEntry key = new DatabaseEntry();
1455          OperationStatus status;
1456          LockMode lockMode = LockMode.RMW;
1457          DatabaseEntry data = new DatabaseEntry();
1458    
1459          Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
1460    
1461          try
1462          {
1463            status = cursor.getFirst(key, data, lockMode);
1464            while(status == OperationStatus.SUCCESS)
1465            {
1466              if(debugEnabled())
1467              {
1468                StringBuilder searchKeyHex = new StringBuilder();
1469                StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
1470                StringBuilder foundKeyHex = new StringBuilder();
1471                StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
1472                TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
1473                    "%s\nSearch Key:%s\nFound Key:%s\n",
1474                                    config.getName(),
1475                                    searchKeyHex,
1476                                    foundKeyHex);
1477              }
1478              long[] ids = SortValuesSet.getEncodedIDs(data.getData(), 0);
1479              idSets.add(ids);
1480              currentCount += ids.length;
1481              status = cursor.getNext(key, data, lockMode);
1482            }
1483          }
1484          finally
1485          {
1486            cursor.close();
1487          }
1488    
1489          selectedIDs = new long[currentCount];
1490          int pos = 0;
1491          for(long[] id : idSets)
1492          {
1493            System.arraycopy(id, 0, selectedIDs, pos, id.length);
1494            pos += id.length;
1495          }
1496    
1497          if(debugBuilder != null)
1498          {
1499            debugBuilder.append("[COUNT:");
1500            debugBuilder.append(currentCount);
1501            debugBuilder.append("]");
1502          }
1503        }
1504        return new EntryIDSet(selectedIDs, 0, selectedIDs.length);
1505      }
1506    
1507        /**
1508       * Set the vlvIndex trust state.
1509       * @param txn A database transaction, or null if none is required.
1510       * @param trusted True if this vlvIndex should be trusted or false
1511       *                otherwise.
1512       * @throws DatabaseException If an error occurs in the JE database.
1513       */
1514      public synchronized void setTrusted(Transaction txn, boolean trusted)
1515          throws DatabaseException
1516      {
1517        this.trusted = trusted;
1518        state.putIndexTrustState(txn, this, trusted);
1519      }
1520    
1521      /**
1522       * Set the rebuild status of this vlvIndex.
1523       * @param rebuildRunning True if a rebuild process on this vlvIndex
1524       *                       is running or False otherwise.
1525       */
1526      public synchronized void setRebuildStatus(boolean rebuildRunning)
1527      {
1528        this.rebuildRunning = rebuildRunning;
1529      }
1530    
1531      /**
1532       * Gets the values to sort on from the entry.
1533       *
1534       * @param entry The entry to get the values from.
1535       * @return The attribute values to sort on.
1536       */
1537      AttributeValue[] getSortValues(Entry entry)
1538      {
1539        SortKey[] sortKeys = sortOrder.getSortKeys();
1540        AttributeValue[] values = new AttributeValue[sortKeys.length];
1541        for (int i=0; i < sortKeys.length; i++)
1542        {
1543          SortKey sortKey = sortKeys[i];
1544          AttributeType attrType = sortKey.getAttributeType();
1545          List<Attribute> attrList = entry.getAttribute(attrType);
1546          if (attrList != null)
1547          {
1548            AttributeValue sortValue = null;
1549    
1550            // There may be multiple versions of this attribute in the target entry
1551            // (e.g., with different sets of options), and it may also be a
1552            // multivalued attribute.  In that case, we need to find the value that
1553            // is the best match for the corresponding sort key (i.e., for sorting
1554            // in ascending order, we want to find the lowest value; for sorting in
1555            // descending order, we want to find the highest value).  This is
1556            // handled by the SortKey.compareValues method.
1557            for (Attribute a : attrList)
1558            {
1559              for (AttributeValue v : a.getValues())
1560              {
1561                if (sortValue == null)
1562                {
1563                  sortValue = v;
1564                }
1565                else if (sortKey.compareValues(v, sortValue) < 0)
1566                {
1567                  sortValue = v;
1568                }
1569              }
1570            }
1571    
1572            values[i] = sortValue;
1573          }
1574        }
1575        return values;
1576      }
1577    
1578      /**
1579       * Encode a VLV database key with the given information.
1580       *
1581       * @param entryID The entry ID to encode.
1582       * @param values The values to encode.
1583       * @return The encoded bytes.
1584       * @throws DirectoryException If a Directory Server error occurs.
1585       */
1586      byte[] encodeKey(long entryID, AttributeValue[] values)
1587          throws DirectoryException
1588      {
1589        int totalValueBytes = 0;
1590        LinkedList<byte[]> valueBytes = new LinkedList<byte[]>();
1591        for (AttributeValue v : values)
1592        {
1593          byte[] vBytes;
1594          if(v == null)
1595          {
1596            vBytes = new byte[0];
1597          }
1598          else
1599          {
1600            vBytes = v.getNormalizedValueBytes();
1601          }
1602          byte[] vLength = ASN1Element.encodeLength(vBytes.length);
1603          valueBytes.add(vLength);
1604          valueBytes.add(vBytes);
1605          totalValueBytes += vLength.length + vBytes.length;
1606        }
1607    
1608        byte[] entryIDBytes =
1609            JebFormat.entryIDToDatabase(entryID);
1610        byte[] attrBytes = new byte[entryIDBytes.length + totalValueBytes];
1611    
1612        int pos = 0;
1613        for (byte[] b : valueBytes)
1614        {
1615          System.arraycopy(b, 0, attrBytes, pos, b.length);
1616          pos += b.length;
1617        }
1618    
1619        System.arraycopy(entryIDBytes, 0, attrBytes, pos, entryIDBytes.length);
1620    
1621        return attrBytes;
1622      }
1623    
1624      /**
1625       * Decode a VLV database key.
1626       *
1627       * @param  keyBytes The byte array to decode.
1628       * @return The sort values represented by the key bytes.
1629       * @throws DirectoryException If a Directory Server error occurs.
1630       */
1631      SortValues decodeKey(byte[] keyBytes)
1632          throws DirectoryException
1633      {
1634        if(keyBytes == null || keyBytes.length == 0)
1635        {
1636          return null;
1637        }
1638    
1639        AttributeValue[] attributeValues =
1640            new AttributeValue[sortOrder.getSortKeys().length];
1641        int vBytesPos = 0;
1642    
1643        for(int i = 0; i < attributeValues.length; i++)
1644        {
1645          int valueLength = keyBytes[vBytesPos] & 0x7F;
1646          if (valueLength != keyBytes[vBytesPos++])
1647          {
1648            int valueLengthBytes = valueLength;
1649            valueLength = 0;
1650            for (int j=0; j < valueLengthBytes; j++, vBytesPos++)
1651            {
1652              valueLength = (valueLength << 8) | (keyBytes[vBytesPos] & 0xFF);
1653            }
1654          }
1655    
1656          if(valueLength == 0)
1657          {
1658            attributeValues[i] = null;
1659          }
1660          else
1661          {
1662            byte[] valueBytes = new byte[valueLength];
1663            System.arraycopy(keyBytes, vBytesPos, valueBytes, 0, valueLength);
1664            attributeValues[i] =
1665                new AttributeValue(sortOrder.getSortKeys()[i].getAttributeType(),
1666                    new ASN1OctetString(valueBytes));
1667          }
1668    
1669          vBytesPos += valueLength;
1670        }
1671    
1672        // FIXME: Should pos+offset method for decoding IDs be added to
1673        // JebFormat?
1674        long v = 0;
1675        for (int i = vBytesPos; i < keyBytes.length; i++)
1676        {
1677          v <<= 8;
1678          v |= (keyBytes[i] & 0xFF);
1679        }
1680    
1681        return new SortValues(new EntryID(v), attributeValues, sortOrder);
1682      }
1683    
1684      /**
1685       * Get the sorted set capacity configured for this VLV index.
1686       *
1687       * @return The sorted set capacity.
1688       */
1689      public int getSortedSetCapacity()
1690      {
1691        return sortedSetCapacity;
1692      }
1693    
1694      /**
1695       * Indicates if the given entry should belong in this VLV index.
1696       *
1697       * @param entry The entry to check.
1698       * @return True if the given entry should belong in this VLV index or False
1699       *         otherwise.
1700       * @throws DirectoryException If a Directory Server error occurs.
1701       */
1702      public boolean shouldInclude(Entry entry) throws DirectoryException
1703      {
1704        DN entryDN = entry.getDN();
1705        if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
1706        {
1707          return true;
1708        }
1709        return false;
1710      }
1711    
1712      /**
1713       * {@inheritDoc}
1714       */
1715      public synchronized boolean isConfigurationChangeAcceptable(
1716          LocalDBVLVIndexCfg cfg,
1717          List<Message> unacceptableReasons)
1718      {
1719        try
1720        {
1721          this.filter =
1722              SearchFilter.createFilterFromString(config.getFilter());
1723        }
1724        catch(Exception e)
1725        {
1726          Message msg = ERR_JEB_CONFIG_VLV_INDEX_BAD_FILTER.get(
1727                  config.getFilter(), name,
1728                  stackTraceToSingleLineString(e));
1729          unacceptableReasons.add(msg);
1730          return false;
1731        }
1732    
1733        String[] sortAttrs = config.getSortOrder().split(" ");
1734        SortKey[] sortKeys = new SortKey[sortAttrs.length];
1735        OrderingMatchingRule[] orderingRules =
1736            new OrderingMatchingRule[sortAttrs.length];
1737        boolean[] ascending = new boolean[sortAttrs.length];
1738        for(int i = 0; i < sortAttrs.length; i++)
1739        {
1740          try
1741          {
1742            if(sortAttrs[i].startsWith("-"))
1743            {
1744              ascending[i] = false;
1745              sortAttrs[i] = sortAttrs[i].substring(1);
1746            }
1747            else
1748            {
1749              ascending[i] = true;
1750              if(sortAttrs[i].startsWith("+"))
1751              {
1752                sortAttrs[i] = sortAttrs[i].substring(1);
1753              }
1754            }
1755          }
1756          catch(Exception e)
1757          {
1758            Message msg =
1759                    ERR_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(
1760                            String.valueOf(sortKeys[i]), name);
1761            unacceptableReasons.add(msg);
1762            return false;
1763          }
1764    
1765          AttributeType attrType =
1766              DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
1767          if(attrType == null)
1768          {
1769            Message msg = ERR_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(
1770                    sortAttrs[i], name);
1771            unacceptableReasons.add(msg);
1772            return false;
1773          }
1774          sortKeys[i] = new SortKey(attrType, ascending[i]);
1775          orderingRules[i] = attrType.getOrderingMatchingRule();
1776        }
1777    
1778        return true;
1779      }
1780    
1781      /**
1782       * {@inheritDoc}
1783       */
1784      public synchronized ConfigChangeResult applyConfigurationChange(
1785          LocalDBVLVIndexCfg cfg)
1786      {
1787        ResultCode resultCode = ResultCode.SUCCESS;
1788        boolean adminActionRequired = false;
1789        ArrayList<Message> messages = new ArrayList<Message>();
1790    
1791        // Update base DN only if changed..
1792        if(!config.getBaseDN().equals(cfg.getBaseDN()))
1793        {
1794          this.baseDN = cfg.getBaseDN();
1795          adminActionRequired = true;
1796        }
1797    
1798        // Update scope only if changed.
1799        if(!config.getScope().equals(cfg.getScope()))
1800        {
1801          this.scope = SearchScope.valueOf(cfg.getScope().name());
1802          adminActionRequired = true;
1803        }
1804    
1805        // Update sort set capacity only if changed.
1806        if(config.getMaxBlockSize() !=
1807            cfg.getMaxBlockSize())
1808        {
1809          this.sortedSetCapacity = cfg.getMaxBlockSize();
1810    
1811          // Require admin action only if the new capacity is larger. Otherwise,
1812          // we will lazyly update the sorted sets.
1813          if(config.getMaxBlockSize() <
1814              cfg.getMaxBlockSize())
1815          {
1816            adminActionRequired = true;
1817          }
1818        }
1819    
1820        // Update the filter only if changed.
1821        if(!config.getFilter().equals(cfg.getFilter()))
1822        {
1823          try
1824          {
1825            this.filter =
1826                SearchFilter.createFilterFromString(cfg.getFilter());
1827            adminActionRequired = true;
1828          }
1829          catch(Exception e)
1830          {
1831            Message msg = ERR_JEB_CONFIG_VLV_INDEX_BAD_FILTER.get(
1832                    config.getFilter(), name,
1833                    stackTraceToSingleLineString(e));
1834            messages.add(msg);
1835            if(resultCode == ResultCode.SUCCESS)
1836            {
1837              resultCode = ResultCode.INVALID_ATTRIBUTE_SYNTAX;
1838            }
1839          }
1840        }
1841    
1842        // Update the sort order only if changed.
1843        if(!config.getSortOrder().equals(
1844            cfg.getMaxBlockSize()))
1845        {
1846          String[] sortAttrs = cfg.getSortOrder().split(" ");
1847          SortKey[] sortKeys = new SortKey[sortAttrs.length];
1848          OrderingMatchingRule[] orderingRules =
1849              new OrderingMatchingRule[sortAttrs.length];
1850          boolean[] ascending = new boolean[sortAttrs.length];
1851          for(int i = 0; i < sortAttrs.length; i++)
1852          {
1853            try
1854            {
1855              if(sortAttrs[i].startsWith("-"))
1856              {
1857                ascending[i] = false;
1858                sortAttrs[i] = sortAttrs[i].substring(1);
1859              }
1860              else
1861              {
1862                ascending[i] = true;
1863                if(sortAttrs[i].startsWith("+"))
1864                {
1865                  sortAttrs[i] = sortAttrs[i].substring(1);
1866                }
1867              }
1868            }
1869            catch(Exception e)
1870            {
1871              Message msg = ERR_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(
1872                      String.valueOf(String.valueOf(sortKeys[i])), name);
1873              messages.add(msg);
1874              if(resultCode == ResultCode.SUCCESS)
1875              {
1876                resultCode = ResultCode.INVALID_ATTRIBUTE_SYNTAX;
1877              }
1878            }
1879    
1880            AttributeType attrType =
1881                DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
1882            if(attrType == null)
1883            {
1884              Message msg = ERR_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(
1885                      String.valueOf(String.valueOf(sortKeys[i])), name);
1886              messages.add(msg);
1887              if(resultCode == ResultCode.SUCCESS)
1888              {
1889                resultCode = ResultCode.INVALID_ATTRIBUTE_SYNTAX;
1890              }
1891            }
1892            sortKeys[i] = new SortKey(attrType, ascending[i]);
1893            orderingRules[i] = attrType.getOrderingMatchingRule();
1894          }
1895    
1896          this.sortOrder = new SortOrder(sortKeys);
1897          this.comparator = new VLVKeyComparator(orderingRules, ascending);
1898    
1899          // We have to close the database and open it using the new comparator.
1900          entryContainer.exclusiveLock.lock();
1901          try
1902          {
1903            this.close();
1904            this.dbConfig.setBtreeComparator(this.comparator);
1905            this.open();
1906          }
1907          catch(DatabaseException de)
1908          {
1909            messages.add(Message.raw(StaticUtils.stackTraceToSingleLineString(de)));
1910            if(resultCode == ResultCode.SUCCESS)
1911            {
1912              resultCode = DirectoryServer.getServerErrorResultCode();
1913            }
1914          }
1915          finally
1916          {
1917            entryContainer.exclusiveLock.unlock();
1918          }
1919    
1920          adminActionRequired = true;
1921        }
1922    
1923    
1924        if(adminActionRequired)
1925        {
1926          trusted = false;
1927          Message message = NOTE_JEB_INDEX_ADD_REQUIRES_REBUILD.get(name);
1928          messages.add(message);
1929          try
1930          {
1931            state.putIndexTrustState(null, this, false);
1932          }
1933          catch(DatabaseException de)
1934          {
1935            messages.add(Message.raw(StaticUtils.stackTraceToSingleLineString(de)));
1936            if(resultCode == ResultCode.SUCCESS)
1937            {
1938              resultCode = DirectoryServer.getServerErrorResultCode();
1939            }
1940          }
1941        }
1942    
1943        this.config = cfg;
1944        return new ConfigChangeResult(resultCode, adminActionRequired, messages);
1945      }
1946    }