The technote number is 1150 but if
you point your browser to
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
"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