bsd/hfs/hfscommon/Catalog/Catalog.c

   1 /*
   2  * Copyright (c) 2000-2002 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25
  26 #pragma segment Catalog
  27
  28 #include <sys/param.h>
  29 #include <sys/utfconv.h>
  30
  31 #include        "../../hfs_endian.h"
  32
  33 #include        "../headers/FileMgrInternal.h"
  34 #include        "../headers/BTreesInternal.h"
  35 #include        "../headers/CatalogPrivate.h"
  36 #include        "../headers/HFSUnicodeWrappers.h"
  37
  38
  39 // External routines
  40
  41 extern SInt32 FastRelString( ConstStr255Param str1, ConstStr255Param str2 );
  42
  43
  44 //_________________________________________________________________________________
  45 //      Exported Routines
  46 //
  47 //              CompareCatalogKeys  -  Compares two catalog keys.
  48 //
  49 //_________________________________________________________________________________
  50
  51
  52
  53 UInt32
  54 GetDirEntrySize(BTreeIterator *bip, ExtendedVCB * vol)
  55 {
  56         CatalogKey *    ckp;
  57         CatalogName *   cnp;
  58         ByteCount       utf8chars;
  59         UInt8           name[kdirentMaxNameBytes + 1];
  60         OSErr           result;
  61
  62         ckp = (CatalogKey*) &bip->key;
  63
  64         if (vol->vcbSigWord == kHFSPlusSigWord) {
  65                 cnp = (CatalogName*) &ckp->hfsPlus.nodeName;
  66                 utf8chars = utf8_encodelen(cnp->ustr.unicode,
  67                                     cnp->ustr.length * sizeof(UniChar), ':', 0);
  68                 if (utf8chars > kdirentMaxNameBytes)
  69                         utf8chars = kdirentMaxNameBytes;
  70         } else { /* hfs */
  71                 cnp = (CatalogName*) ckp->hfs.nodeName;
  72                 result = hfs_to_utf8(vol, cnp->pstr, kdirentMaxNameBytes + 1,
  73                                 &utf8chars, name);
  74                 if (result) {
  75                         /*
  76                          * When an HFS name cannot be encoded with the current
  77                          * volume encoding we use MacRoman as a fallback.
  78                          */
  79                         result = mac_roman_to_utf8(cnp->pstr, MAXHFSVNODELEN + 1,
  80                                                                    &utf8chars, name);
  81                 }
  82         }
  83
  84         return DIRENTRY_SIZE(utf8chars);
  85 }
  86 /*
  87  * NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE
  88  *
  89  * This is assuming maxinum size of a name is 255 (kdirentMaxNameBytes), which is incorrect.
  90  * Any caller of this has to make sure names > 255 are mangled!!!!!!!!
  91  */
  92
  93 OSErr
  94 PositionIterator(CatalogIterator *cip, UInt32 offset, BTreeIterator *bip, UInt16 *op)
  95 {
  96 #define CAT_START_OFFSET (2 * sizeof(struct hfsdotentry))
  97         ExtendedVCB *   vol;
  98         FCB *           fcb;
  99         OSErr           result = 0;
 100
 101         /* are we past the end of a directory? */
 102         if (cip->folderID != cip->parentID)
 103                 return(cmNotFound);
 104
 105         vol = cip->volume;
 106         fcb = GetFileControlBlock(vol->catalogRefNum);
 107
 108         /* make a btree iterator from catalog iterator */
 109         UpdateBtreeIterator(cip, bip);
 110
 111         if (cip->currentOffset == offset) {
 112                 *op = kBTreeCurrentRecord;
 113
 114         } else if (cip->nextOffset == offset) {
 115                 *op = kBTreeNextRecord;
 116
 117         } else { /* start from beginning */
 118                 *op = kBTreeNextRecord;
 119
 120                 /* Position iterator at the folder's thread record */
 121                 result = BTSearchRecord(fcb, bip, NULL, NULL, bip);
 122                 if (result)
 123                         goto exit;
 124
 125                 /* find offset (note: n^2 / 2) */
 126                 if (offset > CAT_START_OFFSET) {
 127                         HFSCatalogNodeID  pid, *idp;
 128                         UInt32  curOffset, nextOffset;
 129
 130                         /* get first record (ie offset 24) */
 131                         result = BTIterateRecord( fcb, kBTreeNextRecord, bip, NULL, NULL );
 132                         if (result)
 133                                 goto exit;
 134
 135                         if (vol->vcbSigWord == kHFSPlusSigWord)
 136                                 idp = &((CatalogKey*) &bip->key)->hfsPlus.parentID;
 137                         else
 138                                 idp = &((CatalogKey*) &bip->key)->hfs.parentID;
 139
 140                         pid = *idp;
 141
 142                         curOffset = CAT_START_OFFSET;
 143                         nextOffset = CAT_START_OFFSET + GetDirEntrySize(bip, vol);
 144
 145                         while (nextOffset < offset) {
 146                                 result = BTIterateRecord( fcb, kBTreeNextRecord, bip, NULL, NULL );
 147                                 if (result)
 148                                         goto exit;
 149
 150                                 /* check for parent change */
 151                                 if (pid != *idp) {
 152                                         result = cmNotFound;    /* offset past end of directory */
 153                                         goto exit;
 154                                 }
 155
 156                                 curOffset = nextOffset;
 157                                 nextOffset += GetDirEntrySize(bip, vol);
 158                         };
 159
 160                         if (nextOffset != offset) {
 161                                 result = cmNotFound;
 162                                 goto exit;
 163                         }
 164
 165                         UpdateCatalogIterator(bip, cip);
 166                         cip->currentOffset = curOffset;
 167                         cip->nextOffset = nextOffset;
 168                 }
 169         }
 170
 171 exit:
 172         if (result == btNotFound)
 173                 result = cmNotFound;
 174
 175         return result;
 176
 177 } /* end PositionIterator */
 178
 179
 180 //_________________________________________________________________________________
 181 //      Routine:        CompareCatalogKeys
 182 //
 183 //      Function:       Compares two catalog keys (a search key and a trial key).
 184 //
 185 //      Result:         +n  search key > trial key
 186 //                               0  search key = trial key
 187 //                              -n  search key < trial key
 188 //_________________________________________________________________________________
 189
 190 SInt32
 191 CompareCatalogKeys(HFSCatalogKey *searchKey, HFSCatalogKey *trialKey)
 192 {
 193         HFSCatalogNodeID        searchParentID, trialParentID;
 194         SInt32  result;
 195
 196         searchParentID = searchKey->parentID;
 197         trialParentID = trialKey->parentID;
 198
 199         if ( searchParentID > trialParentID )   // parent dirID is unsigned
 200                 result = 1;
 201         else if ( searchParentID < trialParentID )
 202                 result = -1;
 203         else // parent dirID's are equal, compare names
 204                 result = FastRelString(searchKey->nodeName, trialKey->nodeName);
 205
 206         return result;
 207 }
 208
 209
 210 //_________________________________________________________________________________
 211 //      Routine:        CompareExtendedCatalogKeys
 212 //
 213 //      Function:       Compares two large catalog keys (a search key and a trial key).
 214 //
 215 //      Result:         +n  search key > trial key
 216 //                               0  search key = trial key
 217 //                              -n  search key < trial key
 218 //_________________________________________________________________________________
 219
 220 SInt32
 221 CompareExtendedCatalogKeys(HFSPlusCatalogKey *searchKey, HFSPlusCatalogKey *trialKey)
 222 {
 223         SInt32                  result;
 224         HFSCatalogNodeID        searchParentID, trialParentID;
 225
 226         searchParentID = searchKey->parentID;
 227         trialParentID = trialKey->parentID;
 228
 229         if ( searchParentID > trialParentID )   // parent node IDs are unsigned
 230         {
 231                 result = 1;
 232         }
 233         else if ( searchParentID < trialParentID )
 234         {
 235                 result = -1;
 236         }
 237         else // parent node ID's are equal, compare names
 238         {
 239                 if ( searchKey->nodeName.length == 0 || trialKey->nodeName.length == 0 )
 240                         result = searchKey->nodeName.length - trialKey->nodeName.length;
 241                 else
 242                         result = FastUnicodeCompare(&searchKey->nodeName.unicode[0], searchKey->nodeName.length,
 243                                                                                 &trialKey->nodeName.unicode[0], trialKey->nodeName.length);
 244         }
 245
 246         return result;
 247 }
 248