hfs-user February 2002

hfs-user@lists.mars.org

10 participants
15 discussions

Index nodes of a catalog B-Tree
by Entwicklung 11 Feb '02

11 Feb '02

> Simon Bazley, > Thanks for replying ! > I managed to figure out what the problem was- I had mentioned this in my > previous email to the list. > I have a question to which maybe you or someone from the list knows the > answer - > At the moment I'm wondering how to determine the number of index nodes > needed for a catalog tree. I have determined the number of catalog nodes > needed and my question is : Does every leaf node in the catalog-tree have to > be referenced in the index-nodes? > In a broadly logical sense I would say that it has to ...since a leaf > without an index in a 'real' tree would probably be like a leaf falling off > a branch in autumn :). The HFS reference (Inside Macintosh) has this figure > of a sample B-Tree where a reference to every leaf-node is maintained in the > index nodes. > But I came across a sample HFS-image (which is readable on my Mac) which > shattered all my illusions since the root-node (the only index node in this > image) doesn't maintain references to all leaf nodes, only to a few of them. > > Does anyone from Apple (or others) maybe know how the index nodes are to > built up i.e. to which leaf-nodes (if not to all) a reference has to > necessarily be maintained ? I guess a Mac internally should be doing some > kind of optimization to reduce the search-time in finding a leaf-record.... > but all I need to know is what I should take into account while constructing > my index-nodes to make the job easier for the Mac when an external > HFS-volume is mounted. > > Would be grateful for any tips. > > Regards, > Nandini Hengen > > > > ----- Original Message ----- > From: "Simon Bazley <sibaz(a)sibaz.com>" <simon(a)sibaz.com> > To: "Entwicklung" <entwicklung(a)whengenibk.de> > Cc: <hfs-user(a)lists.mars.org> > Sent: Monday, February 11, 2002 2:41 AM > Subject: Re: [hfs-user] Volume-Names in HFS > > > > Have you checked Inside Macintosh Files to see what it says about the MDB > > record (assuming its an HFS volume) or the equivalent in the HFS+ Technote > > (assuming its HFS+). My understanding was that volume name was pretty > > bullet proof. > > > > Simon > > > > On Thu, 7 Feb 2002, Entwicklung wrote: > > > > > Hello, > > > My HFS-Volume seems to be recognized if I give the Volume a name > with an odd no. of characters say "NEW" but fails to be recognized if the > name is say "NAND_HFS". Does anybody know of a possible reason why this is > happening ? > > > > > > I think this had something to do with the key length field. In my case - > if the volume name is even hence implying that the associated key does not > end on an even byte boundary (where applicable), i byte is added for padding > but the key-length and name length fields are maintained as before. In those > keys which have to be of size=maximum key length the padding with zeroes is > done in any case. > > > Does anybody know if something else needs to be changed ? > > > > > > TIA, > > > Nandini Hengen > > > > > >

2 1

Algorithm of B* tree Implementation
by Biswaroop Banerjee 11 Feb '02

11 Feb '02

Hi All, Can anybody of you give me the algorithm of implementating a B* tree which is the prominent data structure in a HFS formatted volume. Waiting for your help. Regards Biswaroop Banerjee. The essence of Success lies in its Struggle -Bisban

4 6

Volume-Names in HFS
by Entwicklung 11 Feb '02

11 Feb '02

Hello, My HFS-Volume seems to be recognized if I give the Volume a name with an odd no. of characters say "NEW" but fails to be recognized if the name is say "NAND_HFS". Does anybody know of a possible reason why this is happening ? I think this had something to do with the key length field. In my case - if the volume name is even hence implying that the associated key does not end on an even byte boundary (where applicable), i byte is added for padding but the key-length and name length fields are maintained as before. In those keys which have to be of size=maximum key length the padding with zeroes is done in any case. Does anybody know if something else needs to be changed ? TIA, Nandini Hengen

2 1

RE: [hfs-user] Algorithm of B* tree Implementation
by Gordon Beatty 08 Feb '02

08 Feb '02

The technote number is 1150 but if you point your browser to http://developer.apple.com/techpubs/macos8/Files/FileManager/filemanager.htm l the links to the original HFS spec in "Inside Macintosh" and the HFS+ spec in TechNote 1150 are listed there (although the way OS X uses and interprets some of the fields in HFS+ does not seem completely reflected in the TechNote). Also, the technote refers to Robert Sedgewick's book 'Algorithms in C - Parts 1-4' -- and similarly 'Algorithms in C++ - Parts 1-4' -- which should prove a fairly clear reference for the purposes of understanding. The 'File Structures' book (previous or current version) by Michael Folk could help in this regard as well. At the end of the day though, a solid C implementation is certainly the best reference. Gord Beatty -----Original Message----- From: hfs-user-admin(a)lists.mars.org [mailto:hfs-user-admin@lists.mars.org]On Behalf Of Patrick Dirks Sent: Thursday, February 07, 2002 1:57 PM To: hfs-user(a)lists.mars.org Cc: Biswaroop Banerjee Subject: Re: [hfs-user] Algorithm of B* tree Implementation "The algorithm" is a bit hard to lay out in an e-mail message - it's wrapped up in a series of design and implementation aspects. Read up on B*-Trees and you should have a good idea what the data structure's supposed to look like at any given time. Read "Inside Macintosh" and you'll find a more detailed explanation of the exact details of the HFS/HFS+ B*-Tree structure. More helpful than "Inside Macintosh", perhaps, is the tech note that Apple's published on the subject - "must read" for anyone implementing a version of HFS/HFS+. I can't remember the tech note number offhand but it's freely available through Apple's web site - do a search there. Finally, note that the Darwin code, which Apple has open sourced, includes a complete "C" implementation of the B*-Tree code as part of a UNIX kernel. Sign up as a Darwin developer and check out a copy of the sources. It's in the "xnu" project in the "hfs" directory inside the "bsd" directory of "xnu". That's the ultimate answer right there. Hope that helps, -Pat Dirks. On Thursday, February 7, 2002, at 02:04 AM, Biswaroop Banerjee wrote: Hi All, Can anybody of you give me the algorithm of implementating a B* tree which is the prominent data structure in a HFS formatted volume. Waiting for your help. Regards Biswaroop Banerjee. The essence of Success lies in its Struggle -Bisban

2 1

Re:HFS Volume Names
by Entwicklung 07 Feb '02

07 Feb '02

Hello, I managed to figure out what the problem was- it didn't have anything to do with odd or even lengths. I had initially hardcoded my volume name length to 3 since I had initialized it as "NEW" and forgotten to update the record offsets at the end of the node while generalizing my code .... that was all:) So I got an error -127on my iMac ..... whatever that may mean... btw does anyone know where to find a listing of all these errors? ... that would probably make things a whole lot easier - at least one would know where to search for the possible source of the error. I did a search on the web and on my iMac but came up with seemingly irrelevant stuff. Regards, Nandini Hengen

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997

1996

1995

hfs-user February 2002