[apple/xnu.git] / bsd / hfs / hfscommon / Catalog / Catalog.c

/*
 * Copyright (c) 2000-2002 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

#pragma segment Catalog

#include <sys/param.h>
#include <sys/utfconv.h>

#include	"../../hfs_endian.h"

#include	"../headers/FileMgrInternal.h"
#include	"../headers/BTreesInternal.h"
#include	"../headers/CatalogPrivate.h"
#include	"../headers/HFSUnicodeWrappers.h"


// External routines

extern SInt32 FastRelString( ConstStr255Param str1, ConstStr255Param str2 );


//_________________________________________________________________________________
//	Exported Routines
//
//		CompareCatalogKeys  -  Compares two catalog keys.
//
//_________________________________________________________________________________


UInt32
GetDirEntrySize(BTreeIterator *bip, ExtendedVCB * vol)
{
	CatalogKey *	ckp;
	CatalogName *	cnp;
	ByteCount	utf8chars;
	UInt8		name[kdirentMaxNameBytes + 1];
	OSErr		result;

	ckp = (CatalogKey*) &bip->key;

	if (vol->vcbSigWord == kHFSPlusSigWord) {
		cnp = (CatalogName*) &ckp->hfsPlus.nodeName;
		utf8chars = utf8_encodelen(cnp->ustr.unicode,
				    cnp->ustr.length * sizeof(UniChar), ':', 0);
		if (utf8chars > kdirentMaxNameBytes)
			utf8chars = kdirentMaxNameBytes;
	} else { /* hfs */
		cnp = (CatalogName*) ckp->hfs.nodeName;
		result = hfs_to_utf8(vol, cnp->pstr, kdirentMaxNameBytes + 1,
				&utf8chars, name);
		if (result) {
			/*
			 * When an HFS name cannot be encoded with the current
			 * volume encoding we use MacRoman as a fallback.
			 */
			result = mac_roman_to_utf8(cnp->pstr, MAXHFSVNODELEN + 1,
					                           &utf8chars, name);
		}
	}

	return DIRENTRY_SIZE(utf8chars);
}
/*
 * NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  NOTE  
 * 
 * This is assuming maxinum size of a name is 255 (kdirentMaxNameBytes), which is incorrect.
 * Any caller of this has to make sure names > 255 are mangled!!!!!!!!
 */

OSErr
PositionIterator(CatalogIterator *cip, UInt32 offset, BTreeIterator *bip, UInt16 *op)
{
#define CAT_START_OFFSET (2 * sizeof(struct hfsdotentry))
	ExtendedVCB *	vol;
	FCB *		fcb;
	OSErr		result = 0;

	/* are we past the end of a directory? */
	if (cip->folderID != cip->parentID)
		return(cmNotFound);

	vol = cip->volume;
	fcb = GetFileControlBlock(vol->catalogRefNum);

	/* make a btree iterator from catalog iterator */
	UpdateBtreeIterator(cip, bip);

	if (cip->currentOffset == offset) {
		*op = kBTreeCurrentRecord;

	} else if (cip->nextOffset == offset) {
		*op = kBTreeNextRecord;

	} else { /* start from beginning */
		*op = kBTreeNextRecord;

		/* Position iterator at the folder's thread record */
		result = BTSearchRecord(fcb, bip, NULL, NULL, bip);
		if (result)
			goto exit;
		
		/* find offset (note: n^2 / 2) */
		if (offset > CAT_START_OFFSET) { 
			HFSCatalogNodeID  pid, *idp;
			UInt32	curOffset, nextOffset;

			/* get first record (ie offset 24) */
			result = BTIterateRecord( fcb, kBTreeNextRecord, bip, NULL, NULL );		
			if (result)
				goto exit;

			if (vol->vcbSigWord == kHFSPlusSigWord)
				idp = &((CatalogKey*) &bip->key)->hfsPlus.parentID;
			else
				idp = &((CatalogKey*) &bip->key)->hfs.parentID;
			
			pid = *idp;

			curOffset = CAT_START_OFFSET;
	 		nextOffset = CAT_START_OFFSET + GetDirEntrySize(bip, vol);

			while (nextOffset < offset) {
				result = BTIterateRecord( fcb, kBTreeNextRecord, bip, NULL, NULL );		
				if (result)
					goto exit;
				
				/* check for parent change */
				if (pid != *idp) {
					result = cmNotFound;	/* offset past end of directory */
					goto exit;
				}

				curOffset = nextOffset;
				nextOffset += GetDirEntrySize(bip, vol);
			};
	
			if (nextOffset != offset) {
				result = cmNotFound;
				goto exit;
			}
	
			UpdateCatalogIterator(bip, cip);
			cip->currentOffset = curOffset;
			cip->nextOffset = nextOffset;
		}
	}

exit:	
	if (result == btNotFound)
		result = cmNotFound;

	return result;

} /* end PositionIterator */


//_________________________________________________________________________________
//	Routine:	CompareCatalogKeys
//
//	Function: 	Compares two catalog keys (a search key and a trial key).
//
// 	Result:		+n  search key > trial key
//				 0  search key = trial key
//				-n  search key < trial key
//_________________________________________________________________________________

SInt32
CompareCatalogKeys(HFSCatalogKey *searchKey, HFSCatalogKey *trialKey)
{
	HFSCatalogNodeID	searchParentID, trialParentID;
	SInt32	result;

	searchParentID = searchKey->parentID;
	trialParentID = trialKey->parentID;

	if ( searchParentID > trialParentID ) 	// parent dirID is unsigned
		result = 1;
	else if ( searchParentID < trialParentID )
		result = -1;
	else // parent dirID's are equal, compare names
		result = FastRelString(searchKey->nodeName, trialKey->nodeName);

	return result;
}


//_________________________________________________________________________________
//	Routine:	CompareExtendedCatalogKeys
//
//	Function: 	Compares two large catalog keys (a search key and a trial key).
//
// 	Result:		+n  search key > trial key
//				 0  search key = trial key
//				-n  search key < trial key
//_________________________________________________________________________________

SInt32
CompareExtendedCatalogKeys(HFSPlusCatalogKey *searchKey, HFSPlusCatalogKey *trialKey)
{
	SInt32			result;
	HFSCatalogNodeID	searchParentID, trialParentID;

	searchParentID = searchKey->parentID;
	trialParentID = trialKey->parentID;
	
	if ( searchParentID > trialParentID ) 	// parent node IDs are unsigned
	{
		result = 1;
	}
	else if ( searchParentID < trialParentID )
	{
		result = -1;
	}
	else // parent node ID's are equal, compare names
	{
		if ( searchKey->nodeName.length == 0 || trialKey->nodeName.length == 0 )
			result = searchKey->nodeName.length - trialKey->nodeName.length;
		else
			result = FastUnicodeCompare(&searchKey->nodeName.unicode[0], searchKey->nodeName.length,
										&trialKey->nodeName.unicode[0], trialKey->nodeName.length);
	}

	return result;
}
Commit	Line	Data
1c79356b	1	/*
9bccf70c	2	* Copyright (c) 2000-2002 Apple Computer, Inc. All rights reserved.
1c79356b A	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
d7e50217	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
1c79356b	7	*
d7e50217 A	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
1c79356b A	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
1c79356b A	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
d7e50217 A	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.
1c79356b A	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
1c79356b A	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"
1c79356b A	37
	38
	39	// External routines
	40
	41	extern SInt32 FastRelString( ConstStr255Param str1, ConstStr255Param str2 );
	42
1c79356b A	43
	44	//_________________________________________________________________________________
	45	// Exported Routines
	46	//
9bccf70c	47	// CompareCatalogKeys - Compares two catalog keys.
1c79356b A	48	//
	49	//_________________________________________________________________________________
	50
1c79356b A	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;
1c79356b A	70	} else { /* hfs */
	71	cnp = (CatalogName*) ckp->hfs.nodeName;
	72	result = hfs_to_utf8(vol, cnp->pstr, kdirentMaxNameBytes + 1,
	73	&utf8chars, name);
0b4e3aa0 A	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	}
1c79356b A	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	{
d71b494c	96	#define CAT_START_OFFSET (2 * sizeof(struct hfsdotentry))
1c79356b A	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 */
1c79356b A	118	*op = kBTreeNextRecord;
1c79356b A	119
1c79356b	120	/* Position iterator at the folder's thread record */
9bccf70c	121	result = BTSearchRecord(fcb, bip, NULL, NULL, bip);
1c79356b A	122	if (result)
1c79356b A	123	goto exit;
1c79356b A	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;
d71b494c	143	nextOffset = CAT_START_OFFSET + GetDirEntrySize(bip, vol);
1c79356b A	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
1c79356b A	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
1c79356b A	204	result = FastRelString(searchKey->nodeName, trialKey->nodeName);
1c79356b A	205
1c79356b A	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