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 2006-2008 Sun Microsystems, Inc. 025 * Portions Copyright 2014-2015 ForgeRock AS 026 */ 027package org.opends.server.backends.jeb; 028 029import org.forgerock.opendj.ldap.ByteString; 030import org.forgerock.opendj.ldap.DecodeException; 031import org.forgerock.opendj.ldap.ResultCode; 032import org.forgerock.opendj.ldap.schema.MatchingRule; 033import org.opends.server.core.DirectoryServer; 034import org.opends.server.types.DirectoryException; 035 036import com.sleepycat.je.DatabaseComparator; 037import com.sleepycat.je.DatabaseException; 038 039/** 040 * This class is used to compare the keys used in a VLV index. Each key is 041 * made up the sort values and the entry ID of the largest entry in the sorted 042 * set stored in the data for the key. 043 */ 044public class VLVKeyComparator implements DatabaseComparator 045{ 046 /** 047 * The serial version identifier required to satisfy the compiler because this 048 * class implements the <CODE>java.io.Serializable</CODE> interface. This 049 * value was generated using the <CODE>serialver</CODE> command-line utility 050 * included with the Java SDK. 051 */ 052 static final long serialVersionUID = 1585167927344130604L; 053 054 /** Matching rules are not serializable. */ 055 private transient MatchingRule[] orderingRules; 056 057 /** 058 * Only oids of matching rules are recorded for serialization. Oids allow to 059 * retrieve matching rules after deserialization, through 060 * {@code initialize(ClassLoader)} method. 061 */ 062 private String[] orderingRuleOids; 063 064 private boolean[] ascending; 065 066 /** 067 * Construct a new VLV Key Comparator object. 068 * 069 * @param orderingRules The array of ordering rules to use when comparing 070 * the decoded values in the key. 071 * @param ascending The array of booleans indicating the ordering for 072 * each value. 073 */ 074 public VLVKeyComparator(MatchingRule[] orderingRules, boolean[] ascending) 075 { 076 this.orderingRules = orderingRules; 077 this.orderingRuleOids = new String[orderingRules.length]; 078 for (int i = 0; i < orderingRules.length; i++) 079 { 080 orderingRuleOids[i] = orderingRules[i].getOID(); 081 } 082 this.ascending = ascending; 083 } 084 085 /** 086 * Compares the contents of the provided byte arrays to determine their 087 * relative order. A key in the VLV index contains the sorted attribute values 088 * in order followed by the 8 byte entry ID. A attribute value of length 0 089 * means that value is null and the attribute type was not part of the entry. 090 * A null value is always considered greater then a non null value. If all 091 * attribute values are the same, the entry ID will be used to determine the 092 * ordering. 093 * 094 * When comparing partial keys (ie. keys with only the first attribute value 095 * encoded for evaluating VLV assertion value offsets or keys with no entry 096 * IDs), only information available in both byte keys will be used to 097 * determine the ordering. If all available information is the same, 0 will 098 * be returned. 099 * 100 * @param b1 The first byte array to use in the comparison. 101 * @param b2 The second byte array to use in the comparison. 102 * 103 * @return A negative integer if <CODE>b1</CODE> should come before 104 * <CODE>b2</CODE> in ascending order, a positive integer if 105 * <CODE>b1</CODE> should come after <CODE>b2</CODE> in ascending 106 * order, or zero if there is no difference between the values with 107 * regard to ordering. 108 */ 109 @Override 110 public int compare(byte[] b1, byte[] b2) 111 { 112 // A 0 length byte array is a special key used for the unbound max 113 // sort values set. It always comes after a non length byte array. 114 if(b1.length == 0) 115 { 116 if(b2.length == 0) 117 { 118 return 0; 119 } 120 else 121 { 122 return 1; 123 } 124 } 125 else if(b2.length == 0) 126 { 127 return -1; 128 } 129 130 int b1Pos = 0; 131 int b2Pos = 0; 132 for (int j=0; 133 j < orderingRules.length && b1Pos < b1.length && b2Pos < b2.length; 134 j++) 135 { 136 int b1Length = b1[b1Pos] & 0x7F; 137 if (b1[b1Pos++] != b1Length) 138 { 139 int b1NumLengthBytes = b1Length; 140 b1Length = 0; 141 for (int k=0; k < b1NumLengthBytes; k++, b1Pos++) 142 { 143 b1Length = (b1Length << 8) | 144 (b1[b1Pos] & 0xFF); 145 } 146 } 147 148 int b2Length = b2[b2Pos] & 0x7F; 149 if (b2[b2Pos++] != b2Length) 150 { 151 int b2NumLengthBytes = b2Length; 152 b2Length = 0; 153 for (int k=0; k < b2NumLengthBytes; k++, b2Pos++) 154 { 155 b2Length = (b2Length << 8) | 156 (b2[b2Pos] & 0xFF); 157 } 158 } 159 160 byte[] b1Bytes; 161 byte[] b2Bytes; 162 if(b1Length > 0) 163 { 164 b1Bytes = new byte[b1Length]; 165 System.arraycopy(b1, b1Pos, b1Bytes, 0, b1Length); 166 b1Pos += b1Length; 167 } 168 else 169 { 170 b1Bytes = null; 171 } 172 173 if(b2Length > 0) 174 { 175 b2Bytes = new byte[b2Length]; 176 System.arraycopy(b2, b2Pos, b2Bytes, 0, b2Length); 177 b2Pos += b2Length; 178 } 179 else 180 { 181 b2Bytes = null; 182 } 183 184 // A null value will always come after a non-null value. 185 if (b1Bytes == null) 186 { 187 if (b2Bytes == null) 188 { 189 continue; 190 } 191 else 192 { 193 return 1; 194 } 195 } 196 else if (b2Bytes == null) 197 { 198 return -1; 199 } 200 201 final ByteString val1 = ByteString.valueOf(b1Bytes); 202 final ByteString val2 = ByteString.valueOf(b2Bytes); 203 final int result = ascending[j] ? val1.compareTo(val2) : val2.compareTo(val1); 204 if(result != 0) 205 { 206 return result; 207 } 208 } 209 210 // If we've gotten here, then we can't tell a difference between the sets 211 // of available values, so sort based on entry ID if its in the key. 212 213 if(b1Pos + 8 <= b1.length && b2Pos + 8 <= b2.length) 214 { 215 long b1ID = JebFormat.toLong(b1, b1Pos, b1Pos + 8); 216 long b2ID = JebFormat.toLong(b2, b2Pos, b2Pos + 8); 217 return compare(b1ID, b2ID); 218 } 219 220 // If we've gotten here, then we can't tell the difference between the sets 221 // of available values and entry IDs are not all available, so just return 0 222 return 0; 223 } 224 225 /** 226 * Compares the contents in the provided values set with the given values to 227 * determine their relative order. A null value is always considered greater 228 * then a non null value. If all attribute values are the same, the entry ID 229 * will be used to determine the ordering. 230 * 231 * If the given attribute values array does not contain all the values in the 232 * sort order, any missing values will be considered as a unknown or 233 * wildcard value instead of a non existent value. When comparing partial 234 * information, only values available in both the values set and the 235 * given values will be used to determine the ordering. If all available 236 * information is the same, 0 will be returned. 237 * 238 * @param set The sort values set to containing the values. 239 * @param index The index of the values in the set. 240 * @param entryID The entry ID to use in the comparison. 241 * @param values The values to use in the comparison. 242 * @return A negative integer if the values in the set should come before 243 * the given values in ascending order, a positive integer if 244 * the values in the set should come after the given values in 245 * ascending order, or zero if there is no difference between the 246 * values with regard to ordering. 247 * @throws DatabaseException If an error occurs during an operation on a 248 * JE database. 249 * @throws DirectoryException If an error occurs while trying to 250 * normalize the value (e.g., if it is 251 * not acceptable for use with the 252 * associated equality matching rule). 253 */ 254 public int compare(SortValuesSet set, int index, long entryID, 255 ByteString[] values) throws DatabaseException, DirectoryException 256 { 257 for (int j=0; j < orderingRules.length; j++) 258 { 259 if(j >= values.length) 260 { 261 break; 262 } 263 264 ByteString b1Bytes = set.getValue(index * orderingRules.length + j); 265 ByteString b2Bytes = null; 266 267 if(values[j] != null) 268 { 269 try 270 { 271 b2Bytes = orderingRules[j].normalizeAttributeValue(values[j]); 272 } 273 catch (DecodeException e) 274 { 275 throw new DirectoryException( 276 ResultCode.INVALID_ATTRIBUTE_SYNTAX, e.getMessageObject(), e); 277 } 278 } 279 280 // A null value will always come after a non-null value. 281 if (b1Bytes == null) 282 { 283 if (b2Bytes == null) 284 { 285 continue; 286 } 287 else 288 { 289 return 1; 290 } 291 } 292 else if (b2Bytes == null) 293 { 294 return -1; 295 } 296 297 final int result = ascending[j] ? b1Bytes.compareTo(b2Bytes) : b2Bytes.compareTo(b1Bytes); 298 if(result != 0) 299 { 300 return result; 301 } 302 } 303 304 if(entryID != -1) 305 { 306 // If we've gotten here, then we can't tell a difference between the sets 307 // of values, so sort based on entry ID. 308 return compare(set.getEntryIDs()[index], entryID); 309 } 310 311 // If we've gotten here, then we can't tell the difference between the sets 312 // of available values and the entry ID is not available. Just return 0. 313 return 0; 314 } 315 316 private int compare(long l1, long l2) 317 { 318 final long difference = l1 - l2; 319 if (difference < 0) 320 { 321 return -1; 322 } 323 else if (difference > 0) 324 { 325 return 1; 326 } 327 else 328 { 329 return 0; 330 } 331 } 332 333 /** {@inheritDoc} */ 334 @Override 335 public void initialize(ClassLoader loader) 336 { 337 if (orderingRules == null) 338 { 339 orderingRules = new MatchingRule[orderingRuleOids.length]; 340 for (int i = 0; i < orderingRuleOids.length; i++) 341 { 342 orderingRules[i] = DirectoryServer.getSchema().getMatchingRule(orderingRuleOids[i]); 343 } 344 } 345 } 346}