2.4.1 Record Slot Offsets

Recursively calculating the slot span of a record would be an incredibly costly operation for deeply nested records, so we reduce this lookup to O(1) constant time by recomputing it each time a record slot is set. To eliminate an O(n) linear scan of the slots for record span recomputation, each slot has its offset cached; this also allows us to look up a slot in constant time.

These offsets are stored directly after the Record Header, before the slot values; this allows quick lookup and modification —modifying the record header involves reconstructing an element, which involves many more operations than swapping out items in a sequence.

For records, it is also important that we know the entire record span so that the end of the entire record in a sequence can be immediately known without consulting the final slot span, which involves looking up the last slot offset and then determining its span. This offset precedes the individual slot offsets.

The resulting construction is called a record sequence:

(<header>       as R:Record,
 <record span>  as xs:integer,
 <slot span>... as xs:integer*,
 <slot>...      as item()*)

function: item()+ R:init-slots (Record as element( R:Record ))

xmlns:R="http://mikegerwitz.com/hoxsl/record"

Produce a record sequence of Record initialized with N empty slots, where N is the slot count of Record.

Slots are initialized to R:empty-slot. The resulting sequence contains 2N + 2 items, with the first item being Record.

Definition:

<function name="R:init-slots"  as="item()+">
  <param name="Record"  as="element( R:Record )" />

  <variable name="n"  as="xs:integer"  select="R:slot-count( $Record )" />

  <variable name="offsets"  as="xs:integer*"  select="for $i in 1 to $n return $i" />
  <variable name="slots"  as="element( R:empty-slot )*"  select="for $i in 1 to $n return $R:empty-slot" />

  <sequence select="$Record, (2*$n + 2), $offsets, $slots" />
</function>

function: xs:boolean R:is-record-seq (seq as item()*)

xmlns:R="http://mikegerwitz.com/hoxsl/record"

Determine whether the given sequence seq is a valid record sequence.

This ensures that the a proper Record Header is present and that there are enough items in the sequence to satisfy all data requirements for that record (see record span). It does not, however, guarantee that the items in the sequence do actually belong to that record.

Definition:

<function name="R:is-record-seq"  as="xs:boolean">
  <param name="seq"  as="item()*" />

  <variable name="header"  as="item()?"  select="$seq[ 1 ]" />
  <variable name="slen"  as="xs:integer"  select="max( ( 2, R:record-span( $seq ) ) )" />

  <sequence select="$header and R:is-record( $header ) and count( $seq ) ge $slen" />
</function>

function: xs:integer? R:record-span (Rseq as item()+)

xmlns:R="http://mikegerwitz.com/hoxsl/record"

Determine the record span of the record sequence Rseq.

This function checks to ensure that the first item in the sequence is a Record Header, but it does not ensure that the provided sequence is a valid record sequence; to do so, use R:is-record-seq#1.

Definition:

<function name="R:record-span"  as="xs:integer?">
  <param name="Rseq"  as="item()+" />

  <variable name="header"  as="item()?"  select="$Rseq[ 1 ]" />
  <variable name="span"  as="item()?"  select="$Rseq[ 2 ]" />

  <sequence select="if ( R:is-record( $header ) and $span instance of xs:integer ) then $span else ()" />
</function>