001/*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License").  You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
010 * or http://forgerock.org/license/CDDLv1.0.html.
011 * See the License for the specific language governing permissions
012 * and limitations under the License.
013 *
014 * When distributing Covered Code, include this CDDL HEADER in each
015 * file and include the License file at legal-notices/CDDLv1_0.txt.
016 * If applicable, add the following below this CDDL HEADER, with the
017 * fields enclosed by brackets "[]" replaced with your own identifying
018 * information:
019 *      Portions Copyright [yyyy] [name of copyright owner]
020 *
021 * CDDL HEADER END
022 *
023 *
024 *      Copyright 2006-2008 Sun Microsystems, Inc.
025 *      Portions Copyright 2014-2015 ForgeRock AS
026 */
027package org.opends.server.backends.jeb;
028
029import java.util.*;
030
031import org.forgerock.opendj.ldap.ByteSequence;
032import org.forgerock.opendj.ldap.ByteString;
033import org.opends.server.types.DirectoryException;
034
035import com.sleepycat.je.DatabaseEntry;
036import com.sleepycat.je.DatabaseException;
037import com.sleepycat.je.Transaction;
038
039/**
040 * A buffered index is used to buffer multiple reads or writes to the
041 * same index key into a single read or write.
042 * It can only be used to buffer multiple reads and writes under
043 * the same transaction. The transaction may be null if it is known
044 * that there are no other concurrent updates to the index.
045 */
046public class IndexBuffer
047{
048  private final EntryContainer entryContainer;
049
050  /**
051   * The buffered records stored as a map from the record key to the
052   * buffered value for that key for each index.
053   */
054  private final LinkedHashMap<Index, TreeMap<ByteString, BufferedIndexValues>> bufferedIndexes = new LinkedHashMap<>();
055  /** The buffered records stored as a set of buffered VLV values for each index. */
056  private final LinkedHashMap<VLVIndex, BufferedVLVValues> bufferedVLVIndexes = new LinkedHashMap<>();
057
058  /** A simple class representing a pair of added and deleted indexed IDs. */
059  static class BufferedIndexValues
060  {
061    private EntryIDSet addedIDs;
062    private EntryIDSet deletedIDs;
063
064    /**
065     * Adds the provided entryID to this object associating it with the provided keyBytes.
066     *
067     * @param keyBytes the keyBytes mapping for this entryID
068     * @param entryID the entryID to add
069     */
070    void addEntryID(ByteString keyBytes, EntryID entryID)
071    {
072      if (!remove(deletedIDs, entryID))
073      {
074        if (this.addedIDs == null)
075        {
076          this.addedIDs = new EntryIDSet(keyBytes, null);
077        }
078        this.addedIDs.add(entryID);
079      }
080    }
081
082    /**
083     * Deletes the provided entryID from this object.
084     *
085     * @param keyBytes the keyBytes mapping for this entryID
086     * @param entryID the entryID to delete
087     */
088    void deleteEntryID(ByteString keyBytes, EntryID entryID)
089    {
090      if (!remove(addedIDs, entryID))
091      {
092        if (this.deletedIDs == null)
093        {
094          this.deletedIDs = new EntryIDSet(keyBytes, null);
095        }
096        this.deletedIDs.add(entryID);
097      }
098    }
099
100    private boolean remove(EntryIDSet ids, EntryID entryID)
101    {
102      if (ids != null && ids.contains(entryID))
103      {
104        ids.remove(entryID);
105        return true;
106      }
107      return false;
108    }
109  }
110
111  /** A simple class representing a pair of added and deleted VLV values. */
112  static class BufferedVLVValues
113  {
114    private TreeSet<SortValues> addedValues;
115    private TreeSet<SortValues> deletedValues;
116
117    /**
118     * Adds the provided values to this object.
119     *
120     * @param sortValues the values to add
121     */
122    void addValues(SortValues sortValues)
123    {
124      if (!remove(deletedValues, sortValues))
125      {
126        if (this.addedValues == null)
127        {
128          this.addedValues = new TreeSet<>();
129        }
130        this.addedValues.add(sortValues);
131      }
132    }
133
134    /**
135     * Deletes the provided values from this object.
136     *
137     * @param sortValues the values to delete
138     */
139    void deleteValues(SortValues sortValues)
140    {
141      if (!remove(addedValues, sortValues))
142      {
143        if (this.deletedValues == null)
144        {
145          this.deletedValues = new TreeSet<>();
146        }
147        this.deletedValues.add(sortValues);
148      }
149    }
150
151    private boolean remove(TreeSet<SortValues> values, SortValues sortValues)
152    {
153      if (values != null && values.contains(sortValues))
154      {
155        values.remove(sortValues);
156        return true;
157      }
158      return false;
159    }
160  }
161
162  /**
163   * Construct a new empty index buffer object.
164   *
165   * @param entryContainer The database entryContainer using this
166   * index buffer.
167   */
168  public IndexBuffer(EntryContainer entryContainer)
169  {
170    this.entryContainer = entryContainer;
171  }
172
173  /**
174   * Get the buffered VLV values for the given VLV index.
175   *
176   * @param vlvIndex The VLV index with the buffered values to retrieve.
177   * @return The buffered VLV values or <code>null</code> if there are
178   * no buffered VLV values for the specified VLV index.
179   */
180  public BufferedVLVValues getVLVIndex(VLVIndex vlvIndex)
181  {
182    BufferedVLVValues bufferedValues = bufferedVLVIndexes.get(vlvIndex);
183    if (bufferedValues == null)
184    {
185      bufferedValues = new BufferedVLVValues();
186      bufferedVLVIndexes.put(vlvIndex, bufferedValues);
187    }
188    return bufferedValues;
189  }
190
191  /**
192   * Get the buffered index values for the given index and keyBytes.
193   *
194   * @param index
195   *          The index for which to retrieve the buffered index values
196   * @param keyBytes
197   *          The keyBytes for which to retrieve the buffered index values
198   * @param bsComparator
199   *          The byte sequence comparator to use when retrieving the
200   *          BufferedIndexValues
201   * @return The buffered index values, it can never be null
202   */
203  BufferedIndexValues getBufferedIndexValues(Index index, ByteString keyBytes, Comparator<ByteSequence> bsComparator)
204  {
205    BufferedIndexValues values = null;
206
207    TreeMap<ByteString, BufferedIndexValues> bufferedOperations = bufferedIndexes.get(index);
208    if (bufferedOperations == null)
209    {
210      bufferedOperations = new TreeMap<>(bsComparator);
211      bufferedIndexes.put(index, bufferedOperations);
212    }
213    else
214    {
215      values = bufferedOperations.get(keyBytes);
216    }
217
218    if (values == null)
219    {
220      values = new BufferedIndexValues();
221      bufferedOperations.put(keyBytes, values);
222    }
223    return values;
224  }
225
226  /**
227   * Flush the buffered index changes until the given transaction to
228   * the database.
229   *
230   * @param txn The database transaction to be used for the updates.
231   * @throws DatabaseException If an error occurs in the JE database.
232   * @throws DirectoryException If a Directory Server error occurs.
233   */
234  public void flush(Transaction txn) throws DatabaseException, DirectoryException
235  {
236    DatabaseEntry key = new DatabaseEntry();
237
238    for (AttributeIndex attributeIndex : entryContainer.getAttributeIndexes())
239    {
240      for (Index index : attributeIndex.getAllIndexes())
241      {
242        updateKeys(index, txn, key, bufferedIndexes.remove(index));
243      }
244    }
245
246    for (VLVIndex vlvIndex : entryContainer.getVLVIndexes())
247    {
248      BufferedVLVValues bufferedVLVValues = bufferedVLVIndexes.remove(vlvIndex);
249      if (bufferedVLVValues != null)
250      {
251        vlvIndex.updateIndex(txn, bufferedVLVValues.addedValues, bufferedVLVValues.deletedValues);
252      }
253    }
254
255    final Index id2children = entryContainer.getID2Children();
256    updateKeys(id2children, txn, key, bufferedIndexes.remove(id2children));
257
258    final Index id2subtree = entryContainer.getID2Subtree();
259    final TreeMap<ByteString, BufferedIndexValues> bufferedValues = bufferedIndexes.remove(id2subtree);
260    if (bufferedValues != null)
261    {
262      /*
263       * OPENDJ-1375: add keys in reverse order to be consistent with single
264       * entry processing in add/delete processing. This is necessary in order
265       * to avoid deadlocks.
266       */
267      updateKeys(id2subtree, txn, key, bufferedValues.descendingMap());
268    }
269  }
270
271  private void updateKeys(Index index, Transaction txn, DatabaseEntry key,
272      Map<ByteString, BufferedIndexValues> bufferedValues)
273  {
274    if (bufferedValues != null)
275    {
276      final Iterator<Map.Entry<ByteString, BufferedIndexValues>> it = bufferedValues.entrySet().iterator();
277      while (it.hasNext())
278      {
279        final Map.Entry<ByteString, BufferedIndexValues> entry = it.next();
280        final ByteString bufferedKey = entry.getKey();
281        final BufferedIndexValues values = entry.getValue();
282
283        key.setData(bufferedKey.toByteArray());
284        index.updateKey(txn, key, values.deletedIDs, values.addedIDs);
285
286        it.remove();
287      }
288    }
289  }
290}