These set of changes implement VLV and filter capability to OpenDS:

boli

27.06.2007 05875933ae6929bc8e53f366ce116f2fc431fd46

These set of changes implement VLV and filter capability to OpenDS:

- A VLV index is defined by a name, base DN, search filter, search scope, sort order. A search request must match these parameters exactly to 
use the VLV index.
- A VLV index made up of the entry IDs matching the definition criteria (above) and the corresponding attribute values that are part of the sort 
order in the sort order. This information is broken up into blocks of sorted sets. The block size can be configured through admin framework. 
Default block size is 4000. In the database, the sorted set is stored with the following format:

      4 byte set size | entry IDs of 8 bytes each ... | attribute values of 16 bytes each ...

- Each sorted set is keyed by the entry ID and attribute values of the largest entry in the sorted set. A special comparator (VLVKeyComparator) 
is used to sort the keys in the database in the order of the specified sort order.
- When entries are added to the VLV index, its sort values are extracted and inserted into the sorted set whose key (also the largest entry in 
the set) is the smallest key that represents a entry that is greater or equal to the entry being inserted. If the sorted set exceeds the block 
size, it is divided in two and stored back into the database with the new key. In this implementation, a sorted set's key is never changed after 
it is created.
- On importing from LDIF, each entry's sort values and ID is written out to a intermediate file in order. These files are later merged and 
inserted into the database.
- Index rebuild and verify also works with VLV indexes. The verify job ensures that all the entries stored in the VLV index is in the correct 
order.
- With this implementation, once a VLV index is created, it can not be changed without a rebuild. The server will NOT warn the user if 
the index 
has changed offline. Until a rebuild is done, it can return incorrect results. This should be fixed later.
- Performance wise, modify, add, and delete performance will be degraded if the entry matches the indexing criteria. Searches not using the VLV 
index should not see any notable performance degradation. If the block size is set too big, there is a potential that a large number of updates 
will result in some JE lock timeouts since the few sorted sets are hotly contested. However, if the block size is too small, searches using the 
VLV control with offsets could be slow since there are more records to look through. This area need further investigation to determine the 
optimal default value.

Fix for issue 38

 opends/resource/admin/abbreviations.xsl

@@ -48,7 +48,7 @@
              or $value = 'jdbc' or $value = 'tcp' or $value = 'tls'
              or $value = 'pkcs11' or $value = 'sasl' or $value = 'gssapi'
              or $value = 'md5' or $value = 'je' or $value = 'dse'
              or $value = 'fifo'
              or $value = 'fifo' or $value= 'vlv'
             "/>
  </xsl:template>
</xsl:stylesheet>

 opends/resource/config/config.ldif

@@ -223,6 +223,11 @@
ds-cfg-index-attribute: entryuuid
ds-cfg-index-type: equality

dn: cn=VLV Index,ds-cfg-backend-id=userRoot,cn=Backends,cn=config
objectClass: top
objectClass: ds-cfg-branch
cn: VLV Index

dn: ds-cfg-backend-id=backup,cn=Backends,cn=config
objectClass: top
objectClass: ds-cfg-backend

 opends/resource/schema/02-config.ldif

@@ -1475,6 +1475,24 @@
  NAME 'ds-cfg-strip-syntax-minimum-upper-bound'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.7 SINGLE-VALUE
  X-ORIGIN 'OpenDS Directory Server' )
attributeTypes: ( 1.3.6.1.4.1.26027.1.1.437
  NAME 'ds-cfg-vlv-je-index-base-dn'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.12 X-ORIGIN 'OpenDS Directory Server' )
attributeTypes: ( 1.3.6.1.4.1.26027.1.1.438
  NAME 'ds-cfg-vlv-je-index-scope'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.15 X-ORIGIN 'OpenDS Directory Server' )
attributeTypes: ( 1.3.6.1.4.1.26027.1.1.439
  NAME 'ds-cfg-vlv-je-index-filter'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.15 X-ORIGIN 'OpenDS Directory Server' )
attributeTypes: ( 1.3.6.1.4.1.26027.1.1.440
  NAME 'ds-cfg-vlv-je-index-sort-order'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.15 X-ORIGIN 'OpenDS Directory Server' )
attributeTypes: ( 1.3.6.1.4.1.26027.1.1.441
  NAME 'ds-cfg-vlv-je-index-name'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.15 X-ORIGIN 'OpenDS Directory Server' )
attributeTypes: ( 1.3.6.1.4.1.26027.1.1.442
  NAME 'ds-cfg-vlv-je-index-maximum-block-size'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.27 X-ORIGIN 'OpenDS Directory Server' )
attributeTypes: ( 1.3.6.1.4.1.26027.1.1.443
  NAME 'ds-cfg-state-update-failure-policy'
  SYNTAX 1.3.6.1.4.1.1466.115.121.1.15 SINGLE-VALUE
@@ -2108,6 +2126,13 @@
  MAY ( ds-cfg-default-user-password-storage-scheme $
  ds-cfg-default-auth-password-storage-scheme )
  X-ORIGIN 'OpenDS Directory Server' )
objectClasses: ( 1.3.6.1.4.1.26027.1.2.117
  NAME 'ds-cfg-vlv-je-index' SUP top STRUCTURAL
  MUST ( ds-cfg-vlv-je-index-base-dn $ ds-cfg-vlv-je-index-scope $
         ds-cfg-vlv-je-index-filter $ ds-cfg-vlv-je-index-sort-order $
         ds-cfg-vlv-je-index-name )
  MAY  ( ds-cfg-vlv-je-index-maximum-block-size )
  X-ORIGIN 'OpenDS Directory Server' )
objectClasses: ( 1.3.6.1.4.1.26027.1.2.118
  NAME 'ds-cfg-smtp-alert-handler' SUP ds-cfg-alert-handler STRUCTURAL
  MUST ( ds-cfg-sender-address $ ds-cfg-recipient-address $

 opends/src/admin/defn/org/opends/server/admin/std/JEBackendConfiguration.xml

@@ -66,6 +66,22 @@
      </cli:relation>
    </adm:profile>
  </adm:relation>
  <adm:relation name="vlv-je-index">
    <adm:one-to-many naming-property="vlv-index-name"/>
     <adm:profile name="ldap">
      <ldap:rdn-sequence>
        cn=VLV Index
      </ldap:rdn-sequence>
    </adm:profile>
    <adm:profile name="cli">
      <cli:relation>
        <cli:default-property name="vlv-index-base-dn" />
        <cli:default-property name="vlv-index-scope" />
        <cli:default-property name="vlv-index-filter" />
        <cli:default-property name="vlv-index-sort-order" />
      </cli:relation>
    </adm:profile>
  </adm:relation>
  <adm:property-override name="backend-class">
    <adm:default-behavior>
      <adm:defined>

 opends/src/admin/defn/org/opends/server/admin/std/VLVJEIndexConfiguration.xml

New file
@@ -0,0 +1,219 @@
<?xml version="1.0" encoding="UTF-8"?>
<!--
 ! CDDL HEADER START
 !
 ! The contents of this file are subject to the terms of the
 ! Common Development and Distribution License, Version 1.0 only
 ! (the "License").  You may not use this file except in compliance
 ! with the License.
 !
 ! You can obtain a copy of the license at
 ! trunk/opends/resource/legal-notices/OpenDS.LICENSE
 ! or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 ! See the License for the specific language governing permissions
 ! and limitations under the License.
 !
 ! When distributing Covered Code, include this CDDL HEADER in each
 ! file and include the License file at
 ! trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 ! add the following below this CDDL HEADER, with the fields enclosed
 ! by brackets "[]" replaced with your own identifying information:
 !      Portions Copyright [yyyy] [name of copyright owner]
 !
 ! CDDL HEADER END
 !
 !
 !      Portions Copyright 2007 Sun Microsystems, Inc.
 ! -->

<adm:managed-object name="vlv-je-index" plural-name="vlv-je-indexes"
  package="org.opends.server.admin.std"
  xmlns:adm="http://www.opends.org/admin"
  xmlns:ldap="http://www.opends.org/admin-ldap">
  <adm:synopsis>
    The <adm:user-friendly-plural-name/> are used to store information about
    a specific search request that makes it possible to efficiently process
    them using the VLV control.
  </adm:synopsis>
  <adm:description>
    A VLV index effectively notifies the server that a virtual list view, with
    specific query and sort parameters, will be performed. This index also
    allows the server to collect and maintain the information required to make
    using the virtual list view faster.
  </adm:description>
  <adm:tag name="database" />
  <adm:profile name="ldap">
    <ldap:object-class>
      <ldap:oid>1.3.6.1.4.1.26027.1.2.117</ldap:oid>
      <ldap:name>ds-cfg-vlv-je-index</ldap:name>
      <ldap:superior>top</ldap:superior>
    </ldap:object-class>
  </adm:profile>
  <adm:property name="vlv-index-base-dn"
                mandatory="true"
                multi-valued="false">
    <adm:synopsis>
      This specifies the base DN used in the search query being indexed.
    </adm:synopsis>
    <adm:requires-admin-action>
      <adm:other>
        <adm:synopsis>
          The index will need to be rebuilt after this modifying this
          property.
        </adm:synopsis>
      </adm:other>
    </adm:requires-admin-action>
    <adm:syntax>
      <adm:dn/>
    </adm:syntax>
    <adm:profile name="ldap">
      <ldap:attribute>
        <ldap:oid>1.3.6.1.4.1.26027.1.1.437</ldap:oid>
        <ldap:name>ds-cfg-vlv-je-index-base-dn</ldap:name>
      </ldap:attribute>
    </adm:profile>
  </adm:property>
  <adm:property name="vlv-index-scope"
                mandatory="true"
                multi-valued="false">
    <adm:synopsis>
      This specifies the LDAP scope of the query being indexed.
    </adm:synopsis>
    <adm:requires-admin-action>
      <adm:other>
        <adm:synopsis>
          The index will need to be rebuilt after this modifying this
          property.
        </adm:synopsis>
      </adm:other>
    </adm:requires-admin-action>
    <adm:syntax>
      <adm:enumeration>
        <adm:value name="base-level">
          <adm:synopsis>
            Search the base object only.
          </adm:synopsis>
        </adm:value>
        <adm:value name="single-object">
          <adm:synopsis>
            Search subordinate objects to the base object but not include
            the base object itself.
          </adm:synopsis>
        </adm:value>
        <adm:value name="subordinate-subtree">
          <adm:synopsis>
            Search the entire subtree below the base object but not include
            the base object itself.
          </adm:synopsis>
        </adm:value>
        <adm:value name="whole-subtree">
          <adm:synopsis>
            Search the base object and the entire subtree below the base
            object.
          </adm:synopsis>
        </adm:value>
      </adm:enumeration>
    </adm:syntax>
    <adm:profile name="ldap">
      <ldap:attribute>
        <ldap:oid>1.3.6.1.4.1.26027.1.1.438</ldap:oid>
        <ldap:name>ds-cfg-vlv-je-index-scope </ldap:name>
      </ldap:attribute>
    </adm:profile>
  </adm:property>
  <adm:property name="vlv-index-filter"
                mandatory="true"
                multi-valued="false">
    <adm:synopsis>
      This specifies the LDAP filter used in the query being indexed.
    </adm:synopsis>
    <adm:requires-admin-action>
      <adm:other>
        <adm:synopsis>
          The index will need to be rebuilt after this modifying this
          property.
        </adm:synopsis>
      </adm:other>
    </adm:requires-admin-action>
    <adm:syntax>
      <adm:string />
    </adm:syntax>
    <adm:profile name="ldap">
      <ldap:attribute>
        <ldap:oid>1.3.6.1.4.1.26027.1.1.439</ldap:oid>
        <ldap:name>ds-cfg-vlv-je-index-filter</ldap:name>
      </ldap:attribute>
    </adm:profile>
  </adm:property>
  <adm:property name="vlv-index-sort-order"
                mandatory="true"
                multi-valued="false">
    <adm:synopsis>
      This specifies the names of attributes to sort the entries for the query
      being indexed.
    </adm:synopsis>
    <adm:requires-admin-action>
      <adm:other>
        <adm:synopsis>
         The index will need to be rebuilt after this modifying this
          property.
        </adm:synopsis>
      </adm:other>
    </adm:requires-admin-action>
    <adm:syntax>
      <adm:string />
    </adm:syntax>
    <adm:profile name="ldap">
      <ldap:attribute>
        <ldap:oid>1.3.6.1.4.1.26027.1.1.440</ldap:oid>
        <ldap:name>ds-cfg-vlv-je-index-sort-order</ldap:name>
      </ldap:attribute>
    </adm:profile>
  </adm:property>
  <adm:property name="vlv-index-name"
                mandatory="true"
                multi-valued="false"
                read-only="true">
    <adm:synopsis>
      This specifies a unique name for this VLV index.
    </adm:synopsis>
    <adm:syntax>
      <adm:string />
    </adm:syntax>
    <adm:profile name="ldap">
      <ldap:attribute>
        <ldap:oid>1.3.6.1.4.1.26027.1.1.441</ldap:oid>
        <ldap:name>ds-cfg-vlv-je-index-name</ldap:name>
      </ldap:attribute>
    </adm:profile>
  </adm:property>
  <adm:property name="vlv-index-sorted-set-capacity"
                mandatory="false"
                multi-valued="false"
                read-only="true">
    <adm:synopsis>
      This specifies the number of entry IDs to store in a single
      sorted set before it must be split.
    </adm:synopsis>
    <adm:default-behavior>
      <adm:defined>
        <adm:value>
          4000
        </adm:value>
      </adm:defined>
    </adm:default-behavior>
    <adm:syntax>
      <adm:integer>
        <adm:unit-synopsis>
          Number of entry IDs
        </adm:unit-synopsis>
      </adm:integer>
    </adm:syntax>
    <adm:profile name="ldap">
      <ldap:attribute>
        <ldap:oid>1.3.6.1.4.1.26027.1.1.442</ldap:oid>
        <ldap:name>ds-cfg-vlv-je-index-maximum-block-size</ldap:name>
      </ldap:attribute>
    </adm:profile>
  </adm:property>
</adm:managed-object>

 opends/src/server/org/opends/server/backends/jeb/AttributeIndexBuilder.java

New file
@@ -0,0 +1,386 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.backends.jeb;

import org.opends.server.protocols.asn1.ASN1OctetString;
import org.opends.server.types.Entry;
import static org.opends.server.util.StaticUtils.getFileForPath;

import com.sleepycat.je.DatabaseException;
import com.sleepycat.je.Transaction;

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.io.ByteArrayOutputStream;
import java.io.BufferedOutputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FilenameFilter;
import java.io.FileOutputStream;
import java.io.IOException;

/**
 * This class is used to create an attribute index for an import process.
 * It is used as follows.
 * <pre>
 * startProcessing();
 * processEntry(entry);
 * processEntry(entry);
 * ...
 * stopProcessing();
 * merge();
 * </pre>
 */
public class AttributeIndexBuilder implements IndexBuilder
{
  /**
   * The import context.
   */
  private ImportContext importContext;

  /**
   * The index database.
   */
  private Index index;

  /**
   * The indexer to generate the index keys.
   */
  private Indexer indexer;

  /**
   * The write buffer.
   */
  ArrayList<IndexMod> buffer;

  /**
   * The write buffer size.
   */
  private int bufferSize;

  /**
   * Current output file number.
   */
  private int fileNumber = 0;

  /**
   * The index entry limit.
   */
  private int entryLimit;

  /**
   * A unique prefix for temporary files to prevent conflicts.
   */
  private String fileNamePrefix;

  /**
   * Indicates whether we are replacing existing data or not.
   */
  private boolean replaceExisting = false;


  private ByteArrayOutputStream addBytesStream = new ByteArrayOutputStream();
  private ByteArrayOutputStream delBytesStream = new ByteArrayOutputStream();

  private DataOutputStream addBytesDataStream;
  private DataOutputStream delBytesDataStream;

  /**
   * A file name filter to identify temporary files we have written.
   */
  private FilenameFilter filter = new FilenameFilter()
  {
    public boolean accept(File d, String name)
    {
      return name.startsWith(fileNamePrefix);
    }
  };

  /**
   * Construct an index builder.
   *
   * @param importContext The import context.
   * @param index The index database we are writing.
   * @param entryLimit The index entry limit.
   * @param bufferSize The amount of memory available for buffering.
   */
  public AttributeIndexBuilder(ImportContext importContext,
                      Index index, int entryLimit, long bufferSize)
  {
    this.importContext = importContext;
    this.index = index;
    this.indexer = index.indexer;
    this.entryLimit = entryLimit;
    this.bufferSize = (int)bufferSize/100;
    long tid = Thread.currentThread().getId();
    fileNamePrefix = index.getName() + "_" + tid + "_";
    replaceExisting =
         importContext.getLDIFImportConfig().appendToExistingData() &&
         importContext.getLDIFImportConfig().replaceExistingEntries();
    addBytesDataStream = new DataOutputStream(addBytesStream);
    delBytesDataStream = new DataOutputStream(delBytesStream);
  }

  /**
   * {@inheritDoc}
   */
  public void startProcessing()
  {
    // Clean up any work files left over from a previous run.
    File tempDir = getFileForPath(
        importContext.getConfig().getBackendImportTempDirectory());
    File[] files = tempDir.listFiles(filter);
    if (files != null)
    {
      for (File f : files)
      {
        f.delete();
      }
    }

    buffer = new ArrayList<IndexMod>(bufferSize);
  }

  /**
   * {@inheritDoc}
   */
  public void processEntry(Entry oldEntry, Entry newEntry, EntryID entryID)
       throws DatabaseException, IOException
  {
    Transaction txn = null;

    // Update the index for this entry.
    if (oldEntry != null)
    {
      // This is an entry being replaced.
      Set<ASN1OctetString> addKeys = new HashSet<ASN1OctetString>();
      Set<ASN1OctetString> delKeys = new HashSet<ASN1OctetString>();

      indexer.replaceEntry(txn, oldEntry, newEntry, addKeys, delKeys);

      for (ASN1OctetString k : delKeys)
      {
        removeID(k.value(), entryID);
      }

      for (ASN1OctetString k : addKeys)
      {
        insertID(k.value(), entryID);
      }
    }
    else
    {
      // This is a new entry.
      Set<ASN1OctetString> addKeys = new HashSet<ASN1OctetString>();
      indexer.indexEntry(txn, newEntry, addKeys);
      for (ASN1OctetString k : addKeys)
      {
        insertID(k.value(), entryID);
      }
    }

  }



  /**
   * {@inheritDoc}
   */
  public void stopProcessing() throws IOException
  {
    flushBuffer();
  }



  /**
   * Get a statistic of the number of keys that reached the entry limit.
   *
   * @return The number of keys that reached the entry limit.
   */
  public int getEntryLimitExceededCount()
  {
    return index.getEntryLimitExceededCount();
  }

  /**
   * Record the insertion of an entry ID.
   * @param key The index key.
   * @param entryID The entry ID.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void insertID(byte[] key, EntryID entryID)
       throws IOException
  {
    if (buffer.size() >= bufferSize)
    {
      flushBuffer();
    }

    IndexMod kav = new IndexMod(key, entryID, false);
    buffer.add(kav);
  }

  /**
   * Record the deletion of an entry ID.
   * @param key The index key.
   * @param entryID The entry ID.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void removeID(byte[] key, EntryID entryID)
       throws IOException
  {
    if (buffer.size() >= bufferSize)
    {
      flushBuffer();
    }

    IndexMod kav = new IndexMod(key, entryID, true);
    buffer.add(kav);
  }

  /**
   * Called when the buffer is full. It first sorts the buffer using the same
   * key comparator used by the index database. Then it merges all the
   * IDs for the same key together and writes each key and its list of IDs
   * to an intermediate binary file.
   * A list of deleted IDs is only present if we are replacing existing entries.
   *
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void flushBuffer() throws IOException
  {
    if (buffer.size() == 0)
    {
      return;
    }

    // Keys must be sorted before we can merge duplicates.
    IndexModComparator comparator;
    if (replaceExisting)
    {
      // The entry IDs may be out of order.
      // We must sort by key and ID.
      comparator = new IndexModComparator(indexer.getComparator(), true);
    }
    else
    {
      // The entry IDs are all new and are therefore already ordered.
      // We just need to sort by key.
      comparator = new IndexModComparator(indexer.getComparator(), false);
    }
    Collections.sort(buffer, comparator);

    // Start a new file.
    fileNumber++;
    String fileName = fileNamePrefix + String.valueOf(fileNumber);
    File file = new File(getFileForPath(
        importContext.getConfig().getBackendImportTempDirectory()),
                         fileName);
    BufferedOutputStream bufferedStream =
         new BufferedOutputStream(new FileOutputStream(file));
    DataOutputStream dataStream = new DataOutputStream(bufferedStream);

    // Reset the byte array output streams but preserve the underlying arrays.
    addBytesStream.reset();
    delBytesStream.reset();

    try
    {
      byte[] currentKey = null;
      for (IndexMod key : buffer)
      {
        byte[] keyString = key.key;
        if (!Arrays.equals(keyString,currentKey))
        {
          if (currentKey != null)
          {
            dataStream.writeInt(currentKey.length);
            dataStream.write(currentKey);
            dataStream.writeInt(addBytesStream.size());
            addBytesStream.writeTo(dataStream);
            if (replaceExisting)
            {
              dataStream.writeInt(delBytesStream.size());
              delBytesStream.writeTo(dataStream);
            }
          }

          currentKey = keyString;
          addBytesStream.reset();
          delBytesStream.reset();
        }

        if (key.isDelete)
        {
          delBytesDataStream.writeLong(key.value.longValue());
        }
        else
        {
          addBytesDataStream.writeLong(key.value.longValue());
        }

      }

      if (currentKey != null)
      {
        dataStream.writeInt(currentKey.length);
        dataStream.write(currentKey);
        dataStream.writeInt(addBytesStream.size());
        addBytesStream.writeTo(dataStream);
        if (replaceExisting)
        {
          dataStream.writeInt(delBytesStream.size());
          delBytesStream.writeTo(dataStream);
        }
      }

      buffer = new ArrayList<IndexMod>(bufferSize);
    }
    finally
    {
      dataStream.close();
    }
  }

  /**
   * Get a string that identifies this index builder.
   *
   * @return A string that identifies this index builder.
   */
  public String toString()
  {
    return indexer.toString();
  }
}


 opends/src/server/org/opends/server/backends/jeb/BackendImpl.java

@@ -906,6 +906,16 @@
      }
      throw createDirectoryException(e);
    }
    catch (JebException e)
    {
      if (debugEnabled())
      {
        TRACER.debugCaught(DebugLogLevel.ERROR, e);
      }
      String message = getMessage(MSGID_JEB_DATABASE_EXCEPTION, e.getMessage());
      throw new DirectoryException(DirectoryServer.getServerErrorResultCode(),
                                   message, MSGID_JEB_DATABASE_EXCEPTION);
    }
    finally
    {
      ec.sharedLock.unlock();

 opends/src/server/org/opends/server/backends/jeb/EntryContainer.java

@@ -59,6 +59,7 @@
import static org.opends.server.util.ServerConstants.*;
import org.opends.server.admin.std.server.JEBackendCfg;
import org.opends.server.admin.std.server.JEIndexCfg;
import org.opends.server.admin.std.server.VLVJEIndexCfg;
import org.opends.server.admin.server.ConfigurationChangeListener;
import org.opends.server.admin.server.ConfigurationAddListener;
import org.opends.server.admin.server.ConfigurationDeleteListener;
@@ -70,9 +71,7 @@
 * the guts of the backend API methods for LDAP operations.
 */
public class EntryContainer
    implements ConfigurationChangeListener<JEBackendCfg>,
    ConfigurationAddListener<JEIndexCfg>,
    ConfigurationDeleteListener<JEIndexCfg>
    implements ConfigurationChangeListener<JEBackendCfg>
{
  /**
   * The tracer object for the debug logger.
@@ -116,6 +115,16 @@
  public static final String ATTR_DEBUG_SEARCH_INDEX = "debugsearchindex";

  /**
   * The attribute index configuration manager.
   */
  public AttributeJEIndexCfgManager attributeJEIndexCfgManager;

  /**
   * The vlv index configuration manager.
   */
  public VLVJEIndexCfgManager vlvJEIndexCfgManager;

  /**
   * The backend to which this entry entryContainer belongs.
   */
  private Backend backend;
@@ -176,6 +185,11 @@
  private HashMap<AttributeType, AttributeIndex> attrIndexMap;

  /**
   * The set of VLV indexes.
   */
  private HashMap<String, VLVIndex> vlvIndexMap;

  /**
   * Cached value from config so they don't have to be retrieved per operation.
   */
  private int deadlockRetryLimit;
@@ -188,6 +202,196 @@

  private String databasePrefix;
  /**
   * This class is responsible for managing the configuraiton for attribute
   * indexes used within this entry container.
   */
  public class AttributeJEIndexCfgManager implements
      ConfigurationAddListener<JEIndexCfg>,
      ConfigurationDeleteListener<JEIndexCfg>
  {
    /**
     * {@inheritDoc}
     */
    public boolean isConfigurationAddAcceptable(JEIndexCfg cfg,
                                               List<String> unacceptableReasons)
    {
      // TODO: validate more before returning true?
      return true;
    }

    /**
     * {@inheritDoc}
     */
    public ConfigChangeResult applyConfigurationAdd(JEIndexCfg cfg)
    {
      ConfigChangeResult ccr;
      boolean adminActionRequired = false;
      ArrayList<String> messages = new ArrayList<String>();

      try
      {
        AttributeIndex index =
            new AttributeIndex(cfg, state, env, EntryContainer.this);
        index.open();
        attrIndexMap.put(cfg.getIndexAttribute(), index);
      }
      catch(Exception e)
      {
        messages.add(StaticUtils.stackTraceToSingleLineString(e));
        ccr = new ConfigChangeResult(DirectoryServer.getServerErrorResultCode(),
                                     adminActionRequired,
                                     messages);
        return ccr;
      }

      adminActionRequired = true;
      int msgID = MSGID_JEB_INDEX_ADD_REQUIRES_REBUILD;
      messages.add(getMessage(msgID, cfg.getIndexAttribute().getNameOrOID()));
      return new ConfigChangeResult(ResultCode.SUCCESS, adminActionRequired,
                                    messages);
    }

    /**
     * {@inheritDoc}
     */
    public synchronized boolean isConfigurationDeleteAcceptable(
        JEIndexCfg cfg, List<String> unacceptableReasons)
    {
      // TODO: validate more before returning true?
      return true;
    }

    /**
     * {@inheritDoc}
     */
    public ConfigChangeResult applyConfigurationDelete(JEIndexCfg cfg)
    {
      ConfigChangeResult ccr;
      boolean adminActionRequired = false;
      ArrayList<String> messages = new ArrayList<String>();

      exclusiveLock.lock();
      try
      {
        AttributeIndex index = attrIndexMap.get(cfg.getIndexAttribute());
        deleteAttributeIndex(index);
        attrIndexMap.remove(cfg.getIndexAttribute());
      }
      catch(DatabaseException de)
      {
        messages.add(StaticUtils.stackTraceToSingleLineString(de));
        ccr = new ConfigChangeResult(DirectoryServer.getServerErrorResultCode(),
                                     adminActionRequired,
                                     messages);
        return ccr;
      }
      finally
      {
        exclusiveLock.unlock();
      }

      return new ConfigChangeResult(ResultCode.SUCCESS, adminActionRequired,
                                    messages);
    }
  }

  /**
   * This class is responsible for managing the configuraiton for VLV indexes
   * used within this entry container.
   */
  public class VLVJEIndexCfgManager implements
      ConfigurationAddListener<VLVJEIndexCfg>,
      ConfigurationDeleteListener<VLVJEIndexCfg>
  {
    /**
     * {@inheritDoc}
     */
    public boolean isConfigurationAddAcceptable(
        VLVJEIndexCfg cfg, List<String> unacceptableReasons)
    {
      // TODO: validate more before returning true?
      return true;
    }

    /**
     * {@inheritDoc}
     */
    public ConfigChangeResult applyConfigurationAdd(VLVJEIndexCfg cfg)
    {
      ConfigChangeResult ccr;
      boolean adminActionRequired = false;
      ArrayList<String> messages = new ArrayList<String>();

      try
      {
        VLVIndex vlvIndex = new VLVIndex(cfg, state, env, EntryContainer.this);
        vlvIndex.open();
        vlvIndexMap.put(cfg.getVLVIndexName().toLowerCase(), vlvIndex);
      }
      catch(Exception e)
      {
        messages.add(StaticUtils.stackTraceToSingleLineString(e));
        ccr = new ConfigChangeResult(DirectoryServer.getServerErrorResultCode(),
                                     adminActionRequired,
                                     messages);
        return ccr;
      }

      adminActionRequired = true;
      int msgID = MSGID_JEB_INDEX_ADD_REQUIRES_REBUILD;
      messages.add(getMessage(msgID, cfg.getVLVIndexName()));
      return new ConfigChangeResult(ResultCode.SUCCESS, adminActionRequired,
                                    messages);
    }

    /**
     * {@inheritDoc}
     */
    public boolean isConfigurationDeleteAcceptable(VLVJEIndexCfg cfg,
                                               List<String> unacceptableReasons)
    {
      // TODO: validate more before returning true?
      return true;
    }

    /**
     * {@inheritDoc}
     */
    public ConfigChangeResult applyConfigurationDelete(VLVJEIndexCfg cfg)
    {
      ConfigChangeResult ccr;
      boolean adminActionRequired = false;
      ArrayList<String> messages = new ArrayList<String>();

      exclusiveLock.lock();
      try
      {
        VLVIndex vlvIndex =
            vlvIndexMap.get(cfg.getVLVIndexName().toLowerCase());
        vlvIndex.close();
        deleteDatabase(vlvIndex);
        vlvIndexMap.remove(cfg.getVLVIndexName());
      }
      catch(DatabaseException de)
      {
        messages.add(StaticUtils.stackTraceToSingleLineString(de));
        ccr = new ConfigChangeResult(DirectoryServer.getServerErrorResultCode(),
                                     adminActionRequired,
                                     messages);
        return ccr;
      }
      finally
      {
        exclusiveLock.unlock();
      }

      return new ConfigChangeResult(ResultCode.SUCCESS, adminActionRequired,
                                    messages);
    }

  }

  /**
   * A read write lock to handle schema changes and bulk changes.
   */
  private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
@@ -243,9 +447,20 @@
    // Instantiate the attribute indexes.
    attrIndexMap = new HashMap<AttributeType, AttributeIndex>();

    // Instantiate the VLV indexes.
    vlvIndexMap = new HashMap<String, VLVIndex>();

    config.addJEChangeListener(this);
    config.addJEIndexAddListener(this);
    config.addJEIndexDeleteListener(this);

    attributeJEIndexCfgManager =
        new AttributeJEIndexCfgManager();
    config.addJEIndexAddListener(attributeJEIndexCfgManager);
    config.addJEIndexDeleteListener(attributeJEIndexCfgManager);

    vlvJEIndexCfgManager =
        new VLVJEIndexCfgManager();
    config.addVLVJEIndexAddListener(vlvJEIndexCfgManager);
    config.addVLVJEIndexDeleteListener(vlvJEIndexCfgManager);
  }

  /**
@@ -298,6 +513,15 @@
        index.open();
        attrIndexMap.put(indexCfg.getIndexAttribute(), index);
      }

      for(String idx : config.listVLVJEIndexes())
      {
        VLVJEIndexCfg vlvIndexCfg = config.getVLVJEIndex(idx);

        VLVIndex vlvIndex = new VLVIndex(vlvIndexCfg, state, env, this);
        vlvIndex.open();
        vlvIndexMap.put(vlvIndexCfg.getVLVIndexName().toLowerCase(), vlvIndex);
      }
    }
    catch (DatabaseException de)
    {
@@ -326,8 +550,10 @@
    }

    config.removeJEChangeListener(this);
    config.removeJEIndexAddListener(this);
    config.removeJEIndexDeleteListener(this);
    config.removeJEIndexAddListener(attributeJEIndexCfgManager);
    config.removeJEIndexDeleteListener(attributeJEIndexCfgManager);
    config.removeVLVJEIndexDeleteListener(vlvJEIndexCfgManager);
    config.removeVLVJEIndexDeleteListener(vlvJEIndexCfgManager);
  }

  /**
@@ -397,6 +623,17 @@
  }

  /**
   * Look for an VLV index for the given index name.
   *
   * @param vlvIndexName The vlv index name for which an vlv index is needed.
   * @return The VLV index or null if there is none with that name.
   */
  public VLVIndex getVLVIndex(String vlvIndexName)
  {
    return vlvIndexMap.get(vlvIndexName);
  }

  /**
   * Retrieve all attribute indexes.
   *
   * @return All attribute indexes defined in this entry container.
@@ -406,6 +643,15 @@
    return attrIndexMap.values();
  }

  /**
   * Retrieve all VLV indexes.
   *
   * @return The collection of VLV indexes defined in this entry container.
   */
  public Collection<VLVIndex> getVLVIndexes()
  {
    return vlvIndexMap.values();
  }

  /**
   * Determine the highest entryID in the entryContainer.
@@ -448,9 +694,10 @@
   *          If a problem occurs while processing the
   *          search.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  public void search(SearchOperation searchOperation)
       throws DirectoryException, DatabaseException
       throws DirectoryException, DatabaseException, JebException
  {
    DN baseDN = searchOperation.getBaseDN();
    SearchScope searchScope = searchOperation.getScope();
@@ -617,54 +864,115 @@
      debugBuffer = new StringBuilder();
    }

    // Create an index filter to get the search result candidate entries.
    IndexFilter indexFilter =
         new IndexFilter(this, searchOperation, debugBuffer);

    // Evaluate the filter against the attribute indexes.
    EntryIDSet entryIDList = indexFilter.evaluate();

    // Evaluate the search scope against the id2children and id2subtree indexes.
    EntryIDSet entryIDList = null;
    boolean candidatesAreInScope = false;
    if (entryIDList.size() > IndexFilter.FILTER_CANDIDATE_THRESHOLD)
    if(sortRequest != null)
    {
      // Read the ID from dn2id.
      EntryID baseID = dn2id.get(null, baseDN);
      if (baseID == null)
      for(VLVIndex vlvIndex : vlvIndexMap.values())
      {
        int messageID = MSGID_JEB_SEARCH_NO_SUCH_OBJECT;
        String message = getMessage(messageID, baseDN.toString());
        DN matchedDN = getMatchedDN(baseDN);
        throw new DirectoryException(ResultCode.NO_SUCH_OBJECT,
            message, messageID, matchedDN, null);
      }
      DatabaseEntry baseIDData = baseID.getDatabaseEntry();

      EntryIDSet scopeList;
      if (searchScope == SearchScope.SINGLE_LEVEL)
      {
        scopeList = id2children.readKey(baseIDData, null, LockMode.DEFAULT);
      }
      else
      {
        scopeList = id2subtree.readKey(baseIDData, null, LockMode.DEFAULT);
        if (searchScope == SearchScope.WHOLE_SUBTREE)
        try
        {
          // The id2subtree list does not include the base entry ID.
          scopeList.add(baseID);
          entryIDList =
              vlvIndex.evaluate(null, searchOperation, sortRequest, vlvRequest,
                                debugBuffer);
          if(entryIDList != null)
          {
            searchOperation.addResponseControl(
                new ServerSideSortResponseControl(LDAPResultCode.SUCCESS,
                                                  null));
            candidatesAreInScope = true;
            break;
          }
        }
        catch (DirectoryException de)
        {
          searchOperation.addResponseControl(
              new ServerSideSortResponseControl(
                  de.getResultCode().getIntValue(), null));

          if (sortRequest.isCritical())
          {
            throw de;
          }
        }
      }
      entryIDList.retainAll(scopeList);
      if (debugBuffer != null)
    }

    if(entryIDList == null)
    {
      // Create an index filter to get the search result candidate entries.
      IndexFilter indexFilter =
          new IndexFilter(this, searchOperation, debugBuffer);

      // Evaluate the filter against the attribute indexes.
      entryIDList = indexFilter.evaluate();

      // Evaluate the search scope against the id2children and id2subtree
      // indexes.
      if (entryIDList.size() > IndexFilter.FILTER_CANDIDATE_THRESHOLD)
      {
        debugBuffer.append(" scope=");
        debugBuffer.append(searchScope);
        scopeList.toString(debugBuffer);
        // Read the ID from dn2id.
        EntryID baseID = dn2id.get(null, baseDN);
        if (baseID == null)
        {
          int messageID = MSGID_JEB_SEARCH_NO_SUCH_OBJECT;
          String message = getMessage(messageID, baseDN.toString());
          DN matchedDN = getMatchedDN(baseDN);
          throw new DirectoryException(ResultCode.NO_SUCH_OBJECT,
              message, messageID, matchedDN, null);
        }
        DatabaseEntry baseIDData = baseID.getDatabaseEntry();

        EntryIDSet scopeList;
        if (searchScope == SearchScope.SINGLE_LEVEL)
        {
          scopeList = id2children.readKey(baseIDData, null, LockMode.DEFAULT);
        }
        else
        {
          scopeList = id2subtree.readKey(baseIDData, null, LockMode.DEFAULT);
          if (searchScope == SearchScope.WHOLE_SUBTREE)
          {
            // The id2subtree list does not include the base entry ID.
            scopeList.add(baseID);
          }
        }
        entryIDList.retainAll(scopeList);
        if (debugBuffer != null)
        {
          debugBuffer.append(" scope=");
          debugBuffer.append(searchScope);
          scopeList.toString(debugBuffer);
        }
        if (scopeList.isDefined())
        {
          // In this case we know that every candidate is in scope.
          candidatesAreInScope = true;
        }
      }
      if (scopeList.isDefined())

      if (sortRequest != null)
      {
        // In this case we know that every candidate is in scope.
        candidatesAreInScope = true;
        try
        {
          entryIDList = EntryIDSetSorter.sort(this, entryIDList,
                                              searchOperation,
                                              sortRequest.getSortOrder(),
                                              vlvRequest);
          searchOperation.addResponseControl(
              new ServerSideSortResponseControl(LDAPResultCode.SUCCESS, null));
        }
        catch (DirectoryException de)
        {
          searchOperation.addResponseControl(
              new ServerSideSortResponseControl(
                  de.getResultCode().getIntValue(), null));

          if (sortRequest.isCritical())
          {
            throw de;
          }
        }
      }
    }

@@ -697,30 +1005,6 @@

    if (entryIDList.isDefined())
    {
      if (sortRequest != null)
      {
        try
        {
          entryIDList = EntryIDSetSorter.sort(this, entryIDList,
                                              searchOperation,
                                              sortRequest.getSortOrder(),
                                              vlvRequest);
          searchOperation.addResponseControl(
               new ServerSideSortResponseControl(LDAPResultCode.SUCCESS, null));
        }
        catch (DirectoryException de)
        {
          searchOperation.addResponseControl(
               new ServerSideSortResponseControl(
                        de.getResultCode().getIntValue(), null));

          if (sortRequest.isCritical())
          {
            throw de;
          }
        }
      }

      searchIndexed(entryIDList, candidatesAreInScope, searchOperation,
                    pageRequest);
    }
@@ -3313,6 +3597,11 @@
    {
      index.addEntry(txn, entryID, entry);
    }

    for (VLVIndex vlvIndex : vlvIndexMap.values())
    {
      vlvIndex.addEntry(txn, entryID, entry);
    }
  }

  /**
@@ -3332,6 +3621,11 @@
    {
      index.removeEntry(txn, entryID, entry);
    }

    for (VLVIndex vlvIndex : vlvIndexMap.values())
    {
      vlvIndex.removeEntry(txn, entryID, entry);
    }
  }

  /**
@@ -3344,11 +3638,13 @@
   * @param entryID The ID of the entry that was changed.
   * @param mods The sequence of modifications made to the entry.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws JebException If an error occurs in the JE backend.
   */
  private void indexModifications(Transaction txn, Entry oldEntry,
                                  Entry newEntry,
                                  EntryID entryID, List<Modification> mods)
      throws DatabaseException
      throws DatabaseException, DirectoryException, JebException
  {
    // Process in index configuration order.
    for (AttributeIndex index : attrIndexMap.values())
@@ -3370,6 +3666,11 @@
        index.modifyEntry(txn, entryID, oldEntry, newEntry, mods);
      }
    }

    for(VLVIndex vlvIndex : vlvIndexMap.values())
    {
      vlvIndex.modifyEntry(txn, entryID, oldEntry, newEntry, mods);
    }
  }

  /**
@@ -3417,6 +3718,11 @@
    {
      index.listDatabases(dbList);
    }

    for (VLVIndex vlvIndex : vlvIndexMap.values())
    {
      dbList.add(vlvIndex);
    }
  }

  /**
@@ -3861,92 +4167,6 @@
  }

  /**
   * {@inheritDoc}
   */
  public synchronized boolean isConfigurationAddAcceptable(
      JEIndexCfg cfg, List<String> unacceptableReasons)
  {
    // TODO: validate more before returning true?
    return true;
  }

  /**
   * {@inheritDoc}
   */
  public synchronized ConfigChangeResult applyConfigurationAdd(JEIndexCfg cfg)
  {
    ConfigChangeResult ccr;
    boolean adminActionRequired = false;
    ArrayList<String> messages = new ArrayList<String>();

    try
    {
      AttributeIndex index =
          new AttributeIndex(cfg, state, env, this);
      index.open();
      attrIndexMap.put(cfg.getIndexAttribute(), index);
    }
    catch(Exception e)
    {
      messages.add(StaticUtils.stackTraceToSingleLineString(e));
      ccr = new ConfigChangeResult(DirectoryServer.getServerErrorResultCode(),
                                   adminActionRequired,
                                   messages);
      return ccr;
    }

    adminActionRequired = true;
    int msgID = MSGID_JEB_INDEX_ADD_REQUIRES_REBUILD;
    messages.add(getMessage(msgID, cfg.getIndexAttribute().getNameOrOID()));
    return new ConfigChangeResult(ResultCode.SUCCESS, adminActionRequired,
                                  messages);
  }

  /**
   * {@inheritDoc}
   */
  public synchronized boolean isConfigurationDeleteAcceptable(
      JEIndexCfg cfg, List<String> unacceptableReasons)
  {
    // TODO: validate more before returning true?
    return true;
  }

  /**
   * {@inheritDoc}
   */
  public synchronized ConfigChangeResult applyConfigurationDelete(
      JEIndexCfg cfg)
  {
    ConfigChangeResult ccr;
    boolean adminActionRequired = false;
    ArrayList<String> messages = new ArrayList<String>();

    exclusiveLock.lock();
    try
    {
      AttributeIndex index = attrIndexMap.get(cfg.getIndexAttribute());
      deleteAttributeIndex(index);
      attrIndexMap.remove(cfg.getIndexAttribute());
    }
    catch(DatabaseException de)
    {
      messages.add(StaticUtils.stackTraceToSingleLineString(de));
      ccr = new ConfigChangeResult(DirectoryServer.getServerErrorResultCode(),
                                   adminActionRequired,
                                   messages);
      return ccr;
    }
    finally
    {
      exclusiveLock.unlock();
    }

    return new ConfigChangeResult(ResultCode.SUCCESS, adminActionRequired,
                                  messages);
  }

  /**
   * Get the environment config of the JE environment used in this entry
   * container.
   *

 opends/src/server/org/opends/server/backends/jeb/ImportJob.java

@@ -359,6 +359,9 @@

      ArrayList<IndexMergeThread> mergers = new ArrayList<IndexMergeThread>();

      ArrayList<VLVIndexMergeThread> vlvIndexMergeThreads =
        new ArrayList<VLVIndexMergeThread>();

      // Create merge threads for each base DN.
      for (ImportContext importContext : importMap.values())
      {
@@ -420,6 +423,14 @@
          }
        }

        for(VLVIndex vlvIndex : entryContainer.getVLVIndexes())
        {
          VLVIndexMergeThread vlvIndexMergeThread =
              new VLVIndexMergeThread(config, ldifImportConfig, vlvIndex);
          vlvIndexMergeThread.setUncaughtExceptionHandler(this);
          vlvIndexMergeThreads.add(vlvIndexMergeThread);
        }

        // Id2Children index.
        Index id2Children = entryContainer.getID2Children();
        IndexMergeThread indexMergeThread =
@@ -444,6 +455,10 @@
      {
        imt.start();
      }
      for (VLVIndexMergeThread imt : vlvIndexMergeThreads)
      {
        imt.start();
      }

      // Wait for the threads to finish.
      for (IndexMergeThread imt : mergers)
@@ -460,6 +475,21 @@
          }
        }
      }
      // Wait for the threads to finish.
      for (VLVIndexMergeThread imt : vlvIndexMergeThreads)
      {
        try
        {
          imt.join();
        }
        catch (InterruptedException e)
        {
          if (debugEnabled())
          {
            TRACER.debugCaught(DebugLogLevel.ERROR, e);
          }
        }
      }

      long mergeEndTime = System.currentTimeMillis();

@@ -977,7 +1007,7 @@
    threads.remove(t);
    int msgID = MSGID_JEB_IMPORT_THREAD_EXCEPTION;
    String msg = getMessage(msgID, t.getName(),
                            StaticUtils.stackTraceToSingleLineString(e));
                        StaticUtils.stackTraceToSingleLineString(e.getCause()));
    logError(ErrorLogCategory.BACKEND, ErrorLogSeverity.SEVERE_ERROR, msg,
             msgID);
  }

 opends/src/server/org/opends/server/backends/jeb/ImportThread.java

@@ -170,6 +170,8 @@
      }
    }

    nIndexes += entryContainer.getVLVIndexes().size();

    // Divide the total buffer size by the number of threads
    // and give that much to each index.
    long indexBufferSize = importContext.getBufferSize() / nIndexes;
@@ -186,64 +188,72 @@

      if (attrIndex.equalityIndex != null)
      {
        IndexBuilder indexBuilder =
             new IndexBuilder(importContext,
        AttributeIndexBuilder attributeIndexBuilder =
             new AttributeIndexBuilder(importContext,
                              attrIndex.equalityIndex,
                              indexEntryLimit,
                              indexBufferSize);
        builders.add(indexBuilder);
        builders.add(attributeIndexBuilder);
      }
      if (attrIndex.presenceIndex != null)
      {
        IndexBuilder indexBuilder =
             new IndexBuilder(importContext,
        AttributeIndexBuilder attributeIndexBuilder =
             new AttributeIndexBuilder(importContext,
                              attrIndex.presenceIndex,
                              indexEntryLimit,
                              indexBufferSize);
        builders.add(indexBuilder);
        builders.add(attributeIndexBuilder);
      }
      if (attrIndex.substringIndex != null)
      {
        IndexBuilder indexBuilder =
             new IndexBuilder(importContext,
        AttributeIndexBuilder attributeIndexBuilder =
             new AttributeIndexBuilder(importContext,
                              attrIndex.substringIndex,
                              indexEntryLimit,
                              indexBufferSize);
        builders.add(indexBuilder);
        builders.add(attributeIndexBuilder);
      }
      if (attrIndex.orderingIndex != null)
      {
        IndexBuilder indexBuilder =
             new IndexBuilder(importContext, attrIndex.orderingIndex,
        AttributeIndexBuilder attributeIndexBuilder =
             new AttributeIndexBuilder(importContext, attrIndex.orderingIndex,
                              indexEntryLimit,
                              indexBufferSize);
        builders.add(indexBuilder);
        builders.add(attributeIndexBuilder);
      }
      if (attrIndex.approximateIndex != null)
      {
        IndexBuilder indexBuilder =
            new IndexBuilder(importContext, attrIndex.approximateIndex,
        AttributeIndexBuilder attributeIndexBuilder =
            new AttributeIndexBuilder(importContext, attrIndex.approximateIndex,
                             indexEntryLimit,
                             indexBufferSize);
        builders.add(indexBuilder);
        builders.add(attributeIndexBuilder);
      }
    }

    // Create an vlvIndex builder for each VLV index database.
    for (VLVIndex vlvIndex : entryContainer.getVLVIndexes())
    {
      VLVIndexBuilder vlvIndexBuilder =
          new VLVIndexBuilder(importContext, vlvIndex, indexBufferSize);
      builders.add(vlvIndexBuilder);
    }

    // Create an index builder for the children index.
    Index id2Children = entryContainer.getID2Children();
    IndexBuilder indexBuilder =
         new IndexBuilder(importContext, id2Children,
    AttributeIndexBuilder attributeIndexBuilder =
         new AttributeIndexBuilder(importContext, id2Children,
                          importContext.getConfig().getBackendIndexEntryLimit(),
                          indexBufferSize);
    builders.add(indexBuilder);
    builders.add(attributeIndexBuilder);

    // Create an index builder for the subtree index.
    Index id2Subtree = entryContainer.getID2Subtree();
    indexBuilder =
         new IndexBuilder(importContext, id2Subtree,
    attributeIndexBuilder =
         new AttributeIndexBuilder(importContext, id2Subtree,
                          importContext.getConfig().getBackendIndexEntryLimit(),
                          indexBufferSize);
    builders.add(indexBuilder);
    builders.add(attributeIndexBuilder);

    for (IndexBuilder b : builders)
    {

 opends/src/server/org/opends/server/backends/jeb/IndexBuilder.java

@@ -26,149 +26,23 @@
 */
package org.opends.server.backends.jeb;

import org.opends.server.protocols.asn1.ASN1OctetString;
import org.opends.server.types.Entry;
import static org.opends.server.util.StaticUtils.getFileForPath;

import org.opends.server.types.DirectoryException;
import com.sleepycat.je.DatabaseException;
import com.sleepycat.je.Transaction;

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.io.ByteArrayOutputStream;
import java.io.BufferedOutputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FilenameFilter;
import java.io.FileOutputStream;
import java.io.IOException;

/**
 * This class is used to create an attribute index for an import process.
 * It is used as follows.
 * <pre>
 * startProcessing();
 * processEntry(entry);
 * processEntry(entry);
 * ...
 * stopProcessing();
 * merge();
 * </pre>
 * The interface that represents a index builder for the import process.
 */
public class IndexBuilder
public interface IndexBuilder
{
  /**
   * The import context.
   */
  private ImportContext importContext;

  /**
   * The index database.
   */
  private Index index;

  /**
   * The indexer to generate the index keys.
   */
  private Indexer indexer;

  /**
   * The write buffer.
   */
  ArrayList<IndexMod> buffer;

  /**
   * The write buffer size.
   */
  private int bufferSize;

  /**
   * Current output file number.
   */
  private int fileNumber = 0;

  /**
   * The index entry limit.
   */
  private int entryLimit;

  /**
   * A unique prefix for temporary files to prevent conflicts.
   */
  private String fileNamePrefix;

  /**
   * Indicates whether we are replacing existing data or not.
   */
  private boolean replaceExisting = false;


  private ByteArrayOutputStream addBytesStream = new ByteArrayOutputStream();
  private ByteArrayOutputStream delBytesStream = new ByteArrayOutputStream();

  private DataOutputStream addBytesDataStream;
  private DataOutputStream delBytesDataStream;

  /**
   * A file name filter to identify temporary files we have written.
   */
  private FilenameFilter filter = new FilenameFilter()
  {
    public boolean accept(File d, String name)
    {
      return name.startsWith(fileNamePrefix);
    }
  };

  /**
   * Construct an index builder.
   *
   * @param importContext The import context.
   * @param index The index database we are writing.
   * @param entryLimit The index entry limit.
   * @param bufferSize The amount of memory available for buffering.
   */
  public IndexBuilder(ImportContext importContext,
                      Index index, int entryLimit, long bufferSize)
  {
    this.importContext = importContext;
    this.index = index;
    this.indexer = index.indexer;
    this.entryLimit = entryLimit;
    this.bufferSize = (int)bufferSize/100;
    long tid = Thread.currentThread().getId();
    fileNamePrefix = index.getName() + "_" + tid + "_";
    replaceExisting =
         importContext.getLDIFImportConfig().appendToExistingData() &&
         importContext.getLDIFImportConfig().replaceExistingEntries();
    addBytesDataStream = new DataOutputStream(addBytesStream);
    delBytesDataStream = new DataOutputStream(delBytesStream);
  }

  /**
   * This method must be called before this object can process any
   * entries. It cleans up any temporary files left over from a
   * previous import.
   */
  public void startProcessing()
  {
    // Clean up any work files left over from a previous run.
    File tempDir = getFileForPath(
        importContext.getConfig().getBackendImportTempDirectory());
    File[] files = tempDir.listFiles(filter);
    if (files != null)
    {
      for (File f : files)
      {
        f.delete();
      }
    }

    buffer = new ArrayList<IndexMod>(bufferSize);
  }
  void startProcessing();

  /**
   * Indicates that the index thread should process the provided entry.
@@ -176,222 +50,19 @@
   * a new entry.
   * @param newEntry The new contents of the entry.
   * @param entryID The entry ID.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   * @throws com.sleepycat.je.DatabaseException If an error occurs in the JE
   * database.
   * @throws java.io.IOException If an I/O error occurs while writing an
   * intermediate file.
   * @throws DirectoryException If an error occurs while processing the entry.
   */
  public void processEntry(Entry oldEntry, Entry newEntry, EntryID entryID)
       throws DatabaseException, IOException
  {
    Transaction txn = null;

    // Update the index for this entry.
    if (oldEntry != null)
    {
      // This is an entry being replaced.
      Set<ASN1OctetString> addKeys = new HashSet<ASN1OctetString>();
      Set<ASN1OctetString> delKeys = new HashSet<ASN1OctetString>();

      indexer.replaceEntry(txn, oldEntry, newEntry, addKeys, delKeys);

      for (ASN1OctetString k : delKeys)
      {
        removeID(k.value(), entryID);
      }

      for (ASN1OctetString k : addKeys)
      {
        insertID(k.value(), entryID);
      }
    }
    else
    {
      // This is a new entry.
      Set<ASN1OctetString> addKeys = new HashSet<ASN1OctetString>();
      indexer.indexEntry(txn, newEntry, addKeys);
      for (ASN1OctetString k : addKeys)
      {
        insertID(k.value(), entryID);
      }
    }

  }


  void processEntry(Entry oldEntry, Entry newEntry, EntryID entryID)
      throws DatabaseException, IOException, DirectoryException;

  /**
   * Indicates that there will be no more updates.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  public void stopProcessing() throws IOException
  {
    flushBuffer();
  }



  /**
   * Get a statistic of the number of keys that reached the entry limit.
   *
   * @return The number of keys that reached the entry limit.
   */
  public int getEntryLimitExceededCount()
  {
    return index.getEntryLimitExceededCount();
  }

  /**
   * Record the insertion of an entry ID.
   * @param key The index key.
   * @param entryID The entry ID.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void insertID(byte[] key, EntryID entryID)
       throws IOException
  {
    if (buffer.size() >= bufferSize)
    {
      flushBuffer();
    }

    IndexMod kav = new IndexMod(key, entryID, false);
    buffer.add(kav);
  }

  /**
   * Record the deletion of an entry ID.
   * @param key The index key.
   * @param entryID The entry ID.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void removeID(byte[] key, EntryID entryID)
       throws IOException
  {
    if (buffer.size() >= bufferSize)
    {
      flushBuffer();
    }

    IndexMod kav = new IndexMod(key, entryID, true);
    buffer.add(kav);
  }

  /**
   * Called when the buffer is full. It first sorts the buffer using the same
   * key comparator used by the index database. Then it merges all the
   * IDs for the same key together and writes each key and its list of IDs
   * to an intermediate binary file.
   * A list of deleted IDs is only present if we are replacing existing entries.
   *
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void flushBuffer() throws IOException
  {
    if (buffer.size() == 0)
    {
      return;
    }

    // Keys must be sorted before we can merge duplicates.
    IndexModComparator comparator;
    if (replaceExisting)
    {
      // The entry IDs may be out of order.
      // We must sort by key and ID.
      comparator = new IndexModComparator(indexer.getComparator(), true);
    }
    else
    {
      // The entry IDs are all new and are therefore already ordered.
      // We just need to sort by key.
      comparator = new IndexModComparator(indexer.getComparator(), false);
    }
    Collections.sort(buffer, comparator);

    // Start a new file.
    fileNumber++;
    String fileName = fileNamePrefix + String.valueOf(fileNumber);
    File file = new File(getFileForPath(
        importContext.getConfig().getBackendImportTempDirectory()),
                         fileName);
    BufferedOutputStream bufferedStream =
         new BufferedOutputStream(new FileOutputStream(file));
    DataOutputStream dataStream = new DataOutputStream(bufferedStream);

    // Reset the byte array output streams but preserve the underlying arrays.
    addBytesStream.reset();
    delBytesStream.reset();

    try
    {
      byte[] currentKey = null;
      for (IndexMod key : buffer)
      {
        byte[] keyString = key.key;
        if (!Arrays.equals(keyString,currentKey))
        {
          if (currentKey != null)
          {
            dataStream.writeInt(currentKey.length);
            dataStream.write(currentKey);
            dataStream.writeInt(addBytesStream.size());
            addBytesStream.writeTo(dataStream);
            if (replaceExisting)
            {
              dataStream.writeInt(delBytesStream.size());
              delBytesStream.writeTo(dataStream);
            }
          }

          currentKey = keyString;
          addBytesStream.reset();
          delBytesStream.reset();
        }

        if (key.isDelete)
        {
          delBytesDataStream.writeLong(key.value.longValue());
        }
        else
        {
          addBytesDataStream.writeLong(key.value.longValue());
        }

      }

      if (currentKey != null)
      {
        dataStream.writeInt(currentKey.length);
        dataStream.write(currentKey);
        dataStream.writeInt(addBytesStream.size());
        addBytesStream.writeTo(dataStream);
        if (replaceExisting)
        {
          dataStream.writeInt(delBytesStream.size());
          delBytesStream.writeTo(dataStream);
        }
      }

      buffer = new ArrayList<IndexMod>(bufferSize);
    }
    finally
    {
      dataStream.close();
    }
  }

  /**
   * Get a string that identifies this index builder.
   *
   * @return A string that identifies this index builder.
   */
  public String toString()
  {
    return indexer.toString();
  }
  void stopProcessing() throws IOException;
}


 opends/src/server/org/opends/server/backends/jeb/IndexRebuildThread.java

@@ -71,6 +71,11 @@
  AttributeIndex attrIndex = null;

  /**
   * The VLV index to rebuild.
   */
  VLVIndex vlvIndex = null;

  /**
   * The indexType to rebuild.
   */
  Index index = null;
@@ -112,7 +117,7 @@
   */
  enum IndexType
  {
    DN2ID, DN2URI, ID2CHILDREN, ID2SUBTREE, INDEX, ATTRIBUTEINDEX
    DN2ID, DN2URI, ID2CHILDREN, ID2SUBTREE, INDEX, ATTRIBUTEINDEX, VLVINDEX
  }

  /**
@@ -161,6 +166,21 @@
  }

  /**
   * Construct a new index rebuild thread to rebuild an VLV index.
   *
   * @param ec The entry container to rebuild in.
   * @param vlvIndex The VLV index to rebuild.
   */
  IndexRebuildThread(EntryContainer ec, VLVIndex vlvIndex)
  {
    super("Index Rebuild Thread " + vlvIndex.getName());
    this.ec = ec;
    this.indexType = IndexType.VLVINDEX;
    this.vlvIndex = vlvIndex;
    this.id2entry = ec.getID2Entry();
  }

  /**
   * Clear the database and prep it for the rebuild.
   *
   * @throws DatabaseException if a JE databse error occurs while clearing
@@ -202,6 +222,18 @@
      return;
    }

    if(indexType == IndexType.VLVINDEX && vlvIndex == null)
    {
      //TODO: throw error
      if(debugEnabled())
      {
        TRACER.debugError("No VLV index specified. Rebuild process " +
            "terminated.");
      }

      return;
    }

    switch(indexType)
    {
      case DN2ID :
@@ -222,6 +254,10 @@
        ec.clearAttributeIndex(attrIndex);
        attrIndex.setRebuildStatus(true);
        break;
      case VLVINDEX :
        ec.clearDatabase(vlvIndex);
        vlvIndex.setRebuildStatus(true);
        break;
      case INDEX :
        ec.clearDatabase(index);
        index.setRebuildStatus(true);
@@ -267,6 +303,18 @@
      return;
    }

    if(indexType == IndexType.VLVINDEX && vlvIndex == null)
    {
      //TODO: throw error
      if(debugEnabled())
      {
        TRACER.debugError("No VLV index specified. Rebuild process " +
            "terminated.");
      }

      return;
    }

    try
    {
      totalEntries = getTotalEntries();
@@ -283,6 +331,8 @@
          break;
        case ATTRIBUTEINDEX : rebuildAttributeIndex(attrIndex);
          break;
        case VLVINDEX : rebuildVLVIndex(vlvIndex);
          break;
        case INDEX : rebuildAttributeIndex(index);
      }

@@ -325,7 +375,7 @@

    //Iterate through the id2entry database and insert associated dn2id
    //records.
    Cursor cursor = id2entry.openCursor(null, null);
    Cursor cursor = id2entry.openCursor(null, CursorConfig.READ_COMMITTED);
    try
    {
      DatabaseEntry key = new DatabaseEntry();
@@ -337,15 +387,14 @@
           status == OperationStatus.SUCCESS;
           status = cursor.getNext(key, data, lockMode))
      {
        Transaction txn = ec.beginTransaction();
        try
        {
          EntryID entryID = new EntryID(key);
          Entry entry = JebFormat.entryFromDatabase(data.getData());

          //TODO: Should we add all records in a big transaction?
          //TODO: Should we make each insert a transaction?
          // Insert into dn2id.
          if (dn2id.insert(null, entry.getDN(), entryID))
          if (dn2id.insert(txn, entry.getDN(), entryID))
          {
            rebuiltEntries++;
          }
@@ -363,13 +412,12 @@
                        entry.getDN().toString(), entryID.longValue());
            }
          }
          EntryContainer.transactionCommit(txn);
          processedEntries++;
        }
        catch (Exception e)
        {
          //TODO: throw error stating that the indexType could be in an
          // inconsistant state.
          //TODO: Should we continue on or stop right now?
          EntryContainer.transactionAbort(txn);
          skippedEntries++;

          int    msgID   = MSGID_JEB_REBUILD_INSERT_ENTRY_FAILED;
@@ -410,7 +458,7 @@

    //Iterate through the id2entry database and insert associated dn2uri
    //records.
    Cursor cursor = id2entry.openCursor(null, null);
    Cursor cursor = id2entry.openCursor(null, CursorConfig.READ_COMMITTED);
    try
    {
      DatabaseEntry key = new DatabaseEntry();
@@ -423,15 +471,14 @@
           status == OperationStatus.SUCCESS;
           status = cursor.getNext(key, data, lockMode))
      {
        Transaction txn = ec.beginTransaction();
        try
        {
          EntryID entryID = new EntryID(key);
          Entry entry = JebFormat.entryFromDatabase(data.getData());

          //TODO: Should we add all records in a big transaction?
          //TODO: Should we make each insert a transaction?
          // Insert into dn2uri.
          if (dn2uri.addEntry(null, entry))
          if (dn2uri.addEntry(txn, entry))
          {
            rebuiltEntries++;
          }
@@ -449,13 +496,12 @@
                        entry.getDN().toString(), entryID.longValue());
            }
          }
          EntryContainer.transactionCommit(txn);
          processedEntries++;
        }
        catch (Exception e)
        {
          //TODO: throw error stating that the indexType could be in an
          // inconsistant state.
          //TODO: Should we continue on or stop right now?
          EntryContainer.transactionAbort(txn);
          skippedEntries++;

          int    msgID   = MSGID_JEB_REBUILD_INSERT_ENTRY_FAILED;
@@ -500,7 +546,7 @@

    //Iterate through the id2entry database and insert associated dn2children
    //records.
    Cursor cursor = id2entry.openCursor(null, null);
    Cursor cursor = id2entry.openCursor(null, CursorConfig.READ_COMMITTED);
    try
    {
      DatabaseEntry key = new DatabaseEntry();
@@ -512,6 +558,7 @@
           status == OperationStatus.SUCCESS;
           status = cursor.getNext(key, data, lockMode))
      {
        Transaction txn = ec.beginTransaction();
        try
        {
          EntryID entryID = new EntryID(key);
@@ -525,11 +572,11 @@
            dn2uri.targetEntryReferrals(entry.getDN(), null);

            // Read the parent ID from dn2id.
            EntryID parentID = dn2id.get(null, parentDN);
            EntryID parentID = dn2id.get(txn, parentDN);
            if (parentID != null)
            {
              // Insert into id2children for parent ID.
              if(id2children.insertID(null, parentID.getDatabaseEntry(),
              if(id2children.insertID(txn, parentID.getDatabaseEntry(),
                                      entryID))
              {
                rebuiltEntries++;
@@ -561,11 +608,12 @@
          {
            skippedEntries++;
          }
          EntryContainer.transactionCommit(txn);
          processedEntries++;
        }
        catch (Exception e)
        {
          //TODO: Should we continue on or stop right now?
          EntryContainer.transactionAbort(txn);
          skippedEntries++;

          int    msgID   = MSGID_JEB_REBUILD_INSERT_ENTRY_FAILED;
@@ -612,7 +660,7 @@

    //Iterate through the id2entry database and insert associated dn2subtree
    //records.
    Cursor cursor = id2entry.openCursor(null, null);
    Cursor cursor = id2entry.openCursor(null, CursorConfig.READ_COMMITTED);
    try
    {
      DatabaseEntry key = new DatabaseEntry();
@@ -624,6 +672,7 @@
           status == OperationStatus.SUCCESS;
           status = cursor.getNext(key, data, lockMode))
      {
        Transaction txn = ec.beginTransaction();
        try
        {
          EntryID entryID = new EntryID(key);
@@ -639,11 +688,11 @@
            dn2uri.targetEntryReferrals(entry.getDN(), null);

            // Read the parent ID from dn2id.
            EntryID parentID = dn2id.get(null, parentDN);
            EntryID parentID = dn2id.get(txn, parentDN);
            if (parentID != null)
            {
              // Insert into id2subtree for parent ID.
              if(!id2subtree.insertID(null, parentID.getDatabaseEntry(),
              if(!id2subtree.insertID(txn, parentID.getDatabaseEntry(),
                                      entryID))
              {
                success = false;
@@ -703,11 +752,12 @@
          {
            skippedEntries++;
          }
          EntryContainer.transactionCommit(txn);
          processedEntries++;
        }
        catch (Exception e)
        {
          //TODO: Should we continue on or stop right now?
          EntryContainer.transactionAbort(txn);
          skippedEntries++;

          int    msgID   = MSGID_JEB_REBUILD_INSERT_ENTRY_FAILED;
@@ -749,7 +799,7 @@

    //Iterate through the id2entry database and insert associated indexType
    //records.
    Cursor cursor = id2entry.openCursor(null, null);
    Cursor cursor = id2entry.openCursor(null, CursorConfig.READ_COMMITTED);
    try
    {
      DatabaseEntry key = new DatabaseEntry();
@@ -761,13 +811,14 @@
           status == OperationStatus.SUCCESS;
           status = cursor.getNext(key, data, lockMode))
      {
        Transaction txn = ec.beginTransaction();
        try
        {
          EntryID entryID = new EntryID(key);
          Entry entry = JebFormat.entryFromDatabase(data.getData());

          // Insert into attribute indexType.
          if(index.addEntry(null, entryID, entry))
          if(index.addEntry(txn, entryID, entry))
          {
            rebuiltEntries++;
          }
@@ -786,11 +837,12 @@
                        entry.getDN().toString(), entryID.longValue());
            }
          }
          EntryContainer.transactionCommit(txn);
          processedEntries++;
        }
        catch (Exception e)
        {
          //TODO: Should we continue on or stop right now?
          EntryContainer.transactionAbort(txn);
          skippedEntries++;

          int    msgID   = MSGID_JEB_REBUILD_INSERT_ENTRY_FAILED;
@@ -815,6 +867,87 @@
  }

  /**
   * Rebuild the VLV index.
   *
   * @param vlvIndex The VLV index to rebuild.
   * @throws DatabaseException if an error occurs during rebuild.
   */
  private void rebuildVLVIndex(VLVIndex vlvIndex)
      throws DatabaseException
  {

    //Iterate through the id2entry database and insert associated indexType
    //records.
    Cursor cursor = id2entry.openCursor(null, CursorConfig.READ_COMMITTED);
    try
    {
      DatabaseEntry key = new DatabaseEntry();
      DatabaseEntry data = new DatabaseEntry();
      LockMode lockMode = LockMode.DEFAULT;

      OperationStatus status;
      for (status = cursor.getFirst(key, data, lockMode);
           status == OperationStatus.SUCCESS;
           status = cursor.getNext(key, data, lockMode))
      {
        Transaction txn = ec.beginTransaction();
        try
        {
          EntryID entryID = new EntryID(key);
          Entry entry = JebFormat.entryFromDatabase(data.getData());

          // Insert into attribute indexType.
          if(vlvIndex.addEntry(txn, entryID, entry))
          {
            rebuiltEntries++;
          }
          else
          {
            // The entry already exists in one or more entry sets.
            // This could happen if some other process got to this entry
            // before we did. Since the backend should be offline, this
            // might be a problem.
            if(debugEnabled())
            {
              duplicatedEntries++;
              TRACER.debugInfo("Unable to insert entry with DN %s and ID %d " +
                  "into the VLV index %s because it already " +
                  "exists.",
                        entry.getDN().toString(), entryID.longValue(),
                        vlvIndex.getName());
            }
          }

          EntryContainer.transactionCommit(txn);
          processedEntries++;
        }
        catch (Exception e)
        {
          EntryContainer.transactionAbort(txn);
          skippedEntries++;

          int    msgID   = MSGID_JEB_REBUILD_INSERT_ENTRY_FAILED;
          String message = getMessage(msgID, index.getName(),
                                      stackTraceToSingleLineString(e));
          logError(ErrorLogCategory.BACKEND, ErrorLogSeverity.MILD_ERROR,
                   message, msgID);

          if (debugEnabled())
          {
            TRACER.debugCaught(DebugLogLevel.ERROR, e);
          }
        }
      }
      vlvIndex.setRebuildStatus(false);
      vlvIndex.setTrusted(null, true);
    }
    finally
    {
      cursor.close();
    }
  }

  /**
   * Rebuild the partial attribute index.
   *
   * @param index The indexType to rebuild.
@@ -832,7 +965,7 @@

    //Iterate through the id2entry database and insert associated indexType
    //records.
    Cursor cursor = id2entry.openCursor(null, null);
    Cursor cursor = id2entry.openCursor(null, CursorConfig.READ_COMMITTED);
    try
    {
      DatabaseEntry key = new DatabaseEntry();
@@ -844,13 +977,14 @@
           status == OperationStatus.SUCCESS;
           status = cursor.getNext(key, data, lockMode))
      {
        Transaction txn = ec.beginTransaction();
        try
        {
          EntryID entryID = new EntryID(key);
          Entry entry = JebFormat.entryFromDatabase(data.getData());

          // Insert into attribute indexType.
          if(index.addEntry(null, entryID, entry))
          if(index.addEntry(txn, entryID, entry))
          {
            rebuiltEntries++;
          }
@@ -869,11 +1003,12 @@
                        entry.getDN().toString(), entryID.longValue());
            }
          }
          EntryContainer.transactionCommit(txn);
          processedEntries++;
        }
        catch (Exception e)
        {
          //TODO: Should we continue on or stop right now?
          EntryContainer.transactionAbort(txn);
          skippedEntries++;

          int    msgID   = MSGID_JEB_REBUILD_INSERT_ENTRY_FAILED;

 opends/src/server/org/opends/server/backends/jeb/RebuildJob.java

@@ -54,6 +54,8 @@
    MSGID_JEB_REBUILD_INDEX_CONFLICT;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_REBUILD_START;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_VLV_INDEX_NOT_CONFIGURED;
import static org.opends.server.messages.MessageHandler.getMessage;

/**
@@ -270,32 +272,35 @@
    //Make sure there are no running rebuild jobs
    jobsMutex.lock();

    for(RebuildJob otherJob : rebuildJobs)
    try
    {
      String conflictIndex =
          job.rebuildConfig.checkConflicts(otherJob.rebuildConfig);
      if(conflictIndex != null)
      for(RebuildJob otherJob : rebuildJobs)
      {
        jobsMutex.unlock();
        //TODO: Throw error and bail out.
        if(debugEnabled())
        String conflictIndex =
            job.rebuildConfig.checkConflicts(otherJob.rebuildConfig);
        if(conflictIndex != null)
        {
          TRACER.debugError("Conflit detected. This job config: %s, " +
              "That job config: %s.",
                     job.rebuildConfig, otherJob.rebuildConfig);
          if(debugEnabled())
          {
            TRACER.debugError("Conflit detected. This job config: %s, " +
                "That job config: %s.",
                              job.rebuildConfig, otherJob.rebuildConfig);
          }

          int msgID = MSGID_JEB_REBUILD_INDEX_CONFLICT;
          String msg = getMessage(msgID, conflictIndex);
          throw new JebException(msgID, msg);
        }


        int msgID = MSGID_JEB_REBUILD_INDEX_CONFLICT;
        String msg = getMessage(msgID, conflictIndex);
        throw new JebException(msgID, msg);
      }

      //No conflicts are found. Add the job to the list of currently running
      // jobs.
      rebuildJobs.add(job);
    }

    //No conflicts are found. Add the job to the list of currently running jobs.
    rebuildJobs.add(job);

    jobsMutex.unlock();
    finally
    {
      jobsMutex.unlock();
    }
  }

  private static void removeJob(RebuildJob job)
@@ -360,6 +365,26 @@
            rebuildThread = new IndexRebuildThread(entryContainer,
                                       IndexRebuildThread.IndexType.ID2SUBTREE);
          }
          else if (lowerName.startsWith("vlv."))
          {
            if(lowerName.length() < 5)
            {
              int msgID = MSGID_JEB_VLV_INDEX_NOT_CONFIGURED;
              String msg = getMessage(msgID, lowerName);
              throw new JebException(msgID, msg);
            }

            VLVIndex vlvIndex =
                entryContainer.getVLVIndex(lowerName.substring(4));
            if(vlvIndex == null)
            {
              int msgID = MSGID_JEB_VLV_INDEX_NOT_CONFIGURED;
              String msg = getMessage(msgID, lowerName.substring(4));
              throw new JebException(msgID, msg);
            }

            rebuildThread = new IndexRebuildThread(entryContainer, vlvIndex);
          }
          else
          {
            String[] attrIndexParts = lowerName.split("\\.");

 opends/src/server/org/opends/server/backends/jeb/SortValues.java

@@ -38,7 +38,6 @@
import org.opends.server.types.SortOrder;



/**
 * This class defines a data structure that holds a set of attribute values that
 * are associated with a sort order for a given entry.  Any or all of the
@@ -66,6 +65,22 @@
  /**
   * Creates a new sort values object with the provided information.
   *
   * @param entryID    The entry ID for the entry associated with this set of
   *                   values.
   * @param values     The attribute values for this sort values.
   * @param sortOrder  The sort order to use to obtain the necessary values.
   */
  public SortValues(EntryID entryID, AttributeValue[] values,
                    SortOrder sortOrder)
  {
    this.entryID = entryID;
    this.sortOrder = sortOrder;
    this.values = values;
  }

  /**
   * Creates a new sort values object with the provided information.
   *
   * @param  entryID    The entry ID for the entry associated with this set of
   *                    values.
   * @param  entry      The entry containing the values to extract and use when
@@ -243,5 +258,26 @@
    buffer.append(entryID.toString());
    buffer.append(")");
  }

  /**
   * Retrieve the attribute values in this sort values.
   *
   * @return The array of attribute values for this sort values.
   */
  public AttributeValue[] getValues()
  {
    return values;
  }

  /**
   * Retrieve the entry ID in this sort values.
   *
   * @return The entry ID for this sort values.
   */
  public long getEntryID()
  {
    return entryID.longValue();
  }
}



 opends/src/server/org/opends/server/backends/jeb/SortValuesSet.java

New file
@@ -0,0 +1,647 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.backends.jeb;

import org.opends.server.types.*;
import org.opends.server.protocols.asn1.ASN1OctetString;

import java.util.HashMap;

import com.sleepycat.je.DatabaseException;

/**
 * This class representsa  partial sorted set of sorted entries in a VLV
 * index.
 */
public class SortValuesSet
{
  private static final int ENCODED_VALUE_SIZE = 16;
  private static final int ENCODED_VALUE_LENGTH_SIZE =
      encodedLengthSize(ENCODED_VALUE_SIZE);
  private static final int ENCODED_ATTRIBUTE_VALUE_SIZE =
      ENCODED_VALUE_LENGTH_SIZE + ENCODED_VALUE_SIZE;

  private ID2Entry id2entry;

  private long[] entryIDs;

  private byte[] valuesBytes;

  private byte[] keyBytes;

  private HashMap<EntryID, AttributeValue[]> cachedAttributeValues;

  private VLVIndex vlvIndex;

  /**
   * Construct an empty sort values set with the given information.
   *
   * @param vlvIndex The VLV index using this set.
   * @param id2entry The ID2Entry database.
   */
  public SortValuesSet(VLVIndex vlvIndex, ID2Entry id2entry)
  {
    this.keyBytes = new byte[0];
    this.entryIDs = null;
    this.valuesBytes = null;
    this.id2entry = id2entry;
    this.vlvIndex = vlvIndex;
    this.cachedAttributeValues = new HashMap<EntryID, AttributeValue[]>();
  }

  /**
   * Construct a sort values set from the database.
   *
   * @param keyBytes The database key used to locate this set.
   * @param dataBytes The bytes to decode and construct this set.
   * @param vlvIndex The VLV index using this set.
   * @param id2entry The ID2Entry database.
   */
  public SortValuesSet(byte[] keyBytes, byte[] dataBytes, VLVIndex vlvIndex,
                       ID2Entry id2entry)
  {
    this.keyBytes = keyBytes;
    this.id2entry = id2entry;
    this.vlvIndex = vlvIndex;
    this.cachedAttributeValues = new HashMap<EntryID, AttributeValue[]>();

    if(dataBytes == null)
    {
      entryIDs = new long[0];
      return;
    }

    entryIDs = getEncodedIDs(dataBytes, 0);
    valuesBytes = new byte[entryIDs.length * ENCODED_ATTRIBUTE_VALUE_SIZE *
        vlvIndex.sortOrder.getSortKeys().length];
    System.arraycopy(dataBytes, entryIDs.length * 8 + 4, valuesBytes, 0,
                     valuesBytes.length);
  }

  private SortValuesSet(long[] entryIDs, byte[] keyBytes, byte[] valuesBytes,
                        VLVIndex vlvIndex, ID2Entry id2entry)
  {
    this.keyBytes = keyBytes;
    this.id2entry = id2entry;
    this.entryIDs = entryIDs;
    this.valuesBytes = valuesBytes;
    this.vlvIndex = vlvIndex;
    this.cachedAttributeValues = new HashMap<EntryID, AttributeValue[]>();
  }

  /**
   * Add the given entryID and values from this VLV idnex.
   *
   * @param entryID The entry ID to add.
   * @param values The values to add.
   * @return True if the information was successfully added or False
   * otherwise.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  public boolean add(long entryID, AttributeValue[] values)
      throws JebException, DatabaseException, DirectoryException
  {
    if(values == null)
    {
      return false;
    }

    if(entryIDs == null || entryIDs.length == 0)
    {
      entryIDs = new long[1];
      entryIDs[0] = entryID;
      valuesBytes = attributeValuesToDatabase(values);
      return true;
    }
    if(vlvIndex.comparator.compareValuesInSet(this,
                                              entryIDs.length - 1, entryID,
                                              values) < 0)
    {
      long[] updatedEntryIDs = new long[entryIDs.length + 1];
      System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, entryIDs.length);
      updatedEntryIDs[entryIDs.length] = entryID;

      byte[] newValuesBytes = attributeValuesToDatabase(values);
      byte[] updatedValuesBytes = new byte[valuesBytes.length +
          newValuesBytes.length];
      System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0,
                       valuesBytes.length);
      System.arraycopy(newValuesBytes, 0, updatedValuesBytes,
                       valuesBytes.length,
                       newValuesBytes.length);

      entryIDs = updatedEntryIDs;
      valuesBytes = updatedValuesBytes;
      return true;
    }
    else
    {
      int pos = binarySearch(entryID, values);
      if(pos >= 0)
      {
        if(entryIDs[pos] == entryID)
        {
          // The entry ID is alreadly present.
          return false;
        }
      }
      else
      {
        // For a negative return value r, the vlvIndex -(r+1) gives the array
        // ndex at which the specified value can be inserted to maintain
        // the sorted order of the array.
        pos = -(pos+1);
      }

      long[] updatedEntryIDs = new long[entryIDs.length + 1];
      System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, pos);
      System.arraycopy(entryIDs, pos, updatedEntryIDs, pos+1,
                       entryIDs.length-pos);
      updatedEntryIDs[pos] = entryID;

      byte[] newValuesBytes = attributeValuesToDatabase(values);
      int valuesPos = pos * newValuesBytes.length;
      byte[] updatedValuesBytes = new byte[valuesBytes.length +
          newValuesBytes.length];
      System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0, valuesPos);
      System.arraycopy(valuesBytes, valuesPos,  updatedValuesBytes,
                       valuesPos + newValuesBytes.length,
                       valuesBytes.length - valuesPos);
      System.arraycopy(newValuesBytes, 0, updatedValuesBytes, valuesPos,
                       newValuesBytes.length);

      entryIDs = updatedEntryIDs;
      valuesBytes = updatedValuesBytes;
    }

    return true;
  }

  /**
   * Remove the given entryID and values from this VLV idnex.
   *
   * @param entryID The entry ID to remove.
   * @param values The values to remove.
   * @return True if the information was successfully removed or False
   * otherwise.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  public boolean remove(long entryID, AttributeValue[] values)
      throws JebException, DatabaseException, DirectoryException
  {
    if(entryIDs == null || entryIDs.length == 0)
    {
      return false;
    }

    int pos = binarySearch(entryID, values);
    if(pos < 0)
    {
      // Not found.
      return false;
    }
    else
    {
      // Found it.
      long[] updatedEntryIDs = new long[entryIDs.length - 1];
      System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, pos);
      System.arraycopy(entryIDs, pos+1, updatedEntryIDs, pos,
                       entryIDs.length-pos-1);

      int valuesLength = ENCODED_ATTRIBUTE_VALUE_SIZE *
          vlvIndex.sortOrder.getSortKeys().length;
      int valuesPos = pos * valuesLength;
      byte[] updatedValuesBytes = new byte[valuesBytes.length - valuesLength];
      System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0, valuesPos);
      System.arraycopy(valuesBytes, valuesPos + valuesLength,
                       updatedValuesBytes, valuesPos,
                       valuesBytes.length - valuesPos - valuesLength);

      entryIDs = updatedEntryIDs;
      valuesBytes = updatedValuesBytes;
      return true;
    }
  }

  /**
   * Split portions of this set into another set. The values of the new set is
   * from the front of this set.
   *
   * @param splitLength The size of the new set.
   * @return The split set.
   */
  public SortValuesSet split(int splitLength)
  {
    long[] splitEntryIDs = new long[splitLength];
    byte[] splitValuesBytes = new byte[splitLength *
        ENCODED_ATTRIBUTE_VALUE_SIZE * vlvIndex.sortOrder.getSortKeys().length];

    long[] updatedEntryIDs = new long[entryIDs.length - splitEntryIDs.length];
    System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, updatedEntryIDs.length);
    System.arraycopy(entryIDs, updatedEntryIDs.length, splitEntryIDs, 0,
                     splitEntryIDs.length);

    byte[] updatedValuesBytes = new byte[valuesBytes.length -
        splitValuesBytes.length];
    System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0,
                     updatedValuesBytes.length);
    System.arraycopy(valuesBytes, updatedValuesBytes.length, splitValuesBytes,
                     0, splitValuesBytes.length);

    SortValuesSet splitValuesSet = new SortValuesSet(splitEntryIDs,
                                                     keyBytes,
                                                     splitValuesBytes,
                                                     vlvIndex, id2entry);

    entryIDs = updatedEntryIDs;
    valuesBytes = updatedValuesBytes;
    keyBytes = null;

    return splitValuesSet;
  }

  /**
   * Encode this set to its database format.
   *
   * @return The encoded bytes representing this set.
   */
  public byte[] toDatabase()
  {
    byte[] entryIDBytes = JebFormat.entryIDListToDatabase(entryIDs);
    byte[] concatBytes = new byte[entryIDBytes.length + valuesBytes.length + 4];
    int v = entryIDs.length;

    for (int j = 3; j >= 0; j--)
    {
      concatBytes[j] = (byte) (v & 0xFF);
      v >>>= 8;
    }

    System.arraycopy(entryIDBytes, 0, concatBytes, 4, entryIDBytes.length);
    System.arraycopy(valuesBytes, 0, concatBytes, entryIDBytes.length+4,
                     valuesBytes.length);

    return concatBytes;
  }

  /**
   * Get the size of the provided encoded set.
   *
   * @param bytes The encoded bytes of a SortValuesSet to decode the size from.
   * @param offset The byte offset to start decoding.
   * @return The size of the provided encoded set.
   */
  public static int getEncodedSize(byte[] bytes, int offset)
  {
    int v = 0;
    for (int i = offset; i < offset + 4; i++)
    {
      v <<= 8;
      v |= (bytes[i] & 0xFF);
    }
    return v;
  }

  /**
   * Get the IDs from the provided encoded set.
   *
   * @param bytes The encoded bytes of a SortValuesSet to decode the IDs from.
   * @param offset The byte offset to start decoding.
   * @return The decoded IDs in the provided encoded set.
   */
  public static long[] getEncodedIDs(byte[] bytes, int offset)
  {
    int length = getEncodedSize(bytes, offset);
    byte[] entryIDBytes = new byte[length * 8];
    System.arraycopy(bytes, offset+4, entryIDBytes, 0, entryIDBytes.length);
    return JebFormat.entryIDListFromDatabase(entryIDBytes);
  }

  /**
   * Searches this set for the specified values and entry ID using the binary
   * search algorithm.
   *
   * @param entryID The entry ID to match or -1 if not matching on entry ID.
   * @param values The values to match.
   * @return Index of the entry matching the values and optionally the entry ID
   * if it is found or a negative index if its not found.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  int binarySearch(long entryID, AttributeValue[] values)
      throws JebException, DatabaseException, DirectoryException
  {
    if(entryIDs == null || entryIDs.length == 0)
    {
      return -1;
    }

    int i = 0;
    for(int j = entryIDs.length - 1; i <= j;)
    {
      int k = i + j >> 1;
      int l = vlvIndex.comparator.compareValuesInSet(this, k, entryID, values);
      if(l < 0)
        i = k + 1;
      else
      if(l > 0)
        j = k - 1;
      else
        return k;
    }

    return -(i + 1);
  }

  /**
   * Retrieve the size of this set.
   *
   * @return The size of this set.
   */
  public int size()
  {
    if(entryIDs == null)
    {
      return 0;
    }

    return entryIDs.length;
  }

  /**
   * Retrieve the entry IDs in this set.
   *
   * @return The entry IDs in this set.
   */
  public long[] getEntryIDs()
  {
    return entryIDs;
  }

  private static int encodedLengthSize(int length)
  {
    if ((length & 0x000000FF) == length)
    {
      return 1;
    }
    else if ((length & 0x0000FFFF) == length)
    {
      return 2;
    }
    else if ((length & 0x00FFFFFF) == length)
    {
      return 3;
    }
    else
    {
      return 4;
    }
  }

  private byte[] attributeValuesToDatabase(AttributeValue[] values)
      throws DirectoryException
  {
    byte[] valuesBytes = new byte[values.length *
        (ENCODED_ATTRIBUTE_VALUE_SIZE)];
    for(int i = 0; i < values.length; i++)
    {
      AttributeValue value = values[i];
      int length;
      byte[] lengthBytes = new byte[ENCODED_VALUE_LENGTH_SIZE];
      if(value == null)
      {
        length = 0;
      }
      else
      {
        byte[] valueBytes = value.getNormalizedValueBytes();
        length = valueBytes.length;
        if(valueBytes.length > ENCODED_VALUE_SIZE)
        {
          System.arraycopy(valueBytes, 0, valuesBytes,
                           i * ENCODED_ATTRIBUTE_VALUE_SIZE +
                               ENCODED_VALUE_LENGTH_SIZE,
                           ENCODED_VALUE_SIZE);
        }
        else
        {
          System.arraycopy(valueBytes, 0, valuesBytes,
                           i * ENCODED_ATTRIBUTE_VALUE_SIZE +
                               ENCODED_VALUE_LENGTH_SIZE,
                           valueBytes.length);
        }
      }

      for (int j = ENCODED_VALUE_LENGTH_SIZE - 1; j >= 0; j--)
      {
        lengthBytes[j] = (byte) (length & 0xFF);
        length >>>= 8;
      }

      System.arraycopy(lengthBytes, 0, valuesBytes,
                       i * (ENCODED_ATTRIBUTE_VALUE_SIZE),
                       lengthBytes.length);
    }
    return valuesBytes;
  }

  /**
   * Returns the key to use for this set of sort values in the database.
   *
   * @return The key as an array of bytes that should be used for this set in
   * the database or NULL if this set is empty.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  public byte[] getKeyBytes()
      throws JebException, DatabaseException, DirectoryException
  {
    if(entryIDs == null || entryIDs.length == 0)
    {
      return null;
    }

    if(keyBytes != null)
    {
      return keyBytes;
    }

    SortKey[] sortKeys = vlvIndex.sortOrder.getSortKeys();
    int numValues = sortKeys.length;
    AttributeValue[] values =
        new AttributeValue[numValues];
    for (int i = (entryIDs.length - 1) * numValues, j = 0;
         i < entryIDs.length * numValues;
         i++, j++)
    {
      values[j] = new AttributeValue(sortKeys[j].getAttributeType(),
                                     new ASN1OctetString(getValue(i)));
    }
    keyBytes = vlvIndex.encodeKey(entryIDs[entryIDs.length - 1], values);
    return keyBytes;
  }

  /**
   * Returns the key to use for this set of sort values in the database.
   *
   * @return The key as a sort values object that should be used for this set in
   * the database or NULL if this set is empty or unbounded.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  public SortValues getKeySortValues()
      throws JebException, DatabaseException, DirectoryException
  {
    if(entryIDs == null || entryIDs.length == 0)
    {
      return null;
    }

    if(keyBytes != null && keyBytes.length == 0)
    {
      return null;
    }

    EntryID id = new EntryID(entryIDs[entryIDs.length - 1]);
    SortKey[] sortKeys = vlvIndex.sortOrder.getSortKeys();
    int numValues = sortKeys.length;
    AttributeValue[] values =
        new AttributeValue[numValues];
    for (int i = (entryIDs.length - 1) * numValues, j = 0;
         i < entryIDs.length * numValues;
         i++, j++)
    {
      values[j] = new AttributeValue(sortKeys[j].getAttributeType(),
                                     new ASN1OctetString(getValue(i)));
    }

    return new SortValues(id, values, vlvIndex.sortOrder);
  }

  /**
   * Returns the sort values at the index in this set.
   *
   * @param index The index of the sort values to get.
   * @return The sort values object at the specified index.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   **/
  public SortValues getSortValues(int index)
      throws JebException, DatabaseException, DirectoryException
  {
    if(entryIDs == null || entryIDs.length == 0)
    {
      return null;
    }

    EntryID id = new EntryID(entryIDs[index]);
    SortKey[] sortKeys = vlvIndex.sortOrder.getSortKeys();
    int numValues = sortKeys.length;
    AttributeValue[] values =
        new AttributeValue[numValues];
    for (int i = index * numValues, j = 0;
         i < (index + 1) * numValues;
         i++, j++)
    {
      byte[] value = getValue(i);

      if(value != null)
      {
        values[j] = new AttributeValue(sortKeys[j].getAttributeType(),
                                       new ASN1OctetString(value));
      }
    }

    return new SortValues(id, values, vlvIndex.sortOrder);
  }

  /**
   * Retrieve an attribute value from this values set. The index is the
   * absolute index. (ie. for a sort on 3 attributes per entry, an vlvIndex of 6
   * will be the 1st attribute value of the 3rd entry).
   *
   * @param index The vlvIndex of the attribute value to retrieve.
   * @return The byte array representation of the attribute value.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  public byte[] getValue(int index)
      throws JebException, DatabaseException, DirectoryException
  {
    // If values bytes is null, we have to get the value by getting the
    // entry by ID and getting the value.
    if(valuesBytes != null)
    {
      int pos = index * ENCODED_ATTRIBUTE_VALUE_SIZE;
      int length = 0;
      byte[] valueBytes;
      for (int k = 0; k < ENCODED_VALUE_LENGTH_SIZE; k++, pos++)
      {
        length <<= 8;
        length |= (valuesBytes[pos] & 0xFF);
      }

      if(length == 0)
      {
        return null;
      }
      // If the value has exceeded the max value size, we have to get the
      // value by getting the entry by ID.
      else if(length <= ENCODED_VALUE_SIZE && length > 0)
      {
        valueBytes = new byte[length];
        System.arraycopy(valuesBytes, pos, valueBytes, 0, length);

        return valueBytes;
      }
    }

    // Get the entry from id2entry and assign the values from the entry.
    // Once the values are assigned from the retrieved entry, it will
    // not be retrieve again from future compares.
    EntryID id = new EntryID(entryIDs[index /
        vlvIndex.sortOrder.getSortKeys().length]);
    AttributeValue[] values = cachedAttributeValues.get(id);
    if(values == null)
    {
      values = vlvIndex.getSortValues(id2entry.get(null, id));
      cachedAttributeValues.put(id, values);
    }
    int offset = index % values.length;
    return values[offset].getNormalizedValueBytes();
  }

}

 opends/src/server/org/opends/server/backends/jeb/State.java

@@ -136,6 +136,34 @@
  }

  /**
   * Fetch index state from the database.
   * @param txn The database transaction or null if none.
   * @param vlvIndex The index storing the trusted state info.
   * @return The trusted state of the index in the database.
   * @throws DatabaseException If an error occurs in the JE database.
   */
  public boolean getIndexTrustState(Transaction txn, VLVIndex vlvIndex)
      throws DatabaseException
  {
    String shortName =
        vlvIndex.getName().replace(entryContainer.getDatabasePrefix(), "");
    DatabaseEntry key =
        new DatabaseEntry(StaticUtils.getBytes(shortName));
    DatabaseEntry data = new DatabaseEntry();

    OperationStatus status;
    status = read(txn, key, data, LockMode.DEFAULT);

    if (status != OperationStatus.SUCCESS)
    {
      return false;
    }

    byte[] bytes = data.getData();
    return Arrays.equals(bytes, trueBytes);
  }

  /**
   * Put index state to database.
   * @param txn The database transaction or null if none.
   * @param index The index storing the trusted state info.
@@ -147,10 +175,10 @@
                                    boolean trusted)
       throws DatabaseException
  {
    String sortName =
    String shortName =
        index.getName().replace(entryContainer.getDatabasePrefix(), "");
    DatabaseEntry key =
        new DatabaseEntry(StaticUtils.getBytes(sortName));
        new DatabaseEntry(StaticUtils.getBytes(shortName));
    DatabaseEntry data = new DatabaseEntry();

    if(trusted)
@@ -167,5 +195,35 @@
    return true;
  }

  // TODO: Make sure to update the VLV state access methods to use shortname.
  /**
   * Put VLV index state to database.
   * @param txn The database transaction or null if none.
   * @param vlvIndex The VLV index storing the trusted state info.
   * @param trusted The state value to put into the database.
   * @return true if the entry was written, false if it was not.
   * @throws DatabaseException If an error occurs in the JE database.
   */
  public boolean putIndexTrustState(Transaction txn, VLVIndex vlvIndex,
                                    boolean trusted)
       throws DatabaseException
  {
    String shortName =
        vlvIndex.getName().replace(entryContainer.getDatabasePrefix(), "");
    DatabaseEntry key =
        new DatabaseEntry(StaticUtils.getBytes(shortName));
    DatabaseEntry data = new DatabaseEntry();

    if(trusted)
      data.setData(trueBytes);
    else
      data.setData(falseBytes);

    OperationStatus status;
    status = put(txn, key, data);
    if (status != OperationStatus.SUCCESS)
    {
      return false;
    }
    return true;
  }
}

 opends/src/server/org/opends/server/backends/jeb/VLVIndex.java

New file
@@ -0,0 +1,1451 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.backends.jeb;

import com.sleepycat.je.*;
import org.opends.server.loggers.debug.DebugTracer;
import static org.opends.server.loggers.debug.DebugLogger.getTracer;
import org.opends.server.loggers.ErrorLogger;
import org.opends.server.types.*;
import org.opends.server.admin.std.server.VLVJEIndexCfg;
import org.opends.server.admin.server.ConfigurationChangeListener;
import org.opends.server.core.DirectoryServer;
import org.opends.server.core.SearchOperation;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_INDEX_ADD_REQUIRES_REBUILD;
import static org.opends.server.messages.JebMessages.
    MSGID_ENTRYIDSORTER_NEGATIVE_START_POS;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_CONFIG_VLV_INDEX_BAD_FILTER;

import static org.opends.server.messages.MessageHandler.getMessage;
import static org.opends.server.loggers.debug.DebugLogger.*;
import org.opends.server.util.StaticUtils;
import static org.opends.server.util.StaticUtils.stackTraceToSingleLineString;
import org.opends.server.api.OrderingMatchingRule;
import org.opends.server.config.ConfigException;
import org.opends.server.protocols.asn1.ASN1Element;
import org.opends.server.protocols.ldap.LDAPResultCode;
import org.opends.server.controls.VLVRequestControl;
import org.opends.server.controls.VLVResponseControl;
import org.opends.server.controls.ServerSideSortRequestControl;

import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * This class represents a VLV index. Each database record is a sorted list
 * of entry IDs followed by sets of attribute values used to sort the entries.
 * The entire set of entry IDs are broken up into sorted subsets to decrease
 * the number of database retrivals needed for a range lookup. The records are
 * keyed by the last entry's first sort attribute value. The list of entries
 * in a particular database record maintains the property where the first sort
 * attribute value is bigger then the previous key but smaller or equal
 * to its own key.
 */
public class VLVIndex extends DatabaseContainer
    implements ConfigurationChangeListener<VLVJEIndexCfg>
{
  /**
   * The tracer object for the debug logger.
   */
  private static final DebugTracer TRACER = getTracer();

  /**
   * The comparator for vlvIndex keys.
   */
  public VLVKeyComparator comparator;

  /**
   * The limit on the number of entry IDs that may be indexed by one key.
   */
  private int sortedSetCapacity = 4000;

  /**
   * The cached count of entries in this index.
   */
  private AtomicInteger count;

  private State state;

  /**
   * A flag to indicate if this vlvIndex should be trusted to be consistent
   * with the entries database.
   */
  private boolean trusted = false;

  /**
   * A flag to indicate if a rebuild process is running on this vlvIndex.
   */
  private boolean rebuildRunning = false;

  /**
   * The VLV vlvIndex configuration.
   */
  private VLVJEIndexCfg config;

  private ID2Entry id2entry;

  private DN baseDN;

  private SearchFilter filter;

  private SearchScope scope;

  /**
   * The SortOrder in use by this VLV index to sort the entries.
   */
  public SortOrder sortOrder;


  /**
   * Create a new VLV vlvIndex object.
   *
   * @param config           The VLV index config object to use for this VLV
   *                         index.
   * @param state            The state database to persist vlvIndex state info.
   * @param env              The JE Environemnt
   * @param entryContainer   The database entryContainer holding this vlvIndex.
   * @throws com.sleepycat.je.DatabaseException
   *          If an error occurs in the JE database.
   * @throws ConfigException if a error occurs while reading the VLV index
   * configuration
   */
  public VLVIndex(VLVJEIndexCfg config, State state, Environment env,
                  EntryContainer entryContainer)
      throws DatabaseException, ConfigException
  {
    super(entryContainer.getDatabasePrefix()+"_vlv."+config.getVLVIndexName(),
          env, entryContainer);

    this.config = config;
    this.baseDN = config.getVLVIndexBaseDN();
    this.scope = SearchScope.valueOf(config.getVLVIndexScope().name());
    this.sortedSetCapacity = config.getVLVIndexSortedSetCapacity();
    this.id2entry = entryContainer.getID2Entry();

    try
    {
      this.filter =
          SearchFilter.createFilterFromString(config.getVLVIndexFilter());
    }
    catch(Exception e)
    {
      int msgID = MSGID_JEB_CONFIG_VLV_INDEX_BAD_FILTER;
      String msg = getMessage(msgID, config.getVLVIndexFilter(), name,
                              stackTraceToSingleLineString(e));
      throw new ConfigException(msgID, msg);
    }

    String[] sortAttrs = config.getVLVIndexSortOrder().split(" ");
    SortKey[] sortKeys = new SortKey[sortAttrs.length];
    OrderingMatchingRule[] orderingRules =
        new OrderingMatchingRule[sortAttrs.length];
    boolean[] ascending = new boolean[sortAttrs.length];
    for(int i = 0; i < sortAttrs.length; i++)
    {
      try
      {
        if(sortAttrs[i].startsWith("-"))
        {
          ascending[i] = false;
          sortAttrs[i] = sortAttrs[i].substring(1);
        }
        else
        {
          ascending[i] = true;
          if(sortAttrs[i].startsWith("+"))
          {
            sortAttrs[i] = sortAttrs[i].substring(1);
          }
        }
      }
      catch(Exception e)
      {
        int msgID = MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
        String msg = getMessage(msgID, sortKeys[i], name);
        throw new ConfigException(msgID, msg);
      }

      AttributeType attrType =
          DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
      if(attrType == null)
      {
        int msgID = MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
        String msg = getMessage(msgID, sortKeys[i], name);
        throw new ConfigException(msgID, msg);
      }
      sortKeys[i] = new SortKey(attrType, ascending[i]);
      orderingRules[i] = attrType.getOrderingMatchingRule();
    }

    this.sortOrder = new SortOrder(sortKeys);
    this.comparator = new VLVKeyComparator(orderingRules, ascending);

    DatabaseConfig dbNodupsConfig = new DatabaseConfig();

    if(env.getConfig().getReadOnly())
    {
      dbNodupsConfig.setReadOnly(true);
      dbNodupsConfig.setAllowCreate(false);
      dbNodupsConfig.setTransactional(false);
    }
    else if(!env.getConfig().getTransactional())
    {
      dbNodupsConfig.setAllowCreate(true);
      dbNodupsConfig.setTransactional(false);
      dbNodupsConfig.setDeferredWrite(true);
    }
    else
    {
      dbNodupsConfig.setAllowCreate(true);
      dbNodupsConfig.setTransactional(true);
    }

    this.dbConfig = dbNodupsConfig;
    this.dbConfig.setOverrideBtreeComparator(true);
    this.dbConfig.setBtreeComparator(this.comparator);

    this.state = state;

    this.trusted = state.getIndexTrustState(null, this);
    if(!trusted && entryContainer.getEntryCount() <= 0)
    {
      // If there are no entries in the entry container then there
      // is no reason why this vlvIndex can't be upgraded to trusted.
      setTrusted(null, true);
    }

    // Issue warning if this vlvIndex is not trusted
    if(!trusted)
    {
      int msgID = MSGID_JEB_INDEX_ADD_REQUIRES_REBUILD;
      ErrorLogger.logError(ErrorLogCategory.BACKEND,
                           ErrorLogSeverity.NOTICE, msgID, name);
    }

    this.count = new AtomicInteger(0);
  }

  /**
   * {@inheritDoc}
   */
  public void open() throws DatabaseException
  {
    super.open();

    DatabaseEntry key = new DatabaseEntry();
    OperationStatus status;
    LockMode lockMode = LockMode.RMW;
    DatabaseEntry data = new DatabaseEntry();

    Cursor cursor = openCursor(null, CursorConfig.READ_COMMITTED);

    try
    {
      status = cursor.getFirst(key, data,lockMode);
      while(status == OperationStatus.SUCCESS)
      {
        count.getAndAdd(SortValuesSet.getEncodedSize(data.getData(), 0));
        status = cursor.getNext(key, data, lockMode);
      }
    }
    finally
    {
      cursor.close();
    }
  }

  /**
   * Update the vlvIndex for a new entry.
   *
   * @param txn A database transaction, or null if none is required.
   * @param entryID     The entry ID.
   * @param entry       The entry to be indexed.
   * @return True if the entry ID for the entry are added. False if
   *         the entry ID already exists.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws org.opends.server.types.DirectoryException If a Directory Server
   * error occurs.
   * @throws JebException If an error occurs in the JE backend.
   */
  public boolean addEntry(Transaction txn, EntryID entryID, Entry entry)
      throws DatabaseException, DirectoryException, JebException
  {
    DN entryDN = entry.getDN();
    if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
    {
      return insertValues(txn, entryID.longValue(), entry);
    }
    return false;
  }

  /**
   * Update the vlvIndex for a deleted entry.
   *
   * @param txn         The database transaction to be used for the deletions
   * @param entryID     The entry ID
   * @param entry       The contents of the deleted entry.
   * @return True if the entry was successfully removed from this VLV index
   * or False otherwise.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws JebException If an error occurs in the JE backend.
   */
  public boolean removeEntry(Transaction txn, EntryID entryID, Entry entry)
      throws DatabaseException, DirectoryException, JebException
  {
    DN entryDN = entry.getDN();
    if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
    {
      return removeValues(txn, entryID.longValue(), entry);
    }
    return false;
  }

  /**
   * Update the vlvIndex to reflect a sequence of modifications in a Modify
   * operation.
   *
   * @param txn The JE transaction to use for database updates.
   * @param entryID The ID of the entry that was modified.
   * @param oldEntry The entry before the modifications were applied.
   * @param newEntry The entry after the modifications were applied.
   * @param mods The sequence of modifications in the Modify operation.
   * @return True if the modification was successfully processed or False
   * otherwise.
   * @throws JebException If an error occurs during an operation on a
   * JE database.
   * @throws DatabaseException If an error occurs during an operation on a
   * JE database.
   * @throws DirectoryException If a Directory Server error occurs.
   */
  public boolean modifyEntry(Transaction txn,
                          EntryID entryID,
                          Entry oldEntry,
                          Entry newEntry,
                          List<Modification> mods)
       throws DatabaseException, DirectoryException, JebException
  {
    DN oldEntryDN = oldEntry.getDN();
    DN newEntryDN = newEntry.getDN();
    if(oldEntryDN.matchesBaseAndScope(baseDN, scope) &&
        filter.matchesEntry(oldEntry))
    {
      if(newEntryDN.matchesBaseAndScope(baseDN, scope) &&
          filter.matchesEntry(newEntry))
      {
        // The entry should still be indexed. See if any sorted attributes are
        // changed.
        boolean sortAttributeModified = false;
        SortKey[] sortKeys = sortOrder.getSortKeys();
        for(SortKey sortKey : sortKeys)
        {
          for(Modification mod : mods)
          {
            if(mod.getAttribute().getAttributeType().
                equals(sortKey.getAttributeType()))
            {
              sortAttributeModified = true;
              break;
            }
          }
          if(sortAttributeModified)
          {
            break;
          }
        }
        if(sortAttributeModified)
        {
          boolean success;
          // Sorted attributes have changed. Reindex the entry;
          success = removeValues(txn, entryID.longValue(), oldEntry);
          success &= insertValues(txn, entryID.longValue(), newEntry);
          return success;
        }
      }
      else
      {
        // The modifications caused the new entry to be unindexed. Remove from
        // vlvIndex.
        return removeValues(txn, entryID.longValue(), oldEntry);
      }
    }
    else
    {
      if(newEntryDN.matchesBaseAndScope(baseDN, scope) &&
          filter.matchesEntry(newEntry))
      {
        // The modifications caused the new entry to be indexed. Add to
        // vlvIndex.
        return insertValues(txn, entryID.longValue(), newEntry);
      }
    }

    // The modifications does not affect this vlvIndex
    return true;
  }

  /**
   * Put a sort values set in this VLV index.
   *
   * @param txn The transaction to use when retriving the set or NULL if it is
   *            not required.
   * @param sortValuesSet The SortValuesSet to put.
   * @return True if the sortValuesSet was put successfully or False otherwise.
   * @throws JebException If an error occurs during an operation on a
   * JE database.
   * @throws DatabaseException If an error occurs during an operation on a
   * JE database.
   * @throws DirectoryException If a Directory Server error occurs.
   */
  public boolean putSortValuesSet(Transaction txn, SortValuesSet sortValuesSet)
      throws JebException, DatabaseException, DirectoryException
  {
    DatabaseEntry key = new DatabaseEntry();
    DatabaseEntry data = new DatabaseEntry();

    byte[] after = sortValuesSet.toDatabase();
    key.setData(sortValuesSet.getKeyBytes());
    data.setData(after);
    return put(txn, key, data) == OperationStatus.SUCCESS;
  }

  /**
   * Get a sorted values set that should contain the entry with the given
   * information.
   *
   * @param txn The transaction to use when retriving the set or NULL if it is
   *            not required.
   * @param entryID The entry ID to use.
   * @param values The values to use.
   * @return The SortValuesSet that should contain the entry with the given
   *         information.
   * @throws DatabaseException If an error occurs during an operation on a
   * JE database.
   * @throws DirectoryException If a Directory Server error occurs.
   */
  public SortValuesSet getSortValuesSet(Transaction txn, long entryID,
                                        AttributeValue[] values)
      throws DatabaseException, DirectoryException
  {
    SortValuesSet sortValuesSet = null;
    DatabaseEntry key = new DatabaseEntry();
    OperationStatus status;
    LockMode lockMode = LockMode.DEFAULT;
    DatabaseEntry data = new DatabaseEntry();

    Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);

    try
    {
      key.setData(encodeKey(entryID, values));
      status = cursor.getSearchKeyRange(key, data,lockMode);

      if(status != OperationStatus.SUCCESS)
      {
        // There are no records in the database
        if(debugEnabled())
        {
          TRACER.debugVerbose("No sort values set exist in VLV vlvIndex %s. " +
              "Creating unbound set.", config.getVLVIndexName());
        }
        sortValuesSet = new SortValuesSet(this, id2entry);
      }
      else
      {
        if(debugEnabled())
        {
          StringBuilder searchKeyHex = new StringBuilder();
          StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
          StringBuilder foundKeyHex = new StringBuilder();
          StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
          TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
              "%s\nSearch Key:%s\nFound Key:%s\n",
                              config.getVLVIndexName(),
                              searchKeyHex,
                              foundKeyHex);
        }
        sortValuesSet = new SortValuesSet(key.getData(), data.getData(),
                                          this, id2entry);
      }
    }
    finally
    {
      cursor.close();
    }

    return sortValuesSet;
  }

  /**
   * Search for entries matching the entry ID and attribute values and
   * return its entry ID.
   *
   * @param txn The JE transaction to use for database updates.
   * @param entryID The entry ID to search for.
   * @param values The values to search for.
   * @return The index of the entry ID matching the values or -1 if its not
   * found.
   * @throws DatabaseException If an error occurs during an operation on a
   * JE database.
   * @throws JebException If an error occurs during an operation on a
   * JE database.
   * @throws DirectoryException If a Directory Server error occurs.
   */
  public boolean containsValues(Transaction txn, long entryID,
                             AttributeValue[] values)
      throws JebException, DatabaseException, DirectoryException
  {
    SortValuesSet valuesSet = getSortValuesSet(txn, entryID, values);
    int pos = valuesSet.binarySearch(entryID, values);
    if(pos < 0)
    {
      return false;
    }
    return true;
  }

  private boolean insertValues(Transaction txn, long entryID, Entry entry)
      throws JebException, DatabaseException, DirectoryException
  {
    SortValuesSet sortValuesSet;
    AttributeValue[] values = getSortValues(entry);
    DatabaseEntry key = new DatabaseEntry();
    OperationStatus status;
    LockMode lockMode = LockMode.RMW;
    DatabaseEntry data = new DatabaseEntry();
    boolean success = true;

    Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);

    try
    {
      key.setData(encodeKey(entryID, values));
      status = cursor.getSearchKeyRange(key, data,lockMode);
    }
    finally
    {
      cursor.close();
    }

    if(status != OperationStatus.SUCCESS)
    {
      // There are no records in the database
      if(debugEnabled())
      {
        TRACER.debugVerbose("No sort values set exist in VLV vlvIndex %s. " +
            "Creating unbound set.", config.getVLVIndexName());
      }
      sortValuesSet = new SortValuesSet(this, id2entry);
      key.setData(new byte[0]);
    }
    else
    {
      if(debugEnabled())
      {
        StringBuilder searchKeyHex = new StringBuilder();
        StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
        StringBuilder foundKeyHex = new StringBuilder();
        StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
        TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
            "%s\nSearch Key:%s\nFound Key:%s\n",
                            config.getVLVIndexName(),
                            searchKeyHex,
                            foundKeyHex);
      }
      sortValuesSet = new SortValuesSet(key.getData(), data.getData(),
                                        this, id2entry);
    }




    success = sortValuesSet.add(entryID, values);

    int newSize = sortValuesSet.size();
    if(newSize >= sortedSetCapacity)
    {
      SortValuesSet splitSortValuesSet = sortValuesSet.split(newSize / 2);
      byte[] splitAfter = splitSortValuesSet.toDatabase();
      key.setData(splitSortValuesSet.getKeyBytes());
      data.setData(splitAfter);
      put(txn, key, data);
      byte[] after = sortValuesSet.toDatabase();
      key.setData(sortValuesSet.getKeyBytes());
      data.setData(after);
      put(txn, key, data);

      if(debugEnabled())
      {
        TRACER.debugInfo("SortValuesSet with key %s has reached" +
            " the entry size of %d. Spliting into two sets with " +
            " keys %s and %s.", splitSortValuesSet.getKeySortValues(),
                                newSize, sortValuesSet.getKeySortValues(),
                                splitSortValuesSet.getKeySortValues());
      }
    }
    else
    {
      byte[] after = sortValuesSet.toDatabase();
      data.setData(after);
      put(txn, key, data);
    }

    if(success)
    {
      count.getAndIncrement();
    }

    return success;
  }

  private boolean removeValues(Transaction txn, long entryID, Entry entry)
      throws JebException, DatabaseException, DirectoryException
  {
    SortValuesSet sortValuesSet;
    AttributeValue[] values = getSortValues(entry);
    DatabaseEntry key = new DatabaseEntry();
    OperationStatus status;
    LockMode lockMode = LockMode.RMW;
    DatabaseEntry data = new DatabaseEntry();

    Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);

    try
    {
      key.setData(encodeKey(entryID, values));
      status = cursor.getSearchKeyRange(key, data,lockMode);
    }
    finally
    {
      cursor.close();
    }

    if(status == OperationStatus.SUCCESS)
    {
      if(debugEnabled())
      {
        StringBuilder searchKeyHex = new StringBuilder();
        StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
        StringBuilder foundKeyHex = new StringBuilder();
        StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
        TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
            "%s\nSearch Key:%s\nFound Key:%s\n",
                            config.getVLVIndexName(),
                            searchKeyHex,
                            foundKeyHex);
      }
      sortValuesSet = new SortValuesSet(key.getData(), data.getData(),
                                        this, id2entry);
      boolean success = sortValuesSet.remove(entryID, values);
      byte[] after = sortValuesSet.toDatabase();
      data.setData(after);
      put(txn, key, data);

      if(success)
      {
        count.getAndDecrement();
      }

      return success;
    }
    else
    {
      return false;
    }
  }

  /**
   * Evaluate a search with sort control using this VLV index.
   *
   * @param txn The transaction to used when reading the index or NULL if it is
   *            not required.
   * @param searchOperation The search operation to evaluate.
   * @param sortControl The sort request control to evaluate.
   * @param vlvRequest The VLV request control to evaluate or NULL if VLV is not
   *                   requested.
   * @param debugBuilder If not null, a diagnostic string will be written
   *                     which will help determine how this index contributed
   *                     to this search.
   * @return The sorted EntryIDSet containing the entry IDs that match the
   *         search criteria.
   * @throws DirectoryException If a Directory Server error occurs.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE database.
   */
  public EntryIDSet evaluate(Transaction txn,
                             SearchOperation searchOperation,
                             ServerSideSortRequestControl sortControl,
                             VLVRequestControl vlvRequest,
                             StringBuilder debugBuilder)
      throws DirectoryException, DatabaseException, JebException
  {
    if(!trusted || rebuildRunning)
    {
      return null;
    }
    if(!searchOperation.getBaseDN().equals(baseDN))
    {
      return null;
    }
    if(!searchOperation.getScope().equals(scope))
    {
      return null;
    }
    if(!searchOperation.getFilter().equals(filter))
    {
      return null;
    }
    if(!sortControl.getSortOrder().equals(this.sortOrder))
    {
      return null;
    }

    if (debugBuilder != null)
    {
      debugBuilder.append("vlv=");
      debugBuilder.append("[INDEX:");
      debugBuilder.append(name.replace(entryContainer.getDatabasePrefix() + "_",
                                       ""));
      debugBuilder.append("]");
    }

    long[] selectedIDs = new long[0];
    if(vlvRequest != null)
    {
      int currentCount = count.get();
      int beforeCount = vlvRequest.getBeforeCount();
      int afterCount  = vlvRequest.getAfterCount();

      if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET)
      {
        int targetOffset = vlvRequest.getOffset();
        if (targetOffset < 0)
        {
          // The client specified a negative target offset.  This should never
          // be allowed.
          searchOperation.addResponseControl(
              new VLVResponseControl(targetOffset, currentCount,
                                     LDAPResultCode.OFFSET_RANGE_ERROR));

          int    msgID   = MSGID_ENTRYIDSORTER_NEGATIVE_START_POS;
          String message = getMessage(msgID);
          throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR,
                                       message, msgID);
        }
        else if (targetOffset == 0)
        {
          // This is an easy mistake to make, since VLV offsets start at 1
          // instead of 0.  We'll assume the client meant to use 1.
          targetOffset = 1;
        }
        int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0.
        int startPos = listOffset - beforeCount;
        if (startPos < 0)
        {
          // This can happen if beforeCount >= offset, and in this case we'll
          // just adjust the start position to ignore the range of beforeCount
          // that doesn't exist.
          startPos    = 0;
          beforeCount = listOffset;
        }
        else if(startPos >= currentCount)
        {
          // The start position is beyond the end of the list.  In this case,
          // we'll assume that the start position was one greater than the
          // size of the list and will only return the beforeCount entries.
          // The start position is beyond the end of the list.  In this case,
          // we'll assume that the start position was one greater than the
          // size of the list and will only return the beforeCount entries.
          targetOffset = currentCount + 1;
          listOffset   = currentCount;
          startPos     = listOffset - beforeCount;
          afterCount   = 0;
        }

        int count = 1 + beforeCount + afterCount;
        selectedIDs = new long[count];

        DatabaseEntry key = new DatabaseEntry();
        OperationStatus status;
        LockMode lockMode = LockMode.DEFAULT;
        DatabaseEntry data = new DatabaseEntry();

        Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);

        try
        {
          //Locate the set that contains the target entry.
          int cursorCount = 0;
          int selectedPos = 0;
          status = cursor.getFirst(key, data,lockMode);
          while(status == OperationStatus.SUCCESS)
          {
            if(debugEnabled())
            {
              StringBuilder searchKeyHex = new StringBuilder();
              StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(),
                                                  4);
              StringBuilder foundKeyHex = new StringBuilder();
              StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(),
                                                  4);
              TRACER.debugVerbose("Retrieved a sort values set in VLV " +
                  "vlvIndex %s\nSearch Key:%s\nFound Key:%s\n",
                                  config.getVLVIndexName(),
                                  searchKeyHex,
                                  foundKeyHex);
            }
            long[] IDs = SortValuesSet.getEncodedIDs(data.getData(), 0);
            for(int i = startPos + selectedPos - cursorCount;
                i < IDs.length && selectedPos < count;
                i++, selectedPos++)
            {
              selectedIDs[selectedPos] = IDs[i];
            }
            cursorCount += IDs.length;
            status = cursor.getNext(key, data,lockMode);
          }

          if (selectedPos < count)
          {
            // We don't have enough entries in the set to meet the requested
            // page size, so we'll need to shorten the array.
            long[] newIDArray = new long[selectedPos];
            System.arraycopy(selectedIDs, 0, newIDArray, 0, selectedPos);
            selectedIDs = newIDArray;
          }

          searchOperation.addResponseControl(
              new VLVResponseControl(targetOffset, currentCount,
                                     LDAPResultCode.SUCCESS));

          if(debugBuilder != null)
          {
            debugBuilder.append("[COUNT:");
            debugBuilder.append(cursorCount);
            debugBuilder.append("]");
          }
        }
        finally
        {
          cursor.close();
        }
      }
      else
      {
        int targetOffset = 0;
        int includedBeforeCount = 0;
        int includedAfterCount  = 0;
        LinkedList<EntryID> idList = new LinkedList<EntryID>();
        DatabaseEntry key = new DatabaseEntry();
        OperationStatus status;
        LockMode lockMode = LockMode.DEFAULT;
        DatabaseEntry data = new DatabaseEntry();

        Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);

        try
        {
          byte[] vBytes = vlvRequest.getGreaterThanOrEqualAssertion().value();
          byte[] vLength = ASN1Element.encodeLength(vBytes.length);
          byte[] keyBytes = new byte[vBytes.length + vLength.length];
          System.arraycopy(vLength, 0, keyBytes, 0, vLength.length);
          System.arraycopy(vBytes, 0, keyBytes, vLength.length, vBytes.length);

          key.setData(keyBytes);
          status = cursor.getSearchKeyRange(key, data, lockMode);
          if(status == OperationStatus.SUCCESS)
          {
            if(debugEnabled())
            {
              StringBuilder searchKeyHex = new StringBuilder();
              StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(),
                                                  4);
              StringBuilder foundKeyHex = new StringBuilder();
              StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(),
                                                  4);
              TRACER.debugVerbose("Retrieved a sort values set in VLV " +
                  "vlvIndex %s\nSearch Key:%s\nFound Key:%s\n",
                                  config.getVLVIndexName(),
                                  searchKeyHex,
                                  foundKeyHex);
            }
            SortValuesSet sortValuesSet =
                new SortValuesSet(key.getData(), data.getData(), this,
                                  id2entry);
            AttributeValue[] assertionValue = new AttributeValue[1];
            assertionValue[0] =
                new AttributeValue(
                    sortOrder.getSortKeys()[0].getAttributeType(),
                    vlvRequest.getGreaterThanOrEqualAssertion());

            int adjustedTargetOffset =
                sortValuesSet.binarySearch(-1, assertionValue);
            if(adjustedTargetOffset < 0)
            {
              // For a negative return value r, the vlvIndex -(r+1) gives the
              // array index of the ID that is greater then the assertion value.
              adjustedTargetOffset = -(adjustedTargetOffset+1);
            }

            targetOffset = adjustedTargetOffset;

            // Iterate through all the sort values sets before this one to find
            // the target offset in the index.
            int lastOffset = adjustedTargetOffset - 1;
            long[] lastIDs = sortValuesSet.getEntryIDs();
            while(true)
            {
              for(int i = lastOffset;
                  i >= 0 && includedBeforeCount < beforeCount; i--)
              {
                idList.addFirst(new EntryID(lastIDs[i]));
                includedBeforeCount++;
              }

              status = cursor.getPrev(key, data, lockMode);

              if(status != OperationStatus.SUCCESS)
              {
                break;
              }

              if(includedBeforeCount < beforeCount)
              {
                lastIDs =
                    SortValuesSet.getEncodedIDs(data.getData(), 0);
                lastOffset = lastIDs.length - 1;
                targetOffset += lastIDs.length;
              }
              else
              {
                targetOffset += SortValuesSet.getEncodedSize(data.getData(), 0);
              }
            }


            // Set the cursor back to the position of the target entry set
            key.setData(sortValuesSet.getKeyBytes());
            cursor.getSearchKey(key, data, lockMode);

            // Add the target and after count entries if the target was found.
            lastOffset = adjustedTargetOffset;
            lastIDs = sortValuesSet.getEntryIDs();
            int afterIDCount = 0;
            while(true)
            {
              for(int i = lastOffset;
                  i < lastIDs.length && includedAfterCount < afterCount + 1;
                  i++)
              {
                idList.addLast(new EntryID(lastIDs[i]));
                includedAfterCount++;
              }

              if(includedAfterCount >= afterCount + 1)
              {
                break;
              }

              status = cursor.getNext(key, data, lockMode);

              if(status != OperationStatus.SUCCESS)
              {
                break;
              }

              lastIDs =
                  SortValuesSet.getEncodedIDs(data.getData(), 0);
              lastOffset = 0;
              afterIDCount += lastIDs.length;
            }

            selectedIDs = new long[idList.size()];
            Iterator<EntryID> idIterator = idList.iterator();
            for (int i=0; i < selectedIDs.length; i++)
            {
              selectedIDs[i] = idIterator.next().longValue();
            }

            searchOperation.addResponseControl(
                new VLVResponseControl(targetOffset + 1, currentCount,
                                       LDAPResultCode.SUCCESS));

            if(debugBuilder != null)
            {
              debugBuilder.append("[COUNT:");
              debugBuilder.append(targetOffset + afterIDCount + 1);
              debugBuilder.append("]");
            }
          }
        }
        finally
        {
          cursor.close();
        }
      }
    }
    else
    {
      LinkedList<long[]> idSets = new LinkedList<long[]>();
      int currentCount = 0;
      DatabaseEntry key = new DatabaseEntry();
      OperationStatus status;
      LockMode lockMode = LockMode.RMW;
      DatabaseEntry data = new DatabaseEntry();

      Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED);

      try
      {
        status = cursor.getFirst(key, data, lockMode);
        while(status == OperationStatus.SUCCESS)
        {
          if(debugEnabled())
          {
            StringBuilder searchKeyHex = new StringBuilder();
            StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4);
            StringBuilder foundKeyHex = new StringBuilder();
            StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4);
            TRACER.debugVerbose("Retrieved a sort values set in VLV vlvIndex " +
                "%s\nSearch Key:%s\nFound Key:%s\n",
                                config.getVLVIndexName(),
                                searchKeyHex,
                                foundKeyHex);
          }
          long[] ids = SortValuesSet.getEncodedIDs(data.getData(), 0);
          idSets.add(ids);
          currentCount += ids.length;
          status = cursor.getNext(key, data, lockMode);
        }
      }
      finally
      {
        cursor.close();
      }

      selectedIDs = new long[currentCount];
      int pos = 0;
      for(long[] id : idSets)
      {
        System.arraycopy(id, 0, selectedIDs, pos, id.length);
        pos += id.length;
      }

      if(debugBuilder != null)
      {
        debugBuilder.append("[COUNT:");
        debugBuilder.append(currentCount);
        debugBuilder.append("]");
      }
    }
    return new EntryIDSet(selectedIDs, 0, selectedIDs.length);
  }

    /**
   * Set the vlvIndex trust state.
   * @param txn A database transaction, or null if none is required.
   * @param trusted True if this vlvIndex should be trusted or false
   *                otherwise.
   * @throws DatabaseException If an error occurs in the JE database.
   */
  public synchronized void setTrusted(Transaction txn, boolean trusted)
      throws DatabaseException
  {
    this.trusted = trusted;
    state.putIndexTrustState(txn, this, trusted);
  }

  /**
   * Set the rebuild status of this vlvIndex.
   * @param rebuildRunning True if a rebuild process on this vlvIndex
   *                       is running or False otherwise.
   */
  public synchronized void setRebuildStatus(boolean rebuildRunning)
  {
    this.rebuildRunning = rebuildRunning;
  }

  /**
   * Gets the values to sort on from the entry.
   *
   * @param entry The entry to get the values from.
   * @return The attribute values to sort on.
   */
  AttributeValue[] getSortValues(Entry entry)
  {
    SortKey[] sortKeys = sortOrder.getSortKeys();
    AttributeValue[] values = new AttributeValue[sortKeys.length];
    for (int i=0; i < sortKeys.length; i++)
    {
      SortKey sortKey = sortKeys[i];
      AttributeType attrType = sortKey.getAttributeType();
      List<Attribute> attrList = entry.getAttribute(attrType);
      if (attrList != null)
      {
        AttributeValue sortValue = null;

        // There may be multiple versions of this attribute in the target entry
        // (e.g., with different sets of options), and it may also be a
        // multivalued attribute.  In that case, we need to find the value that
        // is the best match for the corresponding sort key (i.e., for sorting
        // in ascending order, we want to find the lowest value; for sorting in
        // descending order, we want to find the highest value).  This is
        // handled by the SortKey.compareValues method.
        for (Attribute a : attrList)
        {
          for (AttributeValue v : a.getValues())
          {
            if (sortValue == null)
            {
              sortValue = v;
            }
            else if (sortKey.compareValues(v, sortValue) < 0)
            {
              sortValue = v;
            }
          }
        }

        values[i] = sortValue;
      }
    }
    return values;
  }

  /**
   * Encode a VLV database key with the given information.
   *
   * @param entryID The entry ID to encode.
   * @param values The values to encode.
   * @return The encoded bytes.
   * @throws DirectoryException If a Directory Server error occurs.
   */
  byte[] encodeKey(long entryID, AttributeValue[] values)
      throws DirectoryException
  {
    int totalValueBytes = 0;
    LinkedList<byte[]> valueBytes = new LinkedList<byte[]>();
    for (AttributeValue v : values)
    {
      byte[] vBytes;
      if(v == null)
      {
        vBytes = new byte[0];
      }
      else
      {
        vBytes = v.getNormalizedValueBytes();
      }
      byte[] vLength = ASN1Element.encodeLength(vBytes.length);
      valueBytes.add(vLength);
      valueBytes.add(vBytes);
      totalValueBytes += vLength.length + vBytes.length;
    }

    byte[] entryIDBytes =
        JebFormat.entryIDToDatabase(entryID);
    byte[] attrBytes = new byte[entryIDBytes.length + totalValueBytes];

    int pos = 0;
    for (byte[] b : valueBytes)
    {
      System.arraycopy(b, 0, attrBytes, pos, b.length);
      pos += b.length;
    }

    System.arraycopy(entryIDBytes, 0, attrBytes, pos, entryIDBytes.length);

    return attrBytes;
  }

  /**
   * Get the sorted set capacity configured for this VLV index.
   *
   * @return The sorted set capacity.
   */
  public int getSortedSetCapacity()
  {
    return sortedSetCapacity;
  }

  /**
   * Indicates if the given entry should belong in this VLV index.
   *
   * @param entry The entry to check.
   * @return True if the given entry should belong in this VLV index or False
   *         otherwise.
   * @throws DirectoryException If a Directory Server error occurs.
   */
  public boolean shouldInclude(Entry entry) throws DirectoryException
  {
    DN entryDN = entry.getDN();
    if(entryDN.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(entry))
    {
      return true;
    }
    return false;
  }

  /**
   * {@inheritDoc}
   */
  public synchronized boolean isConfigurationChangeAcceptable(
      VLVJEIndexCfg cfg,
      List<String> unacceptableReasons)
  {
    try
    {
      this.filter =
          SearchFilter.createFilterFromString(config.getVLVIndexFilter());
    }
    catch(Exception e)
    {
      int msgID = MSGID_JEB_CONFIG_VLV_INDEX_BAD_FILTER;
      String msg = getMessage(msgID, config.getVLVIndexFilter(), name,
                              stackTraceToSingleLineString(e));
      unacceptableReasons.add(msg);
      return false;
    }

    String[] sortAttrs = config.getVLVIndexSortOrder().split(" ");
    SortKey[] sortKeys = new SortKey[sortAttrs.length];
    OrderingMatchingRule[] orderingRules =
        new OrderingMatchingRule[sortAttrs.length];
    boolean[] ascending = new boolean[sortAttrs.length];
    for(int i = 0; i < sortAttrs.length; i++)
    {
      try
      {
        if(sortAttrs[i].startsWith("-"))
        {
          ascending[i] = false;
          sortAttrs[i] = sortAttrs[i].substring(1);
        }
        else
        {
          ascending[i] = true;
          if(sortAttrs[i].startsWith("+"))
          {
            sortAttrs[i] = sortAttrs[i].substring(1);
          }
        }
      }
      catch(Exception e)
      {
        int msgID = MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
        String msg = getMessage(msgID, sortKeys[i], name);
        unacceptableReasons.add(msg);
        return false;
      }

      AttributeType attrType =
          DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
      if(attrType == null)
      {
        int msgID = MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
        String msg = getMessage(msgID, sortKeys[i], name);
        unacceptableReasons.add(msg);
        return false;
      }
      sortKeys[i] = new SortKey(attrType, ascending[i]);
      orderingRules[i] = attrType.getOrderingMatchingRule();
    }

    return true;
  }

  /**
   * {@inheritDoc}
   */
  public synchronized ConfigChangeResult applyConfigurationChange(
      VLVJEIndexCfg cfg)
  {
    ResultCode resultCode = ResultCode.SUCCESS;
    boolean adminActionRequired = false;
    ArrayList<String> messages = new ArrayList<String>();

    // Update base DN only if changed..
    if(!config.getVLVIndexBaseDN().equals(cfg.getVLVIndexBaseDN()))
    {
      this.baseDN = cfg.getVLVIndexBaseDN();
      adminActionRequired = true;
    }

    // Update scope only if changed.
    if(!config.getVLVIndexScope().equals(cfg.getVLVIndexScope()))
    {
      this.scope = SearchScope.valueOf(cfg.getVLVIndexScope().name());
      adminActionRequired = true;
    }

    // Update sort set capacity only if changed.
    if(config.getVLVIndexSortedSetCapacity() !=
        cfg.getVLVIndexSortedSetCapacity())
    {
      this.sortedSetCapacity = cfg.getVLVIndexSortedSetCapacity();

      // Require admin action only if the new capacity is larger. Otherwise,
      // we will lazyly update the sorted sets.
      if(config.getVLVIndexSortedSetCapacity() <
          cfg.getVLVIndexSortedSetCapacity())
      {
        adminActionRequired = true;
      }
    }

    // Update the filter only if changed.
    if(!config.getVLVIndexFilter().equals(cfg.getVLVIndexFilter()))
    {
      try
      {
        this.filter =
            SearchFilter.createFilterFromString(cfg.getVLVIndexFilter());
        adminActionRequired = true;
      }
      catch(Exception e)
      {
        int msgID = MSGID_JEB_CONFIG_VLV_INDEX_BAD_FILTER;
        String msg = getMessage(msgID, config.getVLVIndexFilter(), name,
                                stackTraceToSingleLineString(e));
        messages.add(msg);
        if(resultCode == ResultCode.SUCCESS)
        {
          resultCode = ResultCode.INVALID_ATTRIBUTE_SYNTAX;
        }
      }
    }

    // Update the sort order only if changed.
    if(!config.getVLVIndexSortOrder().equals(
        cfg.getVLVIndexSortedSetCapacity()))
    {
      String[] sortAttrs = cfg.getVLVIndexSortOrder().split(" ");
      SortKey[] sortKeys = new SortKey[sortAttrs.length];
      OrderingMatchingRule[] orderingRules =
          new OrderingMatchingRule[sortAttrs.length];
      boolean[] ascending = new boolean[sortAttrs.length];
      for(int i = 0; i < sortAttrs.length; i++)
      {
        try
        {
          if(sortAttrs[i].startsWith("-"))
          {
            ascending[i] = false;
            sortAttrs[i] = sortAttrs[i].substring(1);
          }
          else
          {
            ascending[i] = true;
            if(sortAttrs[i].startsWith("+"))
            {
              sortAttrs[i] = sortAttrs[i].substring(1);
            }
          }
        }
        catch(Exception e)
        {
          int msgID = MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
          String msg = getMessage(msgID, sortKeys[i], name);
          messages.add(msg);
          if(resultCode == ResultCode.SUCCESS)
          {
            resultCode = ResultCode.INVALID_ATTRIBUTE_SYNTAX;
          }
        }

        AttributeType attrType =
            DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase());
        if(attrType == null)
        {
          int msgID = MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR;
          String msg = getMessage(msgID, sortKeys[i], name);
          messages.add(msg);
          if(resultCode == ResultCode.SUCCESS)
          {
            resultCode = ResultCode.INVALID_ATTRIBUTE_SYNTAX;
          }
        }
        sortKeys[i] = new SortKey(attrType, ascending[i]);
        orderingRules[i] = attrType.getOrderingMatchingRule();
      }

      this.sortOrder = new SortOrder(sortKeys);
      this.comparator = new VLVKeyComparator(orderingRules, ascending);

      // We have to close the database and open it using the new comparator.
      entryContainer.exclusiveLock.lock();
      try
      {
        this.close();
        this.dbConfig.setBtreeComparator(this.comparator);
        this.open();
      }
      catch(DatabaseException de)
      {
        messages.add(StaticUtils.stackTraceToSingleLineString(de));
        if(resultCode == ResultCode.SUCCESS)
        {
          resultCode = DirectoryServer.getServerErrorResultCode();
        }
      }
      finally
      {
        entryContainer.exclusiveLock.unlock();
      }

      adminActionRequired = true;
    }


    if(adminActionRequired)
    {
      trusted = false;
      try
      {
        state.putIndexTrustState(null, this, false);
      }
      catch(DatabaseException de)
      {
        messages.add(StaticUtils.stackTraceToSingleLineString(de));
        if(resultCode == ResultCode.SUCCESS)
        {
          resultCode = DirectoryServer.getServerErrorResultCode();
        }
      }
    }

    this.config = cfg;
    return new ConfigChangeResult(resultCode, adminActionRequired, messages);
  }
}

 opends/src/server/org/opends/server/backends/jeb/VLVIndexBuilder.java

New file
@@ -0,0 +1,324 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.backends.jeb;

import static org.opends.server.util.StaticUtils.getFileForPath;
import org.opends.server.types.*;

import java.util.*;
import java.io.*;

import com.sleepycat.je.DatabaseException;
import com.sleepycat.je.Transaction;

/**
 * This class is used to create an VLV vlvIndex for an import process.
 * It is used as follows.
 * <pre>
 * startProcessing();
 * processEntry(entry);
 * processEntry(entry);
 * ...
 * stopProcessing();
 * merge();
 * </pre>
 */
public class VLVIndexBuilder implements IndexBuilder
{
  /**
   * The import context.
   */
  private ImportContext importContext;

  /**
   * The vlvIndex database.
   */
  private VLVIndex vlvIndex;

  /**
   * The add write buffer.
   */
  TreeMap<SortValues,EntryID> addBuffer;

  /**
   * The delete write buffer.
   */
  TreeMap<SortValues,EntryID> delBuffer;

  /**
   * The write buffer size.
   */
  private int bufferSize;

  /**
   * Current output file number.
   */
  private int fileNumber = 0;

  /**
   * A unique prefix for temporary files to prevent conflicts.
   */
  private String fileNamePrefix;

  /**
   * Indicates whether we are replacing existing data or not.
   */
  private boolean replaceExisting = false;


  private ByteArrayOutputStream addBytesStream = new ByteArrayOutputStream();
  private ByteArrayOutputStream delBytesStream = new ByteArrayOutputStream();

  private DataOutputStream addBytesDataStream;
  private DataOutputStream delBytesDataStream;

  /**
   * A file name filter to identify temporary files we have written.
   */
  private FilenameFilter filter = new FilenameFilter()
  {
    public boolean accept(File d, String name)
    {
      return name.startsWith(fileNamePrefix);
    }
  };

  /**
   * Construct an vlvIndex builder.
   *
   * @param importContext The import context.
   * @param vlvIndex The vlvIndex database we are writing.
   * @param bufferSize The amount of memory available for buffering.
   */
  public VLVIndexBuilder(ImportContext importContext,
                         VLVIndex vlvIndex, long bufferSize)
  {
    this.importContext = importContext;
    this.vlvIndex = vlvIndex;
    this.bufferSize = (int)bufferSize/100;
    long tid = Thread.currentThread().getId();
    fileNamePrefix = vlvIndex.getName() + "_" + tid + "_";
    replaceExisting =
        importContext.getLDIFImportConfig().appendToExistingData() &&
            importContext.getLDIFImportConfig().replaceExistingEntries();
    addBytesDataStream = new DataOutputStream(addBytesStream);
    delBytesDataStream = new DataOutputStream(delBytesStream);
  }

  /**
   * {@inheritDoc}
   */
  public void startProcessing()
  {
    // Clean up any work files left over from a previous run.
    File tempDir = getFileForPath(
        importContext.getConfig().getBackendImportTempDirectory());
    File[] files = tempDir.listFiles(filter);
    if (files != null)
    {
      for (File f : files)
      {
        f.delete();
      }
    }

    addBuffer = new TreeMap<SortValues,EntryID>();
    delBuffer = new TreeMap<SortValues, EntryID>();
  }

  /**
   * {@inheritDoc}
   */
  public void processEntry(Entry oldEntry, Entry newEntry, EntryID entryID)
      throws DatabaseException, IOException, DirectoryException
  {
    Transaction txn = null;
    SortValues newValues = new SortValues(entryID, newEntry,
                                          vlvIndex.sortOrder);
    // Update the vlvIndex for this entry.
    if (oldEntry != null)
    {
      if(vlvIndex.shouldInclude(oldEntry))
      {
      // This is an entry being replaced.
      SortValues oldValues = new SortValues(entryID, oldEntry,
                                            vlvIndex.sortOrder);
      removeValues(oldValues, entryID);
      }

    }

    if(vlvIndex.shouldInclude(newEntry))
    {
      insertValues(newValues, entryID);
    }
  }



  /**
   * {@inheritDoc}
   */
  public void stopProcessing() throws IOException
  {
    flushBuffer();
  }

  /**
   * Record the insertion of an entry ID.
   * @param sortValues The sort values.
   * @param entryID The entry ID.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void insertValues(SortValues sortValues, EntryID entryID)
      throws IOException
  {
    if (addBuffer.size() + delBuffer.size() >= bufferSize)
    {
      flushBuffer();
    }

    addBuffer.put(sortValues, entryID);
  }

  /**
   * Record the deletion of an entry ID.
   * @param sortValues The sort values to remove.
   * @param entryID The entry ID.
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void removeValues(SortValues sortValues, EntryID entryID)
      throws IOException
  {
    if (addBuffer.size() + delBuffer.size() >= bufferSize)
    {
      flushBuffer();
    }

    delBuffer.remove(sortValues);
  }

  /**
   * Called when the buffer is full. It first sorts the buffer using the same
   * key comparator used by the vlvIndex database. Then it merges all the
   * IDs for the same key together and writes each key and its list of IDs
   * to an intermediate binary file.
   * A list of deleted IDs is only present if we are replacing existing entries.
   *
   * @throws IOException If an I/O error occurs while writing an intermediate
   * file.
   */
  private void flushBuffer() throws IOException
  {
    if (addBuffer.size() + delBuffer.size() == 0)
    {
      return;
    }

    // Start a new file.
    fileNumber++;
    String fileName = fileNamePrefix + String.valueOf(fileNumber) + "_add";
    File file = new File(getFileForPath(
        importContext.getConfig().getBackendImportTempDirectory()),
                         fileName);
    BufferedOutputStream bufferedStream =
        new BufferedOutputStream(new FileOutputStream(file));
    DataOutputStream dataStream = new DataOutputStream(bufferedStream);

    try
    {
      for (SortValues values : addBuffer.keySet())
      {
        dataStream.writeLong(values.getEntryID());
        for(AttributeValue value : values.getValues())
        {
          if(value != null)
          {
            byte[] valueBytes = value.getValueBytes();
            dataStream.writeInt(valueBytes.length);
            dataStream.write(valueBytes);
          }
          else
          {
            dataStream.writeInt(0);
          }
        }
      }
    }
    finally
    {
      dataStream.close();
    }

    if (replaceExisting)
    {
      fileName = fileNamePrefix + String.valueOf(fileNumber) + "_del";
      file = new File(getFileForPath(
          importContext.getConfig().getBackendImportTempDirectory()),
                      fileName);
      bufferedStream =
          new BufferedOutputStream(new FileOutputStream(file));
      dataStream = new DataOutputStream(bufferedStream);

      try
      {

        for (SortValues values : delBuffer.keySet())
        {
          dataStream.writeLong(values.getEntryID());
          for(AttributeValue value : values.getValues())
          {
            byte[] valueBytes = value.getValueBytes();
            dataStream.writeInt(valueBytes.length);
            dataStream.write(valueBytes);
          }
        }
      }
      finally
      {
        dataStream.close();
      }
    }

    addBuffer = new TreeMap<SortValues,EntryID>();
    delBuffer = new TreeMap<SortValues, EntryID>();
  }

  /**
   * Get a string that identifies this vlvIndex builder.
   *
   * @return A string that identifies this vlvIndex builder.
   */
  public String toString()
  {
    return vlvIndex.toString() + " builder";
  }
}



 opends/src/server/org/opends/server/backends/jeb/VLVIndexMergeThread.java

New file
@@ -0,0 +1,481 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.backends.jeb;

import org.opends.server.api.DirectoryThread;
import org.opends.server.loggers.debug.DebugTracer;
import static org.opends.server.loggers.debug.DebugLogger.getTracer;
import static org.opends.server.loggers.debug.DebugLogger.debugEnabled;
import static org.opends.server.loggers.ErrorLogger.logError;
import org.opends.server.admin.std.server.JEBackendCfg;
import org.opends.server.types.*;
import org.opends.server.protocols.asn1.ASN1OctetString;
import static org.opends.server.util.StaticUtils.getFileForPath;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_INDEX_MERGE_NO_DATA;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_INDEX_MERGE_START;
import static org.opends.server.messages.JebMessages.
    MSGID_JEB_INDEX_MERGE_COMPLETE;
import static org.opends.server.messages.MessageHandler.getMessage;

import java.util.*;
import java.io.*;

import com.sleepycat.je.Transaction;

/**
 * A thread to merge a set of intermediate files from an vlvIndex builder
 * into an vlvIndex database.
 */
public class VLVIndexMergeThread extends DirectoryThread
{
  /**
   * The tracer object for the debug logger.
   */
  private static final DebugTracer TRACER = getTracer();


  /**
   * The buffer size to use when reading data from disk.
   */
  private static final int INPUT_STREAM_BUFFER_SIZE = 65536;

  /**
   * The configuration of the JE backend containing the vlvIndex.
   */
  JEBackendCfg config;

  /**
   * The LDIF import configuration, which indicates whether we are
   * appending to existing data.
   */
  LDIFImportConfig ldifImportConfig;

  /**
   * The vlvIndex database being written.
   */
  VLVIndex vlvIndex;

  /**
   * The name of the vlvIndex for use in file names and log messages.
   */
  String indexName;

  /**
   * Indicates whether we are replacing existing data or not.
   */
  private boolean replaceExisting = false;

  private List<DataInputStream> addDataStreams;
  private List<DataInputStream> delDataStreams;

  /**
   * A weak reference hash map used to cache last sort values read from files.
   */
  private HashMap<DataInputStream,SortValues> lastAddValues =
      new HashMap<DataInputStream,SortValues>();

  private HashMap<DataInputStream,SortValues> lastDelValues =
      new HashMap<DataInputStream,SortValues>();


  /**
   * A file name filter to identify temporary files we have written.
   */
  private FilenameFilter filter = new FilenameFilter()
  {
    public boolean accept(File d, String name)
    {
      return name.startsWith(vlvIndex.getName());
    }
  };

  /**
   * Create a new vlvIndex merge thread.
   * @param config The configuration of the JE backend containing the vlvIndex.
   * @param ldifImportConfig The LDIF import configuration, which indicates
   * whether we are appending to existing data.
   * @param vlvIndex The vlvIndex database to be written.
   */
  VLVIndexMergeThread(JEBackendCfg config,
                      LDIFImportConfig ldifImportConfig,
                      VLVIndex vlvIndex)
  {
    super("Index Merge Thread " + vlvIndex.getName());

    this.config = config;
    this.ldifImportConfig = ldifImportConfig;
    this.vlvIndex = vlvIndex;
    replaceExisting =
        ldifImportConfig.appendToExistingData() &&
            ldifImportConfig.replaceExistingEntries();
    addDataStreams = new ArrayList<DataInputStream>();
    delDataStreams = new ArrayList<DataInputStream>();
    lastAddValues = new HashMap<DataInputStream, SortValues>();
    lastDelValues = new HashMap<DataInputStream, SortValues>();
  }

  /**
   * Run this thread.
   */
  public void run()
  {
    try
    {
      merge();
    }
    catch (Exception e)
    {
      if (debugEnabled())
      {
        TRACER.debugCaught(DebugLogLevel.ERROR, e);
      }

      throw new RuntimeException(e);
    }
  }

  /**
   * The merge phase builds the vlvIndex from intermediate files written
   * during entry processing. Each line of an intermediate file has data for
   * one vlvIndex key and the keys are in order. For each vlvIndex key, the data
   * from each intermediate file containing a line for that key must be merged
   * and written to the vlvIndex.
   * @throws Exception If an error occurs.
   */
  public void merge() throws Exception
  {
    // Open all the files.
    File tempDir = getFileForPath(config.getBackendImportTempDirectory());
    File[] files = tempDir.listFiles(filter);

    if (files == null || files.length == 0)
    {
      int msgID = MSGID_JEB_INDEX_MERGE_NO_DATA;
      String message = getMessage(msgID, vlvIndex.getName());
      logError(ErrorLogCategory.BACKEND, ErrorLogSeverity.NOTICE,
               message, msgID);
      return;
    }

    if (debugEnabled())
    {
      int msgID = MSGID_JEB_INDEX_MERGE_START;
      String message = getMessage(msgID, files.length, vlvIndex.getName());
      TRACER.debugInfo(message);
    }

    Transaction txn = null;

    try
    {
      for (int i = 0; i < files.length; i++)
      {
        // Open a reader for this file.
        BufferedInputStream bufferedStream =
            new BufferedInputStream(new FileInputStream(files[i]),
                                    INPUT_STREAM_BUFFER_SIZE);
        DataInputStream dis = new DataInputStream(bufferedStream);
        if(files[i].getName().endsWith("_add"))
        {
          addDataStreams.add(dis);
        }
        else if(files[i].getName().endsWith("_del"))
        {
          delDataStreams.add(dis);
        }
      }

      while(true)
      {
        SortValuesSet currentSet = null;
        SortValues maxKey = null;
        // Get a set by using the smallest sort values
        SortValues addValue = readNextAdd(maxKey);

        // Process deletes first for this set
        if(replaceExisting)
        {
          SortValues delValue = readNextDel(maxKey);
          if(delValue != null)
          {
            if(currentSet == null)
            {
              if(addValue == null || delValue.compareTo(addValue) < 0)
              {
                // Set the current set using the del value.
                currentSet = vlvIndex.getSortValuesSet(txn,
                                                       delValue.getEntryID(),
                                                       delValue.getValues());
              }
              else
              {
                // Set the current set using the add value.
                currentSet = vlvIndex.getSortValuesSet(txn,
                                                       addValue.getEntryID(),
                                                       addValue.getValues());
              }
              maxKey = currentSet.getKeySortValues();
            }
          }

          while(delValue != null)
          {
            currentSet.remove(delValue.getEntryID(), delValue.getValues());
            delValue = readNextDel(maxKey);
          }
        }

        if(addValue != null)
        {
          if(currentSet == null)
          {
            currentSet = vlvIndex.getSortValuesSet(txn, addValue.getEntryID(),
                                                   addValue.getValues());
            maxKey = currentSet.getKeySortValues();
          }

          while(addValue != null)
          {
            currentSet.add(addValue.getEntryID(), addValue.getValues());
            if(currentSet.size() > vlvIndex.getSortedSetCapacity())
            {
              // Need to split the set as it has exceeded the entry limit.
              SortValuesSet splitSortValuesSet =
                  currentSet.split(currentSet.size() / 2);
              // Find where the set split and see if the last added values
              // is before or after the split.
              SortValues newKey = currentSet.getKeySortValues();

              if(debugEnabled())
              {
                TRACER.debugInfo("SortValuesSet with key %s has reached" +
                    " the entry size of %d. Spliting into two sets with " +
                    " keys %s and %s.", maxKey, currentSet.size(), newKey,
                                        maxKey);
              }

              if(addValue.compareTo(newKey) < 0)
              {
                // The last added values is before the split so we have to
                // keep adding to it.
                vlvIndex.putSortValuesSet(txn, splitSortValuesSet);
                maxKey = newKey;
              }
              else
              {
                // The last added values is after the split so we can add to
                // the newly split set.
                vlvIndex.putSortValuesSet(txn, currentSet);
                currentSet = splitSortValuesSet;
              }
            }
            addValue = readNextAdd(maxKey);
          }
        }

        // We should have made all the modifications to this set. Store it back
        // to database.
        vlvIndex.putSortValuesSet(txn, currentSet);

        if(maxKey == null)
        {
          // If we reached here, we should have processed all the sets and
          // there should be nothing left to add or delete.
          break;
        }
      }

      if(!ldifImportConfig.appendToExistingData())
      {
        vlvIndex.setTrusted(txn, true);
      }
    }
    finally
    {
      for(DataInputStream stream : addDataStreams)
      {
        stream.close();
      }

      for(DataInputStream stream : delDataStreams)
      {
        stream.close();
      }

      // Delete all the files.
      if (files != null)
      {
        for (File f : files)
        {
          f.delete();
        }
      }
    }

    if (debugEnabled())
    {
      int msgID = MSGID_JEB_INDEX_MERGE_COMPLETE;
      String message = getMessage(msgID, vlvIndex.getName());
      TRACER.debugInfo(message);
    }
  }

  /**
   * Reads the next sort values from the files that is smaller then the max.
   * @throws IOException If an I/O error occurs while reading the input file.
   */
  private SortValues readNextAdd(SortValues maxValues)
      throws IOException
  {
    for(DataInputStream dataInputStream : addDataStreams)
    {
      if(lastAddValues.get(dataInputStream) == null)
      {
        try
        {
          SortKey[] sortKeys = vlvIndex.sortOrder.getSortKeys();
          EntryID id = new EntryID(dataInputStream.readLong());
          AttributeValue[] attrValues =
              new AttributeValue[sortKeys.length];
          for(int i = 0; i < sortKeys.length; i++)
          {
            SortKey sortKey = sortKeys[i];
            int length = dataInputStream.readInt();
            if(length > 0)
            {
              byte[] valueBytes = new byte[length];
              if(length == dataInputStream.read(valueBytes, 0, length))
              {
                attrValues[i] =
                    new AttributeValue(sortKey.getAttributeType(),
                                       new ASN1OctetString(valueBytes));
              }
            }

          }
          lastAddValues.put(dataInputStream,
                            new SortValues(id, attrValues, vlvIndex.sortOrder));
        }
        catch (EOFException e)
        {
          continue;
        }
      }
    }

    Map.Entry<DataInputStream, SortValues> smallestEntry = null;
    for(Map.Entry<DataInputStream, SortValues> entry :
        lastAddValues.entrySet())
    {
      if(smallestEntry == null ||
          entry.getValue().compareTo(smallestEntry.getValue()) < 0)
      {
        smallestEntry = entry;
      }
    }

    if(smallestEntry != null)
    {
      SortValues smallestValues = smallestEntry.getValue();
      if(maxValues == null || smallestValues.compareTo(maxValues) <= 0)
      {
        lastAddValues.remove(smallestEntry.getKey());
        return smallestValues;
      }
    }

    return null;
  }

  /**
   * Reads the next sort values from the files that is smaller then the max.
   * @throws IOException If an I/O error occurs while reading the input file.
   */
  private SortValues readNextDel(SortValues maxValues)
      throws IOException
  {
    for(DataInputStream dataInputStream : delDataStreams)
    {
      if(lastDelValues.get(dataInputStream) == null)
      {
        try
        {
          EntryID id = new EntryID(dataInputStream.readLong());
          AttributeValue[] attrValues =
              new AttributeValue[vlvIndex.sortOrder.getSortKeys().length];
          int i = 0;
          for(SortKey sortKey : vlvIndex.sortOrder.getSortKeys())
          {
            int length = dataInputStream.readInt();
            if(length > 0)
            {
              byte[] valueBytes = new byte[length];
              if(length == dataInputStream.read(valueBytes, 0, length))
              {
                attrValues[i] =
                    new AttributeValue(sortKey.getAttributeType(),
                                       new ASN1OctetString(valueBytes));
              }
            }
          }
          lastDelValues.put(dataInputStream,
                            new SortValues(id, attrValues,
                                           vlvIndex.sortOrder));
        }
        catch (EOFException e)
        {
          continue;
        }
      }
    }

    Map.Entry<DataInputStream, SortValues> smallestEntry = null;
    for(Map.Entry<DataInputStream, SortValues> entry :
        lastDelValues.entrySet())
    {
      if(smallestEntry == null ||
          entry.getValue().compareTo(smallestEntry.getValue()) < 0)
      {
        smallestEntry = entry;
      }
    }

    if(smallestEntry != null)
    {
      SortValues smallestValues = smallestEntry.getValue();
      if(maxValues == null || smallestValues.compareTo(maxValues) <= 0)
      {
        lastDelValues.remove(smallestEntry.getKey());
        return smallestValues;
      }
    }

    return null;
  }
}

 opends/src/server/org/opends/server/backends/jeb/VLVKeyComparator.java

New file
@@ -0,0 +1,352 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.backends.jeb;

import org.opends.server.api.OrderingMatchingRule;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.DirectoryException;

import java.util.Comparator;
import java.io.Serializable;

import com.sleepycat.je.DatabaseException;

/**
 * This class is used to compare the keys used in a VLV index. Each key is
 * made up the sort values and the entry ID of the largest entry in the sorted
 * set stored in the data for the key.
 */
public class VLVKeyComparator implements Comparator<byte[]>, Serializable
{
  /**
   * The serial version identifier required to satisfy the compiler because this
   * class implements the <CODE>java.io.Serializable</CODE> interface.  This
   * value was generated using the <CODE>serialver</CODE> command-line utility
   * included with the Java SDK.
   */
  static final long serialVersionUID = 1585167927344130604L;

  private OrderingMatchingRule[] orderingRules;

  private boolean[] ascending;

  /**
   * Construst a new VLV Key Comparator object.
   *
   * @param orderingRules The array of ordering rules to use when comparing
   *                      the decoded values in the key.
   * @param ascending     The array of booleans indicating the ordering for
   *                      each value.
   */
  public VLVKeyComparator(OrderingMatchingRule[] orderingRules,
                          boolean[] ascending)
  {
    this.orderingRules = orderingRules;
    this.ascending = ascending;
  }

  /**
   * Compares the contents of the provided byte arrays to determine their
   * relative order. A key in the VLV index contains the sorted attribute values
   * in order followed by the 8 byte entry ID. A attribute value of length 0
   * means that value is null and the attribute type was not part of the entry.
   * A null value is always considered greater then a non null value. If all
   * attribute values are the same, the entry ID will be used to determine the
   * ordering.
   *
   * When comparing partial keys (ie. keys with only the first attribute value
   * encoded for evaluating VLV assertion value offsets or keys with no entry
   * IDs), only information available in both byte keys will be used to
   * determine the ordering. If all available information is the same, 0 will
   * be returned.
   *
   * @param  b1  The first byte array to use in the comparison.
   * @param  b2  The second byte array to use in the comparison.
   *
   * @return  A negative integer if <CODE>b1</CODE> should come before
   *          <CODE>b2</CODE> in ascending order, a positive integer if
   *          <CODE>b1</CODE> should come after <CODE>b2</CODE> in ascending
   *          order, or zero if there is no difference between the values with
   *          regard to ordering.
   */
  public int compare(byte[] b1, byte[] b2)
  {
    // A 0 length byte array is a special key used for the unbound max
    // sort values set. It always comes after a non length byte array.
    if(b1.length == 0)
    {
      if(b2.length == 0)
      {
        return 0;
      }
      else
      {
        return 1;
      }
    }
    else if(b2.length == 0)
    {
      return -1;
    }

    int b1Pos = 0;
    int b2Pos = 0;
    for (int j=0;
         j < orderingRules.length && b1Pos < b1.length && b2Pos < b2.length;
         j++)
    {
      int b1Length = b1[b1Pos] & 0x7F;
      if (b1[b1Pos++] != b1Length)
      {
        int b1NumLengthBytes = b1Length;
        b1Length = 0;
        for (int k=0; k < b1NumLengthBytes; k++, b1Pos++)
        {
          b1Length = (b1Length << 8) |
              (b1[b1Pos] & 0xFF);
        }
      }

      int b2Length = b2[b2Pos] & 0x7F;
      if (b2[b2Pos++] != b2Length)
      {
        int b2NumLengthBytes = b2Length;
        b2Length = 0;
        for (int k=0; k < b2NumLengthBytes; k++, b2Pos++)
        {
          b2Length = (b2Length << 8) |
              (b2[b2Pos] & 0xFF);
        }
      }

      byte[] b1Bytes;
      byte[] b2Bytes;
      if(b1Length > 0)
      {
        b1Bytes = new byte[b1Length];
        System.arraycopy(b1, b1Pos, b1Bytes, 0, b1Length);
        b1Pos += b1Length;
      }
      else
      {
        b1Bytes = null;
      }

      if(b2Length > 0)
      {
        b2Bytes = new byte[b2Length];
        System.arraycopy(b2, b2Pos, b2Bytes, 0, b2Length);
        b2Pos += b2Length;
      }
      else
      {
        b2Bytes = null;
      }

      // A null value will always come after a non-null value.
      if (b1Bytes == null)
      {
        if (b2Bytes == null)
        {
          continue;
        }
        else
        {
          return 1;
        }
      }
      else if (b2Bytes == null)
      {
        return -1;
      }

      int result;
      if(ascending[j])
      {
        result = orderingRules[j].compare(b1Bytes, b2Bytes);
      }
      else
      {
        result = orderingRules[j].compare(b2Bytes, b1Bytes);
      }

      if(result != 0)
      {
        return result;
      }
    }

    // If we've gotten here, then we can't tell a difference between the sets
    // of available values, so sort based on entry ID if its in the key.

    if(b1Pos + 8 < b1.length && b2Pos + 8 < b2.length)
    {
      long b1ID = 0;
      for (int i = b1Pos; i < b1Pos + 8; i++)
      {
        b1ID <<= 8;
        b1ID |= (b1[i] & 0xFF);
      }

      long b2ID = 0;
      for (int i = b2Pos; i < b2Pos + 8; i++)
      {
        b2ID <<= 8;
        b2ID |= (b2[i] & 0xFF);
      }

      long idDifference = (b1ID - b2ID);
      if (idDifference < 0)
      {
        return -1;
      }
      else if (idDifference > 0)
      {
        return 1;
      }
      else
      {
        return 0;
      }
    }

    // If we've gotten here, then we can't tell the difference between the sets
    // of available values and entry IDs are not all available, so just return
    // 0
    return 0;

  }

  /**
   * Compares the contents in the provided values set with the given values to
   * determine their relative order. A null value is always considered greater
   * then a non null value. If all attribute values are the same, the entry ID
   * will be used to determine the ordering.
   *
   * If the given attribute values array does not contain all the values in the
   * sort order, any missing values will be considered as a unknown or
   * wildcard value instead of a nonexistant value. When comparing partial
   * information, only values available in both the values set and the
   * given values will be used to determine the ordering. If all available
   * information is the same, 0 will be returned.
   *
   * @param  set  The sort values set to containing the values.
   * @param  index The index of the values in the set.
   * @param  entryID The entry ID to use in the comparasion.
   * @param  values The values to use in the comparasion.
   *
   * @return  A negative integer if the values in the set should come before
   *          the given values in ascending order, a positive integer if
   *          the values in the set should come after the given values in
   *          ascending order, or zero if there is no difference between the
   *          values with regard to ordering.
   * @throws DatabaseException If an error occurs during an operation on a
   * JE database.
   * @throws JebException If an error occurs during an operation on a
   * JE database.
   * @throws DirectoryException  If an error occurs while trying to
   *                              normalize the value (e.g., if it is
   *                              not acceptable for use with the
   *                              associated equality matching rule).
   */
  public int compareValuesInSet(SortValuesSet set, int index,
                                long entryID, AttributeValue[] values)
      throws JebException, DatabaseException, DirectoryException
  {
    for (int j=0; j < orderingRules.length; j++)
    {
      if(j >= values.length)
      {
        break;
      }

      byte[] b1Bytes = set.getValue((index * orderingRules.length) + j);
      byte[] b2Bytes = null;

      if(values[j] != null)
      {
        b2Bytes = values[j].getNormalizedValueBytes();
      }

      // A null value will always come after a non-null value.
      if (b1Bytes == null)
      {
        if (b2Bytes == null)
        {
          continue;
        }
        else
        {
          return 1;
        }
      }
      else if (b2Bytes == null)
      {
        return -1;
      }

      int result;
      if(ascending[j])
      {
        result = orderingRules[j].compare(b1Bytes, b2Bytes);
      }
      else
      {
        result = orderingRules[j].compare(b2Bytes, b1Bytes);
      }

      if(result != 0)
      {
        return result;
      }
    }

    if(entryID != -1)
    {
      // If we've gotten here, then we can't tell a difference between the sets
      // of values, so sort based on entry ID.

      long idDifference = (set.getEntryIDs()[index] - entryID);
      if (idDifference < 0)
      {
        return -1;
      }
      else if (idDifference > 0)
      {
        return 1;
      }
      else
      {
        return 0;
      }
    }

    // If we've gotten here, then we can't tell the difference between the sets
    // of available values and the entry ID is not available. Just return 0.
    return 0;
  }
}

 opends/src/server/org/opends/server/backends/jeb/VerifyJob.java

@@ -44,21 +44,10 @@
import org.opends.server.api.ApproximateMatchingRule;
import org.opends.server.core.DirectoryServer;
import org.opends.server.protocols.asn1.ASN1OctetString;
import org.opends.server.types.Attribute;
import org.opends.server.types.AttributeType;
import org.opends.server.types.AttributeValue;
import org.opends.server.types.ByteString;
import org.opends.server.types.ConditionResult;
import org.opends.server.types.DirectoryException;
import org.opends.server.types.DN;
import org.opends.server.types.Entry;
import org.opends.server.types.ErrorLogCategory;
import org.opends.server.types.ErrorLogSeverity;
import org.opends.server.types.SearchFilter;
import org.opends.server.util.StaticUtils;
import org.opends.server.util.ServerConstants;

import org.opends.server.types.DebugLogLevel;
import org.opends.server.types.*;
import static org.opends.server.messages.MessageHandler.getMessage;
import static org.opends.server.messages.JebMessages.*;
import java.util.ArrayList;
@@ -174,6 +163,12 @@
   * A list of the attribute indexes to be verified.
   */
  ArrayList<AttributeIndex> attrIndexList = new ArrayList<AttributeIndex>();

  /**
   * A list of the VLV indexes to be verified.
   */
  ArrayList<VLVIndex> vlvIndexList = new ArrayList<VLVIndex>();

/**
 * The types of indexes that are verifiable.
 */
@@ -200,9 +195,10 @@
   * @return The error count.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws JebException If an error occurs in the JE backend.
   * @throws DirectoryException If an error occurs while verifying the backend.
   */
  public long verifyBackend(RootContainer rootContainer, Entry statEntry) throws
      DatabaseException, JebException
      DatabaseException, JebException, DirectoryException
  {
    this.rootContainer = rootContainer;
    EntryContainer entryContainer =
@@ -250,6 +246,26 @@
          {
            verifyID2Subtree = true;
          }
          else if(lowerName.startsWith("vlv."))
          {
            if(lowerName.length() < 5)
            {
              int msgID = MSGID_JEB_VLV_INDEX_NOT_CONFIGURED;
              String msg = getMessage(msgID, lowerName);
              throw new JebException(msgID, msg);
            }

            VLVIndex vlvIndex =
                entryContainer.getVLVIndex(lowerName.substring(4));
            if(vlvIndex == null)
            {
              int msgID = MSGID_JEB_VLV_INDEX_NOT_CONFIGURED;
              String msg = getMessage(msgID, lowerName.substring(4));
              throw new JebException(msgID, msg);
            }

            vlvIndexList.add(vlvIndex);
          }
          else
          {
            AttributeType attrType =
@@ -304,6 +320,12 @@
        else
        {
          iterateID2Entry();

          // Make sure the vlv indexes are in correct order.
          for(VLVIndex vlvIndex : vlvIndexList)
          {
            iterateVLVIndex(vlvIndex, false);
          }
        }
      }
      finally
@@ -507,8 +529,10 @@
   *
   * @throws JebException If an error occurs in the JE backend.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws DirectoryException If an error occurs reading values in the index.
   */
  private void iterateIndex() throws JebException, DatabaseException
  private void iterateIndex()
      throws JebException, DatabaseException, DirectoryException
  {
    if (verifyDN2ID)
    {
@@ -524,17 +548,23 @@
    }
    else
    {
      AttributeIndex attrIndex = attrIndexList.get(0);
      iterateAttrIndex(attrIndex.getAttributeType(),
              attrIndex.equalityIndex, IndexType.EQ );
      iterateAttrIndex(attrIndex.getAttributeType(),
              attrIndex.presenceIndex, IndexType.PRES);
      iterateAttrIndex(attrIndex.getAttributeType(),
              attrIndex.substringIndex, IndexType.SUBSTRING);
      iterateAttrIndex(attrIndex.getAttributeType(),
              attrIndex.orderingIndex, IndexType.ORDERING);
      iterateAttrIndex(attrIndex.getAttributeType(),
              attrIndex.approximateIndex, IndexType.APPROXIMATE);
      if(attrIndexList.size() > 0)
      {
        AttributeIndex attrIndex = attrIndexList.get(0);
        iterateAttrIndex(attrIndex.getAttributeType(),
                         attrIndex.equalityIndex, IndexType.EQ );
        iterateAttrIndex(attrIndex.getAttributeType(),
                         attrIndex.presenceIndex, IndexType.PRES);
        iterateAttrIndex(attrIndex.getAttributeType(),
                         attrIndex.substringIndex, IndexType.SUBSTRING);
        iterateAttrIndex(attrIndex.getAttributeType(),
                         attrIndex.orderingIndex, IndexType.ORDERING);
        iterateAttrIndex(attrIndex.getAttributeType(),
                         attrIndex.approximateIndex, IndexType.APPROXIMATE);
      } else if(vlvIndexList.size() > 0)
      {
        iterateVLVIndex(vlvIndexList.get(0), true);
      }
    }
  }

@@ -976,6 +1006,130 @@
  }

  /**
   * Iterate through the entries in a VLV index to perform a check for index
   * cleanliness.
   *
   * @param vlvIndex The VLV index to perform the check against.
   * @param verifyID True to verify the IDs against id2entry.
   * @throws JebException If an error occurs in the JE backend.
   * @throws DatabaseException If an error occurs in the JE database.
   * @throws DirectoryException If an error occurs reading values in the index.
   */
  private void iterateVLVIndex(VLVIndex vlvIndex, boolean verifyID)
      throws JebException, DatabaseException, DirectoryException
  {
    if(vlvIndex == null)
    {
      return;
    }

    Cursor cursor = vlvIndex.openCursor(null, new CursorConfig());
    try
    {
      DatabaseEntry key = new DatabaseEntry();
      OperationStatus status;
      LockMode lockMode = LockMode.DEFAULT;
      DatabaseEntry data = new DatabaseEntry();

      status = cursor.getFirst(key, data, lockMode);
      SortValues lastValues = null;
      while(status == OperationStatus.SUCCESS)
      {
        SortValuesSet sortValuesSet =
            new SortValuesSet(key.getData(), data.getData(), vlvIndex,
                              id2entry);
        for(int i = 0; i < sortValuesSet.getEntryIDs().length; i++)
        {
          keyCount++;
          SortValues values = sortValuesSet.getSortValues(i);
          if(lastValues != null && lastValues.compareTo(values) >= 1)
          {
            // Make sure the values is larger then the previous one.
            if(debugEnabled())
            {
              TRACER.debugError("Values %s and %s are incorrectly ordered",
                                lastValues, values, keyDump(vlvIndex,
                                          sortValuesSet.getKeySortValues()));
            }
            errorCount++;
          }
          if(i == sortValuesSet.getEntryIDs().length - 1 &&
              key.getData().length != 0)
          {
            // If this is the last one in a bounded set, make sure it is the
            // same as the database key.
            byte[] encodedKey = vlvIndex.encodeKey(values.getEntryID(),
                                                   values.getValues());
            if(!Arrays.equals(key.getData(), encodedKey))
            {
              if(debugEnabled())
              {
                TRACER.debugError("Incorrect key for SortValuesSet in VLV " +
                    "index %s. Last values bytes %s, Key bytes %s",
                                  vlvIndex.getName(), encodedKey, key);
              }
              errorCount++;
            }
          }
          lastValues = values;

          if(verifyID)
          {
            Entry entry;
            EntryID id = new EntryID(values.getEntryID());
            try
            {
              entry = id2entry.get(null, id);
            }
            catch (Exception e)
            {
              if (debugEnabled())
              {
                TRACER.debugCaught(DebugLogLevel.ERROR, e);
              }
              errorCount++;
              continue;
            }

            if (entry == null)
            {
              errorCount++;
              if (debugEnabled())
              {
                TRACER.debugError("Reference to unknown ID %d%n%s",
                                  id.longValue(),
                                  keyDump(vlvIndex,
                                          sortValuesSet.getKeySortValues()));
              }
              continue;
            }

            SortValues entryValues =
                new SortValues(id, entry, vlvIndex.sortOrder);
            if(entryValues.compareTo(values) != 0)
            {
              errorCount++;
              if(debugEnabled())
              {
                TRACER.debugError("Reference to entry ID %d " +
                    "which does not match the values%n%s",
                                  id.longValue(),
                                  keyDump(vlvIndex,
                                          sortValuesSet.getKeySortValues()));
              }
            }
          }
        }
        status = cursor.getNext(key, data, lockMode);
      }
    }
    finally
    {
      cursor.close();
    }
  }

  /**
   * Iterate through the entries in an attribute index to perform a check for
   * index cleanliness.
   * @param attrType The attribute type of the index to be checked.
@@ -1244,7 +1398,7 @@
    {
      verifyID2Subtree(entryID, entry);
    }
    verifyAttrIndex(entryID, entry);
    verifyIndex(entryID, entry);
  }

  /**
@@ -1506,12 +1660,49 @@
  }

  /**
   * Construct a printable string from a raw key value.
   *
   * @param vlvIndex The vlvIndex database containing the key value.
   * @param keySortValues THe sort values that is being used as the key.
   * @return A string that may be logged or printed.
   */
  private String keyDump(VLVIndex vlvIndex, SortValues keySortValues)
  {
/*
    String str;
    try
    {
      str = new String(keyBytes, "UTF-8");
    }
    catch (UnsupportedEncodingException e)
    {
      str = StaticUtils.bytesToHex(keyBytes);
    }
    return str;
*/
    StringBuilder buffer = new StringBuilder(128);
    buffer.append("File: ");
    buffer.append(vlvIndex.toString());
    buffer.append(ServerConstants.EOL);
    buffer.append("Key (last sort values):");
    if(keySortValues == null)
    {
      buffer.append("UNBOUNDED (0x00)");
    }
    else
    {
      buffer.append(keySortValues.toString());
    }
    return buffer.toString();
  }

  /**
   * Check that an attribute index is complete for a given entry.
   *
   * @param entryID The entry ID.
   * @param entry The entry to be checked.
   */
  private void verifyAttrIndex(EntryID entryID, Entry entry)
  private void verifyIndex(EntryID entryID, Entry entry)
  {
    for (AttributeIndex attrIndex : attrIndexList)
    {
@@ -1538,6 +1729,67 @@
        }
      }
    }

    for (VLVIndex vlvIndex : vlvIndexList)
    {
      try
      {
        if(vlvIndex.shouldInclude(entry))
        {
          if(!vlvIndex.containsValues(null, entryID.longValue(),
                                  vlvIndex.getSortValues(entry)))
          {
            if(debugEnabled())
            {
              TRACER.debugError("Missing entry %s in VLV index %s",
                                entry.getDN().toString(),
                                vlvIndex.getName());
            }
            errorCount++;
          }
        }
      }
      catch (DirectoryException e)
      {
        if (debugEnabled())
        {
          TRACER.debugCaught(DebugLogLevel.ERROR, e);

          TRACER.debugError("Error checking entry %s against filter or " +
              "base DN for VLV index %s: %s",
                     entry.getDN().toString(),
                     vlvIndex.getName(),
                     e.getErrorMessage());
        }
        errorCount++;
      }
      catch (DatabaseException e)
      {
        if (debugEnabled())
        {
          TRACER.debugCaught(DebugLogLevel.ERROR, e);

          TRACER.debugError("Error reading VLV index %s for entry %s: %s",
                     vlvIndex.getName(),
                     entry.getDN().toString(),
                     StaticUtils.getBacktrace(e));
        }
        errorCount++;
      }
      catch (JebException e)
      {
        if (debugEnabled())
        {
          TRACER.debugCaught(DebugLogLevel.ERROR, e);

          TRACER.debugError("Error reading VLV index %s for entry %s: %s",
                     vlvIndex.getName(),
                     entry.getDN().toString(),
                     StaticUtils.getBacktrace(e));
        }
        errorCount++;
      }
    }
  }

  /**

 opends/src/server/org/opends/server/messages/JebMessages.java

@@ -1239,6 +1239,29 @@
      CATEGORY_MASK_JEB | SEVERITY_MASK_INFORMATIONAL | 159;

  /**
   * The message ID used to indicate an invalid sort attribute defined for a
   * VLV index.
   */
  public static final int MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR =
       CATEGORY_MASK_JEB | SEVERITY_MASK_SEVERE_ERROR | 160;

  /**
   * The message ID used to indicate a bad search filter defined for a
   * VLV index.
   */
  public static final int MSGID_JEB_CONFIG_VLV_INDEX_BAD_FILTER =
      CATEGORY_MASK_JEB | SEVERITY_MASK_SEVERE_ERROR | 161;

  /**
   * The message ID of an error indicating that there is no VLV index
   * configured for an name that was provided to an index
   * verification job.  This message takes one string argument which is the
   * VLV index name.
   */
  public static final int MSGID_JEB_VLV_INDEX_NOT_CONFIGURED =
      CATEGORY_MASK_JEB | SEVERITY_MASK_MILD_ERROR | 162;

  /**
   * Associates a set of generic messages with the message IDs defined in this
   * class.
   */
@@ -1604,5 +1627,13 @@
                    "Processing LDIF");
    registerMessage(MSGID_JEB_IMPORT_LDIF_END,
                    "End of LDIF reached");
    registerMessage(MSGID_JEB_CONFIG_VLV_INDEX_UNDEFINED_ATTR,
                    "Sort attribute %s for VLV index %s is not defined in " +
                    "the server schema");
    registerMessage(MSGID_JEB_CONFIG_VLV_INDEX_BAD_FILTER,
                    "An error occured while parsing the search filter %s " +
                    "defined for VLV index %s: %s");
    registerMessage(MSGID_JEB_VLV_INDEX_NOT_CONFIGURED,
                    "There is no VLV index configured with name '%s'");
  }
}

 opends/src/server/org/opends/server/tools/VerifyIndex.java

@@ -61,6 +61,7 @@
import static org.opends.server.messages.MessageHandler.*;
import static org.opends.server.util.ServerConstants.*;
import static org.opends.server.util.StaticUtils.*;
import org.opends.server.util.StaticUtils;
import static org.opends.server.tools.ToolConstants.*;
import org.opends.server.admin.std.server.BackendCfg;

@@ -546,7 +547,8 @@
    catch (Exception e)
    {
      int    msgID   = MSGID_VERIFYINDEX_ERROR_DURING_VERIFY;
      String message = getMessage(msgID, getExceptionMessage(e));
      String message = getMessage(msgID,
                                  StaticUtils.stackTraceToSingleLineString(e));
      logError(ErrorLogCategory.BACKEND, ErrorLogSeverity.SEVERE_ERROR, message,
               msgID);
      returnCode = 1;

 opends/src/server/org/opends/server/types/SortKey.java

@@ -280,5 +280,94 @@

    buffer.append(")");
  }

  /**
   * Retrieves the hash code for this sort key.
   *
   * @return  The hash code for this sort key.
   */
  public int hashCode()
  {
    int hashCode = 0;

    if(ascending)
    {
      hashCode += 1;
    }

    hashCode += attributeType.hashCode();

    if(orderingRule != null)
    {
      hashCode += orderingRule.hashCode();
    }

    return hashCode;
  }

  /**
   * Indicates whether this sort key is equal to the provided
   * object.
   *
   * @param  o  The object for which to make the determination.
   *
   * @return  <CODE>true</CODE> if the provide object is equal to this
   *          sort key, or <CODE>false</CODE> if it is not.
   */
  public boolean equals(Object o)
  {
    if(o == null)
    {
      return false;
    }

    if (o == this)
    {
      return true;
    }

    if (! (o instanceof SortKey))
    {
      return false;
    }

    SortKey s = (SortKey) o;

    if(ascending != s.ascending)
    {
      return false;
    }

    if(!attributeType.equals(s.attributeType))
    {
      return false;
    }

    if(orderingRule != null)
    {
      if(s.orderingRule != null)
      {
        if(!orderingRule.equals(s.orderingRule))
        {
          return false;
        }
      }
      else if(!orderingRule.equals(
          s.attributeType.getOrderingMatchingRule()))
      {
        return false;
      }
    }
    else if(s.orderingRule != null)
    {
      if(!attributeType.getOrderingMatchingRule().equals(
          s.orderingRule))
      {
        return false;
      }
    }

    return true;
  }
}


 opends/src/server/org/opends/server/types/SortOrder.java

@@ -131,5 +131,65 @@

    buffer.append(")");
  }

  /**
   * Retrieves the hash code for this sort order.
   *
   * @return  The hash code for this sort order.
   */
  public int hashCode()
  {
    int hashCode = 0;
    for(SortKey sortKey : sortKeys)
    {
      hashCode += sortKey.hashCode();
    }

    return hashCode;
  }

  /**
   * Indicates whether this sort order is equal to the provided
   * object.
   *
   * @param  o  The object for which to make the determination.
   *
   * @return  <CODE>true</CODE> if the provide object is equal to this
   *          sort order, or <CODE>false</CODE> if it is not.
   */
  public boolean equals(Object o)
  {
    if(o == null)
    {
      return false;
    }

    if (o == this)
    {
      return true;
    }

    if (! (o instanceof SortOrder))
    {
      return false;
    }

    SortOrder s = (SortOrder) o;

    if(sortKeys.length != s.sortKeys.length)
    {
      return false;
    }

    for(int i = 0; i < sortKeys.length; i++)
    {
      if(!sortKeys[i].equals(s.sortKeys[i]))
      {
        return false;
      }
    }

    return true;
  }
}


 opends/tests/unit-tests-testng/resource/config-changes.ldif

@@ -402,6 +402,22 @@
ds-cfg-backend-entries-compressed: false
ds-cfg-backend-deadlock-retry-limit: 10

dn: cn=VLV Index,ds-cfg-backend-id=rebuildRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-branch
cn: VLV Index

dn: ds-cfg-vlv-je-index-name=testvlvindex,cn=VLV Index,ds-cfg-backend-id=rebuildRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-vlv-je-index
ds-cfg-vlv-je-index-name: testvlvindex
ds-cfg-vlv-je-index-base-dn: dc=rebuild, dc=jeb
ds-cfg-vlv-je-index-scope: whole-subtree
ds-cfg-vlv-je-index-filter: (objectClass=*)
ds-cfg-vlv-je-index-sort-order: givenname -sn +uid

dn: cn=Index,ds-cfg-backend-id=rebuildRoot,cn=Backends,cn=config
changetype: add
objectClass: top
@@ -443,6 +459,22 @@
ds-cfg-backend-entries-compressed: false
ds-cfg-backend-deadlock-retry-limit: 10

dn: cn=VLV Index,ds-cfg-backend-id=importRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-branch
cn: VLV Index

dn: ds-cfg-vlv-je-index-name=testvlvindex,cn=VLV Index,ds-cfg-backend-id=importRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-vlv-je-index
ds-cfg-vlv-je-index-name: testvlvindex
ds-cfg-vlv-je-index-base-dn: dc=com
ds-cfg-vlv-je-index-scope: whole-subtree
ds-cfg-vlv-je-index-filter: (objectClass=*)
ds-cfg-vlv-je-index-sort-order: givenname -sn +uid

dn: ds-cfg-backend-id=verifyRoot,cn=Backends,cn=config
changetype: add
objectClass: top
@@ -466,6 +498,22 @@
ds-cfg-backend-entries-compressed: false
ds-cfg-backend-deadlock-retry-limit: 10

dn: cn=VLV Index,ds-cfg-backend-id=verifyRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-branch
cn: VLV Index

dn: ds-cfg-vlv-je-index-name=testvlvindex,cn=VLV Index,ds-cfg-backend-id=verifyRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-vlv-je-index
ds-cfg-vlv-je-index-name: testvlvindex
ds-cfg-vlv-je-index-base-dn: dc=verify, dc=jeb
ds-cfg-vlv-je-index-scope: whole-subtree
ds-cfg-vlv-je-index-filter: (objectClass=*)
ds-cfg-vlv-je-index-sort-order: givenname -sn +uid

dn: cn=Index,ds-cfg-backend-id=verifyRoot,cn=Backends,cn=config
changetype: add
objectClass: top
@@ -557,6 +605,7 @@
ds-cfg-backend-writability-mode: enabled
ds-cfg-backend-base-dn: dc=test,dc=com
ds-cfg-backend-base-dn: dc=test1,dc=com
ds-cfg-backend-base-dn: dc=vlvtest,dc=com
ds-cfg-backend-directory: db_index_test
ds-cfg-backend-mode: 700
ds-cfg-backend-index-entry-limit: 13
@@ -570,6 +619,23 @@
ds-cfg-backend-entries-compressed: false
ds-cfg-backend-deadlock-retry-limit: 10

dn: cn=VLV Index,ds-cfg-backend-id=indexRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-branch
cn: VLV Index

dn: ds-cfg-vlv-je-index-name=testvlvindex,cn=VLV Index,ds-cfg-backend-id=indexRoot,cn=Backends,cn=config
changetype: add
objectClass: top
objectClass: ds-cfg-vlv-je-index
ds-cfg-vlv-je-index-name: testvlvindex
ds-cfg-vlv-je-index-base-dn: dc=vlvtest,dc=com
ds-cfg-vlv-je-index-scope: whole-subtree
ds-cfg-vlv-je-index-filter: (objectClass=*)
ds-cfg-vlv-je-index-sort-order: givenname -sn +uid
ds-cfg-vlv-je-index-maximum-block-size: 7

dn: cn=Index,ds-cfg-backend-id=indexRoot,cn=Backends,cn=config
changetype: add
objectClass: top

 opends/tests/unit-tests-testng/src/server/org/opends/server/backends/jeb/TestRebuildJob.java

@@ -73,7 +73,8 @@
        { "mail.substring" },
        { "mail.ordering" },
        { "mail.equality" },
        { "mail.approximate" }
        { "mail.approximate" },
        { "vlv.testvlvindex" }
    };
  }

@@ -164,8 +165,14 @@
    be=(BackendImpl) DirectoryServer.getBackend(beID);
    be.rebuildBackend(rebuildConfig);

    assertEquals(verifyBackend("mail"), 0);

    if(index.contains(".") && !index.startsWith("vlv."))
    {
      assertEquals(verifyBackend(index.split("\\.")[0]), 0);
    }
    else
    {
      assertEquals(verifyBackend(index), 0);
    }
  }

  @Test(dataProvider = "badIndexes",

 opends/tests/unit-tests-testng/src/server/org/opends/server/backends/jeb/TestVLVIndex.java

New file
@@ -0,0 +1,1105 @@
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at
 * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
 * add the following below this CDDL HEADER, with the fields enclosed
 * by brackets "[]" replaced with your own identifying information:
 *      Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 *
 *
 *      Portions Copyright 2006-2007 Sun Microsystems, Inc.
 */
package org.opends.server.backends.jeb;

import org.opends.server.TestCaseUtils;
import static org.opends.server.util.ServerConstants.OID_SERVER_SIDE_SORT_RESPONSE_CONTROL;
import static org.opends.server.util.ServerConstants.OID_VLV_RESPONSE_CONTROL;
import org.opends.server.controls.ServerSideSortRequestControl;
import org.opends.server.controls.VLVRequestControl;
import org.opends.server.controls.ServerSideSortResponseControl;
import org.opends.server.controls.VLVResponseControl;
import org.opends.server.protocols.internal.InternalClientConnection;
import org.opends.server.protocols.internal.InternalSearchOperation;
import org.opends.server.protocols.ldap.LDAPFilter;
import org.opends.server.protocols.ldap.LDAPResultCode;
import org.opends.server.protocols.asn1.ASN1OctetString;
import org.opends.server.core.DirectoryServer;
import org.opends.server.core.SearchOperation;
import org.opends.server.types.*;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;
import org.testng.annotations.AfterClass;
import static org.testng.Assert.*;
import static org.testng.Assert.assertEquals;

import java.util.*;

public class TestVLVIndex
{
  SortOrder sortOrder;

  private  String beID="indexRoot";
  private BackendImpl be;

  // The DN for "Aaccf Johnson"
  DN aaccfJohnsonDN;

  // The DN for "Aaron Zimmerman"
  DN aaronZimmermanDN;

  // The DN for "Albert Smith"
  DN albertSmithDN;

  // The DN for "Albert Zimmerman"
  DN albertZimmermanDN;

  // The DN for "lowercase mcgee"
  DN lowercaseMcGeeDN;

  // The DN for "Mararet Jones"
  DN margaretJonesDN;

  // The DN for "Mary Jones"
  DN maryJonesDN;

  // The DN for "Sam Zweck"
  DN samZweckDN;

  // The DN for "Zorro"
  DN zorroDN;

  // The DN for suffix
  DN suffixDN;

  TreeSet<SortValues> expectedSortedValues;

  @BeforeClass
  public void setUp() throws Exception {
    TestCaseUtils.startServer();

    SortKey[] sortKeys = new SortKey[3];
    sortKeys[0] = new SortKey(DirectoryServer.getAttributeType("givenname"), true);
    sortKeys[1] = new SortKey(DirectoryServer.getAttributeType("sn"),
                              false);
    sortKeys[2] = new SortKey(
        DirectoryServer.getAttributeType("uid"), true);
    sortOrder = new SortOrder(sortKeys);

    aaccfJohnsonDN    = DN.decode("uid=aaccf.johnson,dc=vlvtest,dc=com");
    aaronZimmermanDN  = DN.decode("uid=aaron.zimmerman,dc=vlvtest,dc=com");
    albertSmithDN     = DN.decode("uid=albert.smith,dc=vlvtest,dc=com");
    albertZimmermanDN = DN.decode("uid=albert.zimmerman,dc=vlvtest,dc=com");
    lowercaseMcGeeDN  = DN.decode("uid=lowercase.mcgee,dc=vlvtest,dc=com");
    margaretJonesDN   = DN.decode("uid=margaret.jones,dc=vlvtest,dc=com");
    maryJonesDN       = DN.decode("uid=mary.jones,dc=vlvtest,dc=com");
    samZweckDN        = DN.decode("uid=sam.zweck,dc=vlvtest,dc=com");
    zorroDN           = DN.decode("uid=zorro,dc=vlvtest,dc=com");
    suffixDN          = DN.decode("dc=vlvtest,dc=com");

    expectedSortedValues = new TreeSet<SortValues>();
  }

  @AfterClass
  public void cleanUp() throws Exception {
  }

  /**
   * Populates the JE DB with a set of test data.
   *
   * @throws  Exception  If an unexpected problem occurs.
   */
  private void populateDB()
      throws Exception
  {
    List<Entry> entries = TestCaseUtils.makeEntries(
        "dn: dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: domain",
        "",
        "dn: uid=albert.zimmerman,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: albert.zimmerman",
        "givenName: Albert",
        "sn: Zimmerman",
        "cn: Albert Zimmerman",
        "",
        "dn: uid=albert.smith,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: albert.smith",
        "givenName: Albert",
        "sn: Smith",
        "cn: Albert Smith",
        "",
        "dn: uid=aaron.zimmerman,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: albert.zimmerman",
        "givenName: Aaron",
        "givenName: Zeke",
        "sn: Zimmerman",
        "cn: Aaron Zimmerman",
        "",
        "dn: uid=mary.jones,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: mary.jones",
        "givenName: Mary",
        "sn: Jones",
        "cn: Mary Jones",
        "",
        "dn: uid=margaret.jones,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: margaret.jones",
        "givenName: Margaret",
        "givenName: Maggie",
        "sn: Jones",
        "sn: Smith",
        "cn: Maggie Jones-Smith",
        "",
        "dn: uid=aaccf.johnson,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: aaccf.johnson",
        "givenName: Aaccf",
        "sn: Johnson",
        "cn: Aaccf Johnson",
        "",
        "dn: uid=sam.zweck,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: sam.zweck",
        "givenName: Sam",
        "sn: Zweck",
        "cn: Sam Zweck",
        "",
        "dn: uid=lowercase.mcgee,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: lowercase.mcgee",
        "givenName: lowercase",
        "sn: mcgee",
        "cn: lowercase mcgee",
        "",
        "dn: uid=zorro,dc=vlvtest,dc=com",
        "objectClass: top",
        "objectClass: person",
        "objectClass: organizationalPerson",
        "objectClass: inetOrgPerson",
        "uid: zorro",
        "sn: Zorro",
        "cn: Zorro"
    );

    long id = 1;
    for(Entry entry : entries)
    {
      TestCaseUtils.addEntry(entry);
      expectedSortedValues.add(new SortValues(new EntryID(id), entry,
                                              sortOrder));
      id++;
    }
  }


  @Test
  public void testAdd() throws Exception
  {
    populateDB();
    be=(BackendImpl) DirectoryServer.getBackend(beID);
    RootContainer rootContainer = be.getRootContainer();
    EntryContainer entryContainer =
        rootContainer.getEntryContainer(DN.decode("dc=vlvtest,dc=com"));

    for(VLVIndex vlvIndex : entryContainer.getVLVIndexes())
    {
      if(vlvIndex.getName().contains("testvlvindex"))
      {


        SortValuesSet svs1 =
            vlvIndex.getSortValuesSet(null, 0,
                                      expectedSortedValues.first().getValues());

        assertNotNull(svs1);
        assertEquals(svs1.size(), 4);

        SortValuesSet svs2 =
            vlvIndex.getSortValuesSet(null, 0,
                                      expectedSortedValues.last().getValues());

        assertNotNull(svs2);
        assertEquals(svs2.size(), 6);

        int i = 0;
        for(SortValues values : expectedSortedValues)
        {
          for(int j = 0; j < values.getValues().length; j++)
          {
            byte[] value;
            if(i < 4)
            {
              value = svs1.getValue(i * 3 + j);
            }
            else
            {
              value = svs2.getValue((i - 4) * 3 + j);
            }
            byte[] oValue = null;
            if(values.getValues()[j] != null)
            {
              oValue = values.getValues()[j].getNormalizedValueBytes();
            }
            assertEquals(value, oValue);
          }
          i++;
        }
      }
    }
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an offset of one.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByOffsetOneOffset()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3, 1, 0));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(aaccfJohnsonDN);    // Aaccf
    expectedDNOrder.add(aaronZimmermanDN);  // Aaron
    expectedDNOrder.add(albertZimmermanDN); // Albert, bigger
    expectedDNOrder.add(albertSmithDN);     // Albert, smaller sn

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 1);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an offset of zero, which should be treated like
   * an offset of one.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByOffsetZeroOffset()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3, 0, 0));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(aaccfJohnsonDN);    // Aaccf
    expectedDNOrder.add(aaronZimmermanDN);  // Aaron
    expectedDNOrder.add(albertZimmermanDN); // Albert, bigger
    expectedDNOrder.add(albertSmithDN);     // Albert, smaller sn

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl            vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 1);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an offset that isn't at the beginning of the
   * result set but is still completely within the bounds of that set.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByOffsetThreeOffset()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3, 3, 0));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(albertZimmermanDN); // Albert, bigger
    expectedDNOrder.add(albertSmithDN);     // Albert, smaller sn
    expectedDNOrder.add(lowercaseMcGeeDN);  // lowercase
    expectedDNOrder.add(margaretJonesDN);   // Maggie

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl            vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 3);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control with a negative
   * target offset.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByOffsetNegativeOffset()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3, -1, 0));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();

    // It will be successful because it's not a critical control.
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);

    VLVResponseControl vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
    }

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(),
                 LDAPResultCode.OFFSET_RANGE_ERROR);
  }

  /**
   * Tests performing an internal search using the VLV control with an offset of
   * one but a beforeCount that puts the start position at a negative value.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByOffsetNegativeStartPosition()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(3, 3, 1, 0));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();

    // It will be successful because it's not a critical control.
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);

    VLVResponseControl vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
    }

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), LDAPResultCode.SUCCESS);
  }

  /**
   * Tests performing an internal search using the VLV control with a start
   * start position beyond the end of the result set.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByOffsetStartPositionTooHigh()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(3, 3, 30, 0));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();

    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(samZweckDN);        // Sam
    expectedDNOrder.add(zorroDN);           // No first name
    expectedDNOrder.add(suffixDN);          // No sort attributes

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);

    VLVResponseControl vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
    }

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), LDAPResultCode.SUCCESS);
    assertEquals(vlvResponse.getTargetPosition(), 11);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control with a start
   * start position within the bounds of the list but not enough remaining
   * entries to meet the afterCount
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByOffsetIncompleteAfterCount()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 4, 7, 0));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(maryJonesDN);       // Mary
    expectedDNOrder.add(samZweckDN);        // Sam
    expectedDNOrder.add(zorroDN);           // No first name
    expectedDNOrder.add(suffixDN);          // No sort attributes

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl            vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 7);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an assertion value before any actual value in
   * the list.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByValueBeforeAll()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3, new ASN1OctetString("a")));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(aaccfJohnsonDN);    // Aaccf
    expectedDNOrder.add(aaronZimmermanDN);  // Aaron
    expectedDNOrder.add(albertZimmermanDN); // Albert, lower entry ID
    expectedDNOrder.add(albertSmithDN);     // Albert, higher entry ID

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl            vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 1);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an assertion value that matches the first value
   * in the list.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByValueMatchesFirst()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3,
                                              new ASN1OctetString("aaccf")));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(aaccfJohnsonDN);    // Aaccf
    expectedDNOrder.add(aaronZimmermanDN);  // Aaron
    expectedDNOrder.add(albertZimmermanDN); // Albert, lower entry ID
    expectedDNOrder.add(albertSmithDN);     // Albert, higher entry ID

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl            vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 1);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an assertion value that matches the third value
   * in the list.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByValueMatchesThird()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3,
                                              new ASN1OctetString("albert")));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(albertZimmermanDN); // Albert, lower entry ID
    expectedDNOrder.add(albertSmithDN);     // Albert, higher entry ID
    expectedDNOrder.add(lowercaseMcGeeDN);  // lowercase
    expectedDNOrder.add(margaretJonesDN);   // Maggie

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl            vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 3);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an assertion value that matches the third value
   * in the list and includes a nonzero before count.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByValueMatchesThirdWithBeforeCount()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(1, 3,
                                              new ASN1OctetString("albert")));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(aaronZimmermanDN);  // Aaron
    expectedDNOrder.add(albertZimmermanDN); // Albert, lower entry ID
    expectedDNOrder.add(albertSmithDN);     // Albert, higher entry ID
    expectedDNOrder.add(lowercaseMcGeeDN);  // lowercase
    expectedDNOrder.add(margaretJonesDN);   // Maggie

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);
    assertEquals(responseControls.size(), 2);

    ServerSideSortResponseControl sortResponse = null;
    VLVResponseControl            vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_SERVER_SIDE_SORT_RESPONSE_CONTROL))
      {
        sortResponse = ServerSideSortResponseControl.decodeControl(c);
      }
      else if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
      else
      {
        fail("Response control with unexpected OID " + c.getOID());
      }
    }

    assertNotNull(sortResponse);
    assertEquals(sortResponse.getResultCode(), 0);

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(), 0);
    assertEquals(vlvResponse.getTargetPosition(), 3);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

  /**
   * Tests performing an internal search using the VLV control to retrieve a
   * subset of the entries using an assertion value that is after all values in
   * the list.
   *
   * @throws  Exception  If an unexpected problem occurred.
   */
  @Test( dependsOnMethods = { "testAdd" } )
  public void testInternalSearchByValueAfterAll()
      throws Exception
  {
    InternalClientConnection conn =
        InternalClientConnection.getRootConnection();

    ArrayList<Control> requestControls = new ArrayList<Control>();
    requestControls.add(new ServerSideSortRequestControl(sortOrder));
    requestControls.add(new VLVRequestControl(0, 3, new ASN1OctetString("zz")));

    InternalSearchOperation internalSearch =
        new InternalSearchOperation(conn, conn.nextOperationID(),
                                    conn.nextMessageID(), requestControls,
                                    DN.decode("dc=vlvtest,dc=com"), SearchScope.WHOLE_SUBTREE,
                                    DereferencePolicy.NEVER_DEREF_ALIASES, 0, 0, false,
                                    SearchFilter.createFilterFromString("(objectClass=*)"),
                                    null, null);

    internalSearch.run();

    // It will be successful because the control isn't critical.
    assertEquals(internalSearch.getResultCode(), ResultCode.SUCCESS);

    // Null values for given name are still bigger then zz
    ArrayList<DN> expectedDNOrder = new ArrayList<DN>();
    expectedDNOrder.add(zorroDN);           // No first name
    expectedDNOrder.add(suffixDN);          // No sort attributes

    ArrayList<DN> returnedDNOrder = new ArrayList<DN>();
    for (Entry e : internalSearch.getSearchEntries())
    {
      returnedDNOrder.add(e.getDN());
    }

    assertEquals(returnedDNOrder, expectedDNOrder);

    List<Control> responseControls = internalSearch.getResponseControls();
    assertNotNull(responseControls);

    VLVResponseControl vlvResponse  = null;
    for (Control c : responseControls)
    {
      if (c.getOID().equals(OID_VLV_RESPONSE_CONTROL))
      {
        vlvResponse = VLVResponseControl.decodeControl(c);
      }
    }

    assertNotNull(vlvResponse);
    assertEquals(vlvResponse.getVLVResultCode(),
                 LDAPResultCode.SUCCESS);
    assertEquals(vlvResponse.getTargetPosition(), 9);
    assertEquals(vlvResponse.getContentCount(), 10);
  }

}

 opends/tests/unit-tests-testng/src/server/org/opends/server/backends/jeb/TestVerifyJob.java

@@ -373,6 +373,53 @@
    }
  }

  /**
   * Runs clean verify against the testvlvindex VLV index
   * after adding various errors to each of these index files.
   * @throws Exception if the error count is not equal to 6.
   */
  @Test() public void testCleanVLV() throws Exception {
    String indexName = "testvlvindex";
    preTest(4);
    eContainer.sharedLock.lock();
    try
    {
      VLVIndex vlvIndex = eContainer.getVLVIndex(indexName);

      // Add an incorrectly ordered values.
      SortValuesSet svs =
          vlvIndex.getSortValuesSet(null, 0, new AttributeValue[3]);
      long id = svs.getEntryIDs()[0];
      Entry entry = eContainer.getID2Entry().get(null, new EntryID(id));

      SortValuesSet svs2 = svs.split(2);
      svs2.add(id, vlvIndex.getSortValues(entry));

      // Add an invalid ID
      svs2.add(1000, vlvIndex.getSortValues(entry));

      // Muck up the values of another ID
      id = svs.getEntryIDs()[0];
      entry = eContainer.getID2Entry().get(null, new EntryID(id));
      AttributeValue[] values = vlvIndex.getSortValues(entry);
      AttributeValue[] badValues = new AttributeValue[values.length];
      System.arraycopy(values, 1, badValues, 0, values.length - 1);
      badValues[badValues.length-1] = values[0];
      svs.remove(id, values);
      svs.add(id, badValues);

      vlvIndex.putSortValuesSet(null, svs);
      vlvIndex.putSortValuesSet(null, svs2);
      performBECleanVerify("vlv." + indexName, 3);
    }
    finally
    {
      eContainer.sharedLock.unlock();
    }

  }


  /*
     * Begin complete verify index tests. As described above, these are
     * tests that cursor through the id2entry database and validate
@@ -631,6 +678,51 @@
    }
  }

  /**
   * Runs complete verify against the testvlvindex VLV index
   * after adding various errors to each of these index files.
   * @throws Exception if the error count is not equal to 6.
   */
  @Test() public void testVerifyVLV() throws Exception {
    String indexName = "testvlvindex";
    preTest(4);
    eContainer.sharedLock.lock();
    try
    {
      VLVIndex vlvIndex = eContainer.getVLVIndex(indexName);

      // Remove an ID
      SortValuesSet svs =
          vlvIndex.getSortValuesSet(null, 0, new AttributeValue[3]);
      long id = svs.getEntryIDs()[0];
      Entry entry = eContainer.getID2Entry().get(null, new EntryID(id));
      svs.remove(id, vlvIndex.getSortValues(entry));

      // Add an incorrectly ordered values.
      SortValuesSet svs2 = svs.split(2);
      svs2.add(1000, vlvIndex.getSortValues(entry));

      // Muck up the values of another ID
      id = svs.getEntryIDs()[0];
      entry = eContainer.getID2Entry().get(null, new EntryID(id));
      AttributeValue[] values = vlvIndex.getSortValues(entry);
      AttributeValue[] badValues = new AttributeValue[values.length];
      System.arraycopy(values, 1, badValues, 0, values.length - 1);
      badValues[badValues.length-1] = values[0];
      svs.remove(id, values);
      svs.add(id, badValues);

      vlvIndex.putSortValuesSet(null, svs);
      vlvIndex.putSortValuesSet(null, svs2);
      performBECompleteVerify("vlv." + indexName, 3);
    }
    finally
    {
      eContainer.sharedLock.unlock();
    }

  }

  /* Various tests not either clean or complete */