12.9 Struct objects

A data structure is a variable–length block of memory referenced by machine words tagged as vectors; the first machine word of a structure is a reference to its structure type descriptor (STD), which is itself a data structure; the subsequent words, if any, are the fields of the structure. A block of memory is a data structure if and only if: a reference to it is tagged as vector and its first word is tagged as vector.

     |----------------|----------| reference to structure
       heap pointer    vector tag
     
     |----------------|----------| first word of structure
       heap pointer    vector tag    = reference to STD
                                     = reference to structure

The whole memory block layout of a struct with 5 fields is as follows:

     |-----|------|------|------|------|------|
       STD  field0 field1 field2 field3 field4

fields are indexed starting at zero.

The type descriptor of the type descriptors is the return value of base-rtd at the Scheme level and the structure referenced by the field base_rtd in the process control block (PCB). Such base type descriptor is built at Vicare's startup.

The graph of references for a structure and its type descriptor is as follows:

           STD ref
          |-------|---------------| structure instance
              |
       ---<---
      |
      |    RTD ref
       -->|-------|---------------| struct type descriptor
              |
       ---<---
      |
      |    STD ref
      +-->|-------|---------------| base struct type descriptor
      |       |
       ---<---

the struct type descriptor of the base struct type descriptor is the base type descriptor itself.

About R6RS records and their types:

• An R6RS record instance is a struct instance whose first word references its R6RS record type descriptor (RTD).
• An R6RS record type descriptor (RTD) is a struct instance of type <rtd>.
• An R6RS record constructor descriptor is a struct instance of type <rcd>.

The graph of references for an R6RS record and its type descriptor is as follows:

          RTD ref
         |-------|---------------| R6RS record instance
             |
      ---<---
     |
     |    STD ref
      -->|-------|---------------| R6RS record type descriptor
             |                      = struct instance of type <rtd>
      ---<---
     |
     |    STD ref
     +-->|-------|---------------| <rtd> struct type descriptor
             |
      ---<---
     |
     |    STD ref
     +-->|-------|---------------| base struct type descriptor
     |       |
      ---<---

A struct type descriptor (STD) is a fixed–length block of memory composed of 6 machine words interpreted as follows:

1. A reference to the base STD.
2. A fixnum representing the number of machine words in the structure minus 1; this is the number of fields in the structure excluding the reference to the STD. This value is 5 in the base STD.
3. Scheme symbol representing the name of this structure type.
4. Scheme list of symbols representing the names of fields in structures of this type.
5. False or a reference to closure used to print to a Scheme port the structures of this type. This is the printer function.
6. Scheme symbol used as unique identifier for this type.

Type descriptors are best defined at the Scheme level using the functions from the (vicare) library, iklib structs for details. To instantiate a structure at the C language level we should write a C function accepting the type descriptor as argument, and have the Scheme code hand the descriptor to it. For example, at the Scheme level we do:

     (define-struct timeval
       (tv_sec tv_usec))
     
     (define (gettimeofday)
       (foreign-call "ikrt_posix_gettimeofday"
                     (type-descriptor timeval)))

and at the C level we do:

     ikptr
     ikrt_posix_gettimeofday (ikptr s_rtd, ikpcb * pcb)
     {
       /* build and return an instance of "timeval" */
     }

Basic operations

Data structure objects are allocated on the heap; to perform the allocation we compute the whole size of the structure:

     ikpcb * pcb        = ik_the_pcb();
     long    num_of_fields = ...;
     long    block_size = disp_record_data +
                          wordsize * num_of_fields;
     long    align_size = IK_ALIGN(block_size);
     ikptr   s_stru     = ik_safe_alloc(pcb, align_size) | record_tag;

ik_safe_alloc() returns an ikptr value representing the aligned pointer, having the 3 least significant bits set to zero; we add to it the record tag (an integer value fitting in 3 bits) which allows to recognise records among all the other built in objects.

We have to explicitly store a reference to the RTD in the first machine word of the structure, so a full allocation looks like this:

     ikptr
     ika_struct_alloc (ikpcb * pcb, ikptr s_rtd)
     {
       long	num_of_fields;
       long  align_size;
       ikptr s_stru;
       num_of_fields = IK_UNFIX(IK_REF(s_rtd, off_rtd_length));
       align_size = IK_ALIGN(disp_record_data +
                             num_of_fields * wordsize);
       pcb->root9 = &s_rtd;
       {
         s_ stru = ik_safe_alloc(pcb, align_size) | record_tag;
       }
       pcb->root9 = NULL;
       IK_REF(s_stru, off_record_rtd) = s_rtd;
       return s_stru;
     }

The allocation operation described above leaves the data area uninitialised: its content is undefined. This is bad if the garbage collector moves the newly built record before the elements are initialised to a correct Scheme value.

To recognise an ikptr value as reference to a structure we do:

     ikptr   R = the_value;
     
     if ((record_tag == (record_mask & R)) &&
         (record_tag == (record_mask & IK_REF(R, off_record_rtd))))
       it_is_a_structure();
     else
       it_is_not();

structure fields are identified at the C level by a zero–based index; to store a value in field 2 of a structure we do:

     ikptr  s_stru  = the_structure;
     ikptr  s_field = the_field;
     
     IK_REF(s_stru, off_record_data + 2 * wordsize) = the_field;

and to retrieve a the value of field 2 we do:

     ikptr  s_stru  = the_structure;
     ikptr  s_field;
     
     s_field = IK_REF(s_stru, off_record_data + 2 * wordsize);

Convenience preprocessor macros

Operations on vectors