[hfs-user] Algorithm of B* tree Implementation

Patrick Dirks pwd@apple.com
Thu, 7 Feb 2002 20:56:47 -0800


--Apple-Mail-1-477269666
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=ISO-8859-1;
	format=flowed

Ah, yes - Mac OS X came after the format for HFS+ was laid down and=20
documented.  Fortunately we'd at least reserved 16 bytes for Mac OS X's=20=

UNIX-style permissions.  The 16 bytes are used to store user and group=20=

ids (4 bytes ea), permissions mode and flags (2 bytes each - look at=20
code for exact packing) and 4-byte dev_t for special nodes.

As Gordon says, nothing like the actual code to document the proper use.

You don't say what you're trying to accomplish.  Hope this helps.

-Pat Dirks.

On Thursday, February 7, 2002, at 07:30 PM, Gordon Beatty wrote:

> =A0=A0=A0 The technote number is 1150 but if you point your browser to
> =A0
> =A0=A0=A0=20
> =
http://developer.apple.com/techpubs/macos8/Files/FileManager/filemanager.
> html
> =A0
> the links to the original HFS spec in "Inside Macintosh" and the HFS+=20=

> spec in TechNote 1150 are listed there (although the way OS X uses and=20=

> interprets some of the fields in HFS+=A0does not seem=A0completely=20
> reflected in the TechNote).=A0 Also, the technote refers to Robert=20
> Sedgewick's book 'Algorithms in C - Parts 1-4' -- and similarly=20
> 'Algorithms in C++ - Parts 1-4' -- which should prove a fairly clear=20=

> reference for the purposes of understanding.=A0 The 'File Structures'=20=

> book (previous or current version) by Michael Folk could help in this=20=

> regard=A0as well.
> =A0
> =A0=A0=A0 At the end of the day though, a solid C implementation is =
certainly=20
> the best reference.
> =A0
> =A0
> =A0=A0=A0 Gord Beatty
> =A0
>
> -----Original Message-----
> From: hfs-user-admin@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@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=20=

> wrapped up in a series of design and implementation aspects. Read up =
on=20
> B*-Trees and you should have a good idea what the data structure's=20
> supposed to look like at any given time. Read "Inside Macintosh" and=20=

> you'll find a more detailed explanation of the exact details of the=20
> HFS/HFS+ B*-Tree structure. More helpful than "Inside Macintosh",=20
> perhaps, is the tech note that Apple's published on the subject - =
"must=20
> read" for anyone implementing a version of HFS/HFS+. I can't remember=20=

> the tech note number offhand but it's freely available through Apple's=20=

> web site - do a search there.
>
> Finally, note that the Darwin code, which Apple has open sourced,=20
> includes a complete "C" implementation of the B*-Tree code as part of =
a=20
> UNIX kernel. Sign up as a Darwin developer and check out a copy of the=20=

> sources. It's in the "xnu" project in the "hfs" directory inside the=20=

> "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,
> =A0
> =A0 Can anybody of you give me the algorithm of implementating a B* =
tree=20
> which is the prominent data structure in a HFS formatted volume.
> =A0
> Waiting=A0 for your help.
> =A0Regards
> Biswaroop Banerjee.
> =A0
> =A0
> The essence of Success lies in its Struggle
> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=20
> -Bisban=A0
>

--Apple-Mail-1-477269666
Content-Transfer-Encoding: quoted-printable
Content-Type: text/enriched;
	charset=ISO-8859-1

Ah, yes - Mac OS X came after the format for HFS+ was laid down and
documented.  Fortunately we'd at least reserved 16 bytes for Mac OS
X's UNIX-style permissions.  The 16 bytes are used to store user and
group ids (4 bytes ea), permissions mode and flags (2 bytes each -
look at code for exact packing) and 4-byte dev_t for special nodes.


As Gordon says, nothing like the actual code to document the proper
use.


You don't say what you're trying to accomplish.  Hope this helps.


-Pat Dirks.


On Thursday, February 7, 2002, at 07:30 PM, Gordon Beatty wrote:


=
<excerpt><fontfamily><param>Arial</param><color><param>0000,0000,FFFF</par=
am><smaller>=A0=A0=A0
The technote number is 1150 but if you point your browser =
to</smaller></color></fontfamily>

=A0

=
<fontfamily><param>Arial</param><color><param>0000,0000,FFFF</param><small=
er>=A0=A0=A0
=
</smaller></color><underline><color><param>1999,1999,FFFF</param><smaller>=
http://developer.apple.com/techpubs/macos8/Files/FileManager/filemanager.h=
tml</smaller></color></underline></fontfamily>

=A0

=
<fontfamily><param>Arial</param><color><param>0000,0000,FFFF</param><small=
er>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+=A0does not seem=A0completely
reflected in the TechNote).=A0 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.=A0 The 'File Structures'
book (previous or current version) by Michael Folk could help in this
regard=A0as well.</smaller></color></fontfamily>

=A0

=
<fontfamily><param>Arial</param><color><param>0000,0000,FFFF</param><small=
er>=A0=A0=A0
At the end of the day though, a solid C implementation is certainly
the best reference.</smaller></color></fontfamily>

=A0

=A0

=
<fontfamily><param>Arial</param><color><param>0000,0000,FFFF</param><small=
er>=A0=A0=A0
Gord Beatty</smaller></color></fontfamily>

=A0


<fontfamily><param>Tahoma</param><smaller>-----Original Message-----

<bold>From:</bold> hfs-user-admin@lists.mars.org
[mailto:hfs-user-admin@lists.mars.org]<bold>On Behalf Of
</bold>Patrick Dirks

<bold>Sent:</bold> Thursday, February 07, 2002 1:57 PM

<bold>To:</bold> hfs-user@lists.mars.org

<bold>Cc:</bold> Biswaroop Banerjee

<bold>Subject:</bold> Re: [hfs-user] Algorithm of B* tree
Implementation


</smaller></fontfamily>"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,

=A0

=A0 Can anybody of you give me the algorithm of implementating a B* tree
which is the prominent data structure in a HFS formatted volume.

=A0

Waiting=A0 for your help.

=A0Regards

Biswaroop Banerjee.

=A0

=A0

The essence of Success lies in its Struggle

=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0
-Bisban=A0


</excerpt>=

--Apple-Mail-1-477269666--