| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you under the Apache License, Version 2.0 (the |
| // "License"); you may not use this file except in compliance |
| // with the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, |
| // software distributed under the License is distributed on an |
| // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| // KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations |
| // under the License. |
| |
| #ifndef DocFormats_DFDOM_h |
| #define DocFormats_DFDOM_h |
| |
| /** \file |
| |
| # DocFormats Document Object Model (DOM) |
| |
| This file defines data structures and functions for manipulating parsed XML data, represented in |
| memory as a tree. It is inspired by the Document Object Model (DOM) API commonly used for |
| processing XML data, but does not follow the API strictly. |
| |
| The two primary classes are DFDocument and DFNode. A DFDocument represents a parsed XML or HTML |
| document, and acts as a container for all of the nodes within the document. A DFNode object |
| represents either an element (represented textually as `<element-name> ... </element-name>`) or a |
| text node (containing literal text from the XML document, residing inside an element). |
| |
| Every DFDocument object has a root note, and every DFNode object has a doubly-linked list of |
| children. You can traverse the tree of nodes by using the first and next fields defined in the |
| DFNode struct, and determine the element or node type via the \ref tag field, and the textual |
| content (for text nodes) via the \value object. |
| |
| ## Tags |
| |
| Naming of XML elements and attributes is considerably complicated by the use of namespaces. |
| Conceptually, every element is identified by a (namespcae URI, local name) pair, which determines |
| its semantic meaning. However, these pairs are not directly specified in source files, as namespace |
| URIs can be quite long. Instead, the XML Namespace specification [1] specifies a mechanism to map |
| *prefixes* to namespace URIs, and elements in the textual representation are named based on a |
| (prefix, local name) combination. With this mechanism, a program reading an XML document must first |
| look up the prefix mapping to determine the namespace URI, before it can correctly identify an |
| element. Worse, the mapping between prefixes and namespace URI can differ between different parts |
| of the document. |
| |
| DocFormats uses an in-memory representation of XML elements in which the name is replaced by a |
| numeric *tag*. Each possible tag corresponds to a (namespace URI, local name) pair, which |
| simplifies checking the types of elements to a simple integer comparison, rather than a complicated |
| symbol resolution algorithm. Furthermore, these tags can optionally be declared as pre-defined |
| constants, as in \ref XMLNames.h, enabling them to be used in switch statements --- which improves |
| performance of code that has to check for many different element types. |
| |
| Each document has a \ref DFNameMap object which stores the information necessary to map between |
| numeric tags and (namespace URI, local name) pairs, and also stores the default prefix to be used |
| for ecah namespace URI. During parsing, as carried out DFParseXMLFile() and DFParseXMLString(), |
| symbol resolution based on the textual names given in the source file is performed, resulting in |
| the tags in the constructed tree corresponding to either pre-defined tags in the default name map, |
| or other tags whose numeric values have been dynamically allocated during parsing. During |
| serialisation, namespace mappings based on the default prefix for each namespace URI are set on the |
| root element of the output file, and tags are translated into (prefix:local name) combinations for |
| the actual start and end tags of elements. |
| |
| ## Memory allocation |
| |
| DFDocument objects are reference-counted, but the memory occupied by all DFNode objects is managed |
| by their containing documents. As you create new nodes, the document itself takes care of |
| allocating memory for them, and also keeping track of all the nodes it has allocated. When a |
| document is freed --- that is, when its reference count drops to zero --- all nodes allocated by |
| that document are also freed. |
| |
| This approach is for performance reasons. In an earlier version of the library, each DFNode object |
| was allocated separately, as a reference-counted Objective C object. This implied large overheads |
| both for incrementing and decrementing the reference count, and for traversing through the node |
| tree releasing all the references individually. The approach used now, implemented by DFAllocator, |
| makes only a few calls to `malloc` to allocate large chunks of memory, and then allocates portions |
| of those memory blocks itself for the DFNode objects. When a DFDocument object is freed, those |
| blocks are simply released in one go, without the need to individually inspect each node to check |
| its reference count. The same memory blocks are used to allocate strings for attribute values, |
| which also get freed along with the document. |
| |
| THe previous paragraph describes an implementation detail which you don't need to worry about |
| when using documents. Just call DFDocumentNew() or DFDocumentNewWithRoot() to create a document, |
| and DFDocumentRelease() when you are finished with it. All memory that has been allocated for |
| nodes, attribute values, and text node values will automatically be freed when the document's |
| reference count drops to zero, as it would after a simple new/release sequence. |
| |
| */ |
| |
| #include "DFXMLNamespaces.h" |
| #include "DFXMLNames.h" |
| #include <DocFormats/DFXMLForward.h> |
| #include "DFBuffer.h" |
| #include <stdarg.h> |
| |
| #define DOM_DOCUMENT 1 |
| #define DOM_TEXT 2 |
| #define DOM_COMMENT 3 |
| #define DOM_CDATA 4 |
| #define DOM_PROCESSING_INSTRUCTION 5 |
| |
| #define MIN_ELEMENT_TAG 10 |
| |
| typedef struct { |
| Tag tag; |
| char *value; |
| } DFAttribute; |
| |
| //////////////////////////////////////////////////////////////////////////////////////////////////// |
| // // |
| // DFNode // |
| // // |
| //////////////////////////////////////////////////////////////////////////////////////////////////// |
| |
| /** Documentation for DFNode */ |
| struct DFNode { |
| Tag tag; |
| DFNode *parent; |
| DFNode *first; |
| DFNode *last; |
| DFNode *next; |
| DFNode *prev; |
| unsigned int seqNo; |
| struct DFDocument *doc; |
| void *js; |
| int changed; |
| int childrenChanged; |
| DFNode *seqNoHashNext; |
| DFAttribute *attrs; |
| unsigned int attrsCount; |
| unsigned int attrsAlloc; |
| char *target; |
| char *value; |
| }; |
| |
| //////////////////////////////////////////////////////////////////////////////////////////////////// |
| // // |
| // DFDocument // |
| // // |
| //////////////////////////////////////////////////////////////////////////////////////////////////// |
| |
| #define SEQNO_HASH_SIZE 3571 |
| |
| /** |
| |
| The DFDocument class represents an XML or HTML document in memory which has either been parsed from |
| a file, or has been newly-created and is destined to be serialised to a file. |
| |
| */ |
| struct DFDocument { |
| size_t retainCount; |
| struct DFAllocator *allocator; |
| DFNode *seqNoHashBins[SEQNO_HASH_SIZE]; |
| struct DFHashTable *nodesByIdAttr; |
| DFNode **nodes; |
| size_t nodesCount; |
| size_t nodesAlloc; |
| |
| struct DFNameMap *map; |
| DFNode *docNode; |
| DFNode *root; |
| unsigned int nextSeqNo; |
| }; |
| |
| DFDocument *DFDocumentNew(void); |
| DFDocument *DFDocumentNewWithRoot(Tag rootTag); |
| DFDocument *DFDocumentRetain(DFDocument *doc); |
| void DFDocumentRelease(DFDocument *doc); |
| |
| void DFDocumentReassignSeqNos(DFDocument *doc); |
| |
| DFNode *DFNodeForSeqNo(DFDocument *doc, unsigned int seqNo); |
| DFNode *DFElementForIdAttr(DFDocument *doc, const char *idAttr); |
| |
| //////////////////////////////////////////////////////////////////////////////////////////////////// |
| // // |
| // DOM // |
| // // |
| //////////////////////////////////////////////////////////////////////////////////////////////////// |
| |
| // Strings |
| |
| char *DFCopyString(DFDocument *doc, const char *str); |
| |
| // Document methods |
| |
| DFNode *DFCreateElement(DFDocument *doc, Tag tag); |
| DFNode *DFCreateTextNode(DFDocument *doc, const char *data); |
| DFNode *DFCreateComment(DFDocument *doc, const char *data); |
| DFNode *DFCreateCDATASection(DFDocument *doc, char *data); |
| DFNode *DFCreateProcessingInstruction(DFDocument *doc, const char *target, const char *content); |
| |
| // Node methods |
| |
| void DFInsertBefore(DFNode *parent, DFNode *newChild, DFNode *refChild); |
| void DFAppendChild(DFNode *parent, DFNode *newChild); |
| DFNode *DFCreateChildElement(DFNode *parent, Tag tag); |
| DFNode *DFCreateChildTextNode(DFNode *parent, const char *data); |
| void DFRemoveNode(DFNode *node); |
| void DFRemoveNodeButKeepChildren(DFNode *node); |
| void DFSetNodeValue(DFNode *node, const char *value); |
| |
| // Element methods |
| |
| const char *DFGetAttribute(DFNode *node, Tag tag); |
| const char *DFGetChildAttribute(DFNode *parent, Tag childTag, Tag attrTag); |
| void DFSetAttribute(DFNode *element, Tag tag, const char *value); |
| void DFVFormatAttribute(DFNode *element, Tag tag, const char *format, va_list ap); |
| void DFFormatAttribute(DFNode *element, Tag tag, const char *format, ...) ATTRIBUTE_FORMAT(printf,3,4); |
| void DFRemoveAttribute(DFNode *element, Tag tag); |
| void DFRemoveAllAttributes(DFNode *element); |
| |
| // Tree traversal |
| |
| DFNode *DFPrevNode(DFNode *node); |
| DFNode *DFNextNodeAfter(DFNode *node); |
| DFNode *DFNextNode(DFNode *node); |
| |
| // Names |
| |
| Tag DFLookupTag(DFDocument *doc, const char *URI, const char *name); |
| const char *DFTagName(DFDocument *doc, Tag tag); |
| const char *DFTagURI(DFDocument *doc, Tag tag); |
| const char *DFNodeName(DFNode *node); |
| const char *DFNodeURI(DFNode *node); |
| |
| // Misc |
| |
| void DFNodeTextToBuffer(DFNode *node, DFBuffer *buf); |
| char *DFNodeTextToString(DFNode *node); |
| void DFStripIds(DFNode *node); |
| DFNode *DFChildWithTag(DFNode *parent, Tag tag); |
| void DFRemoveWhitespaceNodes(DFNode *node); |
| int DFIsWhitespaceNode(DFNode *node); |
| int identicalAttributesExcept(DFNode *first, DFNode *second, Tag except); |
| void DFStripWhitespace(DFNode *node); |
| |
| #endif |
