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}