001    /*
002     * CDDL HEADER START
003     *
004     * The contents of this file are subject to the terms of the
005     * Common Development and Distribution License, Version 1.0 only
006     * (the "License").  You may not use this file except in compliance
007     * with the License.
008     *
009     * You can obtain a copy of the license at
010     * trunk/opends/resource/legal-notices/OpenDS.LICENSE
011     * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
012     * See the License for the specific language governing permissions
013     * and limitations under the License.
014     *
015     * When distributing Covered Code, include this CDDL HEADER in each
016     * file and include the License file at
017     * trunk/opends/resource/legal-notices/OpenDS.LICENSE.  If applicable,
018     * add the following below this CDDL HEADER, with the fields enclosed
019     * by brackets "[]" replaced with your own identifying information:
020     *      Portions Copyright [yyyy] [name of copyright owner]
021     *
022     * CDDL HEADER END
023     *
024     *
025     *      Copyright 2008 Sun Microsystems, Inc.
026     */
027    package org.opends.server.backends.jeb;
028    import org.opends.messages.Message;
029    
030    
031    
032    import java.util.Map;
033    import java.util.Iterator;
034    import java.util.LinkedList;
035    import java.util.TreeMap;
036    
037    import org.opends.server.controls.VLVRequestControl;
038    import org.opends.server.controls.VLVResponseControl;
039    import org.opends.server.core.DirectoryServer;
040    import org.opends.server.core.SearchOperation;
041    import org.opends.server.protocols.ldap.LDAPResultCode;
042    import org.opends.server.types.AttributeValue;
043    import org.opends.server.types.DirectoryException;
044    import org.opends.server.types.DN;
045    import org.opends.server.types.Entry;
046    import org.opends.server.types.ResultCode;
047    import org.opends.server.types.SearchFilter;
048    import org.opends.server.types.SearchScope;
049    import org.opends.server.types.SortOrder;
050    
051    import static org.opends.messages.JebMessages.*;
052    import static org.opends.server.util.StaticUtils.*;
053    import com.sleepycat.je.LockMode;
054    
055    
056    /**
057     * This class provides a mechanism for sorting the contents of an entry ID set
058     * based on a given sort order.
059     */
060    public class EntryIDSetSorter
061    {
062      /**
063       * Creates a new entry ID set which is a sorted representation of the provided
064       * set using the given sort order.
065       *
066       * @param  entryContainer   The entry container with which the ID list is
067       *                          associated.
068       * @param  entryIDSet       The entry ID set to be sorted.
069       * @param  searchOperation  The search operation being processed.
070       * @param  sortOrder        The sort order to use for the entry ID set.
071       * @param  vlvRequest       The VLV request control included in the search
072       *                          request, or {@code null} if there was none.
073       *
074       * @return  A new entry ID set which is a sorted representation of the
075       *          provided set using the given sort order.
076       *
077       * @throws  DirectoryException  If an error occurs while performing the sort.
078       */
079      public static EntryIDSet sort(EntryContainer entryContainer,
080                                    EntryIDSet entryIDSet,
081                                    SearchOperation searchOperation,
082                                    SortOrder sortOrder,
083                                    VLVRequestControl vlvRequest)
084             throws DirectoryException
085      {
086        if (! entryIDSet.isDefined())
087        {
088          return new EntryIDSet();
089        }
090    
091        ID2Entry id2Entry = entryContainer.getID2Entry();
092        DN baseDN = searchOperation.getBaseDN();
093        SearchScope scope = searchOperation.getScope();
094        SearchFilter filter = searchOperation.getFilter();
095    
096        TreeMap<SortValues,EntryID> sortMap = new TreeMap<SortValues,EntryID>();
097        for (EntryID id : entryIDSet)
098        {
099          try
100          {
101            Entry e = id2Entry.get(null, id, LockMode.DEFAULT);
102    
103            if ((! e.matchesBaseAndScope(baseDN, scope)) ||
104                (! filter.matchesEntry(e)))
105            {
106              continue;
107            }
108    
109            sortMap.put(new SortValues(id, e, sortOrder), id);
110          }
111          catch (Exception e)
112          {
113            Message message = ERR_ENTRYIDSORTER_CANNOT_EXAMINE_ENTRY.get(
114                String.valueOf(id), getExceptionMessage(e));
115            throw new DirectoryException(DirectoryServer.getServerErrorResultCode(),
116                                         message, e);
117          }
118        }
119    
120    
121        // See if there is a VLV request to further pare down the set of results,
122        // and if there is where it should be processed by offset or assertion
123        // value.
124        long[] sortedIDs;
125        if (vlvRequest != null)
126        {
127          int beforeCount = vlvRequest.getBeforeCount();
128          int afterCount  = vlvRequest.getAfterCount();
129    
130          if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET)
131          {
132            int targetOffset = vlvRequest.getOffset();
133            if (targetOffset < 0)
134            {
135              // The client specified a negative target offset.  This should never
136              // be allowed.
137              searchOperation.addResponseControl(
138                   new VLVResponseControl(targetOffset, sortMap.size(),
139                                          LDAPResultCode.OFFSET_RANGE_ERROR));
140    
141              Message message = ERR_ENTRYIDSORTER_NEGATIVE_START_POS.get();
142              throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR,
143                                           message);
144            }
145            else if (targetOffset == 0)
146            {
147              // This is an easy mistake to make, since VLV offsets start at 1
148              // instead of 0.  We'll assume the client meant to use 1.
149              targetOffset = 1;
150            }
151    
152            int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0.
153            int startPos = listOffset - beforeCount;
154            if (startPos < 0)
155            {
156              // This can happen if beforeCount >= offset, and in this case we'll
157              // just adjust the start position to ignore the range of beforeCount
158              // that doesn't exist.
159              startPos    = 0;
160              beforeCount = listOffset;
161            }
162            else if (startPos >= sortMap.size())
163            {
164              // The start position is beyond the end of the list.  In this case,
165              // we'll assume that the start position was one greater than the
166              // size of the list and will only return the beforeCount entries.
167              targetOffset = sortMap.size() + 1;
168              listOffset   = sortMap.size();
169              startPos     = listOffset - beforeCount;
170              afterCount   = 0;
171            }
172    
173            int count = 1 + beforeCount + afterCount;
174            sortedIDs = new long[count];
175    
176            int treePos = 0;
177            int arrayPos = 0;
178            Iterator<EntryID> idIterator = sortMap.values().iterator();
179            while (idIterator.hasNext())
180            {
181              EntryID id = idIterator.next();
182              if (treePos++ < startPos)
183              {
184                continue;
185              }
186    
187              sortedIDs[arrayPos++] = id.longValue();
188              if (arrayPos >= count)
189              {
190                break;
191              }
192            }
193    
194            if (arrayPos < count)
195            {
196              // We don't have enough entries in the set to meet the requested
197              // page size, so we'll need to shorten the array.
198              long[] newIDArray = new long[arrayPos];
199              System.arraycopy(sortedIDs, 0, newIDArray, 0, arrayPos);
200              sortedIDs = newIDArray;
201            }
202    
203            searchOperation.addResponseControl(
204                 new VLVResponseControl(targetOffset, sortMap.size(),
205                                        LDAPResultCode.SUCCESS));
206          }
207          else
208          {
209            AttributeValue assertionValue = new
210                 AttributeValue(sortOrder.getSortKeys()[0].getAttributeType(),
211                                vlvRequest.getGreaterThanOrEqualAssertion());
212    
213            boolean targetFound     = false;
214            int targetOffset        = 0;
215            int includedBeforeCount = 0;
216            int includedAfterCount  = 0;
217            int listSize            = 0;
218            LinkedList<EntryID> idList = new LinkedList<EntryID>();
219            Iterator<Map.Entry<SortValues,EntryID>> mapIterator =
220                 sortMap.entrySet().iterator();
221            while (mapIterator.hasNext())
222            {
223              Map.Entry<SortValues,EntryID> entry = mapIterator.next();
224              SortValues sortValues = entry.getKey();
225              EntryID id = entry.getValue();
226    
227              if (targetFound)
228              {
229                idList.add(id);
230                listSize++;
231                includedAfterCount++;
232                if (includedAfterCount >= afterCount)
233                {
234                  break;
235                }
236              }
237              else
238              {
239                targetFound = (sortValues.compareTo(assertionValue) >= 0);
240                targetOffset++;
241    
242                if (targetFound)
243                {
244                  idList.add(id);
245                  listSize++;
246                }
247                else if (beforeCount > 0)
248                {
249                  if (beforeCount > 0)
250                  {
251                    idList.add(id);
252                    includedBeforeCount++;
253                    if (includedBeforeCount > beforeCount)
254                    {
255                      idList.removeFirst();
256                      includedBeforeCount--;
257                    }
258                    else
259                    {
260                      listSize++;
261                    }
262                  }
263                }
264              }
265            }
266    
267            if (! targetFound)
268            {
269              // No entry was found to be greater than or equal to the sort key, so
270              // the target offset will be one greater than the content count.
271              targetOffset = sortMap.size() + 1;
272            }
273    
274            sortedIDs = new long[listSize];
275            Iterator<EntryID> idIterator = idList.iterator();
276            for (int i=0; i < listSize; i++)
277            {
278              sortedIDs[i] = idIterator.next().longValue();
279            }
280    
281            searchOperation.addResponseControl(
282                 new VLVResponseControl(targetOffset, sortMap.size(),
283                                        LDAPResultCode.SUCCESS));
284          }
285        }
286        else
287        {
288          sortedIDs = new long[sortMap.size()];
289          int i=0;
290          for (EntryID id : sortMap.values())
291          {
292            sortedIDs[i++] = id.longValue();
293          }
294        }
295    
296        return new EntryIDSet(sortedIDs, 0, sortedIDs.length);
297      }
298    }
299