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
Biswaroop,
You'll probably have to come up with an algorithm yourself - based on the general structure of a B* tree as described in the specs. There's no such thing as 'the algorithm'. I'm sure all the HFS-implementations on the web generate relatively different images using different approaches (though based on the same underlying principle).
Once you've read thru' the specs and understood how a B* tree has to be built you'll be in a position to come up with some idea as to how to build it (based on your particular requirements).
Regards, Nandini Hengen ----- Original Message ----- From: Biswaroop Banerjee To: hfs-user@lists.mars.org Sent: Thursday, February 07, 2002 11:04 AM Subject: [hfs-user] Algorithm of B* tree Implementation
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
Having said that, in the Technote covering HFS+ they refer to a book called Algorithms in C (Addison Wesley), which they say explains B-Trees. I've not seen it, but I intend to look at it when I can. Check out the Tech Note if you're interested.
Simon
On Thu, 7 Feb 2002, Entwicklung wrote:
Biswaroop,
You'll probably have to come up with an algorithm yourself - based on the general structure of a B* tree as described in the specs. There's no such thing as 'the algorithm'. I'm sure all the HFS-implementations on the web generate relatively different images using different approaches (though based on the same underlying principle).
Once you've read thru' the specs and understood how a B* tree has to be built you'll be in a position to come up with some idea as to how to build it (based on your particular requirements).
Regards, Nandini Hengen ----- Original Message ----- From: Biswaroop Banerjee To: hfs-user@lists.mars.org Sent: Thursday, February 07, 2002 11:04 AM Subject: [hfs-user] Algorithm of B* tree Implementation
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
"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
Sir,
I thank you for giving me a good pointer to start my adventure. I am already going through the B* tree information and start gathering information from your named sources too. I came to know that you are in Apple. I want to give you a more clear picture of my plans.
Aim of the Project : To create a Hybrid CD image which can be afterwards written to a Blank CD/DVD to make a Hybrid CD/DVD.
Platforms : The Image file is generated on Windows9x and Windows2000,WinXP and WIN NT4.0
Brief Operational View : The end user will select a list of files from a Windows formatted volume . This is taken care by the Front End (Visual C++).
According to the Filesystem specs for HFS and ISO9660 the filenames of the selected files will be checked.
A file will be opened to write the Image. Upto the first 16 sectors(1sector = 2048 bytes) the file will contain HFS specific data structures namely 1. HFS volume recognizition sequence in the first 512 bytes of the file. 2. Volume Bitmap . 3. Catlog File 4. Extents Overflow file.
The space requirements for the above data structures can be found out beforehand since we will be targetting Disc at once writng method and we already know which files to be written to the HFS volume.
In the 16 th sector the Primary Volume descriptors for ISO9660 will be written and then the data for ISO9660 filesystem and then the data corresponding to the HFS volume will be dumped.
This implementation overview is my understanding and I would request you all for and Comments and Suggestions .
I have the source code for mkhybrid for guidance. I want to have suggestion on that too. Is it similar too the ' Darwin' code.
Waitng for your suggestions and inputs eagerly. regards Biswaroop
----- Original Message ----- From: Patrick Dirks To: hfs-user@lists.mars.org Cc: Biswaroop Banerjee Sent: Friday, February 08, 2002 12:26 AM 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
There is a toolset availiable called HFS_UTILS which appears to create and manipulate HFS volumes. I've sofar been able to create and format a HFS volume, then mount it on my linux box, then create files and generalyl mess. I did this by creating a large file containing zero's then using HFS_Format (one of hfs_utils) to format it. The only downside to this is that you have to know the volume size in advance. If you have a rough idea for the volume size needed, I'd reccomend tryign this out. As an asside, I've successfully compiled HFS_UTILS under NT using Cygwin, and using the hfs utils tools, I've manipulated it, then copied it to linux and mounted it, so while not ideal I guess this will work on most OS's
Simon
On Fri, 8 Feb 2002, Biswaroop Banerjee wrote:
Sir,
I thank you for giving me a good pointer to start myadventure. I am already going through the B* tree information and start gathering information from your named sources too. I came to know that you are in Apple. I want to give you a more clear picture of my plans.
Aim of the Project : To create a Hybrid CD image which can be afterwards written to a Blank CD/DVD to make a Hybrid CD/DVD.
Platforms : The Image file is generated on Windows9x and Windows2000,WinXP and WIN NT4.0
Brief Operational View : The end user will select a list of files from a Windows formatted volume . This is taken care by the Front End (Visual C++).
According to the Filesystem specs for HFS and ISO9660 the filenames of the selected files will be checked.
A file will be opened to write the Image. Upto the first 16 sectors(1sector = 2048 bytes) the file will contain HFS specific data structures namely
HFS volume recognizition sequence in the first 512 bytes of the file.
Volume Bitmap .
Catlog File
Extents Overflow file.
The space requirements for the above data structures can be found out beforehand since we will be targetting Disc at once writng method and we alreadyknow which files to be written to the HFS volume.
In the 16 th sector the Primary Volume descriptors for ISO9660 will be written and then the data for ISO9660 filesystem and then the data corresponding to the HFS volume will be dumped.
This implementation overview is my understanding and I would request you all for and Comments and Suggestions .
I have the source code for mkhybrid for guidance. I want to have suggestion on that too. Is it similar too the ' Darwin' code.
Waitng for your suggestions and inputs eagerly. regards Biswaroop
----- Original Message ----- From: Patrick Dirks To: hfs-user@lists.mars.org Cc: Biswaroop Banerjee Sent: Friday, February 08, 2002 12:26 AM 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
The spec is in Macintosh Files, An implementation is in the linux HFS_FS code. I'm currently implementing a replacement that allows for bigger Nodes, as required by HFS+, but it'll be a while before its usable.
Simon
On Thu, 7 Feb 2002, 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
-
Biswaroop Banerjee -
Entwicklung -
Patrick Dirks -
Simon Bazley <sibaz＠sibaz.com>