[Prev]

12.1 C Data Structures

From .sg a header (NN-data.h) is generated. This header contains structs that represent the data of the elements. Each element and attribute generates its own node. Even trivial nodes like strings have to be kept this way because the nodes form basis of remembering the ordering of data. This ordering is needed for exclusive XML canonicalization, and thus for signature verification. ((It's unfortunate that the XML standards do not make this any easier. Without order maintenance requirement, it would be possible to represent trivial child elements directly as struct fields. An approach that tried to do just this is available from CVS tag GEN_LALR (ca. 29.5.2006).))

Any missing data is represented by NULL pointer.

Any repeating data is kept as a linked list, in reverse order of being seen in the data stream. ((Reverse order is just an optimization - or an artifact of simply adding latest element to the head of the list. If this bothers you, it's easy enough to reverse the list afterwards. Linked list is simple and works well for data whose order does not matter much (we use separate pointer for remembering the canonicalization order) and where random access is not needed, or cardinality is low enough so that simple pointer chasing is efficient enough.))

Simple elements and all attributes are represented by simple string node (even if they are booleans or integers).

Example

Consider following XML 

  <ds:Signature>
     <ds:SignedInfo>
       <ds:CanonicalizationMethod
           Algorithm="http://w3.org/xml-exc-c14n#"/>
       <ds:SignatureMethod
           Algorithm="http://w3.org/xmldsig#rsa-sha1"/>
       <ds:Reference
           URI="#RrcrNwFIw6n">
         <ds:Transforms>
           <ds:Transform
               Algorithm="http://w3.org/xml-exc-c14n#"/>
           <ds:Transform
               Algorithm="http://w3.org/xmldsig#env-sig"/></>
         <ds:DigestMethod
             Algorithm="http://w3.org/xmldsig#sha1"/>
         <ds:DigestValue>lNIzVMrp8CwTE=</></></>
     <ds:SignatureValue>
       GeMp7LS...vnjn8=</></>

Decoding would produce the data structure in Fig-3. You should also look at c/zx-sa-data.h to see the structs involved in this example.


Fig-3: Typical data structure produced by decode.

There are two pointer systems at play here. The black solid arrows depict the logical structure of the XML document. For each child element there is a struct field that simply points to the child. If there are multiple occurrences of the child, as in sig->SignedInfo->Reference->Transforms->Transform, the children are kept in a linked list connected by gg.g.n (next) fields. ((This linked list may be in inverted order depending on the phase of the moon and position of the trams in Helsinki. Until implementation matures, its better not to depend on the ordering.))

The wide order structure, depicted by red dashed arrows, is maintained using gg.kids and gg.g.wo fields. For example sig->SignedInfo->Reference->Transforms keeps its kids, the zx_ds_Transform objects, in the original order hanging from the kids and linked with the wo field. As can be seen, the order kept with wo fields can be different than the one kept using n (next) fields. What's more, the kids list can contain dissimilar objects, witness sig->SignedInfo->Reference->gg.kids. The wire order representation is only captured when decoding the document and is mainly useful for correctly canonicalizing the document for signature verification. If you are building a data structure in your own program, you typically will not set the gg.kids and gg.g.wo fields.

In the diagram, the objects of type zx_str were collapsed to double quoted strings. Superfluous gg.kids, gg.g.wo, and gg.g.n fields were omitted: they exist in all structures, but are not shown when they are NULL. The NULL is depicted as zero (0). ((All this <tt>gg.g</tt> business is just C's way of referencing the fields of a common base type of element objects.))

[Prev | Next]