Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * This file is part of libdom.
  3.  * Licensed under the MIT License,
  4.  *                http://www.opensource.org/licenses/mit-license.php
  5.  * Copyright 2007 John-Mark Bell <jmb@netsurf-browser.org>
  6.  * Copyright 2009 Bo Yang <struggleyb.nku@gmail.com>
  7.  */
  8.  
  9. #include <assert.h>
  10. #include <stdlib.h>
  11.  
  12. #include <dom/core/node.h>
  13. #include <dom/core/document.h>
  14. #include <dom/core/nodelist.h>
  15. #include <dom/core/string.h>
  16.  
  17. #include "core/document.h"
  18. #include "core/node.h"
  19. #include "core/nodelist.h"
  20.  
  21. #include "utils/utils.h"
  22.  
  23. /**
  24.  * DOM node list
  25.  */
  26. struct dom_nodelist {
  27.         dom_document *owner;    /**< Owning document */
  28.  
  29.         dom_node_internal *root;       
  30.                         /**< Root of applicable subtree */
  31.  
  32.         nodelist_type type;     /**< Type of this list */
  33.  
  34.         union {
  35.                 struct {
  36.                         dom_string *name;
  37.                                         /**< Tag name to match */
  38.                         bool any_name;          /**< The name is '*' */
  39.                 } n;
  40.                 struct {
  41.                         bool any_namespace;     /**< The namespace is '*' */
  42.                         bool any_localname;     /**< The localname is '*' */
  43.                         dom_string *namespace;  /**< Namespace */
  44.                         dom_string *localname;  /**< Localname */
  45.                 } ns;                   /**< Data for namespace matching */
  46.         } data;
  47.  
  48.         uint32_t refcnt;                /**< Reference count */
  49. };
  50.  
  51. /**
  52.  * Create a nodelist
  53.  *
  54.  * \param doc        Owning document
  55.  * \param type       The type of the NodeList
  56.  * \param root       Root node of subtree that list applies to
  57.  * \param tagname    Name of nodes in list (or NULL)
  58.  * \param namespace  Namespace part of nodes in list (or NULL)
  59.  * \param localname  Local part of nodes in list (or NULL)
  60.  * \param list       Pointer to location to receive list
  61.  * \return DOM_NO_ERR on success, DOM_NO_MEM_ERR on memory exhaustion
  62.  *
  63.  * ::root must be a node owned by ::doc
  64.  *
  65.  * The returned list will already be referenced, so the client need not
  66.  * do so explicitly. The client must unref the list once finished with it.
  67.  */
  68. dom_exception _dom_nodelist_create(dom_document *doc, nodelist_type type,
  69.                 dom_node_internal *root, dom_string *tagname,
  70.                 dom_string *namespace, dom_string *localname,
  71.                 dom_nodelist **list)
  72. {
  73.         dom_nodelist *l;
  74.  
  75.         l = malloc(sizeof(dom_nodelist));
  76.         if (l == NULL)
  77.                 return DOM_NO_MEM_ERR;
  78.  
  79.         dom_node_ref(doc);
  80.         l->owner = doc;
  81.  
  82.         dom_node_ref(root);
  83.         l->root = root;
  84.  
  85.         l->type = type;
  86.  
  87.         if (type == DOM_NODELIST_BY_NAME ||
  88.             type == DOM_NODELIST_BY_NAME_CASELESS) {
  89.                 assert(tagname != NULL);
  90.                 l->data.n.any_name = false;
  91.                 if (dom_string_byte_length(tagname) == 1) {
  92.                         const char *ch = dom_string_data(tagname);
  93.                         if (*ch == '*') {
  94.                                 l->data.n.any_name = true;
  95.                         }
  96.                 }
  97.        
  98.                 l->data.n.name = dom_string_ref(tagname);
  99.         } else if (type == DOM_NODELIST_BY_NAMESPACE ||
  100.                    type == DOM_NODELIST_BY_NAMESPACE_CASELESS) {
  101.                 l->data.ns.any_localname = false;
  102.                 l->data.ns.any_namespace = false;
  103.                 if (localname != NULL) {
  104.                         if (dom_string_byte_length(localname) == 1) {
  105.                                 const char *ch = dom_string_data(localname);
  106.                                 if (*ch == '*') {
  107.                                    l->data.ns.any_localname = true;
  108.                                 }
  109.                         }
  110.                         dom_string_ref(localname);
  111.                 }
  112.                 if (namespace != NULL) {
  113.                         if (dom_string_byte_length(namespace) == 1) {
  114.                                 const char *ch = dom_string_data(namespace);
  115.                                 if (*ch == '*') {
  116.                                         l->data.ns.any_namespace = true;
  117.                                 }
  118.                         }
  119.                         dom_string_ref(namespace);
  120.                 }
  121.  
  122.                 l->data.ns.namespace = namespace;
  123.                 l->data.ns.localname = localname;
  124.         }
  125.  
  126.         l->refcnt = 1;
  127.  
  128.         *list = l;
  129.  
  130.         return DOM_NO_ERR;
  131. }
  132.  
  133. /**
  134.  * Claim a reference on a DOM node list
  135.  *
  136.  * \param list  The list to claim a reference on
  137.  */
  138. void dom_nodelist_ref(dom_nodelist *list)
  139. {
  140.         assert(list != NULL);
  141.         list->refcnt++;
  142. }
  143.  
  144. /**
  145.  * Release a reference on a DOM node list
  146.  *
  147.  * \param list  The list to release the reference from
  148.  *
  149.  * If the reference count reaches zero, any memory claimed by the
  150.  * list will be released
  151.  */
  152. void dom_nodelist_unref(dom_nodelist *list)
  153. {
  154.         if (list == NULL)
  155.                 return;
  156.  
  157.         if (--list->refcnt == 0) {
  158.                 dom_node_internal *owner = (dom_node_internal *) list->owner;
  159.                 switch (list->type) {
  160.                 case DOM_NODELIST_CHILDREN:
  161.                         /* Nothing to do */
  162.                         break;
  163.                 case DOM_NODELIST_BY_NAMESPACE:
  164.                 case DOM_NODELIST_BY_NAMESPACE_CASELESS:
  165.                         if (list->data.ns.namespace != NULL)
  166.                                 dom_string_unref(list->data.ns.namespace);
  167.                         if (list->data.ns.localname != NULL)
  168.                                 dom_string_unref(list->data.ns.localname);
  169.                         break;
  170.                 case DOM_NODELIST_BY_NAME:
  171.                 case DOM_NODELIST_BY_NAME_CASELESS:
  172.                         assert(list->data.n.name != NULL);
  173.                         dom_string_unref(list->data.n.name);
  174.                         break;
  175.                 }
  176.  
  177.                 dom_node_unref(list->root);
  178.  
  179.                 /* Remove list from document */
  180.                 _dom_document_remove_nodelist(list->owner, list);
  181.  
  182.                 /* Destroy the list object */
  183.                 free(list);
  184.  
  185.                 /* And release our reference on the owning document
  186.                  * This must be last as, otherwise, it's possible that
  187.                  * the document is destroyed before we are */
  188.                 dom_node_unref(owner);
  189.         }
  190. }
  191.  
  192. /**
  193.  * Retrieve the length of a node list
  194.  *
  195.  * \param list    List to retrieve length of
  196.  * \param length  Pointer to location to receive length
  197.  * \return DOM_NO_ERR.
  198.  */
  199. dom_exception dom_nodelist_get_length(dom_nodelist *list, uint32_t *length)
  200. {
  201.         dom_node_internal *cur = list->root->first_child;
  202.         uint32_t len = 0;
  203.  
  204.         /* Traverse data structure */
  205.         while (cur != NULL) {
  206.                 /* Process current node */
  207.                 if (list->type == DOM_NODELIST_CHILDREN) {
  208.                         len++;
  209.                 } else if (list->type == DOM_NODELIST_BY_NAME) {
  210.                         if (list->data.n.any_name == true || (
  211.                                         cur->name != NULL &&
  212.                                         dom_string_isequal(cur->name,
  213.                                                 list->data.n.name))) {
  214.                                 if (cur->type == DOM_ELEMENT_NODE)
  215.                                         len++;
  216.                         }
  217.                 } else if (list->type == DOM_NODELIST_BY_NAME_CASELESS) {
  218.                         if (list->data.n.any_name == true || (
  219.                                         cur->name != NULL &&
  220.                                         dom_string_caseless_isequal(cur->name,
  221.                                                 list->data.n.name))) {
  222.                                 if (cur->type == DOM_ELEMENT_NODE)
  223.                                         len++;
  224.                         }
  225.                 } else if (list->type == DOM_NODELIST_BY_NAMESPACE) {
  226.                         if (list->data.ns.any_namespace == true ||
  227.                                         dom_string_isequal(cur->namespace,
  228.                                         list->data.ns.namespace)) {
  229.                                 if (list->data.ns.any_localname == true ||
  230.                                                 (cur->name != NULL &&
  231.                                                 dom_string_isequal(cur->name,
  232.                                                 list->data.ns.localname))) {
  233.                                         if (cur->type == DOM_ELEMENT_NODE)
  234.                                                 len++;
  235.                                 }
  236.                         }
  237.                 } else if (list->type == DOM_NODELIST_BY_NAMESPACE_CASELESS) {
  238.                         if (list->data.ns.any_namespace == true ||
  239.                                         dom_string_caseless_isequal(
  240.                                         cur->namespace,
  241.                                         list->data.ns.namespace)) {
  242.                                 if (list->data.ns.any_localname == true ||
  243.                                                 (cur->name != NULL &&
  244.                                                 dom_string_caseless_isequal(
  245.                                                 cur->name,
  246.                                                 list->data.ns.localname))) {
  247.                                         if (cur->type == DOM_ELEMENT_NODE)
  248.                                                 len++;
  249.                                 }
  250.                         }
  251.                 } else {
  252.                         assert("Unknown list type" == NULL);
  253.                 }
  254.  
  255.                 /* Now, find next node */
  256.                 if (list->type == DOM_NODELIST_CHILDREN) {
  257.                         /* Just interested in sibling list */
  258.                         cur = cur->next;
  259.                 } else {
  260.                         /* Want a full in-order tree traversal */
  261.                         if (cur->first_child != NULL) {
  262.                                 /* Has children */
  263.                                 cur = cur->first_child;
  264.                         } else if (cur->next != NULL) {
  265.                                 /* No children, but has siblings */
  266.                                 cur = cur->next;
  267.                         } else {
  268.                                 /* No children or siblings.
  269.                                  * Find first unvisited relation. */
  270.                                 dom_node_internal *parent = cur->parent;
  271.  
  272.                                 while (parent != list->root &&
  273.                                                 cur == parent->last_child) {
  274.                                         cur = parent;
  275.                                         parent = parent->parent;
  276.                                 }
  277.  
  278.                                 cur = cur->next;
  279.                         }
  280.                 }
  281.         }
  282.  
  283.         *length = len;
  284.  
  285.         return DOM_NO_ERR;
  286. }
  287.  
  288. /**
  289.  * Retrieve an item from a node list
  290.  *
  291.  * \param list   The list to retrieve the item from
  292.  * \param index  The list index to retrieve
  293.  * \param node   Pointer to location to receive item
  294.  * \return DOM_NO_ERR.
  295.  *
  296.  * ::index is a zero-based index into ::list.
  297.  * ::index lies in the range [0, length-1]
  298.  *
  299.  * The returned node will have had its reference count increased. The client
  300.  * should unref the node once it has finished with it.
  301.  */
  302. dom_exception _dom_nodelist_item(dom_nodelist *list,
  303.                 uint32_t index, dom_node **node)
  304. {
  305.         dom_node_internal *cur = list->root->first_child;
  306.         uint32_t count = 0;
  307.  
  308.         /* Traverse data structure */
  309.         while (cur != NULL) {
  310.                 /* Process current node */
  311.                 if (list->type == DOM_NODELIST_CHILDREN) {
  312.                         count++;
  313.                 } else if (list->type == DOM_NODELIST_BY_NAME) {
  314.                         if (list->data.n.any_name == true || (
  315.                                         cur->name != NULL &&
  316.                                         dom_string_isequal(cur->name,
  317.                                                 list->data.n.name))) {
  318.                                 if (cur->type == DOM_ELEMENT_NODE)
  319.                                         count++;
  320.                         }
  321.                 } else if (list->type == DOM_NODELIST_BY_NAME_CASELESS) {
  322.                         if (list->data.n.any_name == true || (
  323.                                         cur->name != NULL &&
  324.                                         dom_string_caseless_isequal(cur->name,
  325.                                                 list->data.n.name))) {
  326.                                 if (cur->type == DOM_ELEMENT_NODE)
  327.                                         count++;
  328.                         }
  329.                 } else if (list->type == DOM_NODELIST_BY_NAMESPACE) {
  330.                         if (list->data.ns.any_namespace == true ||
  331.                                         (cur->namespace != NULL &&
  332.                                         dom_string_isequal(cur->namespace,
  333.                                                 list->data.ns.namespace))) {
  334.                                 if (list->data.ns.any_localname == true ||
  335.                                                 (cur->name != NULL &&
  336.                                                 dom_string_isequal(cur->name,
  337.                                                 list->data.ns.localname))) {
  338.                                         if (cur->type == DOM_ELEMENT_NODE)
  339.                                                 count++;
  340.                                 }
  341.                         }
  342.                 } else if (list->type == DOM_NODELIST_BY_NAMESPACE_CASELESS) {
  343.                         if (list->data.ns.any_namespace == true ||
  344.                                         (cur->namespace != NULL &&
  345.                                         dom_string_caseless_isequal(
  346.                                                 cur->namespace,
  347.                                                 list->data.ns.namespace))) {
  348.                                 if (list->data.ns.any_localname == true ||
  349.                                                 (cur->name != NULL &&
  350.                                                 dom_string_caseless_isequal(
  351.                                                 cur->name,
  352.                                                 list->data.ns.localname))) {
  353.                                         if (cur->type == DOM_ELEMENT_NODE)
  354.                                                 count++;
  355.                                 }
  356.                         }
  357.                 } else {
  358.                         assert("Unknown list type" == NULL);
  359.                 }
  360.  
  361.                 /* Stop if this is the requested index */
  362.                 if ((index + 1) == count) {
  363.                         break;
  364.                 }
  365.  
  366.                 /* Now, find next node */
  367.                 if (list->type == DOM_NODELIST_CHILDREN) {
  368.                         /* Just interested in sibling list */
  369.                         cur = cur->next;
  370.                 } else {
  371.                         /* Want a full in-order tree traversal */
  372.                         if (cur->first_child != NULL) {
  373.                                 /* Has children */
  374.                                 cur = cur->first_child;
  375.                         } else if (cur->next != NULL) {
  376.                                 /* No children, but has siblings */
  377.                                 cur = cur->next;
  378.                         } else {
  379.                                 /* No children or siblings.
  380.                                  * Find first unvisited relation. */
  381.                                 dom_node_internal *parent = cur->parent;
  382.  
  383.                                 while (parent != list->root &&
  384.                                                 cur == parent->last_child) {
  385.                                         cur = parent;
  386.                                         parent = parent->parent;
  387.                                 }
  388.  
  389.                                 cur = cur->next;
  390.                         }
  391.                 }
  392.         }
  393.  
  394.         if (cur != NULL) {
  395.                 dom_node_ref(cur);
  396.         }
  397.         *node = (dom_node *) cur;
  398.  
  399.         return DOM_NO_ERR;
  400. }
  401.  
  402. /**
  403.  * Match a nodelist instance against a set of nodelist creation parameters
  404.  *
  405.  * \param list       List to match
  406.  * \param type       The type of the NodeList
  407.  * \param root       Root node of subtree that list applies to
  408.  * \param tagname    Name of nodes in list (or NULL)
  409.  * \param namespace  Namespace part of nodes in list (or NULL)
  410.  * \param localname  Local part of nodes in list (or NULL)
  411.  * \return true if list matches, false otherwise
  412.  */
  413. bool _dom_nodelist_match(dom_nodelist *list, nodelist_type type,
  414.                 dom_node_internal *root, dom_string *tagname,
  415.                 dom_string *namespace, dom_string *localname)
  416. {
  417.         if (list->root != root)
  418.                 return false;
  419.  
  420.         if (list->type != type)
  421.                 return false;
  422.        
  423.         switch (list->type) {
  424.         case DOM_NODELIST_CHILDREN:
  425.                 return true;
  426.         case DOM_NODELIST_BY_NAME:
  427.                 return dom_string_isequal(list->data.n.name, tagname);
  428.         case DOM_NODELIST_BY_NAMESPACE:
  429.                 return dom_string_isequal(list->data.ns.namespace, namespace) &&
  430.                         dom_string_isequal(list->data.ns.localname, localname);
  431.         case DOM_NODELIST_BY_NAME_CASELESS:
  432.                 return dom_string_caseless_isequal(list->data.n.name, tagname);
  433.         case DOM_NODELIST_BY_NAMESPACE_CASELESS:
  434.                 return dom_string_caseless_isequal(list->data.ns.namespace,
  435.                                                    namespace) &&
  436.                         dom_string_caseless_isequal(list->data.ns.localname,
  437.                                                     localname);
  438.         }
  439.        
  440.         return false;
  441. }
  442.  
  443. /**
  444.  * Test whether the two NodeList are equal
  445.  *
  446.  * \param l1  One list
  447.  * \param l2  The other list
  448.  * \reutrn true for equal, false otherwise.
  449.  */
  450. bool _dom_nodelist_equal(dom_nodelist *l1, dom_nodelist *l2)
  451. {
  452.         return _dom_nodelist_match(l1, l1->type, l2->root, l2->data.n.name,
  453.                         l2->data.ns.namespace, l2->data.ns.localname);
  454. }
  455.  
  456.