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