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