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

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