fsck_hfs/dfalib/SKeyCompare.c

   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
  31 SInt32 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
  44 SInt32  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
 153 SInt32 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
 205 SInt32
 206 CompareCatalogKeys(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
 235 SInt32
 236 CompareExtendedCatalogKeys(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
 276 SInt32
 277 CaseSensitiveCatalogKeyCompare(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
 332 SInt32 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
 395 SInt32 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__
 457 SInt32
 458 CompareAttributeKeys(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