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 legal-notices/CDDLv1_0.txt
010 * or http://forgerock.org/license/CDDLv1.0.html.
011 * See the License for the specific language governing permissions
012 * and limitations under the License.
013 *
014 * When distributing Covered Code, include this CDDL HEADER in each
015 * file and include the License file at legal-notices/CDDLv1_0.txt.
016 * If applicable, add the following below this CDDL HEADER, with the
017 * fields enclosed by brackets "[]" replaced with your own identifying
018 * information:
019 *      Portions Copyright [yyyy] [name of copyright owner]
020 *
021 * CDDL HEADER END
022 *
023 *
024 *      Copyright 2006-2008 Sun Microsystems, Inc.
025 *      Portions Copyright 2011-2015 ForgeRock AS
026 */
027package org.opends.server.backends.jeb;
028
029import static org.opends.messages.BackendMessages.*;
030import static org.opends.server.util.StaticUtils.*;
031
032import java.util.Iterator;
033import java.util.LinkedList;
034import java.util.List;
035import java.util.TreeSet;
036import java.util.concurrent.atomic.AtomicInteger;
037
038import org.forgerock.i18n.LocalizableMessage;
039import org.forgerock.i18n.slf4j.LocalizedLogger;
040import org.forgerock.opendj.config.server.ConfigChangeResult;
041import org.forgerock.opendj.config.server.ConfigException;
042import org.forgerock.opendj.ldap.ByteSequence;
043import org.forgerock.opendj.ldap.ByteString;
044import org.forgerock.opendj.ldap.ByteStringBuilder;
045import org.forgerock.opendj.ldap.DecodeException;
046import org.forgerock.opendj.ldap.ResultCode;
047import org.forgerock.opendj.ldap.SearchScope;
048import org.forgerock.opendj.ldap.schema.MatchingRule;
049import org.opends.server.admin.server.ConfigurationChangeListener;
050import org.opends.server.admin.std.meta.LocalDBVLVIndexCfgDefn.Scope;
051import org.opends.server.admin.std.server.LocalDBVLVIndexCfg;
052import org.opends.server.controls.ServerSideSortRequestControl;
053import org.opends.server.controls.VLVRequestControl;
054import org.opends.server.controls.VLVResponseControl;
055import org.opends.server.core.DirectoryServer;
056import org.opends.server.core.SearchOperation;
057import org.opends.server.protocols.ldap.LDAPResultCode;
058import org.opends.server.types.Attribute;
059import org.opends.server.types.AttributeType;
060import org.opends.server.types.DN;
061import org.opends.server.types.DirectoryException;
062import org.opends.server.types.Entry;
063import org.opends.server.types.Modification;
064import org.opends.server.types.SearchFilter;
065import org.opends.server.types.SortKey;
066import org.opends.server.types.SortOrder;
067import org.opends.server.util.StaticUtils;
068
069import com.sleepycat.je.*;
070
071/**
072 * This class represents a VLV index. Each database record is a sorted list
073 * of entry IDs followed by sets of attribute values used to sort the entries.
074 * The entire set of entry IDs are broken up into sorted subsets to decrease
075 * the number of database retrievals needed for a range lookup. The records are
076 * keyed by the last entry's first sort attribute value. The list of entries
077 * in a particular database record maintains the property where the first sort
078 * attribute value is bigger then the previous key but smaller or equal
079 * to its own key.
080 */
081public class VLVIndex extends DatabaseContainer
082    implements ConfigurationChangeListener<LocalDBVLVIndexCfg>
083{
084  private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass();
085
086  /** The comparator for vlvIndex keys. */
087  public VLVKeyComparator comparator;
088  /** The limit on the number of entry IDs that may be indexed by one key. */
089  private int sortedSetCapacity = 4000;
090  /** The SortOrder in use by this VLV index to sort the entries. */
091  public SortOrder sortOrder;
092
093  /** The cached count of entries in this index. */
094  private final AtomicInteger count;
095
096  private final State state;
097  /**
098   * A flag to indicate if this vlvIndex should be trusted to be consistent
099   * with the entries database.
100   */
101  private boolean trusted;
102
103  /** The VLV vlvIndex configuration. */
104  private LocalDBVLVIndexCfg config;
105
106  private DN baseDN;
107  private SearchFilter filter;
108  private SearchScope scope;
109
110
111  /**
112   * Create a new VLV vlvIndex object.
113   *
114   * @param config           The VLV index config object to use for this VLV
115   *                         index.
116   * @param state            The state database to persist vlvIndex state info.
117   * @param env              The JE Environment
118   * @param entryContainer   The database entryContainer holding this vlvIndex.
119   * @throws com.sleepycat.je.DatabaseException
120   *          If an error occurs in the JE database.
121   * @throws ConfigException if a error occurs while reading the VLV index
122   * configuration
123   */
124  VLVIndex(LocalDBVLVIndexCfg config, State state, Environment env, EntryContainer entryContainer)
125      throws DatabaseException, ConfigException
126  {
127    super(entryContainer.getDatabasePrefix()+"_vlv."+config.getName(),
128          env, entryContainer);
129
130    this.config = config;
131    this.baseDN = config.getBaseDN();
132    this.scope = convertScope(config.getScope());
133    this.sortedSetCapacity = config.getMaxBlockSize();
134
135    try
136    {
137      this.filter = SearchFilter.createFilterFromString(config.getFilter());
138    }
139    catch(Exception e)
140    {
141      throw new ConfigException(ERR_CONFIG_VLV_INDEX_BAD_FILTER.get(
142          config.getFilter(), name, stackTraceToSingleLineString(e)));
143    }
144
145    String[] sortAttrs = config.getSortOrder().split(" ");
146    SortKey[] sortKeys = new SortKey[sortAttrs.length];
147    MatchingRule[] orderingRules = new MatchingRule[sortAttrs.length];
148    boolean[] ascending = new boolean[sortAttrs.length];
149    for(int i = 0; i < sortAttrs.length; i++)
150    {
151      try
152      {
153        if(sortAttrs[i].startsWith("-"))
154        {
155          ascending[i] = false;
156          sortAttrs[i] = sortAttrs[i].substring(1);
157        }
158        else
159        {
160          ascending[i] = true;
161          if(sortAttrs[i].startsWith("+"))
162          {
163            sortAttrs[i] = sortAttrs[i].substring(1);
164          }
165        }
166      }
167      catch(Exception e)
168      {
169        throw new ConfigException(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name));
170      }
171
172      AttributeType attrType =
173          DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
174      if(attrType == null)
175      {
176        throw new ConfigException(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortAttrs[i], name));
177      }
178      sortKeys[i] = new SortKey(attrType, ascending[i]);
179      orderingRules[i] = attrType.getOrderingMatchingRule();
180    }
181
182    this.sortOrder = new SortOrder(sortKeys);
183    this.comparator = new VLVKeyComparator(orderingRules, ascending);
184
185    this.dbConfig = JEBUtils.toDatabaseConfigNoDuplicates(env);
186    this.dbConfig.setOverrideBtreeComparator(true);
187    this.dbConfig.setBtreeComparator(this.comparator);
188
189    this.state = state;
190
191    this.trusted = state.getIndexTrustState(null, this);
192    if (!trusted && entryContainer.getHighestEntryID().longValue() == 0)
193    {
194      // If there are no entries in the entry container then there
195      // is no reason why this vlvIndex can't be upgraded to trusted.
196      setTrusted(null, true);
197    }
198
199    this.count = new AtomicInteger(0);
200    this.config.addChangeListener(this);
201  }
202
203  private SearchScope convertScope(final Scope cfgScope)
204  {
205    switch (cfgScope)
206    {
207    case BASE_OBJECT:
208      return SearchScope.BASE_OBJECT;
209    case SINGLE_LEVEL:
210      return SearchScope.SINGLE_LEVEL;
211    case SUBORDINATE_SUBTREE:
212      return SearchScope.SUBORDINATES;
213    default: // WHOLE_SUBTREE
214      return SearchScope.WHOLE_SUBTREE;
215    }
216  }
217
218  /** {@inheritDoc} */
219  @Override
220  public void open() throws DatabaseException
221  {
222    super.open();
223
224    DatabaseEntry key = new DatabaseEntry();
225    DatabaseEntry data = new DatabaseEntry();
226    LockMode lockMode = LockMode.RMW;
227
228    Cursor cursor = openCursor(null, CursorConfig.READ_COMMITTED);
229    try
230    {
231      OperationStatus status = cursor.getFirst(key, data,lockMode);
232      while(status == OperationStatus.SUCCESS)
233      {
234        count.getAndAdd(SortValuesSet.getEncodedSize(data.getData(), 0));
235        status = cursor.getNext(key, data, lockMode);
236      }
237    }
238    finally
239    {
240      cursor.close();
241    }
242  }
243
244  /**
245   * Close the VLV index.
246   *
247   * @throws DatabaseException if a JE database error occurs while
248   * closing the index.
249   */
250  @Override
251  public void close() throws DatabaseException
252  {
253    super.close();
254    this.config.removeChangeListener(this);
255  }
256
257  /**
258   * Update the vlvIndex for a new entry.
259   *
260   * @param txn A database transaction, or null if none is required.
261   * @param entryID     The entry ID.
262   * @param entry       The entry to be indexed.
263   * @return True if the entry ID for the entry are added. False if
264   *         the entry ID already exists.
265   * @throws DatabaseException If an error occurs in the JE database.
266   * @throws org.opends.server.types.DirectoryException If a Directory Server
267   * error occurs.
268   * @throws JebException If an error occurs in the JE backend.
269   */
270  public boolean addEntry(Transaction txn, EntryID entryID, Entry entry)
271      throws DatabaseException, DirectoryException, JebException
272  {
273    return shouldInclude(entry)
274        && insertValues(txn, entryID.longValue(), entry);
275  }
276
277  /**
278   * Update the vlvIndex for a new entry.
279   *
280   * @param buffer      The index buffer to buffer the changes.
281   * @param entryID     The entry ID.
282   * @param entry       The entry to be indexed.
283   * @return True if the entry ID for the entry are added. False if
284   *         the entry ID already exists.
285   * @throws DirectoryException If a Directory Server
286   * error occurs.
287   */
288  boolean addEntry(IndexBuffer buffer, EntryID entryID, Entry entry) throws DirectoryException
289  {
290    if (shouldInclude(entry))
291    {
292      final SortValues sortValues = new SortValues(entryID, entry, sortOrder);
293      buffer.getVLVIndex(this).addValues(sortValues);
294      return true;
295    }
296    return false;
297  }
298
299  /**
300   * Update the vlvIndex for a deleted entry.
301   *
302   * @param buffer      The database transaction to be used for the deletions
303   * @param entryID     The entry ID
304   * @param entry       The contents of the deleted entry.
305   * @return True if the entry was successfully removed from this VLV index
306   * or False otherwise.
307   * @throws DirectoryException If a Directory Server error occurs.
308   */
309  boolean removeEntry(IndexBuffer buffer, EntryID entryID, Entry entry) throws DirectoryException
310  {
311    if (shouldInclude(entry))
312    {
313      final SortValues sortValues = new SortValues(entryID, entry, sortOrder);
314      buffer.getVLVIndex(this).deleteValues(sortValues);
315      return true;
316    }
317    return false;
318  }
319
320  /**
321   * Update the vlvIndex to reflect a sequence of modifications in a Modify
322   * operation.
323   *
324   * @param buffer The database transaction to be used for the deletions
325   * @param entryID The ID of the entry that was modified.
326   * @param oldEntry The entry before the modifications were applied.
327   * @param newEntry The entry after the modifications were applied.
328   * @param mods The sequence of modifications in the Modify operation.
329   * @return True if the modification was successfully processed or False
330   * otherwise.
331   * @throws DatabaseException If an error occurs during an operation on a
332   * JE database.
333   * @throws DirectoryException If a Directory Server error occurs.
334   */
335  boolean modifyEntry(IndexBuffer buffer,
336                          EntryID entryID,
337                          Entry oldEntry,
338                          Entry newEntry,
339                          List<Modification> mods)
340       throws DatabaseException, DirectoryException
341  {
342    if (shouldInclude(oldEntry))
343    {
344      if (shouldInclude(newEntry))
345      {
346        // The entry should still be indexed. See if any sorted attributes are changed.
347        if (isSortAttributeModified(mods))
348        {
349          // Sorted attributes have changed. Reindex the entry;
350          boolean success;
351          success = removeEntry(buffer, entryID, oldEntry);
352          success &= addEntry(buffer, entryID, newEntry);
353          return success;
354        }
355      }
356      else
357      {
358        // The modifications caused the new entry to be unindexed.
359        return removeEntry(buffer, entryID, oldEntry);
360      }
361    }
362    else
363    {
364      if (shouldInclude(newEntry))
365      {
366        // The modifications caused the new entry to be indexed. Add to vlvIndex
367        return addEntry(buffer, entryID, newEntry);
368      }
369    }
370
371    // The modifications does not affect this vlvIndex
372    return true;
373  }
374
375  private boolean isSortAttributeModified(List<Modification> mods)
376  {
377    for (SortKey sortKey : sortOrder.getSortKeys())
378    {
379      AttributeType attributeType = sortKey.getAttributeType();
380      List<AttributeType> subTypes = DirectoryServer.getSchema().getSubTypes(attributeType);
381      for (Modification mod : mods)
382      {
383        AttributeType modAttrType = mod.getAttribute().getAttributeType();
384        if (modAttrType.equals(attributeType)
385            || subTypes.contains(modAttrType))
386        {
387          return true;
388        }
389      }
390    }
391    return false;
392  }
393
394  /**
395   * Get a sorted values set that should contain the entry with the given
396   * information.
397   *
398   * @param txn The transaction to use when retrieving the set or NULL if it is
399   *            not required.
400   * @param entryID The entry ID to use.
401   * @param values The values to use.
402   * @param types The types of the values to use.
403   * @return The SortValuesSet that should contain the entry with the given
404   *         information.
405   * @throws DatabaseException If an error occurs during an operation on a
406   * JE database.
407   * @throws DirectoryException If a Directory Server error occurs.
408   */
409  SortValuesSet getSortValuesSet(Transaction txn, long entryID,
410      ByteString[] values, AttributeType[] types) throws DatabaseException,
411      DirectoryException
412  {
413    DatabaseEntry key = new DatabaseEntry(encodeKey(entryID, values, types));
414    DatabaseEntry data = new DatabaseEntry();
415    return getSortValuesSet(txn, key, data, LockMode.DEFAULT);
416  }
417
418  private SortValuesSet getSortValuesSet(Transaction txn, DatabaseEntry key,
419      DatabaseEntry data, LockMode lockMode)
420  {
421    OperationStatus status = getSearchKeyRange(txn, key, data, lockMode);
422    if (status != OperationStatus.SUCCESS)
423    {
424      // There are no records in the database
425      if (logger.isTraceEnabled())
426      {
427        logger.trace("No sort values set exist in VLV vlvIndex %s. "
428            + "Creating unbound set.", config.getName());
429      }
430      // this could not be found, so clean the key for later reuse
431      key.setData(new byte[0]);
432      return new SortValuesSet(this);
433    }
434
435    if (logger.isTraceEnabled())
436    {
437      logSearchKeyResult(key);
438    }
439    return new SortValuesSet(key.getData(), data.getData(), this);
440  }
441
442  private void logSearchKeyResult(DatabaseEntry key)
443  {
444    StringBuilder searchKeyHex = new StringBuilder();
445    StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
446    StringBuilder foundKeyHex = new StringBuilder();
447    StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
448    logger.trace("Retrieved a sort values set in VLV vlvIndex %s\n" +
449        "Search Key:%s\nFound Key:%s\n",
450        config.getName(), searchKeyHex, foundKeyHex);
451  }
452
453  /**
454   * Search for entries matching the entry ID and attribute values and
455   * return its entry ID.
456   *
457   * @param txn The JE transaction to use for database updates.
458   * @param entryID The entry ID to search for.
459   * @param values The values to search for.
460   * @param types The types of the values to search for.
461   * @return The index of the entry ID matching the values or -1 if its not
462   * found.
463   * @throws DatabaseException If an error occurs during an operation on a
464   * JE database.
465   * @throws JebException If an error occurs during an operation on a
466   * JE database.
467   * @throws DirectoryException If a Directory Server error occurs.
468   */
469  boolean containsValues(Transaction txn, long entryID,
470      ByteString[] values, AttributeType[] types) throws JebException,
471      DatabaseException, DirectoryException
472  {
473    SortValuesSet valuesSet = getSortValuesSet(txn, entryID, values, types);
474    int pos = valuesSet.binarySearch(entryID, values);
475    return pos >= 0;
476  }
477
478  private boolean insertValues(Transaction txn, long entryID, Entry entry)
479      throws JebException, DatabaseException, DirectoryException
480  {
481    ByteString[] values = getSortValues(entry);
482    AttributeType[] types = getSortTypes();
483    DatabaseEntry key = new DatabaseEntry(encodeKey(entryID, values, types));
484    DatabaseEntry data = new DatabaseEntry();
485
486    SortValuesSet sortValuesSet =
487        getSortValuesSet(txn, key, data, LockMode.RMW);
488    boolean success = sortValuesSet.add(entryID, values, types);
489
490    int newSize = sortValuesSet.size();
491    if(newSize >= sortedSetCapacity)
492    {
493      SortValuesSet splitSortValuesSet = sortValuesSet.split(newSize / 2);
494      put(txn, key, data, splitSortValuesSet); // splitAfter
495      put(txn, key, data, sortValuesSet); // after
496
497      if(logger.isTraceEnabled())
498      {
499        logger.trace("SortValuesSet with key %s has reached" +
500            " the entry size of %d. Spliting into two sets with " +
501            " keys %s and %s.", splitSortValuesSet.getKeySortValues(),
502                                newSize, sortValuesSet.getKeySortValues(),
503                                splitSortValuesSet.getKeySortValues());
504      }
505    }
506    else
507    {
508      data.setData(sortValuesSet.toDatabase()); // after
509      put(txn, key, data);
510      // TODO: What about phantoms?
511    }
512
513    if(success)
514    {
515      count.getAndIncrement();
516    }
517
518    return success;
519  }
520
521  private void put(Transaction txn, DatabaseEntry key, DatabaseEntry data,
522      SortValuesSet set) throws DirectoryException
523  {
524    key.setData(set.getKeyBytes());
525    data.setData(set.toDatabase());
526    put(txn, key, data);
527  }
528
529  /**
530   * Gets the types of the attribute values to sort.
531   *
532   * @return The types of the attribute values to sort on.
533   */
534  AttributeType[] getSortTypes()
535  {
536    SortKey[] sortKeys = sortOrder.getSortKeys();
537    AttributeType[] types = new AttributeType[sortKeys.length];
538    for (int i = 0; i < sortKeys.length; i++)
539    {
540      types[i] = sortKeys[i].getAttributeType();
541    }
542    return types;
543  }
544
545  private OperationStatus getSearchKeyRange(Transaction txn, DatabaseEntry key,
546      DatabaseEntry data, LockMode lockMode)
547  {
548    Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
549    try
550    {
551      return cursor.getSearchKeyRange(key, data, lockMode);
552    }
553    finally
554    {
555      cursor.close();
556    }
557  }
558
559  /**
560   * Update the vlvIndex with the specified values to add and delete.
561   *
562   * @param txn A database transaction, or null if none is required.
563   * @param addedValues The values to add to the VLV index.
564   * @param deletedValues The values to delete from the VLV index.
565   * @throws DatabaseException If an error occurs in the JE database.
566   * @throws DirectoryException If a Directory Server
567   * error occurs.
568   */
569  void updateIndex(Transaction txn, TreeSet<SortValues> addedValues, TreeSet<SortValues> deletedValues)
570      throws DirectoryException, DatabaseException
571  {
572    // Handle cases where nothing is changed early to avoid
573    // DB access.
574    if((addedValues == null || addedValues.isEmpty()) &&
575        (deletedValues == null || deletedValues.isEmpty()))
576    {
577      return;
578    }
579
580    DatabaseEntry key = new DatabaseEntry();
581    DatabaseEntry data = new DatabaseEntry();
582    Iterator<SortValues> aValues = null;
583    Iterator<SortValues> dValues = null;
584    SortValues av = null;
585    SortValues dv = null;
586
587    if(addedValues != null)
588    {
589      aValues = addedValues.iterator();
590      av = aValues.next();
591    }
592    if(deletedValues != null)
593    {
594      dValues = deletedValues.iterator();
595      dv = dValues.next();
596    }
597
598    while(true)
599    {
600      if(av != null)
601      {
602        if(dv != null)
603        {
604          // Start from the smallest values from either set.
605          if(av.compareTo(dv) < 0)
606          {
607            key.setData(encodeKey(av));
608          }
609          else
610          {
611            key.setData(encodeKey(dv));
612          }
613        }
614        else
615        {
616          key.setData(encodeKey(av));
617        }
618      }
619      else if(dv != null)
620      {
621        key.setData(encodeKey(dv));
622      }
623      else
624      {
625        break;
626      }
627
628      final SortValuesSet sortValuesSet = getSortValuesSet(txn, key, data, LockMode.RMW);
629      int oldSize = sortValuesSet.size();
630      if(key.getData().length == 0)
631      {
632        // This is the last unbounded set.
633        while(av != null)
634        {
635          sortValuesSet.add(av);
636          av = moveToNextSortValues(aValues);
637        }
638
639        while(dv != null)
640        {
641          sortValuesSet.remove(dv);
642          dv = moveToNextSortValues(dValues);
643        }
644      }
645      else
646      {
647        SortValues maxValues = decodeKey(sortValuesSet.getKeyBytes());
648
649        while(av != null && av.compareTo(maxValues) <= 0)
650        {
651          sortValuesSet.add(av);
652          av = moveToNextSortValues(aValues);
653        }
654
655        while(dv != null && dv.compareTo(maxValues) <= 0)
656        {
657          sortValuesSet.remove(dv);
658          dv = moveToNextSortValues(dValues);
659        }
660      }
661
662      int newSize = sortValuesSet.size();
663      if(newSize >= sortedSetCapacity)
664      {
665        SortValuesSet splitSortValuesSet = sortValuesSet.split(newSize / 2);
666        put(txn, key, data, splitSortValuesSet); // splitAfter
667        put(txn, key, data, sortValuesSet); // after
668
669        if(logger.isTraceEnabled())
670        {
671          logger.trace("SortValuesSet with key %s has reached" +
672              " the entry size of %d. Spliting into two sets with " +
673              " keys %s and %s.", splitSortValuesSet.getKeySortValues(),
674              newSize, sortValuesSet.getKeySortValues(),
675              splitSortValuesSet.getKeySortValues());
676        }
677      }
678      else if(newSize == 0)
679      {
680        delete(txn, key);
681      }
682      else
683      {
684        byte[] after = sortValuesSet.toDatabase();
685        data.setData(after);
686        put(txn, key, data);
687      }
688
689      count.getAndAdd(newSize - oldSize);
690    }
691  }
692
693  private SortValues moveToNextSortValues(Iterator<SortValues> sortValues)
694  {
695    sortValues.remove();
696    if (sortValues.hasNext())
697    {
698      return sortValues.next();
699    }
700    return null;
701  }
702
703  private byte[] encodeKey(SortValues sv) throws DirectoryException
704  {
705    return encodeKey(sv.getEntryID(), sv.getValues(), sv.getTypes());
706  }
707
708  /**
709   * Evaluate a search with sort control using this VLV index.
710   *
711   * @param txn The transaction to used when reading the index or NULL if it is
712   *            not required.
713   * @param searchOperation The search operation to evaluate.
714   * @param sortControl The sort request control to evaluate.
715   * @param vlvRequest The VLV request control to evaluate or NULL if VLV is not
716   *                   requested.
717   * @param debugBuilder If not null, a diagnostic string will be written
718   *                     which will help determine how this index contributed
719   *                     to this search.
720   * @return The sorted EntryIDSet containing the entry IDs that match the
721   *         search criteria.
722   * @throws DirectoryException If a Directory Server error occurs.
723   * @throws DatabaseException If an error occurs in the JE database.
724   */
725  EntryIDSet evaluate(Transaction txn,
726                             SearchOperation searchOperation,
727                             ServerSideSortRequestControl sortControl,
728                             VLVRequestControl vlvRequest,
729                             StringBuilder debugBuilder)
730      throws DirectoryException, DatabaseException
731  {
732    if (!trusted
733        || !searchOperation.getBaseDN().equals(baseDN)
734        || !searchOperation.getScope().equals(scope)
735        || !searchOperation.getFilter().equals(filter)
736        || !sortControl.getSortOrder().equals(sortOrder))
737    {
738      return null;
739    }
740
741    if (debugBuilder != null)
742    {
743      debugBuilder.append("vlv=");
744      debugBuilder.append("[INDEX:");
745      debugBuilder.append(name.replace(entryContainer.getDatabasePrefix() + "_", ""));
746      debugBuilder.append("]");
747    }
748
749    long[] selectedIDs = new long[0];
750    if(vlvRequest != null)
751    {
752      int currentCount = count.get();
753      int beforeCount = vlvRequest.getBeforeCount();
754      int afterCount  = vlvRequest.getAfterCount();
755
756      if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET)
757      {
758        int targetOffset = vlvRequest.getOffset();
759        if (targetOffset < 0)
760        {
761          // The client specified a negative target offset.  This should never
762          // be allowed.
763          searchOperation.addResponseControl(
764              new VLVResponseControl(targetOffset, currentCount,
765                                     LDAPResultCode.OFFSET_RANGE_ERROR));
766
767          LocalizableMessage message = ERR_ENTRYIDSORTER_NEGATIVE_START_POS.get();
768          throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR,
769                                       message);
770        }
771        else if (targetOffset == 0)
772        {
773          // This is an easy mistake to make, since VLV offsets start at 1
774          // instead of 0.  We'll assume the client meant to use 1.
775          targetOffset = 1;
776        }
777        int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0.
778        int startPos = listOffset - beforeCount;
779        if (startPos < 0)
780        {
781          // This can happen if beforeCount >= offset, and in this case we'll
782          // just adjust the start position to ignore the range of beforeCount
783          // that doesn't exist.
784          startPos    = 0;
785          beforeCount = listOffset;
786        }
787        else if(startPos >= currentCount)
788        {
789          // The start position is beyond the end of the list.  In this case,
790          // we'll assume that the start position was one greater than the
791          // size of the list and will only return the beforeCount entries.
792          // The start position is beyond the end of the list.  In this case,
793          // we'll assume that the start position was one greater than the
794          // size of the list and will only return the beforeCount entries.
795          targetOffset = currentCount + 1;
796          listOffset   = currentCount;
797          startPos     = listOffset - beforeCount;
798          afterCount   = 0;
799        }
800
801        int count = 1 + beforeCount + afterCount;
802        selectedIDs = new long[count];
803
804        Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
805        try
806        {
807          DatabaseEntry key = new DatabaseEntry();
808          DatabaseEntry data = new DatabaseEntry();
809          LockMode lockMode = LockMode.DEFAULT;
810          //Locate the set that contains the target entry.
811          int cursorCount = 0;
812          int selectedPos = 0;
813          OperationStatus status = cursor.getFirst(key, data, lockMode);
814          while(status == OperationStatus.SUCCESS)
815          {
816            if(logger.isTraceEnabled())
817            {
818              logSearchKeyResult(key);
819            }
820            long[] IDs = SortValuesSet.getEncodedIDs(data.getData(), 0);
821            for(int i = startPos + selectedPos - cursorCount;
822                i < IDs.length && selectedPos < count;
823                i++, selectedPos++)
824            {
825              selectedIDs[selectedPos] = IDs[i];
826            }
827            cursorCount += IDs.length;
828            status = cursor.getNext(key, data,lockMode);
829          }
830
831          if (selectedPos < count)
832          {
833            // We don't have enough entries in the set to meet the requested
834            // page size, so we'll need to shorten the array.
835            long[] newIDArray = new long[selectedPos];
836            System.arraycopy(selectedIDs, 0, newIDArray, 0, selectedPos);
837            selectedIDs = newIDArray;
838          }
839
840          searchOperation.addResponseControl(
841              new VLVResponseControl(targetOffset, currentCount,
842                                     LDAPResultCode.SUCCESS));
843
844          if(debugBuilder != null)
845          {
846            debugBuilder.append("[COUNT:");
847            debugBuilder.append(cursorCount);
848            debugBuilder.append("]");
849          }
850        }
851        finally
852        {
853          cursor.close();
854        }
855      }
856      else
857      {
858        int targetOffset = 0;
859        int includedBeforeCount = 0;
860        int includedAfterCount  = 0;
861        LinkedList<EntryID> idList = new LinkedList<>();
862        DatabaseEntry key = new DatabaseEntry();
863        DatabaseEntry data = new DatabaseEntry();
864
865        Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
866        try
867        {
868          LockMode lockMode = LockMode.DEFAULT;
869          ByteSequence vBytes = vlvRequest.getGreaterThanOrEqualAssertion();
870          ByteStringBuilder keyBytes =
871              new ByteStringBuilder(vBytes.length() + 4);
872          keyBytes.appendBERLength(vBytes.length());
873          vBytes.copyTo(keyBytes);
874
875          key.setData(keyBytes.getBackingArray(), 0, keyBytes.length());
876          OperationStatus status = cursor.getSearchKeyRange(key, data, lockMode);
877          if(status == OperationStatus.SUCCESS)
878          {
879            if(logger.isTraceEnabled())
880            {
881              logSearchKeyResult(key);
882            }
883            SortValuesSet sortValuesSet =
884                new SortValuesSet(key.getData(), data.getData(), this);
885
886            int adjustedTargetOffset = sortValuesSet.binarySearch(
887                -1, vlvRequest.getGreaterThanOrEqualAssertion());
888            if(adjustedTargetOffset < 0)
889            {
890              // For a negative return value r, the vlvIndex -(r+1) gives the
891              // array index of the ID that is greater then the assertion value.
892              adjustedTargetOffset = -(adjustedTargetOffset+1);
893            }
894
895            targetOffset = adjustedTargetOffset;
896
897            // Iterate through all the sort values sets before this one to find
898            // the target offset in the index.
899            int lastOffset = adjustedTargetOffset - 1;
900            long[] lastIDs = sortValuesSet.getEntryIDs();
901            while(true)
902            {
903              for(int i = lastOffset;
904                  i >= 0 && includedBeforeCount < beforeCount; i--)
905              {
906                idList.addFirst(new EntryID(lastIDs[i]));
907                includedBeforeCount++;
908              }
909
910              status = cursor.getPrev(key, data, lockMode);
911              if(status != OperationStatus.SUCCESS)
912              {
913                break;
914              }
915
916              if(includedBeforeCount < beforeCount)
917              {
918                lastIDs = SortValuesSet.getEncodedIDs(data.getData(), 0);
919                lastOffset = lastIDs.length - 1;
920                targetOffset += lastIDs.length;
921              }
922              else
923              {
924                targetOffset += SortValuesSet.getEncodedSize(data.getData(), 0);
925              }
926            }
927
928
929            // Set the cursor back to the position of the target entry set
930            key.setData(sortValuesSet.getKeyBytes());
931            cursor.getSearchKey(key, data, lockMode);
932
933            // Add the target and after count entries if the target was found.
934            lastOffset = adjustedTargetOffset;
935            lastIDs = sortValuesSet.getEntryIDs();
936            int afterIDCount = 0;
937            while(true)
938            {
939              for(int i = lastOffset;
940                  i < lastIDs.length && includedAfterCount < afterCount + 1;
941                  i++)
942              {
943                idList.addLast(new EntryID(lastIDs[i]));
944                includedAfterCount++;
945              }
946
947              if(includedAfterCount >= afterCount + 1)
948              {
949                break;
950              }
951
952              status = cursor.getNext(key, data, lockMode);
953              if(status != OperationStatus.SUCCESS)
954              {
955                break;
956              }
957
958              lastIDs = SortValuesSet.getEncodedIDs(data.getData(), 0);
959              lastOffset = 0;
960              afterIDCount += lastIDs.length;
961            }
962
963            selectedIDs = new long[idList.size()];
964            Iterator<EntryID> idIterator = idList.iterator();
965            for (int i=0; i < selectedIDs.length; i++)
966            {
967              selectedIDs[i] = idIterator.next().longValue();
968            }
969
970            searchOperation.addResponseControl(
971                new VLVResponseControl(targetOffset + 1, currentCount,
972                                       LDAPResultCode.SUCCESS));
973
974            if(debugBuilder != null)
975            {
976              debugBuilder.append("[COUNT:");
977              debugBuilder.append(targetOffset + afterIDCount + 1);
978              debugBuilder.append("]");
979            }
980          }
981        }
982        finally
983        {
984          cursor.close();
985        }
986      }
987    }
988    else
989    {
990      LinkedList<long[]> idSets = new LinkedList<>();
991      int currentCount = 0;
992      DatabaseEntry key = new DatabaseEntry();
993      DatabaseEntry data = new DatabaseEntry();
994
995      Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);
996      try
997      {
998        LockMode lockMode = LockMode.RMW;
999        OperationStatus status = cursor.getFirst(key, data, lockMode);
1000        while(status == OperationStatus.SUCCESS)
1001        {
1002          if(logger.isTraceEnabled())
1003          {
1004            logSearchKeyResult(key);
1005          }
1006          long[] ids = SortValuesSet.getEncodedIDs(data.getData(), 0);
1007          idSets.add(ids);
1008          currentCount += ids.length;
1009          status = cursor.getNext(key, data, lockMode);
1010        }
1011      }
1012      finally
1013      {
1014        cursor.close();
1015      }
1016
1017      selectedIDs = new long[currentCount];
1018      int pos = 0;
1019      for(long[] id : idSets)
1020      {
1021        System.arraycopy(id, 0, selectedIDs, pos, id.length);
1022        pos += id.length;
1023      }
1024
1025      if(debugBuilder != null)
1026      {
1027        debugBuilder.append("[COUNT:");
1028        debugBuilder.append(currentCount);
1029        debugBuilder.append("]");
1030      }
1031    }
1032    return new EntryIDSet(selectedIDs, 0, selectedIDs.length);
1033  }
1034
1035    /**
1036   * Set the vlvIndex trust state.
1037   * @param txn A database transaction, or null if none is required.
1038   * @param trusted True if this vlvIndex should be trusted or false
1039   *                otherwise.
1040   * @throws DatabaseException If an error occurs in the JE database.
1041   */
1042  public synchronized void setTrusted(Transaction txn, boolean trusted)
1043      throws DatabaseException
1044  {
1045    this.trusted = trusted;
1046    state.putIndexTrustState(txn, this, trusted);
1047  }
1048
1049  /**
1050   * Return true iff this index is trusted.
1051   * @return the trusted state of this index
1052   */
1053  public boolean isTrusted()
1054  {
1055    return trusted;
1056  }
1057
1058  /**
1059   * Gets the values to sort on from the entry.
1060   *
1061   * @param entry The entry to get the values from.
1062   * @return The attribute values to sort on.
1063   */
1064  ByteString[] getSortValues(Entry entry)
1065  {
1066    SortKey[] sortKeys = sortOrder.getSortKeys();
1067    ByteString[] values = new ByteString[sortKeys.length];
1068    for (int i=0; i < sortKeys.length; i++)
1069    {
1070      SortKey sortKey = sortKeys[i];
1071      List<Attribute> attrList = entry.getAttribute(sortKey.getAttributeType());
1072      if (attrList != null)
1073      {
1074        // There may be multiple versions of this attribute in the target entry
1075        // (e.g., with different sets of options), and it may also be a
1076        // multivalued attribute.  In that case, we need to find the value that
1077        // is the best match for the corresponding sort key (i.e., for sorting
1078        // in ascending order, we want to find the lowest value; for sorting in
1079        // descending order, we want to find the highest value).  This is
1080        // handled by the SortKey.compareValues method.
1081        ByteString sortValue = null;
1082        for (Attribute a : attrList)
1083        {
1084          for (ByteString v : a)
1085          {
1086            if (sortValue == null || sortKey.compareValues(v, sortValue) < 0)
1087            {
1088              sortValue = v;
1089            }
1090          }
1091        }
1092
1093        values[i] = sortValue;
1094      }
1095    }
1096    return values;
1097  }
1098
1099  /**
1100   * Encode a VLV database key with the given information.
1101   *
1102   * @param entryID The entry ID to encode.
1103   * @param values The values to encode.
1104   * @param types The types of the values to encode.
1105   * @return The encoded bytes.
1106   * @throws DirectoryException If a Directory Server error occurs.
1107   */
1108  byte[] encodeKey(long entryID, ByteString[] values, AttributeType[] types)
1109      throws DirectoryException
1110  {
1111    try
1112    {
1113      final ByteStringBuilder builder = new ByteStringBuilder();
1114
1115      for (int i = 0; i < values.length; i++)
1116      {
1117        final ByteString v = values[i];
1118        if (v == null)
1119        {
1120          builder.appendBERLength(0);
1121        }
1122        else
1123        {
1124          final MatchingRule eqRule = types[i].getEqualityMatchingRule();
1125          final ByteString nv = eqRule.normalizeAttributeValue(v);
1126          builder.appendBERLength(nv.length());
1127          builder.append(nv);
1128        }
1129      }
1130      builder.append(entryID);
1131      builder.trimToSize();
1132
1133      return builder.getBackingArray();
1134    }
1135    catch (DecodeException e)
1136    {
1137      throw new DirectoryException(
1138          ResultCode.INVALID_ATTRIBUTE_SYNTAX, e.getMessageObject(), e);
1139    }
1140  }
1141
1142  /**
1143   * Decode a VLV database key.
1144   *
1145   * @param  keyBytes The byte array to decode.
1146   * @return The sort values represented by the key bytes.
1147   * @throws DirectoryException If a Directory Server error occurs.
1148   */
1149  private SortValues decodeKey(byte[] keyBytes) throws DirectoryException
1150  {
1151    if(keyBytes == null || keyBytes.length == 0)
1152    {
1153      return null;
1154    }
1155
1156    ByteString[] attributeValues = new ByteString[sortOrder.getSortKeys().length];
1157    int vBytesPos = 0;
1158
1159    for(int i = 0; i < attributeValues.length; i++)
1160    {
1161      int valueLength = keyBytes[vBytesPos] & 0x7F;
1162      if (valueLength != keyBytes[vBytesPos++])
1163      {
1164        int valueLengthBytes = valueLength;
1165        valueLength = 0;
1166        for (int j=0; j < valueLengthBytes; j++, vBytesPos++)
1167        {
1168          valueLength = (valueLength << 8) | (keyBytes[vBytesPos] & 0xFF);
1169        }
1170      }
1171
1172      if(valueLength == 0)
1173      {
1174        attributeValues[i] = null;
1175      }
1176      else
1177      {
1178        byte[] valueBytes = new byte[valueLength];
1179        System.arraycopy(keyBytes, vBytesPos, valueBytes, 0, valueLength);
1180        attributeValues[i] = ByteString.wrap(valueBytes);
1181      }
1182
1183      vBytesPos += valueLength;
1184    }
1185
1186    final long id = JebFormat.toLong(keyBytes, vBytesPos, keyBytes.length);
1187    return new SortValues(new EntryID(id), attributeValues, sortOrder);
1188  }
1189
1190  /**
1191   * Get the sorted set capacity configured for this VLV index.
1192   *
1193   * @return The sorted set capacity.
1194   */
1195  public int getSortedSetCapacity()
1196  {
1197    return sortedSetCapacity;
1198  }
1199
1200  /**
1201   * Indicates if the given entry should belong in this VLV index.
1202   *
1203   * @param entry The entry to check.
1204   * @return True if the given entry should belong in this VLV index or False
1205   *         otherwise.
1206   * @throws DirectoryException If a Directory Server error occurs.
1207   */
1208  boolean shouldInclude(Entry entry) throws DirectoryException
1209  {
1210    DN entryDN = entry.getName();
1211    return entryDN.matchesBaseAndScope(baseDN, scope)
1212        && filter.matchesEntry(entry);
1213  }
1214
1215  /** {@inheritDoc} */
1216  @Override
1217  public synchronized boolean isConfigurationChangeAcceptable(
1218      LocalDBVLVIndexCfg cfg,
1219      List<LocalizableMessage> unacceptableReasons)
1220  {
1221    try
1222    {
1223      this.filter = SearchFilter.createFilterFromString(cfg.getFilter());
1224    }
1225    catch(Exception e)
1226    {
1227      unacceptableReasons.add(ERR_CONFIG_VLV_INDEX_BAD_FILTER.get(
1228              cfg.getFilter(), name, stackTraceToSingleLineString(e)));
1229      return false;
1230    }
1231
1232    String[] sortAttrs = cfg.getSortOrder().split(" ");
1233    SortKey[] sortKeys = new SortKey[sortAttrs.length];
1234    MatchingRule[] orderingRules = new MatchingRule[sortAttrs.length];
1235    boolean[] ascending = new boolean[sortAttrs.length];
1236    for(int i = 0; i < sortAttrs.length; i++)
1237    {
1238      try
1239      {
1240        if(sortAttrs[i].startsWith("-"))
1241        {
1242          ascending[i] = false;
1243          sortAttrs[i] = sortAttrs[i].substring(1);
1244        }
1245        else
1246        {
1247          ascending[i] = true;
1248          if(sortAttrs[i].startsWith("+"))
1249          {
1250            sortAttrs[i] = sortAttrs[i].substring(1);
1251          }
1252        }
1253      }
1254      catch(Exception e)
1255      {
1256        unacceptableReasons.add(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name));
1257        return false;
1258      }
1259
1260      AttributeType attrType = DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
1261      if(attrType == null)
1262      {
1263        unacceptableReasons.add(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortAttrs[i], name));
1264        return false;
1265      }
1266      sortKeys[i] = new SortKey(attrType, ascending[i]);
1267      orderingRules[i] = attrType.getOrderingMatchingRule();
1268    }
1269
1270    return true;
1271  }
1272
1273  /** {@inheritDoc} */
1274  @Override
1275  public synchronized ConfigChangeResult applyConfigurationChange(
1276      LocalDBVLVIndexCfg cfg)
1277  {
1278    final ConfigChangeResult ccr = new ConfigChangeResult();
1279
1280    // Update base DN only if changed..
1281    if(!config.getBaseDN().equals(cfg.getBaseDN()))
1282    {
1283      this.baseDN = cfg.getBaseDN();
1284      ccr.setAdminActionRequired(true);
1285    }
1286
1287    // Update scope only if changed.
1288    if(!config.getScope().equals(cfg.getScope()))
1289    {
1290      this.scope = convertScope(cfg.getScope());
1291      ccr.setAdminActionRequired(true);
1292    }
1293
1294    // Update sort set capacity only if changed.
1295    if (config.getMaxBlockSize() != cfg.getMaxBlockSize())
1296    {
1297      this.sortedSetCapacity = cfg.getMaxBlockSize();
1298
1299      // Require admin action only if the new capacity is larger. Otherwise,
1300      // we will lazyly update the sorted sets.
1301      if (config.getMaxBlockSize() < cfg.getMaxBlockSize())
1302      {
1303        ccr.setAdminActionRequired(true);
1304      }
1305    }
1306
1307    // Update the filter only if changed.
1308    if(!config.getFilter().equals(cfg.getFilter()))
1309    {
1310      try
1311      {
1312        this.filter = SearchFilter.createFilterFromString(cfg.getFilter());
1313        ccr.setAdminActionRequired(true);
1314      }
1315      catch(Exception e)
1316      {
1317        ccr.addMessage(ERR_CONFIG_VLV_INDEX_BAD_FILTER.get(config.getFilter(), name, stackTraceToSingleLineString(e)));
1318        ccr.setResultCodeIfSuccess(ResultCode.INVALID_ATTRIBUTE_SYNTAX);
1319      }
1320    }
1321
1322    // Update the sort order only if changed.
1323    if (!config.getSortOrder().equals(cfg.getSortOrder()))
1324    {
1325      String[] sortAttrs = cfg.getSortOrder().split(" ");
1326      SortKey[] sortKeys = new SortKey[sortAttrs.length];
1327      MatchingRule[] orderingRules = new MatchingRule[sortAttrs.length];
1328      boolean[] ascending = new boolean[sortAttrs.length];
1329      for(int i = 0; i < sortAttrs.length; i++)
1330      {
1331        try
1332        {
1333          if(sortAttrs[i].startsWith("-"))
1334          {
1335            ascending[i] = false;
1336            sortAttrs[i] = sortAttrs[i].substring(1);
1337          }
1338          else
1339          {
1340            ascending[i] = true;
1341            if(sortAttrs[i].startsWith("+"))
1342            {
1343              sortAttrs[i] = sortAttrs[i].substring(1);
1344            }
1345          }
1346        }
1347        catch(Exception e)
1348        {
1349          ccr.addMessage(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name));
1350          ccr.setResultCodeIfSuccess(ResultCode.INVALID_ATTRIBUTE_SYNTAX);
1351        }
1352
1353        AttributeType attrType =
1354            DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
1355        if(attrType == null)
1356        {
1357          ccr.addMessage(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name));
1358          ccr.setResultCodeIfSuccess(ResultCode.INVALID_ATTRIBUTE_SYNTAX);
1359        }
1360        else
1361        {
1362          sortKeys[i] = new SortKey(attrType, ascending[i]);
1363          orderingRules[i] = attrType.getOrderingMatchingRule();
1364        }
1365      }
1366
1367      this.sortOrder = new SortOrder(sortKeys);
1368      this.comparator = new VLVKeyComparator(orderingRules, ascending);
1369
1370      // We have to close the database and open it using the new comparator.
1371      entryContainer.exclusiveLock.lock();
1372      try
1373      {
1374        close();
1375        this.dbConfig.setBtreeComparator(this.comparator);
1376        open();
1377      }
1378      catch(DatabaseException de)
1379      {
1380        ccr.addMessage(LocalizableMessage.raw(StaticUtils.stackTraceToSingleLineString(de)));
1381        ccr.setResultCodeIfSuccess(DirectoryServer.getServerErrorResultCode());
1382      }
1383      finally
1384      {
1385        entryContainer.exclusiveLock.unlock();
1386      }
1387
1388      ccr.setAdminActionRequired(true);
1389    }
1390
1391
1392    if (ccr.adminActionRequired())
1393    {
1394      trusted = false;
1395      ccr.addMessage(NOTE_INDEX_ADD_REQUIRES_REBUILD.get(name));
1396      try
1397      {
1398        state.putIndexTrustState(null, this, false);
1399      }
1400      catch(DatabaseException de)
1401      {
1402        ccr.addMessage(LocalizableMessage.raw(StaticUtils.stackTraceToSingleLineString(de)));
1403        ccr.setResultCodeIfSuccess(DirectoryServer.getServerErrorResultCode());
1404      }
1405    }
1406
1407    this.config = cfg;
1408    return ccr;
1409  }
1410}