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