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@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 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
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:
The technote number is 1150 but if you point your browser to http://developer.apple.com/techpubs/macos8/Files/FileManager/filemanager. html 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@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 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
-
Gordon Beatty -
Patrick Dirks