NodeList Implementation Details

The NodeList interface provides the abstraction of a live ordered collection of nodes. A first way to implement the NodeList interface is to physically represent it as list of node handles. To make it live we would have to create a list of active NodeLists associated to the Document or to the DOMImplementation objects that own them. Then, any function which modifies in some way the tree structure has to update accordingly all the lists where the modified nodes appears. This implementation has the great advantage to be an actual list, so that scanning and searching can be performed quickly (in particular, with regard to the getElementsByTagName method). However, the bookkeeping required to maintain the lists is not feasible. The alternative way, which is that implemented in Gdome, tries to reduce the memory occupation by using a completely ``lazy'' structure. More specifically, when a NodeList is requested, we return a reference to the following structure:

typedef struct _Gdome_xml_NodeList Gdome_xml_NodeList;
struct _Gdome_xml_NodeList {
  GdomeNodeList super;
  int refcnt;
  GdomeNode *root;
  GdomeDOMString *tagName;
  GdomeDOMString *tagURI;
  GdomeAccessType accessType;
};

Among the interesting fields of this structure we have a reference to a GdomeNode structure called root pointing to the root of the subtree of concern (each NodeList is relative to a particular subtree, for efficiency reasons. In the worst case, root is the topmost document node, corresponding to the whole tree). tagName is a reference to a GdomeDOMString which is the local or qualified name to be matched; when this field is non-NULL, the list includes any element with the given name which is a descendant of the specified root element. On the other hand, when the field is NULL, the list only includes the children nodes of the root element. tagURI is a reference to a GdomeDOMString representing the namespace URI to be matched. As for the previous field, it can be NULL for lists which contains nodes regardless the namespace. Note in particular that no other structure aside Gdome_xml_NodeList is allocated: when the user calls methods of the NodeList interface we simply traverse the DOM tree starting from the root node, possibly applying the the filter represented by the tagName and tagURI, if specified. In a sense, this implementation of NodeList is much like a view on the DOM tree. Unfortunately, it is relatively complex to find some effective optimizations for this structure, due to its ``liveness'' property. This might induce us to introduce some non-standard interfaces for a more efficient retrieval of document nodes in a near future.