1/* 2 * Copyright (c) 1999-2003 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24 25 26#include "Scavenger.h" 27#include "BTree.h" 28#include "CaseFolding.h" 29 30 31SInt32 FastUnicodeCompare ( register ConstUniCharArrayPtr str1, register ItemCount length1, 32 register ConstUniCharArrayPtr str2, register ItemCount length2); 33 34//_______________________________________________________________________ 35// 36// Routine: FastRelString 37// 38// Output: returns -1 if str1 < str2 39// returns 1 if str1 > str2 40// return 0 if equal 41// 42//_______________________________________________________________________ 43 44SInt32 FastRelString( ConstStr255Param str1, ConstStr255Param str2 ) 45{ 46 SInt32 bestGuess; 47 UInt8 length, length2; 48 49 50 length = *(str1++); 51 length2 = *(str2++); 52 53 if (length == length2) 54 bestGuess = 0; 55 else if (length < length2) 56 bestGuess = -1; 57 else 58 { 59 bestGuess = 1; 60 length = length2; 61 } 62 63 while (length--) 64 { 65 UInt32 aChar, bChar; 66 67 aChar = *(str1++); 68 bChar = *(str2++); 69 70 if (aChar != bChar) /* If they don't match exacly, do case conversion */ 71 { 72 UInt16 aSortWord, bSortWord; 73 74 aSortWord = gCompareTable[aChar]; 75 bSortWord = gCompareTable[bChar]; 76 77 if (aSortWord > bSortWord) 78 return 1; 79 80 if (aSortWord < bSortWord) 81 return -1; 82 } 83 84 /* 85 * If characters match exactly, then go on to next character 86 * immediately without doing any extra work. 87 */ 88 } 89 90 /* if you got to here, then return bestGuess */ 91 return bestGuess; 92} 93 94 95 96// 97// FastUnicodeCompare - Compare two Unicode strings; produce a relative ordering 98// 99// IF RESULT 100// -------------------------- 101// str1 < str2 => -1 102// str1 = str2 => 0 103// str1 > str2 => +1 104// 105// The lower case table starts with 256 entries (one for each of the upper bytes 106// of the original Unicode char). If that entry is zero, then all characters with 107// that upper byte are already case folded. If the entry is non-zero, then it is 108// the _index_ (not byte offset) of the start of the sub-table for the characters 109// with that upper byte. All ignorable characters are folded to the value zero. 110// 111// In pseudocode: 112// 113// Let c = source Unicode character 114// Let table[] = lower case table 115// 116// lower = table[highbyte(c)] 117// if (lower == 0) 118// lower = c 119// else 120// lower = table[lower+lowbyte(c)] 121// 122// if (lower == 0) 123// ignore this character 124// 125// To handle ignorable characters, we now need a loop to find the next valid character. 126// Also, we can't pre-compute the number of characters to compare; the string length might 127// be larger than the number of non-ignorable characters. Further, we must be able to handle 128// ignorable characters at any point in the string, including as the first or last characters. 129// We use a zero value as a sentinel to detect both end-of-string and ignorable characters. 130// Since the File Manager doesn't prevent the NUL character (value zero) as part of a filename, 131// the case mapping table is assumed to map u+0000 to some non-zero value (like 0xFFFF, which is 132// an invalid Unicode character). 133// 134// Pseudocode: 135// 136// while (1) { 137// c1 = GetNextValidChar(str1) // returns zero if at end of string 138// c2 = GetNextValidChar(str2) 139// 140// if (c1 != c2) break // found a difference 141// 142// if (c1 == 0) // reached end of string on both strings at once? 143// return 0; // yes, so strings are equal 144// } 145// 146// // When we get here, c1 != c2. So, we just need to determine which one is less. 147// if (c1 < c2) 148// return -1; 149// else 150// return 1; 151// 152 153SInt32 FastUnicodeCompare ( register ConstUniCharArrayPtr str1, register ItemCount length1, 154 register ConstUniCharArrayPtr str2, register ItemCount length2) 155{ 156 register UInt16 c1,c2; 157 register UInt16 temp; 158 159 while (1) { 160 /* Set default values for c1, c2 in case there are no more valid chars */ 161 c1 = 0; 162 c2 = 0; 163 164 /* Find next non-ignorable char from str1, or zero if no more */ 165 while (length1 && c1 == 0) { 166 c1 = *(str1++); 167 --length1; 168 if ((temp = gLowerCaseTable[c1>>8]) != 0) // is there a subtable for this upper byte? 169 c1 = gLowerCaseTable[temp + (c1 & 0x00FF)]; // yes, so fold the char 170 } 171 172 173 /* Find next non-ignorable char from str2, or zero if no more */ 174 while (length2 && c2 == 0) { 175 c2 = *(str2++); 176 --length2; 177 if ((temp = gLowerCaseTable[c2>>8]) != 0) // is there a subtable for this upper byte? 178 c2 = gLowerCaseTable[temp + (c2 & 0x00FF)]; // yes, so fold the char 179 } 180 181 if (c1 != c2) /* found a difference, so stop looping */ 182 break; 183 184 if (c1 == 0) /* did we reach the end of both strings at the same time? */ 185 return 0; /* yes, so strings are equal */ 186 } 187 188 if (c1 < c2) 189 return -1; 190 else 191 return 1; 192} 193 194 195//������������������������������������������������������������������������������� 196// Routine: CompareCatalogKeys 197// 198// Function: Compares two catalog keys (a search key and a trial key). 199// 200// Result: +n search key > trial key 201// 0 search key = trial key 202// -n search key < trial key 203//������������������������������������������������������������������������������� 204 205SInt32 206CompareCatalogKeys(HFSCatalogKey *searchKey, HFSCatalogKey *trialKey) 207{ 208 HFSCatalogNodeID searchParentID, trialParentID; 209 SInt32 result; 210 211 searchParentID = searchKey->parentID; 212 trialParentID = trialKey->parentID; 213 214 if ( searchParentID > trialParentID ) /* parent dirID is unsigned */ 215 result = 1; 216 else if ( searchParentID < trialParentID ) 217 result = -1; 218 else /* parent dirID's are equal, compare names */ 219 result = FastRelString(searchKey->nodeName, trialKey->nodeName); 220 221 return result; 222} 223 224 225/* 226 * Routine: CompareExtendedCatalogKeys 227 * 228 * Function: Compares two large catalog keys (a search key and a trial key). 229 * 230 * Result: +n search key > trial key 231 * 0 search key = trial key 232 * -n search key < trial key 233 */ 234 235SInt32 236CompareExtendedCatalogKeys(HFSPlusCatalogKey *searchKey, HFSPlusCatalogKey *trialKey) 237{ 238 SInt32 result; 239 HFSCatalogNodeID searchParentID, trialParentID; 240 241 searchParentID = searchKey->parentID; 242 trialParentID = trialKey->parentID; 243 244 if ( searchParentID > trialParentID ) // parent node IDs are unsigned 245 { 246 result = 1; 247 } 248 else if ( searchParentID < trialParentID ) 249 { 250 result = -1; 251 } 252 else // parent node ID's are equal, compare names 253 { 254 if ( searchKey->nodeName.length == 0 || trialKey->nodeName.length == 0 ) 255 result = searchKey->nodeName.length - trialKey->nodeName.length; 256 else 257 result = FastUnicodeCompare(&searchKey->nodeName.unicode[0], searchKey->nodeName.length, 258 &trialKey->nodeName.unicode[0], trialKey->nodeName.length); 259 } 260 261 return result; 262} 263 264 265/* 266 * Routine: CaseSensitiveCatalogKeyCompare 267 * 268 * Function: Compares two catalog keys using a 16-bit binary comparison 269 * for the name portion of the key. 270 * 271 * Result: +n search key > trial key 272 * 0 search key = trial key 273 * -n search key < trial key 274 */ 275 276SInt32 277CaseSensitiveCatalogKeyCompare(HFSPlusCatalogKey *searchKey, HFSPlusCatalogKey *trialKey) 278{ 279 HFSCatalogNodeID searchParentID, trialParentID; 280 SInt32 result; 281 282 searchParentID = searchKey->parentID; 283 trialParentID = trialKey->parentID; 284 result = 0; 285 286 if (searchParentID > trialParentID) { 287 ++result; 288 } else if (searchParentID < trialParentID) { 289 --result; 290 } else { 291 UInt16 * str1 = &searchKey->nodeName.unicode[0]; 292 UInt16 * str2 = &trialKey->nodeName.unicode[0]; 293 int length1 = searchKey->nodeName.length; 294 int length2 = trialKey->nodeName.length; 295 UInt16 c1, c2; 296 int length; 297 298 if (length1 < length2) { 299 length = length1; 300 --result; 301 } else if (length1 > length2) { 302 length = length2; 303 ++result; 304 } else { 305 length = length1; 306 } 307 308 while (length--) { 309 c1 = *(str1++); 310 c2 = *(str2++); 311 if (c1 > c2) { 312 result = 1; 313 break; 314 } 315 if (c1 < c2) { 316 result = -1; 317 break; 318 } 319 } 320 } 321 322 return result; 323} 324 325//������������������������������������������������������������������������������� 326// Routine: CompareExtentKeys 327// 328// Function: Compares two extent file keys (a search key and a trial key) for 329// an HFS volume. 330//������������������������������������������������������������������������������� 331 332SInt32 CompareExtentKeys( const HFSExtentKey *searchKey, const HFSExtentKey *trialKey ) 333{ 334 SInt32 result; // � 1 335 336 #if DEBUG_BUILD 337 if (searchKey->keyLength != kHFSExtentKeyMaximumLength) 338 DebugStr("\pHFS: search Key is wrong length"); 339 if (trialKey->keyLength != kHFSExtentKeyMaximumLength) 340 DebugStr("\pHFS: trial Key is wrong length"); 341 #endif 342 343 result = -1; // assume searchKey < trialKey 344 345 if (searchKey->fileID == trialKey->fileID) { 346 // 347 // FileNum's are equal; compare fork types 348 // 349 if (searchKey->forkType == trialKey->forkType) { 350 // 351 // Fork types are equal; compare allocation block number 352 // 353 if (searchKey->startBlock == trialKey->startBlock) { 354 // 355 // Everything is equal 356 // 357 result = 0; 358 } 359 else { 360 // 361 // Allocation block numbers differ; determine sign 362 // 363 if (searchKey->startBlock > trialKey->startBlock) 364 result = 1; 365 } 366 } 367 else { 368 // 369 // Fork types differ; determine sign 370 // 371 if (searchKey->forkType > trialKey->forkType) 372 result = 1; 373 } 374 } 375 else { 376 // 377 // FileNums differ; determine sign 378 // 379 if (searchKey->fileID > trialKey->fileID) 380 result = 1; 381 } 382 383 return( result ); 384} 385 386 387 388//������������������������������������������������������������������������������� 389// Routine: CompareExtentKeysPlus 390// 391// Function: Compares two extent file keys (a search key and a trial key) for 392// an HFS volume. 393//������������������������������������������������������������������������������� 394 395SInt32 CompareExtentKeysPlus( const HFSPlusExtentKey *searchKey, const HFSPlusExtentKey *trialKey ) 396{ 397 SInt32 result; // � 1 398 399 #if DEBUG_BUILD 400 if (searchKey->keyLength != kHFSPlusExtentKeyMaximumLength) 401 DebugStr("\pHFS: search Key is wrong length"); 402 if (trialKey->keyLength != kHFSPlusExtentKeyMaximumLength) 403 DebugStr("\pHFS: trial Key is wrong length"); 404 #endif 405 406 result = -1; // assume searchKey < trialKey 407 408 if (searchKey->fileID == trialKey->fileID) { 409 // 410 // FileNum's are equal; compare fork types 411 // 412 if (searchKey->forkType == trialKey->forkType) { 413 // 414 // Fork types are equal; compare allocation block number 415 // 416 if (searchKey->startBlock == trialKey->startBlock) { 417 // 418 // Everything is equal 419 // 420 result = 0; 421 } 422 else { 423 // 424 // Allocation block numbers differ; determine sign 425 // 426 if (searchKey->startBlock > trialKey->startBlock) 427 result = 1; 428 } 429 } 430 else { 431 // 432 // Fork types differ; determine sign 433 // 434 if (searchKey->forkType > trialKey->forkType) 435 result = 1; 436 } 437 } 438 else { 439 // 440 // FileNums differ; determine sign 441 // 442 if (searchKey->fileID > trialKey->fileID) 443 result = 1; 444 } 445 446 return( result ); 447} 448 449 450/* 451 * Compare two attribute b-tree keys. 452 * 453 * The name portion of the key is compared using a 16-bit binary comparison. 454 * This is called from the b-tree code. 455 */ 456__private_extern__ 457SInt32 458CompareAttributeKeys(const AttributeKey *searchKey, const AttributeKey *trialKey) 459{ 460 UInt32 searchFileID, trialFileID; 461 SInt32 result; 462 463 searchFileID = searchKey->cnid; 464 trialFileID = trialKey->cnid; 465 result = 0; 466 467 if (searchFileID > trialFileID) { 468 ++result; 469 } else if (searchFileID < trialFileID) { 470 --result; 471 } else { 472 const UInt16 * str1 = searchKey->attrName; 473 const UInt16 * str2 = trialKey->attrName; 474 int length1 = searchKey->attrNameLen; 475 int length2 = trialKey->attrNameLen; 476 UInt16 c1, c2; 477 int length; 478 479 if (length1 < length2) { 480 length = length1; 481 --result; 482 } else if (length1 > length2) { 483 length = length2; 484 ++result; 485 } else { 486 length = length1; 487 } 488 489 while (length--) { 490 c1 = *(str1++); 491 c2 = *(str2++); 492 493 if (c1 > c2) { 494 result = 1; 495 break; 496 } 497 if (c1 < c2) { 498 result = -1; 499 break; 500 } 501 } 502 if (result) 503 return (result); 504 /* 505 * Names are equal; compare startBlock 506 */ 507 if (searchKey->startBlock == trialKey->startBlock) 508 return (0); 509 else 510 return (searchKey->startBlock < trialKey->startBlock ? -1 : 1); 511 } 512 513 return result; 514} 515 516