6.1.6 Basic Layer



next up previous contents
Next: 6.1.7 Interface Layer Up: 6.1 PAI - The Previous: 6.1.5 Caching Layer

6.1.6 Basic Layer

     

This layer is the lowest to implement structured data nodes. Fig. 6.4 shows the general structure of such a basic layer node. The header word of the node determines its type and structure, i.e. the type and number of the generic and specific data slots. The former are common to each node type whereas the latter carry the actual data visible to upper layers. Thus the shaded fields in this figure are maintained and used by the basic layer. For the unshaded fields the basic layer just reserves space and provides access functions.

  
Figure 6.4: Implementation of a basic layer node

The possible data types of the specific slots as determined by the tag field of the header word are:

All these types correspond to the C language types of the same size. To connect nodes together into a list or to implement arrays like strings (consequently stored as character arrays), the flags in the header word are used. The possible values are any combination of the following definitions, responsible for determining the generic slots of the node:

With the basic layer a functional interface to a LISP-like information storage concept is implemented. The interface presents the notion of atoms (primitive data items like a number, character or string value) and constructor nodes (CONS nodes for list creation) to the upper layers, as described in [Wins89]. One significant difference to a LISP interpreter's memory structure is that every basic layer node is implicitly a CONS node providing a CDR pointer as one slot in the data slots and carrying an atomic data value, i.e. the CAR pointer is redundant and therefore removed. The actual CONS node is implemented as a basic layer node with the atomic data value being a CAR pointer.

It should be noted that in contrast to LISP storage concepts, all nodes of the basic layer (and hence the PIF Application Interface) are originally kept on a file and are just cached through the caching layer. This implies, that all reference pointers stored in a basic layer node are file offset pointers and thus do not point to memory locations. It is the caching layer's duty to resolve those references correctly.

To illustrate the different storage concepts, let us consider the simple PIF expression (ref P (valueList 1 2)).

  
Figure 6.5: Example of a LISP internal data structure

  
Figure 6.6: Example of a PIF binary file and basic layer data structure

This construct represents a reference to the first two points of a pointList P. Fig. 6.5 shows how this construct would be stored in the XLISP interpreter with separate CONS nodes. The corresponding PBF structure, as it is handled in the basic layer, is shown in Fig. 6.6. The CONS nodes are fused with the CAR data values, to compact the data structures and minimize data access time, which is crucial on slower external storage media. Furthermore, this concept retains the principle extension language storage structures on the data level.

  
Figure 6.7: Layout of a PIF physical file with multiple logical files

Using this concept of LISP-like information nodes the PLB is stored, whereas the PBF is built as a linked list of PLBs, shown in Fig. 6.7. Since this list is only searched when the file is opened, this is no performance drawback. The data area is shared by all PLBs in the PBF, but on write operations it is checked that no crosspointers into disjoint PLBs occur. To allow fast access to all symbols, these are stored in a hash table which is unique for each PLB so that there are no conflicts between different PLBs.



next up previous contents
Next: 6.1.7 Interface Layer Up: 6.1 PAI - The Previous: 6.1.5 Caching Layer



Martin Stiftinger
Tue Nov 29 19:41:50 MET 1994