\subsection{\B\ Support}

  The purpose of this module is to manage the two major data
structures that exist on a Macintosh volume: the \C\ and the \E\
described in section \ref{description}. The module relies on functions to
read/write raw sectors from disk and exports functions to lookup,
insert and delete catalog and extents records from the B-Trees.

  The module is structured in two functional layers: a generic B-Tree
layer and a layer specialized in the \C\ and the \E. The only purpose
of the specialized layer is to translate the information between
on-disk catalog and extents records and in-memory structures.

  On a Macintosh volume all data is laid out unaligned in big endian
byte order.  On an MC68000 based machine turning the volume data
structures into useable C structures could be done by casting the raw
data from the disk to carefully chosen C structures or in the worst
case by a memory to memory copy operation.

  The machines we initially used to implement MacFS use little endian
byte order (MIPS R3000 and I486) and have precise alignment
requirements (MIPS R3000), so we have to copy and byte-swap all the
information when translating between disk structures and memory
structures. In addition, the specialized layer must translate between
Pascal strings (on the disk) and C strings.  These must be done on all
operations, including key comparison during tree traversals, which is
a significant overhead cost.

  The generic \B\ module is used to perform lookup, insertion and
deletion in a generic \B. The module is parameterized with a key
compare routine that is dependent on the type of tree acted upon.