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 2008 Sun Microsystems, Inc.
025 *      Portions Copyright 2011-2015 ForgeRock AS
026 */
027package org.opends.server.backends.jeb;
028
029import java.util.Iterator;
030import java.util.LinkedList;
031import java.util.Map;
032import java.util.TreeMap;
033
034import org.forgerock.i18n.LocalizableMessage;
035import org.forgerock.opendj.ldap.ByteString;
036import org.forgerock.opendj.ldap.ResultCode;
037import org.forgerock.opendj.ldap.SearchScope;
038import org.opends.server.controls.VLVRequestControl;
039import org.opends.server.controls.VLVResponseControl;
040import org.opends.server.core.DirectoryServer;
041import org.opends.server.core.SearchOperation;
042import org.opends.server.protocols.ldap.LDAPResultCode;
043import org.opends.server.types.*;
044
045import static org.opends.messages.BackendMessages.*;
046import static org.opends.server.util.StaticUtils.*;
047
048/**
049 * This class provides a mechanism for sorting the contents of an entry ID set
050 * based on a given sort order.
051 */
052public class EntryIDSetSorter
053{
054  /**
055   * Creates a new entry ID set which is a sorted representation of the provided
056   * set using the given sort order.
057   *
058   * @param  suffixContainer  The suffix container with which the ID list is associated.
059   * @param  entryIDSet       The entry ID set to be sorted.
060   * @param  searchOperation  The search operation being processed.
061   * @param  sortOrder        The sort order to use for the entry ID set.
062   * @param  vlvRequest       The VLV request control included in the search
063   *                          request, or {@code null} if there was none.
064   *
065   * @return  A new entry ID set which is a sorted representation of the
066   *          provided set using the given sort order.
067   *
068   * @throws  DirectoryException  If an error occurs while performing the sort.
069   */
070  public static EntryIDSet sort(EntryContainer suffixContainer,
071                                EntryIDSet entryIDSet,
072                                SearchOperation searchOperation,
073                                SortOrder sortOrder,
074                                VLVRequestControl vlvRequest)
075         throws DirectoryException
076  {
077    if (! entryIDSet.isDefined())
078    {
079      return new EntryIDSet();
080    }
081
082    DN baseDN = searchOperation.getBaseDN();
083    SearchScope scope = searchOperation.getScope();
084    SearchFilter filter = searchOperation.getFilter();
085
086    TreeMap<SortValues,EntryID> sortMap = new TreeMap<>();
087    for (EntryID id : entryIDSet)
088    {
089      try
090      {
091        Entry e = suffixContainer.getEntry(id);
092        if (e.matchesBaseAndScope(baseDN, scope) && filter.matchesEntry(e))
093        {
094          sortMap.put(new SortValues(id, e, sortOrder), id);
095        }
096      }
097      catch (Exception e)
098      {
099        LocalizableMessage message = ERR_ENTRYIDSORTER_CANNOT_EXAMINE_ENTRY.get(id, getExceptionMessage(e));
100        throw new DirectoryException(DirectoryServer.getServerErrorResultCode(), message, e);
101      }
102    }
103
104
105    // See if there is a VLV request to further pare down the set of results,
106    // and if there is where it should be processed by offset or assertion value.
107    long[] sortedIDs;
108    if (vlvRequest != null)
109    {
110      int beforeCount = vlvRequest.getBeforeCount();
111      int afterCount  = vlvRequest.getAfterCount();
112
113      if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET)
114      {
115        int targetOffset = vlvRequest.getOffset();
116        if (targetOffset < 0)
117        {
118          // The client specified a negative target offset.  This should never be allowed.
119          searchOperation.addResponseControl(
120               new VLVResponseControl(targetOffset, sortMap.size(),
121                                      LDAPResultCode.OFFSET_RANGE_ERROR));
122
123          LocalizableMessage message = ERR_ENTRYIDSORTER_NEGATIVE_START_POS.get();
124          throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR,
125                                       message);
126        }
127        else if (targetOffset == 0)
128        {
129          // This is an easy mistake to make, since VLV offsets start at 1
130          // instead of 0.  We'll assume the client meant to use 1.
131          targetOffset = 1;
132        }
133
134        int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0.
135        int startPos = listOffset - beforeCount;
136        if (startPos < 0)
137        {
138          // This can happen if beforeCount >= offset, and in this case we'll
139          // just adjust the start position to ignore the range of beforeCount
140          // that doesn't exist.
141          startPos    = 0;
142          beforeCount = listOffset;
143        }
144        else if (startPos >= sortMap.size())
145        {
146          // The start position is beyond the end of the list.  In this case,
147          // we'll assume that the start position was one greater than the
148          // size of the list and will only return the beforeCount entries.
149          targetOffset = sortMap.size() + 1;
150          listOffset   = sortMap.size();
151          startPos     = listOffset - beforeCount;
152          afterCount   = 0;
153        }
154
155        int count = 1 + beforeCount + afterCount;
156        sortedIDs = new long[count];
157
158        int treePos = 0;
159        int arrayPos = 0;
160        for (EntryID id : sortMap.values())
161        {
162          if (treePos++ < startPos)
163          {
164            continue;
165          }
166
167          sortedIDs[arrayPos++] = id.longValue();
168          if (arrayPos >= count)
169          {
170            break;
171          }
172        }
173
174        if (arrayPos < count)
175        {
176          // We don't have enough entries in the set to meet the requested
177          // page size, so we'll need to shorten the array.
178          long[] newIDArray = new long[arrayPos];
179          System.arraycopy(sortedIDs, 0, newIDArray, 0, arrayPos);
180          sortedIDs = newIDArray;
181        }
182
183        searchOperation.addResponseControl(
184             new VLVResponseControl(targetOffset, sortMap.size(),
185                                    LDAPResultCode.SUCCESS));
186      }
187      else
188      {
189        ByteString assertionValue = vlvRequest.getGreaterThanOrEqualAssertion();
190
191        boolean targetFound     = false;
192        int targetOffset        = 0;
193        int includedBeforeCount = 0;
194        int includedAfterCount  = 0;
195        int listSize            = 0;
196        LinkedList<EntryID> idList = new LinkedList<>();
197        for (Map.Entry<SortValues, EntryID> entry : sortMap.entrySet())
198        {
199          SortValues sortValues = entry.getKey();
200          EntryID id = entry.getValue();
201
202          if (targetFound)
203          {
204            idList.add(id);
205            listSize++;
206            includedAfterCount++;
207            if (includedAfterCount >= afterCount)
208            {
209              break;
210            }
211          }
212          else
213          {
214            targetFound = sortValues.compareTo(assertionValue) >= 0;
215            targetOffset++;
216
217            if (targetFound)
218            {
219              idList.add(id);
220              listSize++;
221            }
222            else if (beforeCount > 0)
223            {
224              idList.add(id);
225              includedBeforeCount++;
226              if (includedBeforeCount > beforeCount)
227              {
228                idList.removeFirst();
229                includedBeforeCount--;
230              }
231              else
232              {
233                listSize++;
234              }
235            }
236          }
237        }
238
239        if (! targetFound)
240        {
241          // No entry was found to be greater than or equal to the sort key, so
242          // the target offset will be one greater than the content count.
243          targetOffset = sortMap.size() + 1;
244        }
245
246        sortedIDs = new long[listSize];
247        Iterator<EntryID> idIterator = idList.iterator();
248        for (int i=0; i < listSize; i++)
249        {
250          sortedIDs[i] = idIterator.next().longValue();
251        }
252
253        searchOperation.addResponseControl(
254             new VLVResponseControl(targetOffset, sortMap.size(),
255                                    LDAPResultCode.SUCCESS));
256      }
257    }
258    else
259    {
260      sortedIDs = new long[sortMap.size()];
261      int i=0;
262      for (EntryID id : sortMap.values())
263      {
264        sortedIDs[i++] = id.longValue();
265      }
266    }
267
268    return new EntryIDSet(sortedIDs, 0, sortedIDs.length);
269  }
270}