tree.c

Go to the documentation of this file.

/*
 * tree.c : implementation of access function for an XML tree.
 *
 * References:
 *   XHTML 1.0 W3C REC: http://www.w3.org/TR/2002/REC-xhtml1-20020801/
 *
 * See Copyright for the status of this software.
 *
 * daniel@veillard.com
 *
 */
 
/* To avoid EBCDIC trouble when parsing on zOS */
#if defined(__MVS__)
#pragma convert("ISO8859-1")
#endif
 
#define IN_LIBXML
#include "libxml.h"
 
#include <string.h> /* for memset() only ! */
#include <stddef.h>
#include <limits.h>
#include <ctype.h>
#include <stdlib.h>
 
#ifdef LIBXML_ZLIB_ENABLED
#include <zlib.h>
#endif
 
#include <libxml/xmlmemory.h>
#include <libxml/tree.h>
#include <libxml/parser.h>
#include <libxml/uri.h>
#include <libxml/entities.h>
#include <libxml/valid.h>
#include <libxml/xmlerror.h>
#include <libxml/parserInternals.h>
#include <libxml/globals.h>
#ifdef LIBXML_HTML_ENABLED
#include <libxml/HTMLtree.h>
#endif
#ifdef LIBXML_DEBUG_ENABLED
#include <libxml/debugXML.h>
#endif
 
#include "buf.h"
#include "save.h"
 
int __xmlRegisterCallbacks = 0;
 
/************************************************************************
 *                                  *
 *      Forward declarations                    *
 *                                  *
 ************************************************************************/
 
static xmlNsPtr
xmlNewReconciledNs(xmlDocPtr doc, xmlNodePtr tree, xmlNsPtr ns);
 
static xmlChar* xmlGetPropNodeValueInternal(const xmlAttr *prop);
 
/************************************************************************
 *                                  *
 *      Tree memory error handler               *
 *                                  *
 ************************************************************************/
static void
xmlTreeErrMemory(const char *extra)
{
    __xmlSimpleError(XML_FROM_TREE, XML_ERR_NO_MEMORY, NULL, NULL, extra);
}
 
static void
xmlTreeErr(int code, xmlNodePtr node, const char *extra)
{
    const char *msg = NULL;
 
    switch(code) {
        case XML_TREE_INVALID_HEX:
        msg = "invalid hexadecimal character value\n";
        break;
    case XML_TREE_INVALID_DEC:
        msg = "invalid decimal character value\n";
        break;
    case XML_TREE_UNTERMINATED_ENTITY:
        msg = "unterminated entity reference %15s\n";
        break;
    case XML_TREE_NOT_UTF8:
        msg = "string is not in UTF-8\n";
        break;
    default:
        msg = "unexpected error number\n";
    }
    __xmlSimpleError(XML_FROM_TREE, code, node, msg, extra);
}
 
/************************************************************************
 *                                  *
 *      A few static variables and macros           *
 *                                  *
 ************************************************************************/
/* #undef xmlStringText */
const xmlChar xmlStringText[] = { 't', 'e', 'x', 't', 0 };
/* #undef xmlStringTextNoenc */
const xmlChar xmlStringTextNoenc[] =
              { 't', 'e', 'x', 't', 'n', 'o', 'e', 'n', 'c', 0 };
/* #undef xmlStringComment */
const xmlChar xmlStringComment[] = { 'c', 'o', 'm', 'm', 'e', 'n', 't', 0 };
 
static int xmlCompressMode = 0;
static int xmlCheckDTD = 1;
 
#define UPDATE_LAST_CHILD_AND_PARENT(n) if ((n) != NULL) {      \
    xmlNodePtr ulccur = (n)->children;                  \
    if (ulccur == NULL) {                       \
        (n)->last = NULL;                       \
    } else {                                \
        while (ulccur->next != NULL) {                  \
        ulccur->parent = (n);                   \
        ulccur = ulccur->next;                  \
    }                               \
    ulccur->parent = (n);                       \
    (n)->last = ulccur;                     \
}}
 
#define IS_STR_XML(str) ((str != NULL) && (str[0] == 'x') && \
  (str[1] == 'm') && (str[2] == 'l') && (str[3] == 0))
 
/* #define DEBUG_BUFFER */
/* #define DEBUG_TREE */
 
/************************************************************************
 *                                  *
 *      Functions to move to entities.c once the        *
 *      API freeze is smoothen and they can be made public. *
 *                                  *
 ************************************************************************/
#include <libxml/hash.h>
 
#ifdef LIBXML_TREE_ENABLED
static xmlEntityPtr
xmlGetEntityFromDtd(const xmlDtd *dtd, const xmlChar *name) {
    xmlEntitiesTablePtr table;
 
    if((dtd != NULL) && (dtd->entities != NULL)) {
    table = (xmlEntitiesTablePtr) dtd->entities;
    return((xmlEntityPtr) xmlHashLookup(table, name));
    /* return(xmlGetEntityFromTable(table, name)); */
    }
    return(NULL);
}
static xmlEntityPtr
xmlGetParameterEntityFromDtd(const xmlDtd *dtd, const xmlChar *name) {
    xmlEntitiesTablePtr table;
 
    if ((dtd != NULL) && (dtd->pentities != NULL)) {
    table = (xmlEntitiesTablePtr) dtd->pentities;
    return((xmlEntityPtr) xmlHashLookup(table, name));
    /* return(xmlGetEntityFromTable(table, name)); */
    }
    return(NULL);
}
#endif /* LIBXML_TREE_ENABLED */
 
/************************************************************************
 *                                  *
 *          QName handling helper               *
 *                                  *
 ************************************************************************/
 
xmlChar *
xmlBuildQName(const xmlChar *ncname, const xmlChar *prefix,
          xmlChar *memory, int len) {
    int lenn, lenp;
    xmlChar *ret;
 
    if (ncname == NULL) return(NULL);
    if (prefix == NULL) return((xmlChar *) ncname);
 
    lenn = strlen((char *) ncname);
    lenp = strlen((char *) prefix);
 
    if ((memory == NULL) || (len < lenn + lenp + 2)) {
    ret = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
    if (ret == NULL) {
        xmlTreeErrMemory("building QName");
        return(NULL);
    }
    } else {
    ret = memory;
    }
    memcpy(&ret[0], prefix, lenp);
    ret[lenp] = ':';
    memcpy(&ret[lenp + 1], ncname, lenn);
    ret[lenn + lenp + 1] = 0;
    return(ret);
}
 
xmlChar *
xmlSplitQName2(const xmlChar *name, xmlChar **prefix) {
    int len = 0;
    xmlChar *ret = NULL;
 
    if (prefix == NULL) return(NULL);
    *prefix = NULL;
    if (name == NULL) return(NULL);
 
#ifndef XML_XML_NAMESPACE
    /* xml: prefix is not really a namespace */
    if ((name[0] == 'x') && (name[1] == 'm') &&
        (name[2] == 'l') && (name[3] == ':'))
    return(NULL);
#endif
 
    /* nasty but valid */
    if (name[0] == ':')
    return(NULL);
 
    /*
     * we are not trying to validate but just to cut, and yes it will
     * work even if this is as set of UTF-8 encoded chars
     */
    while ((name[len] != 0) && (name[len] != ':'))
    len++;
 
    if (name[len] == 0)
    return(NULL);
 
    *prefix = xmlStrndup(name, len);
    if (*prefix == NULL) {
    xmlTreeErrMemory("QName split");
    return(NULL);
    }
    ret = xmlStrdup(&name[len + 1]);
    if (ret == NULL) {
    xmlTreeErrMemory("QName split");
    if (*prefix != NULL) {
        xmlFree(*prefix);
        *prefix = NULL;
    }
    return(NULL);
    }
 
    return(ret);
}
 
const xmlChar *
xmlSplitQName3(const xmlChar *name, int *len) {
    int l = 0;
 
    if (name == NULL) return(NULL);
    if (len == NULL) return(NULL);
 
    /* nasty but valid */
    if (name[0] == ':')
    return(NULL);
 
    /*
     * we are not trying to validate but just to cut, and yes it will
     * work even if this is as set of UTF-8 encoded chars
     */
    while ((name[l] != 0) && (name[l] != ':'))
    l++;
 
    if (name[l] == 0)
    return(NULL);
 
    *len = l;
 
    return(&name[l+1]);
}
 
/************************************************************************
 *                                  *
 *      Check Name, NCName and QName strings            *
 *                                  *
 ************************************************************************/
 
#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
 
#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_XPATH_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED) || defined(LIBXML_DEBUG_ENABLED) || defined (LIBXML_HTML_ENABLED) || defined(LIBXML_SAX1_ENABLED) || defined(LIBXML_HTML_ENABLED) || defined(LIBXML_WRITER_ENABLED) || defined(LIBXML_LEGACY_ENABLED)
int
xmlValidateNCName(const xmlChar *value, int space) {
    const xmlChar *cur = value;
    int c,l;
 
    if (value == NULL)
        return(-1);
 
    /*
     * First quick algorithm for ASCII range
     */
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (((*cur >= 'a') && (*cur <= 'z')) || ((*cur >= 'A') && (*cur <= 'Z')) ||
    (*cur == '_'))
    cur++;
    else
    goto try_complex;
    while (((*cur >= 'a') && (*cur <= 'z')) ||
       ((*cur >= 'A') && (*cur <= 'Z')) ||
       ((*cur >= '0') && (*cur <= '9')) ||
       (*cur == '_') || (*cur == '-') || (*cur == '.'))
    cur++;
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (*cur == 0)
    return(0);
 
try_complex:
    /*
     * Second check for chars outside the ASCII range
     */
    cur = value;
    c = CUR_SCHAR(cur, l);
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if ((!IS_LETTER(c)) && (c != '_'))
    return(1);
    cur += l;
    c = CUR_SCHAR(cur, l);
    while (IS_LETTER(c) || IS_DIGIT(c) || (c == '.') ||
       (c == '-') || (c == '_') || IS_COMBINING(c) ||
       IS_EXTENDER(c)) {
    cur += l;
    c = CUR_SCHAR(cur, l);
    }
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if (c != 0)
    return(1);
 
    return(0);
}
#endif
 
#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED)
int
xmlValidateQName(const xmlChar *value, int space) {
    const xmlChar *cur = value;
    int c,l;
 
    if (value == NULL)
        return(-1);
    /*
     * First quick algorithm for ASCII range
     */
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (((*cur >= 'a') && (*cur <= 'z')) || ((*cur >= 'A') && (*cur <= 'Z')) ||
    (*cur == '_'))
    cur++;
    else
    goto try_complex;
    while (((*cur >= 'a') && (*cur <= 'z')) ||
       ((*cur >= 'A') && (*cur <= 'Z')) ||
       ((*cur >= '0') && (*cur <= '9')) ||
       (*cur == '_') || (*cur == '-') || (*cur == '.'))
    cur++;
    if (*cur == ':') {
    cur++;
    if (((*cur >= 'a') && (*cur <= 'z')) ||
        ((*cur >= 'A') && (*cur <= 'Z')) ||
        (*cur == '_'))
        cur++;
    else
        goto try_complex;
    while (((*cur >= 'a') && (*cur <= 'z')) ||
           ((*cur >= 'A') && (*cur <= 'Z')) ||
           ((*cur >= '0') && (*cur <= '9')) ||
           (*cur == '_') || (*cur == '-') || (*cur == '.'))
        cur++;
    }
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (*cur == 0)
    return(0);
 
try_complex:
    /*
     * Second check for chars outside the ASCII range
     */
    cur = value;
    c = CUR_SCHAR(cur, l);
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if ((!IS_LETTER(c)) && (c != '_'))
    return(1);
    cur += l;
    c = CUR_SCHAR(cur, l);
    while (IS_LETTER(c) || IS_DIGIT(c) || (c == '.') ||
       (c == '-') || (c == '_') || IS_COMBINING(c) ||
       IS_EXTENDER(c)) {
    cur += l;
    c = CUR_SCHAR(cur, l);
    }
    if (c == ':') {
    cur += l;
    c = CUR_SCHAR(cur, l);
    if ((!IS_LETTER(c)) && (c != '_'))
        return(1);
    cur += l;
    c = CUR_SCHAR(cur, l);
    while (IS_LETTER(c) || IS_DIGIT(c) || (c == '.') ||
           (c == '-') || (c == '_') || IS_COMBINING(c) ||
           IS_EXTENDER(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if (c != 0)
    return(1);
    return(0);
}
 
int
xmlValidateName(const xmlChar *value, int space) {
    const xmlChar *cur = value;
    int c,l;
 
    if (value == NULL)
        return(-1);
    /*
     * First quick algorithm for ASCII range
     */
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (((*cur >= 'a') && (*cur <= 'z')) || ((*cur >= 'A') && (*cur <= 'Z')) ||
    (*cur == '_') || (*cur == ':'))
    cur++;
    else
    goto try_complex;
    while (((*cur >= 'a') && (*cur <= 'z')) ||
       ((*cur >= 'A') && (*cur <= 'Z')) ||
       ((*cur >= '0') && (*cur <= '9')) ||
       (*cur == '_') || (*cur == '-') || (*cur == '.') || (*cur == ':'))
    cur++;
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (*cur == 0)
    return(0);
 
try_complex:
    /*
     * Second check for chars outside the ASCII range
     */
    cur = value;
    c = CUR_SCHAR(cur, l);
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if ((!IS_LETTER(c)) && (c != '_') && (c != ':'))
    return(1);
    cur += l;
    c = CUR_SCHAR(cur, l);
    while (IS_LETTER(c) || IS_DIGIT(c) || (c == '.') || (c == ':') ||
       (c == '-') || (c == '_') || IS_COMBINING(c) || IS_EXTENDER(c)) {
    cur += l;
    c = CUR_SCHAR(cur, l);
    }
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if (c != 0)
    return(1);
    return(0);
}
 
int
xmlValidateNMToken(const xmlChar *value, int space) {
    const xmlChar *cur = value;
    int c,l;
 
    if (value == NULL)
        return(-1);
    /*
     * First quick algorithm for ASCII range
     */
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (((*cur >= 'a') && (*cur <= 'z')) ||
        ((*cur >= 'A') && (*cur <= 'Z')) ||
        ((*cur >= '0') && (*cur <= '9')) ||
        (*cur == '_') || (*cur == '-') || (*cur == '.') || (*cur == ':'))
    cur++;
    else
    goto try_complex;
    while (((*cur >= 'a') && (*cur <= 'z')) ||
       ((*cur >= 'A') && (*cur <= 'Z')) ||
       ((*cur >= '0') && (*cur <= '9')) ||
       (*cur == '_') || (*cur == '-') || (*cur == '.') || (*cur == ':'))
    cur++;
    if (space)
    while (IS_BLANK_CH(*cur)) cur++;
    if (*cur == 0)
    return(0);
 
try_complex:
    /*
     * Second check for chars outside the ASCII range
     */
    cur = value;
    c = CUR_SCHAR(cur, l);
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if (!(IS_LETTER(c) || IS_DIGIT(c) || (c == '.') || (c == ':') ||
        (c == '-') || (c == '_') || IS_COMBINING(c) || IS_EXTENDER(c)))
    return(1);
    cur += l;
    c = CUR_SCHAR(cur, l);
    while (IS_LETTER(c) || IS_DIGIT(c) || (c == '.') || (c == ':') ||
       (c == '-') || (c == '_') || IS_COMBINING(c) || IS_EXTENDER(c)) {
    cur += l;
    c = CUR_SCHAR(cur, l);
    }
    if (space) {
    while (IS_BLANK(c)) {
        cur += l;
        c = CUR_SCHAR(cur, l);
    }
    }
    if (c != 0)
    return(1);
    return(0);
}
#endif /* LIBXML_TREE_ENABLED */
 
/************************************************************************
 *                                  *
 *      Allocation and deallocation of basic structures     *
 *                                  *
 ************************************************************************/
 
void
xmlSetBufferAllocationScheme(xmlBufferAllocationScheme scheme) {
    if ((scheme == XML_BUFFER_ALLOC_EXACT) ||
        (scheme == XML_BUFFER_ALLOC_DOUBLEIT) ||
        (scheme == XML_BUFFER_ALLOC_HYBRID))
    xmlBufferAllocScheme = scheme;
}
 
xmlBufferAllocationScheme
xmlGetBufferAllocationScheme(void) {
    return(xmlBufferAllocScheme);
}
 
xmlNsPtr
xmlNewNs(xmlNodePtr node, const xmlChar *href, const xmlChar *prefix) {
    xmlNsPtr cur;
 
    if ((node != NULL) && (node->type != XML_ELEMENT_NODE))
    return(NULL);
 
    if ((prefix != NULL) && (xmlStrEqual(prefix, BAD_CAST "xml"))) {
        /* xml namespace is predefined, no need to add it */
        if (xmlStrEqual(href, XML_XML_NAMESPACE))
            return(NULL);
 
        /*
         * Problem, this is an attempt to bind xml prefix to a wrong
         * namespace, which breaks
         * Namespace constraint: Reserved Prefixes and Namespace Names
         * from XML namespace. But documents authors may not care in
         * their context so let's proceed.
         */
    }
 
    /*
     * Allocate a new Namespace and fill the fields.
     */
    cur = (xmlNsPtr) xmlMalloc(sizeof(xmlNs));
    if (cur == NULL) {
    xmlTreeErrMemory("building namespace");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNs));
    cur->type = XML_LOCAL_NAMESPACE;
 
    if (href != NULL)
    cur->href = xmlStrdup(href);
    if (prefix != NULL)
    cur->prefix = xmlStrdup(prefix);
 
    /*
     * Add it at the end to preserve parsing order ...
     * and checks for existing use of the prefix
     */
    if (node != NULL) {
    if (node->nsDef == NULL) {
        node->nsDef = cur;
    } else {
        xmlNsPtr prev = node->nsDef;
 
        if (((prev->prefix == NULL) && (cur->prefix == NULL)) ||
        (xmlStrEqual(prev->prefix, cur->prefix))) {
        xmlFreeNs(cur);
        return(NULL);
        }
        while (prev->next != NULL) {
            prev = prev->next;
        if (((prev->prefix == NULL) && (cur->prefix == NULL)) ||
            (xmlStrEqual(prev->prefix, cur->prefix))) {
            xmlFreeNs(cur);
            return(NULL);
        }
        }
        prev->next = cur;
    }
    }
    return(cur);
}
 
void
xmlSetNs(xmlNodePtr node, xmlNsPtr ns) {
    if (node == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlSetNs: node == NULL\n");
#endif
    return;
    }
    if ((node->type == XML_ELEMENT_NODE) ||
        (node->type == XML_ATTRIBUTE_NODE))
    node->ns = ns;
}
 
void
xmlFreeNs(xmlNsPtr cur) {
    if (cur == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlFreeNs : ns == NULL\n");
#endif
    return;
    }
    if (cur->href != NULL) xmlFree((char *) cur->href);
    if (cur->prefix != NULL) xmlFree((char *) cur->prefix);
    xmlFree(cur);
}
 
void
xmlFreeNsList(xmlNsPtr cur) {
    xmlNsPtr next;
    if (cur == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlFreeNsList : ns == NULL\n");
#endif
    return;
    }
    while (cur != NULL) {
        next = cur->next;
        xmlFreeNs(cur);
    cur = next;
    }
}
 
xmlDtdPtr
xmlNewDtd(xmlDocPtr doc, const xmlChar *name,
                    const xmlChar *ExternalID, const xmlChar *SystemID) {
    xmlDtdPtr cur;
 
    if ((doc != NULL) && (doc->extSubset != NULL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewDtd(%s): document %s already have a DTD %s\n",
        /* !!! */ (char *) name, doc->name,
        /* !!! */ (char *)doc->extSubset->name);
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new DTD and fill the fields.
     */
    cur = (xmlDtdPtr) xmlMalloc(sizeof(xmlDtd));
    if (cur == NULL) {
    xmlTreeErrMemory("building DTD");
    return(NULL);
    }
    memset(cur, 0 , sizeof(xmlDtd));
    cur->type = XML_DTD_NODE;
 
    if (name != NULL)
    cur->name = xmlStrdup(name);
    if (ExternalID != NULL)
    cur->ExternalID = xmlStrdup(ExternalID);
    if (SystemID != NULL)
    cur->SystemID = xmlStrdup(SystemID);
    if (doc != NULL)
    doc->extSubset = cur;
    cur->doc = doc;
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue((xmlNodePtr)cur);
    return(cur);
}
 
xmlDtdPtr
xmlGetIntSubset(const xmlDoc *doc) {
    xmlNodePtr cur;
 
    if (doc == NULL)
    return(NULL);
    cur = doc->children;
    while (cur != NULL) {
    if (cur->type == XML_DTD_NODE)
        return((xmlDtdPtr) cur);
    cur = cur->next;
    }
    return((xmlDtdPtr) doc->intSubset);
}
 
xmlDtdPtr
xmlCreateIntSubset(xmlDocPtr doc, const xmlChar *name,
                   const xmlChar *ExternalID, const xmlChar *SystemID) {
    xmlDtdPtr cur;
 
    if ((doc != NULL) && (xmlGetIntSubset(doc) != NULL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
 
     "xmlCreateIntSubset(): document %s already have an internal subset\n",
        doc->name);
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new DTD and fill the fields.
     */
    cur = (xmlDtdPtr) xmlMalloc(sizeof(xmlDtd));
    if (cur == NULL) {
    xmlTreeErrMemory("building internal subset");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlDtd));
    cur->type = XML_DTD_NODE;
 
    if (name != NULL) {
    cur->name = xmlStrdup(name);
    if (cur->name == NULL) {
        xmlTreeErrMemory("building internal subset");
        xmlFree(cur);
        return(NULL);
    }
    }
    if (ExternalID != NULL) {
    cur->ExternalID = xmlStrdup(ExternalID);
    if (cur->ExternalID  == NULL) {
        xmlTreeErrMemory("building internal subset");
        if (cur->name != NULL)
            xmlFree((char *)cur->name);
        xmlFree(cur);
        return(NULL);
    }
    }
    if (SystemID != NULL) {
    cur->SystemID = xmlStrdup(SystemID);
    if (cur->SystemID == NULL) {
        xmlTreeErrMemory("building internal subset");
        if (cur->name != NULL)
            xmlFree((char *)cur->name);
        if (cur->ExternalID != NULL)
            xmlFree((char *)cur->ExternalID);
        xmlFree(cur);
        return(NULL);
    }
    }
    if (doc != NULL) {
    doc->intSubset = cur;
    cur->parent = doc;
    cur->doc = doc;
    if (doc->children == NULL) {
        doc->children = (xmlNodePtr) cur;
        doc->last = (xmlNodePtr) cur;
    } else {
        if (doc->type == XML_HTML_DOCUMENT_NODE) {
        xmlNodePtr prev;
 
        prev = doc->children;
        prev->prev = (xmlNodePtr) cur;
        cur->next = prev;
        doc->children = (xmlNodePtr) cur;
        } else {
        xmlNodePtr next;
 
        next = doc->children;
        while ((next != NULL) && (next->type != XML_ELEMENT_NODE))
            next = next->next;
        if (next == NULL) {
            cur->prev = doc->last;
            cur->prev->next = (xmlNodePtr) cur;
            cur->next = NULL;
            doc->last = (xmlNodePtr) cur;
        } else {
            cur->next = next;
            cur->prev = next->prev;
            if (cur->prev == NULL)
            doc->children = (xmlNodePtr) cur;
            else
            cur->prev->next = (xmlNodePtr) cur;
            next->prev = (xmlNodePtr) cur;
        }
        }
    }
    }
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue((xmlNodePtr)cur);
    return(cur);
}
 
#define DICT_FREE(str)                      \
    if ((str) && ((!dict) ||                \
        (xmlDictOwns(dict, (const xmlChar *)(str)) == 0)))  \
        xmlFree((char *)(str));
 
 
#define DICT_COPY(str, cpy) \
    if (str) { \
    if (dict) { \
        if (xmlDictOwns(dict, (const xmlChar *)(str))) \
        cpy = (xmlChar *) (str); \
        else \
        cpy = (xmlChar *) xmlDictLookup((dict), (const xmlChar *)(str), -1); \
    } else \
        cpy = xmlStrdup((const xmlChar *)(str)); }
 
#define DICT_CONST_COPY(str, cpy) \
    if (str) { \
    if (dict) { \
        if (xmlDictOwns(dict, (const xmlChar *)(str))) \
        cpy = (const xmlChar *) (str); \
        else \
        cpy = xmlDictLookup((dict), (const xmlChar *)(str), -1); \
    } else \
        cpy = (const xmlChar *) xmlStrdup((const xmlChar *)(str)); }
 
 
void
xmlFreeDtd(xmlDtdPtr cur) {
    xmlDictPtr dict = NULL;
 
    if (cur == NULL) {
    return;
    }
    if (cur->doc != NULL) dict = cur->doc->dict;
 
    if ((__xmlRegisterCallbacks) && (xmlDeregisterNodeDefaultValue))
    xmlDeregisterNodeDefaultValue((xmlNodePtr)cur);
 
    if (cur->children != NULL) {
    xmlNodePtr next, c = cur->children;
 
    /*
     * Cleanup all nodes which are not part of the specific lists
     * of notations, elements, attributes and entities.
     */
        while (c != NULL) {
        next = c->next;
        if ((c->type != XML_NOTATION_NODE) &&
            (c->type != XML_ELEMENT_DECL) &&
        (c->type != XML_ATTRIBUTE_DECL) &&
        (c->type != XML_ENTITY_DECL)) {
        xmlUnlinkNode(c);
        xmlFreeNode(c);
        }
        c = next;
    }
    }
    DICT_FREE(cur->name)
    DICT_FREE(cur->SystemID)
    DICT_FREE(cur->ExternalID)
    /* TODO !!! */
    if (cur->notations != NULL)
        xmlFreeNotationTable((xmlNotationTablePtr) cur->notations);
 
    if (cur->elements != NULL)
        xmlFreeElementTable((xmlElementTablePtr) cur->elements);
    if (cur->attributes != NULL)
        xmlFreeAttributeTable((xmlAttributeTablePtr) cur->attributes);
    if (cur->entities != NULL)
        xmlFreeEntitiesTable((xmlEntitiesTablePtr) cur->entities);
    if (cur->pentities != NULL)
        xmlFreeEntitiesTable((xmlEntitiesTablePtr) cur->pentities);
 
    xmlFree(cur);
}
 
xmlDocPtr
xmlNewDoc(const xmlChar *version) {
    xmlDocPtr cur;
 
    if (version == NULL)
    version = (const xmlChar *) "1.0";
 
    /*
     * Allocate a new document and fill the fields.
     */
    cur = (xmlDocPtr) xmlMalloc(sizeof(xmlDoc));
    if (cur == NULL) {
    xmlTreeErrMemory("building doc");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlDoc));
    cur->type = XML_DOCUMENT_NODE;
 
    cur->version = xmlStrdup(version);
    if (cur->version == NULL) {
    xmlTreeErrMemory("building doc");
    xmlFree(cur);
    return(NULL);
    }
    cur->standalone = -1;
    cur->compression = -1; /* not initialized */
    cur->doc = cur;
    cur->parseFlags = 0;
    cur->properties = XML_DOC_USERBUILT;
    /*
     * The in memory encoding is always UTF8
     * This field will never change and would
     * be obsolete if not for binary compatibility.
     */
    cur->charset = XML_CHAR_ENCODING_UTF8;
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue((xmlNodePtr)cur);
    return(cur);
}
 
void
xmlFreeDoc(xmlDocPtr cur) {
    xmlDtdPtr extSubset, intSubset;
    xmlDictPtr dict = NULL;
 
    if (cur == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlFreeDoc : document == NULL\n");
#endif
    return;
    }
#ifdef LIBXML_DEBUG_RUNTIME
#ifdef LIBXML_DEBUG_ENABLED
    xmlDebugCheckDocument(stderr, cur);
#endif
#endif
 
    if (cur != NULL) dict = cur->dict;
 
    if ((__xmlRegisterCallbacks) && (xmlDeregisterNodeDefaultValue))
    xmlDeregisterNodeDefaultValue((xmlNodePtr)cur);
 
    /*
     * Do this before freeing the children list to avoid ID lookups
     */
    if (cur->ids != NULL) xmlFreeIDTable((xmlIDTablePtr) cur->ids);
    cur->ids = NULL;
    if (cur->refs != NULL) xmlFreeRefTable((xmlRefTablePtr) cur->refs);
    cur->refs = NULL;
    extSubset = cur->extSubset;
    intSubset = cur->intSubset;
    if (intSubset == extSubset)
    extSubset = NULL;
    if (extSubset != NULL) {
    xmlUnlinkNode((xmlNodePtr) cur->extSubset);
    cur->extSubset = NULL;
    xmlFreeDtd(extSubset);
    }
    if (intSubset != NULL) {
    xmlUnlinkNode((xmlNodePtr) cur->intSubset);
    cur->intSubset = NULL;
    xmlFreeDtd(intSubset);
    }
 
    if (cur->children != NULL) xmlFreeNodeList(cur->children);
    if (cur->oldNs != NULL) xmlFreeNsList(cur->oldNs);
 
    DICT_FREE(cur->version)
    DICT_FREE(cur->name)
    DICT_FREE(cur->encoding)
    DICT_FREE(cur->URL)
    xmlFree(cur);
    if (dict) xmlDictFree(dict);
}
 
xmlNodePtr
xmlStringLenGetNodeList(const xmlDoc *doc, const xmlChar *value, int len) {
    xmlNodePtr ret = NULL, last = NULL;
    xmlNodePtr node;
    xmlChar *val;
    const xmlChar *cur, *end;
    const xmlChar *q;
    xmlEntityPtr ent;
    xmlBufPtr buf;
 
    if (value == NULL) return(NULL);
    cur = value;
    end = cur + len;
 
    buf = xmlBufCreateSize(0);
    if (buf == NULL) return(NULL);
    xmlBufSetAllocationScheme(buf, XML_BUFFER_ALLOC_DOUBLEIT);
 
    q = cur;
    while ((cur < end) && (*cur != 0)) {
    if (cur[0] == '&') {
        int charval = 0;
        xmlChar tmp;
 
        /*
         * Save the current text.
         */
            if (cur != q) {
        if (xmlBufAdd(buf, q, cur - q))
            goto out;
        }
        q = cur;
        if ((cur + 2 < end) && (cur[1] == '#') && (cur[2] == 'x')) {
        cur += 3;
        if (cur < end)
            tmp = *cur;
        else
            tmp = 0;
        while (tmp != ';') { /* Non input consuming loop */
                    /*
                     * If you find an integer overflow here when fuzzing,
                     * the bug is probably elsewhere. This function should
                     * only receive entities that were already validated by
                     * the parser, typically by xmlParseAttValueComplex
                     * calling xmlStringDecodeEntities.
                     *
                     * So it's better *not* to check for overflow to
                     * potentially discover new bugs.
                     */
            if ((tmp >= '0') && (tmp <= '9'))
            charval = charval * 16 + (tmp - '0');
            else if ((tmp >= 'a') && (tmp <= 'f'))
            charval = charval * 16 + (tmp - 'a') + 10;
            else if ((tmp >= 'A') && (tmp <= 'F'))
            charval = charval * 16 + (tmp - 'A') + 10;
            else {
            xmlTreeErr(XML_TREE_INVALID_HEX, (xmlNodePtr) doc,
                       NULL);
            charval = 0;
            break;
            }
            cur++;
            if (cur < end)
            tmp = *cur;
            else
            tmp = 0;
        }
        if (tmp == ';')
            cur++;
        q = cur;
        } else if ((cur + 1 < end) && (cur[1] == '#')) {
        cur += 2;
        if (cur < end)
            tmp = *cur;
        else
            tmp = 0;
        while (tmp != ';') { /* Non input consuming loops */
                    /* Don't check for integer overflow, see above. */
            if ((tmp >= '0') && (tmp <= '9'))
            charval = charval * 10 + (tmp - '0');
            else {
            xmlTreeErr(XML_TREE_INVALID_DEC, (xmlNodePtr) doc,
                       NULL);
            charval = 0;
            break;
            }
            cur++;
            if (cur < end)
            tmp = *cur;
            else
            tmp = 0;
        }
        if (tmp == ';')
            cur++;
        q = cur;
        } else {
        /*
         * Read the entity string
         */
        cur++;
        q = cur;
        while ((cur < end) && (*cur != 0) && (*cur != ';')) cur++;
        if ((cur >= end) || (*cur == 0)) {
            xmlTreeErr(XML_TREE_UNTERMINATED_ENTITY, (xmlNodePtr) doc,
                       (const char *) q);
            goto out;
        }
        if (cur != q) {
            /*
             * Predefined entities don't generate nodes
             */
            val = xmlStrndup(q, cur - q);
            ent = xmlGetDocEntity(doc, val);
            if ((ent != NULL) &&
            (ent->etype == XML_INTERNAL_PREDEFINED_ENTITY)) {
 
            if (xmlBufCat(buf, ent->content))
                goto out;
 
            } else {
            /*
             * Flush buffer so far
             */
            if (!xmlBufIsEmpty(buf)) {
                node = xmlNewDocText(doc, NULL);
                if (node == NULL) {
                if (val != NULL) xmlFree(val);
                goto out;
                }
                node->content = xmlBufDetach(buf);
 
                if (last == NULL) {
                last = ret = node;
                } else {
                last = xmlAddNextSibling(last, node);
                }
            }
 
            /*
             * Create a new REFERENCE_REF node
             */
            node = xmlNewReference(doc, val);
            if (node == NULL) {
                if (val != NULL) xmlFree(val);
                goto out;
            }
            else if ((ent != NULL) && (ent->children == NULL)) {
                xmlNodePtr temp;
 
                            /* Set to non-NULL value to avoid recursion. */
                ent->children = (xmlNodePtr) -1;
                ent->children = xmlStringGetNodeList(doc,
                    (const xmlChar*)node->content);
                ent->owner = 1;
                temp = ent->children;
                while (temp) {
                temp->parent = (xmlNodePtr)ent;
                ent->last = temp;
                temp = temp->next;
                }
            }
            if (last == NULL) {
                last = ret = node;
            } else {
                last = xmlAddNextSibling(last, node);
            }
            }
            xmlFree(val);
        }
        cur++;
        q = cur;
        }
        if (charval != 0) {
        xmlChar buffer[10];
        int l;
 
        l = xmlCopyCharMultiByte(buffer, charval);
        buffer[l] = 0;
 
        if (xmlBufCat(buf, buffer))
            goto out;
        charval = 0;
        }
    } else
        cur++;
    }
 
    if (cur != q) {
        /*
     * Handle the last piece of text.
     */
    if (xmlBufAdd(buf, q, cur - q))
        goto out;
    }
 
    if (!xmlBufIsEmpty(buf)) {
    node = xmlNewDocText(doc, NULL);
    if (node == NULL) goto out;
    node->content = xmlBufDetach(buf);
 
    if (last == NULL) {
        ret = node;
    } else {
        xmlAddNextSibling(last, node);
    }
    } else if (ret == NULL) {
        ret = xmlNewDocText(doc, BAD_CAST "");
    }
 
out:
    xmlBufFree(buf);
    return(ret);
}
 
xmlNodePtr
xmlStringGetNodeList(const xmlDoc *doc, const xmlChar *value) {
    xmlNodePtr ret = NULL, last = NULL;
    xmlNodePtr node;
    xmlChar *val;
    const xmlChar *cur = value;
    const xmlChar *q;
    xmlEntityPtr ent;
    xmlBufPtr buf;
 
    if (value == NULL) return(NULL);
 
    buf = xmlBufCreateSize(0);
    if (buf == NULL) return(NULL);
    xmlBufSetAllocationScheme(buf, XML_BUFFER_ALLOC_DOUBLEIT);
 
    q = cur;
    while (*cur != 0) {
    if (cur[0] == '&') {
        int charval = 0;
        xmlChar tmp;
 
        /*
         * Save the current text.
         */
            if (cur != q) {
        if (xmlBufAdd(buf, q, cur - q))
            goto out;
        }
        q = cur;
        if ((cur[1] == '#') && (cur[2] == 'x')) {
        cur += 3;
        tmp = *cur;
        while (tmp != ';') { /* Non input consuming loop */
                    /* Don't check for integer overflow, see above. */
            if ((tmp >= '0') && (tmp <= '9'))
            charval = charval * 16 + (tmp - '0');
            else if ((tmp >= 'a') && (tmp <= 'f'))
            charval = charval * 16 + (tmp - 'a') + 10;
            else if ((tmp >= 'A') && (tmp <= 'F'))
            charval = charval * 16 + (tmp - 'A') + 10;
            else {
            xmlTreeErr(XML_TREE_INVALID_HEX, (xmlNodePtr) doc,
                       NULL);
            charval = 0;
            break;
            }
            cur++;
            tmp = *cur;
        }
        if (tmp == ';')
            cur++;
        q = cur;
        } else if  (cur[1] == '#') {
        cur += 2;
        tmp = *cur;
        while (tmp != ';') { /* Non input consuming loops */
                    /* Don't check for integer overflow, see above. */
            if ((tmp >= '0') && (tmp <= '9'))
            charval = charval * 10 + (tmp - '0');
            else {
            xmlTreeErr(XML_TREE_INVALID_DEC, (xmlNodePtr) doc,
                       NULL);
            charval = 0;
            break;
            }
            cur++;
            tmp = *cur;
        }
        if (tmp == ';')
            cur++;
        q = cur;
        } else {
        /*
         * Read the entity string
         */
        cur++;
        q = cur;
        while ((*cur != 0) && (*cur != ';')) cur++;
        if (*cur == 0) {
            xmlTreeErr(XML_TREE_UNTERMINATED_ENTITY,
                       (xmlNodePtr) doc, (const char *) q);
            goto out;
        }
        if (cur != q) {
            /*
             * Predefined entities don't generate nodes
             */
            val = xmlStrndup(q, cur - q);
            ent = xmlGetDocEntity(doc, val);
            if ((ent != NULL) &&
            (ent->etype == XML_INTERNAL_PREDEFINED_ENTITY)) {
 
            if (xmlBufCat(buf, ent->content))
                goto out;
 
            } else {
            /*
             * Flush buffer so far
             */
            if (!xmlBufIsEmpty(buf)) {
                node = xmlNewDocText(doc, NULL);
                if (node == NULL) {
                if (val != NULL) xmlFree(val);
                goto out;
                }
                node->content = xmlBufDetach(buf);
 
                if (last == NULL) {
                last = ret = node;
                } else {
                last = xmlAddNextSibling(last, node);
                }
            }
 
            /*
             * Create a new REFERENCE_REF node
             */
            node = xmlNewReference(doc, val);
            if (node == NULL) {
                if (val != NULL) xmlFree(val);
                goto out;
            }
            else if ((ent != NULL) && (ent->children == NULL)) {
                xmlNodePtr temp;
 
                            /* Set to non-NULL value to avoid recursion. */
                ent->children = (xmlNodePtr) -1;
                ent->children = xmlStringGetNodeList(doc,
                    (const xmlChar*)node->content);
                ent->owner = 1;
                temp = ent->children;
                while (temp) {
                temp->parent = (xmlNodePtr)ent;
                ent->last = temp;
                temp = temp->next;
                }
            }
            if (last == NULL) {
                last = ret = node;
            } else {
                last = xmlAddNextSibling(last, node);
            }
            }
            xmlFree(val);
        }
        cur++;
        q = cur;
        }
        if (charval != 0) {
        xmlChar buffer[10];
        int len;
 
        len = xmlCopyCharMultiByte(buffer, charval);
        buffer[len] = 0;
 
        if (xmlBufCat(buf, buffer))
            goto out;
        charval = 0;
        }
    } else
        cur++;
    }
    if ((cur != q) || (ret == NULL)) {
        /*
     * Handle the last piece of text.
     */
    xmlBufAdd(buf, q, cur - q);
    }
 
    if (!xmlBufIsEmpty(buf)) {
    node = xmlNewDocText(doc, NULL);
        if (node == NULL) {
            xmlBufFree(buf);
            return(NULL);
        }
    node->content = xmlBufDetach(buf);
 
    if (last == NULL) {
        ret = node;
    } else {
        xmlAddNextSibling(last, node);
    }
    }
 
out:
    xmlBufFree(buf);
    return(ret);
}
 
xmlChar *
xmlNodeListGetString(xmlDocPtr doc, const xmlNode *list, int inLine)
{
    const xmlNode *node = list;
    xmlChar *ret = NULL;
    xmlEntityPtr ent;
    int attr;
 
    if (list == NULL)
        return (NULL);
    if ((list->parent != NULL) && (list->parent->type == XML_ATTRIBUTE_NODE))
        attr = 1;
    else
        attr = 0;
 
    while (node != NULL) {
        if ((node->type == XML_TEXT_NODE) ||
            (node->type == XML_CDATA_SECTION_NODE)) {
            if (inLine) {
                ret = xmlStrcat(ret, node->content);
            } else {
                xmlChar *buffer;
 
        if (attr)
            buffer = xmlEncodeAttributeEntities(doc, node->content);
        else
            buffer = xmlEncodeEntitiesReentrant(doc, node->content);
                if (buffer != NULL) {
                    ret = xmlStrcat(ret, buffer);
                    xmlFree(buffer);
                }
            }
        } else if (node->type == XML_ENTITY_REF_NODE) {
            if (inLine) {
                ent = xmlGetDocEntity(doc, node->name);
                if (ent != NULL) {
                    xmlChar *buffer;
 
                    /* an entity content can be any "well balanced chunk",
                     * i.e. the result of the content [43] production:
                     * http://www.w3.org/TR/REC-xml#NT-content.
                     * So it can contain text, CDATA section or nested
                     * entity reference nodes (among others).
                     * -> we recursive  call xmlNodeListGetString()
                     * which handles these types */
                    buffer = xmlNodeListGetString(doc, ent->children, 1);
                    if (buffer != NULL) {
                        ret = xmlStrcat(ret, buffer);
                        xmlFree(buffer);
                    }
                } else {
                    ret = xmlStrcat(ret, node->content);
                }
            } else {
                xmlChar buf[2];
 
                buf[0] = '&';
                buf[1] = 0;
                ret = xmlStrncat(ret, buf, 1);
                ret = xmlStrcat(ret, node->name);
                buf[0] = ';';
                buf[1] = 0;
                ret = xmlStrncat(ret, buf, 1);
            }
        }
#if 0
        else {
            xmlGenericError(xmlGenericErrorContext,
                            "xmlGetNodeListString : invalid node type %d\n",
                            node->type);
        }
#endif
        node = node->next;
    }
    return (ret);
}
 
#ifdef LIBXML_TREE_ENABLED
xmlChar *
xmlNodeListGetRawString(const xmlDoc *doc, const xmlNode *list, int inLine)
{
    const xmlNode *node = list;
    xmlChar *ret = NULL;
    xmlEntityPtr ent;
 
    if (list == NULL)
        return (NULL);
 
    while (node != NULL) {
        if ((node->type == XML_TEXT_NODE) ||
            (node->type == XML_CDATA_SECTION_NODE)) {
            if (inLine) {
                ret = xmlStrcat(ret, node->content);
            } else {
                xmlChar *buffer;
 
                buffer = xmlEncodeSpecialChars(doc, node->content);
                if (buffer != NULL) {
                    ret = xmlStrcat(ret, buffer);
                    xmlFree(buffer);
                }
            }
        } else if (node->type == XML_ENTITY_REF_NODE) {
            if (inLine) {
                ent = xmlGetDocEntity(doc, node->name);
                if (ent != NULL) {
                    xmlChar *buffer;
 
                    /* an entity content can be any "well balanced chunk",
                     * i.e. the result of the content [43] production:
                     * http://www.w3.org/TR/REC-xml#NT-content.
                     * So it can contain text, CDATA section or nested
                     * entity reference nodes (among others).
                     * -> we recursive  call xmlNodeListGetRawString()
                     * which handles these types */
                    buffer =
                        xmlNodeListGetRawString(doc, ent->children, 1);
                    if (buffer != NULL) {
                        ret = xmlStrcat(ret, buffer);
                        xmlFree(buffer);
                    }
                } else {
                    ret = xmlStrcat(ret, node->content);
                }
            } else {
                xmlChar buf[2];
 
                buf[0] = '&';
                buf[1] = 0;
                ret = xmlStrncat(ret, buf, 1);
                ret = xmlStrcat(ret, node->name);
                buf[0] = ';';
                buf[1] = 0;
                ret = xmlStrncat(ret, buf, 1);
            }
        }
#if 0
        else {
            xmlGenericError(xmlGenericErrorContext,
                            "xmlGetNodeListString : invalid node type %d\n",
                            node->type);
        }
#endif
        node = node->next;
    }
    return (ret);
}
#endif /* LIBXML_TREE_ENABLED */
 
static xmlAttrPtr
xmlNewPropInternal(xmlNodePtr node, xmlNsPtr ns,
                   const xmlChar * name, const xmlChar * value,
                   int eatname)
{
    xmlAttrPtr cur;
    xmlDocPtr doc = NULL;
 
    if ((node != NULL) && (node->type != XML_ELEMENT_NODE)) {
        if ((eatname == 1) &&
        ((node->doc == NULL) ||
         (!(xmlDictOwns(node->doc->dict, name)))))
            xmlFree((xmlChar *) name);
        return (NULL);
    }
 
    /*
     * Allocate a new property and fill the fields.
     */
    cur = (xmlAttrPtr) xmlMalloc(sizeof(xmlAttr));
    if (cur == NULL) {
        if ((eatname == 1) &&
        ((node == NULL) || (node->doc == NULL) ||
         (!(xmlDictOwns(node->doc->dict, name)))))
            xmlFree((xmlChar *) name);
        xmlTreeErrMemory("building attribute");
        return (NULL);
    }
    memset(cur, 0, sizeof(xmlAttr));
    cur->type = XML_ATTRIBUTE_NODE;
 
    cur->parent = node;
    if (node != NULL) {
        doc = node->doc;
        cur->doc = doc;
    }
    cur->ns = ns;
 
    if (eatname == 0) {
        if ((doc != NULL) && (doc->dict != NULL))
            cur->name = (xmlChar *) xmlDictLookup(doc->dict, name, -1);
        else
            cur->name = xmlStrdup(name);
    } else
        cur->name = name;
 
    if (value != NULL) {
        xmlNodePtr tmp;
 
        cur->children = xmlNewDocText(doc, value);
        cur->last = NULL;
        tmp = cur->children;
        while (tmp != NULL) {
            tmp->parent = (xmlNodePtr) cur;
            if (tmp->next == NULL)
                cur->last = tmp;
            tmp = tmp->next;
        }
    }
 
    /*
     * Add it at the end to preserve parsing order ...
     */
    if (node != NULL) {
        if (node->properties == NULL) {
            node->properties = cur;
        } else {
            xmlAttrPtr prev = node->properties;
 
            while (prev->next != NULL)
                prev = prev->next;
            prev->next = cur;
            cur->prev = prev;
        }
    }
 
    if ((value != NULL) && (node != NULL) &&
        (xmlIsID(node->doc, node, cur) == 1))
        xmlAddID(NULL, node->doc, value, cur);
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
        xmlRegisterNodeDefaultValue((xmlNodePtr) cur);
    return (cur);
}
 
#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_HTML_ENABLED) || \
    defined(LIBXML_SCHEMAS_ENABLED)
xmlAttrPtr
xmlNewProp(xmlNodePtr node, const xmlChar *name, const xmlChar *value) {
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewProp : name == NULL\n");
#endif
    return(NULL);
    }
 
    return xmlNewPropInternal(node, NULL, name, value, 0);
}
#endif /* LIBXML_TREE_ENABLED */
 
xmlAttrPtr
xmlNewNsProp(xmlNodePtr node, xmlNsPtr ns, const xmlChar *name,
           const xmlChar *value) {
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewNsProp : name == NULL\n");
#endif
    return(NULL);
    }
 
    return xmlNewPropInternal(node, ns, name, value, 0);
}
 
xmlAttrPtr
xmlNewNsPropEatName(xmlNodePtr node, xmlNsPtr ns, xmlChar *name,
           const xmlChar *value) {
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewNsPropEatName : name == NULL\n");
#endif
    return(NULL);
    }
 
    return xmlNewPropInternal(node, ns, name, value, 1);
}
 
xmlAttrPtr
xmlNewDocProp(xmlDocPtr doc, const xmlChar *name, const xmlChar *value) {
    xmlAttrPtr cur;
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewDocProp : name == NULL\n");
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new property and fill the fields.
     */
    cur = (xmlAttrPtr) xmlMalloc(sizeof(xmlAttr));
    if (cur == NULL) {
    xmlTreeErrMemory("building attribute");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlAttr));
    cur->type = XML_ATTRIBUTE_NODE;
 
    if ((doc != NULL) && (doc->dict != NULL))
    cur->name = xmlDictLookup(doc->dict, name, -1);
    else
    cur->name = xmlStrdup(name);
    cur->doc = doc;
    if (value != NULL) {
    xmlNodePtr tmp;
 
    cur->children = xmlStringGetNodeList(doc, value);
    cur->last = NULL;
 
    tmp = cur->children;
    while (tmp != NULL) {
        tmp->parent = (xmlNodePtr) cur;
        if (tmp->next == NULL)
        cur->last = tmp;
        tmp = tmp->next;
    }
    }
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue((xmlNodePtr)cur);
    return(cur);
}
 
void
xmlFreePropList(xmlAttrPtr cur) {
    xmlAttrPtr next;
    if (cur == NULL) return;
    while (cur != NULL) {
        next = cur->next;
        xmlFreeProp(cur);
    cur = next;
    }
}
 
void
xmlFreeProp(xmlAttrPtr cur) {
    xmlDictPtr dict = NULL;
    if (cur == NULL) return;
 
    if (cur->doc != NULL) dict = cur->doc->dict;
 
    if ((__xmlRegisterCallbacks) && (xmlDeregisterNodeDefaultValue))
    xmlDeregisterNodeDefaultValue((xmlNodePtr)cur);
 
    /* Check for ID removal -> leading to invalid references ! */
    if ((cur->doc != NULL) && (cur->atype == XML_ATTRIBUTE_ID)) {
        xmlRemoveID(cur->doc, cur);
    }
    if (cur->children != NULL) xmlFreeNodeList(cur->children);
    DICT_FREE(cur->name)
    xmlFree(cur);
}
 
int
xmlRemoveProp(xmlAttrPtr cur) {
    xmlAttrPtr tmp;
    if (cur == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlRemoveProp : cur == NULL\n");
#endif
    return(-1);
    }
    if (cur->parent == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlRemoveProp : cur->parent == NULL\n");
#endif
    return(-1);
    }
    tmp = cur->parent->properties;
    if (tmp == cur) {
        cur->parent->properties = cur->next;
        if (cur->next != NULL)
            cur->next->prev = NULL;
    xmlFreeProp(cur);
    return(0);
    }
    while (tmp != NULL) {
    if (tmp->next == cur) {
        tmp->next = cur->next;
        if (tmp->next != NULL)
        tmp->next->prev = tmp;
        xmlFreeProp(cur);
        return(0);
    }
        tmp = tmp->next;
    }
#ifdef DEBUG_TREE
    xmlGenericError(xmlGenericErrorContext,
        "xmlRemoveProp : attribute not owned by its node\n");
#endif
    return(-1);
}
 
xmlNodePtr
xmlNewDocPI(xmlDocPtr doc, const xmlChar *name, const xmlChar *content) {
    xmlNodePtr cur;
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewPI : name == NULL\n");
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building PI");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_PI_NODE;
 
    if ((doc != NULL) && (doc->dict != NULL))
        cur->name = xmlDictLookup(doc->dict, name, -1);
    else
    cur->name = xmlStrdup(name);
    if (content != NULL) {
    cur->content = xmlStrdup(content);
    }
    cur->doc = doc;
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue((xmlNodePtr)cur);
    return(cur);
}
 
xmlNodePtr
xmlNewPI(const xmlChar *name, const xmlChar *content) {
    return(xmlNewDocPI(NULL, name, content));
}
 
xmlNodePtr
xmlNewNode(xmlNsPtr ns, const xmlChar *name) {
    xmlNodePtr cur;
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewNode : name == NULL\n");
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building node");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_ELEMENT_NODE;
 
    cur->name = xmlStrdup(name);
    cur->ns = ns;
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
 
xmlNodePtr
xmlNewNodeEatName(xmlNsPtr ns, xmlChar *name) {
    xmlNodePtr cur;
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewNode : name == NULL\n");
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building node");
    /* we can't check here that name comes from the doc dictionary */
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_ELEMENT_NODE;
 
    cur->name = name;
    cur->ns = ns;
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue((xmlNodePtr)cur);
    return(cur);
}
 
xmlNodePtr
xmlNewDocNode(xmlDocPtr doc, xmlNsPtr ns,
              const xmlChar *name, const xmlChar *content) {
    xmlNodePtr cur;
 
    if ((doc != NULL) && (doc->dict != NULL))
        cur = xmlNewNodeEatName(ns, (xmlChar *)
                            xmlDictLookup(doc->dict, name, -1));
    else
    cur = xmlNewNode(ns, name);
    if (cur != NULL) {
        cur->doc = doc;
    if (content != NULL) {
        cur->children = xmlStringGetNodeList(doc, content);
        UPDATE_LAST_CHILD_AND_PARENT(cur)
    }
    }
 
    return(cur);
}
 
xmlNodePtr
xmlNewDocNodeEatName(xmlDocPtr doc, xmlNsPtr ns,
              xmlChar *name, const xmlChar *content) {
    xmlNodePtr cur;
 
    cur = xmlNewNodeEatName(ns, name);
    if (cur != NULL) {
        cur->doc = doc;
    if (content != NULL) {
        cur->children = xmlStringGetNodeList(doc, content);
        UPDATE_LAST_CHILD_AND_PARENT(cur)
    }
    } else {
        /* if name don't come from the doc dictionary free it here */
        if ((name != NULL) && (doc != NULL) &&
        (!(xmlDictOwns(doc->dict, name))))
        xmlFree(name);
    }
    return(cur);
}
 
#ifdef LIBXML_TREE_ENABLED
xmlNodePtr
xmlNewDocRawNode(xmlDocPtr doc, xmlNsPtr ns,
                 const xmlChar *name, const xmlChar *content) {
    xmlNodePtr cur;
 
    cur = xmlNewDocNode(doc, ns, name, NULL);
    if (cur != NULL) {
        cur->doc = doc;
    if (content != NULL) {
        cur->children = xmlNewDocText(doc, content);
        UPDATE_LAST_CHILD_AND_PARENT(cur)
    }
    }
    return(cur);
}
 
xmlNodePtr
xmlNewDocFragment(xmlDocPtr doc) {
    xmlNodePtr cur;
 
    /*
     * Allocate a new DocumentFragment node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building fragment");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_DOCUMENT_FRAG_NODE;
 
    cur->doc = doc;
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
#endif /* LIBXML_TREE_ENABLED */
 
xmlNodePtr
xmlNewText(const xmlChar *content) {
    xmlNodePtr cur;
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building text");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_TEXT_NODE;
 
    cur->name = xmlStringText;
    if (content != NULL) {
    cur->content = xmlStrdup(content);
    }
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
 
#ifdef LIBXML_TREE_ENABLED
xmlNodePtr
xmlNewTextChild(xmlNodePtr parent, xmlNsPtr ns,
            const xmlChar *name, const xmlChar *content) {
    xmlNodePtr cur, prev;
 
    if (parent == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewTextChild : parent == NULL\n");
#endif
    return(NULL);
    }
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewTextChild : name == NULL\n");
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new node
     */
    if (parent->type == XML_ELEMENT_NODE) {
    if (ns == NULL)
        cur = xmlNewDocRawNode(parent->doc, parent->ns, name, content);
    else
        cur = xmlNewDocRawNode(parent->doc, ns, name, content);
    } else if ((parent->type == XML_DOCUMENT_NODE) ||
           (parent->type == XML_HTML_DOCUMENT_NODE)) {
    if (ns == NULL)
        cur = xmlNewDocRawNode((xmlDocPtr) parent, NULL, name, content);
    else
        cur = xmlNewDocRawNode((xmlDocPtr) parent, ns, name, content);
    } else if (parent->type == XML_DOCUMENT_FRAG_NODE) {
        cur = xmlNewDocRawNode( parent->doc, ns, name, content);
    } else {
    return(NULL);
    }
    if (cur == NULL) return(NULL);
 
    /*
     * add the new element at the end of the children list.
     */
    cur->type = XML_ELEMENT_NODE;
    cur->parent = parent;
    cur->doc = parent->doc;
    if (parent->children == NULL) {
        parent->children = cur;
    parent->last = cur;
    } else {
        prev = parent->last;
    prev->next = cur;
    cur->prev = prev;
    parent->last = cur;
    }
 
    return(cur);
}
#endif /* LIBXML_TREE_ENABLED */
 
xmlNodePtr
xmlNewCharRef(xmlDocPtr doc, const xmlChar *name) {
    xmlNodePtr cur;
 
    if (name == NULL)
        return(NULL);
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building character reference");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_ENTITY_REF_NODE;
 
    cur->doc = doc;
    if (name[0] == '&') {
        int len;
        name++;
    len = xmlStrlen(name);
    if (name[len - 1] == ';')
        cur->name = xmlStrndup(name, len - 1);
    else
        cur->name = xmlStrndup(name, len);
    } else
    cur->name = xmlStrdup(name);
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
 
xmlNodePtr
xmlNewReference(const xmlDoc *doc, const xmlChar *name) {
    xmlNodePtr cur;
    xmlEntityPtr ent;
 
    if (name == NULL)
        return(NULL);
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building reference");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_ENTITY_REF_NODE;
 
    cur->doc = (xmlDoc *)doc;
    if (name[0] == '&') {
        int len;
        name++;
    len = xmlStrlen(name);
    if (name[len - 1] == ';')
        cur->name = xmlStrndup(name, len - 1);
    else
        cur->name = xmlStrndup(name, len);
    } else
    cur->name = xmlStrdup(name);
 
    ent = xmlGetDocEntity(doc, cur->name);
    if (ent != NULL) {
    cur->content = ent->content;
    /*
     * The parent pointer in entity is a DTD pointer and thus is NOT
     * updated.  Not sure if this is 100% correct.
     *  -George
     */
    cur->children = (xmlNodePtr) ent;
    cur->last = (xmlNodePtr) ent;
    }
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
 
xmlNodePtr
xmlNewDocText(const xmlDoc *doc, const xmlChar *content) {
    xmlNodePtr cur;
 
    cur = xmlNewText(content);
    if (cur != NULL) cur->doc = (xmlDoc *)doc;
    return(cur);
}
 
xmlNodePtr
xmlNewTextLen(const xmlChar *content, int len) {
    xmlNodePtr cur;
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building text");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_TEXT_NODE;
 
    cur->name = xmlStringText;
    if (content != NULL) {
    cur->content = xmlStrndup(content, len);
    }
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
 
xmlNodePtr
xmlNewDocTextLen(xmlDocPtr doc, const xmlChar *content, int len) {
    xmlNodePtr cur;
 
    cur = xmlNewTextLen(content, len);
    if (cur != NULL) cur->doc = doc;
    return(cur);
}
 
xmlNodePtr
xmlNewComment(const xmlChar *content) {
    xmlNodePtr cur;
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building comment");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_COMMENT_NODE;
 
    cur->name = xmlStringComment;
    if (content != NULL) {
    cur->content = xmlStrdup(content);
    }
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
 
xmlNodePtr
xmlNewCDataBlock(xmlDocPtr doc, const xmlChar *content, int len) {
    xmlNodePtr cur;
 
    /*
     * Allocate a new node and fill the fields.
     */
    cur = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (cur == NULL) {
    xmlTreeErrMemory("building CDATA");
    return(NULL);
    }
    memset(cur, 0, sizeof(xmlNode));
    cur->type = XML_CDATA_SECTION_NODE;
    cur->doc = doc;
 
    if (content != NULL) {
    cur->content = xmlStrndup(content, len);
    }
 
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
    xmlRegisterNodeDefaultValue(cur);
    return(cur);
}
 
xmlNodePtr
xmlNewDocComment(xmlDocPtr doc, const xmlChar *content) {
    xmlNodePtr cur;
 
    cur = xmlNewComment(content);
    if (cur != NULL) cur->doc = doc;
    return(cur);
}
 
static const xmlChar *_copyStringForNewDictIfNeeded(xmlDictPtr oldDict, xmlDictPtr newDict, const xmlChar *oldValue) {
    const xmlChar *newValue = oldValue;
    if (oldValue) {
        int oldDictOwnsOldValue = oldDict && (xmlDictOwns(oldDict, oldValue) == 1);
        if (oldDictOwnsOldValue) {
            if (newDict)
                newValue = xmlDictLookup(newDict, oldValue, -1);
            else
                newValue = xmlStrdup(oldValue);
        }
    }
    return newValue;
}
 
void
xmlSetTreeDoc(xmlNodePtr tree, xmlDocPtr doc) {
    xmlAttrPtr prop;
 
    if ((tree == NULL) || (tree->type == XML_NAMESPACE_DECL))
    return;
    if (tree->doc != doc) {
        xmlDictPtr oldTreeDict = tree->doc ? tree->doc->dict : NULL;
        xmlDictPtr newDict = doc ? doc->dict : NULL;
 
    if(tree->type == XML_ELEMENT_NODE) {
        prop = tree->properties;
        while (prop != NULL) {
                if (prop->atype == XML_ATTRIBUTE_ID) {
                    xmlRemoveID(tree->doc, prop);
                }
 
                if (prop->doc != doc) {
                    xmlDictPtr oldPropDict = prop->doc ? prop->doc->dict : NULL;
                    prop->name = _copyStringForNewDictIfNeeded(oldPropDict, newDict, prop->name);
                    prop->doc = doc;
                }
        xmlSetListDoc(prop->children, doc);
 
                /*
                 * TODO: ID attributes should be also added to the new
                 * document, but this breaks things like xmlReplaceNode.
                 * The underlying problem is that xmlRemoveID is only called
                 * if a node is destroyed, not if it's unlinked.
                 */
#if 0
                if (xmlIsID(doc, tree, prop)) {
                    xmlChar *idVal = xmlNodeListGetString(doc, prop->children,
                                                          1);
                    xmlAddID(NULL, doc, idVal, prop);
                }
#endif
 
        prop = prop->next;
        }
    }
        if (tree->type == XML_ENTITY_REF_NODE) {
            /*
             * Clear 'children' which points to the entity declaration
             * from the original document.
             */
            tree->children = NULL;
        } else if (tree->children != NULL) {
        xmlSetListDoc(tree->children, doc);
        }
 
        tree->name = _copyStringForNewDictIfNeeded(oldTreeDict, newDict, tree->name);
        tree->content = (xmlChar *)_copyStringForNewDictIfNeeded(oldTreeDict, NULL, tree->content);
        /* FIXME: tree->ns should be updated as in xmlStaticCopyNode(). */
    tree->doc = doc;
    }
}
 
void
xmlSetListDoc(xmlNodePtr list, xmlDocPtr doc) {
    xmlNodePtr cur;
 
    if ((list == NULL) || (list->type == XML_NAMESPACE_DECL))
    return;
    cur = list;
    while (cur != NULL) {
    if (cur->doc != doc)
        xmlSetTreeDoc(cur, doc);
    cur = cur->next;
    }
}
 
#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED)
xmlNodePtr
xmlNewChild(xmlNodePtr parent, xmlNsPtr ns,
            const xmlChar *name, const xmlChar *content) {
    xmlNodePtr cur, prev;
 
    if (parent == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewChild : parent == NULL\n");
#endif
    return(NULL);
    }
 
    if (name == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlNewChild : name == NULL\n");
#endif
    return(NULL);
    }
 
    /*
     * Allocate a new node
     */
    if (parent->type == XML_ELEMENT_NODE) {
    if (ns == NULL)
        cur = xmlNewDocNode(parent->doc, parent->ns, name, content);
    else
        cur = xmlNewDocNode(parent->doc, ns, name, content);
    } else if ((parent->type == XML_DOCUMENT_NODE) ||
           (parent->type == XML_HTML_DOCUMENT_NODE)) {
    if (ns == NULL)
        cur = xmlNewDocNode((xmlDocPtr) parent, NULL, name, content);
    else
        cur = xmlNewDocNode((xmlDocPtr) parent, ns, name, content);
    } else if (parent->type == XML_DOCUMENT_FRAG_NODE) {
        cur = xmlNewDocNode( parent->doc, ns, name, content);
    } else {
    return(NULL);
    }
    if (cur == NULL) return(NULL);
 
    /*
     * add the new element at the end of the children list.
     */
    cur->type = XML_ELEMENT_NODE;
    cur->parent = parent;
    cur->doc = parent->doc;
    if (parent->children == NULL) {
        parent->children = cur;
    parent->last = cur;
    } else {
        prev = parent->last;
    prev->next = cur;
    cur->prev = prev;
    parent->last = cur;
    }
 
    return(cur);
}
#endif /* LIBXML_TREE_ENABLED */
 
static xmlNodePtr
xmlAddPropSibling(xmlNodePtr prev, xmlNodePtr cur, xmlNodePtr prop) {
    xmlAttrPtr attr;
 
    if ((cur == NULL) || (cur->type != XML_ATTRIBUTE_NODE) ||
        (prop == NULL) || (prop->type != XML_ATTRIBUTE_NODE) ||
        ((prev != NULL) && (prev->type != XML_ATTRIBUTE_NODE)))
        return(NULL);
 
    /* check if an attribute with the same name exists */
    if (prop->ns == NULL)
        attr = xmlHasNsProp(cur->parent, prop->name, NULL);
    else
        attr = xmlHasNsProp(cur->parent, prop->name, prop->ns->href);
 
    if (prop->doc != cur->doc) {
        xmlSetTreeDoc(prop, cur->doc);
    }
    prop->parent = cur->parent;
    prop->prev = prev;
    if (prev != NULL) {
        prop->next = prev->next;
        prev->next = prop;
        if (prop->next)
            prop->next->prev = prop;
    } else {
        prop->next = cur;
        cur->prev = prop;
    }
    if (prop->prev == NULL && prop->parent != NULL)
        prop->parent->properties = (xmlAttrPtr) prop;
    if ((attr != NULL) && (attr->type != XML_ATTRIBUTE_DECL)) {
        /* different instance, destroy it (attributes must be unique) */
        xmlRemoveProp((xmlAttrPtr) attr);
    }
    return prop;
}
 
xmlNodePtr
xmlAddNextSibling(xmlNodePtr cur, xmlNodePtr elem) {
    if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddNextSibling : cur == NULL\n");
#endif
    return(NULL);
    }
    if ((elem == NULL) || (elem->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddNextSibling : elem == NULL\n");
#endif
    return(NULL);
    }
 
    if (cur == elem) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddNextSibling : cur == elem\n");
#endif
    return(NULL);
    }
 
    xmlUnlinkNode(elem);
 
    if (elem->type == XML_TEXT_NODE) {
    if (cur->type == XML_TEXT_NODE) {
        xmlNodeAddContent(cur, elem->content);
        xmlFreeNode(elem);
        return(cur);
    }
    if ((cur->next != NULL) && (cur->next->type == XML_TEXT_NODE) &&
            (cur->name == cur->next->name)) {
        xmlChar *tmp;
 
        tmp = xmlStrdup(elem->content);
        tmp = xmlStrcat(tmp, cur->next->content);
        xmlNodeSetContent(cur->next, tmp);
        xmlFree(tmp);
        xmlFreeNode(elem);
        return(cur->next);
    }
    } else if (elem->type == XML_ATTRIBUTE_NODE) {
        return xmlAddPropSibling(cur, cur, elem);
    }
 
    if (elem->doc != cur->doc) {
    xmlSetTreeDoc(elem, cur->doc);
    }
    elem->parent = cur->parent;
    elem->prev = cur;
    elem->next = cur->next;
    cur->next = elem;
    if (elem->next != NULL)
    elem->next->prev = elem;
    if ((elem->parent != NULL) && (elem->parent->last == cur))
    elem->parent->last = elem;
    return(elem);
}
 
#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_HTML_ENABLED) || \
    defined(LIBXML_SCHEMAS_ENABLED) || defined(LIBXML_XINCLUDE_ENABLED)
xmlNodePtr
xmlAddPrevSibling(xmlNodePtr cur, xmlNodePtr elem) {
    if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddPrevSibling : cur == NULL\n");
#endif
    return(NULL);
    }
    if ((elem == NULL) || (elem->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddPrevSibling : elem == NULL\n");
#endif
    return(NULL);
    }
 
    if (cur == elem) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddPrevSibling : cur == elem\n");
#endif
    return(NULL);
    }
 
    xmlUnlinkNode(elem);
 
    if (elem->type == XML_TEXT_NODE) {
    if (cur->type == XML_TEXT_NODE) {
        xmlChar *tmp;
 
        tmp = xmlStrdup(elem->content);
        tmp = xmlStrcat(tmp, cur->content);
        xmlNodeSetContent(cur, tmp);
        xmlFree(tmp);
        xmlFreeNode(elem);
        return(cur);
    }
    if ((cur->prev != NULL) && (cur->prev->type == XML_TEXT_NODE) &&
            (cur->name == cur->prev->name)) {
        xmlNodeAddContent(cur->prev, elem->content);
        xmlFreeNode(elem);
        return(cur->prev);
    }
    } else if (elem->type == XML_ATTRIBUTE_NODE) {
        return xmlAddPropSibling(cur->prev, cur, elem);
    }
 
    if (elem->doc != cur->doc) {
    xmlSetTreeDoc(elem, cur->doc);
    }
    elem->parent = cur->parent;
    elem->next = cur;
    elem->prev = cur->prev;
    cur->prev = elem;
    if (elem->prev != NULL)
    elem->prev->next = elem;
    if ((elem->parent != NULL) && (elem->parent->children == cur)) {
        elem->parent->children = elem;
    }
    return(elem);
}
#endif /* LIBXML_TREE_ENABLED */
 
xmlNodePtr
xmlAddSibling(xmlNodePtr cur, xmlNodePtr elem) {
    xmlNodePtr parent;
 
    if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddSibling : cur == NULL\n");
#endif
    return(NULL);
    }
 
    if ((elem == NULL) || (elem->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddSibling : elem == NULL\n");
#endif
    return(NULL);
    }
 
    if (cur == elem) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddSibling : cur == elem\n");
#endif
    return(NULL);
    }
 
    /*
     * Constant time is we can rely on the ->parent->last to find
     * the last sibling.
     */
    if ((cur->type != XML_ATTRIBUTE_NODE) && (cur->parent != NULL) &&
    (cur->parent->children != NULL) &&
    (cur->parent->last != NULL) &&
    (cur->parent->last->next == NULL)) {
    cur = cur->parent->last;
    } else {
    while (cur->next != NULL) cur = cur->next;
    }
 
    xmlUnlinkNode(elem);
 
    if ((cur->type == XML_TEXT_NODE) && (elem->type == XML_TEXT_NODE) &&
        (cur->name == elem->name)) {
    xmlNodeAddContent(cur, elem->content);
    xmlFreeNode(elem);
    return(cur);
    } else if (elem->type == XML_ATTRIBUTE_NODE) {
        return xmlAddPropSibling(cur, cur, elem);
    }
 
    if (elem->doc != cur->doc) {
    xmlSetTreeDoc(elem, cur->doc);
    }
    parent = cur->parent;
    elem->prev = cur;
    elem->next = NULL;
    elem->parent = parent;
    cur->next = elem;
    if (parent != NULL)
    parent->last = elem;
 
    return(elem);
}
 
xmlNodePtr
xmlAddChildList(xmlNodePtr parent, xmlNodePtr cur) {
    xmlNodePtr prev;
 
    if ((parent == NULL) || (parent->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddChildList : parent == NULL\n");
#endif
    return(NULL);
    }
 
    if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddChildList : child == NULL\n");
#endif
    return(NULL);
    }
 
    if ((cur->doc != NULL) && (parent->doc != NULL) &&
        (cur->doc != parent->doc)) {
#ifdef DEBUG_TREE
    xmlGenericError(xmlGenericErrorContext,
        "Elements moved to a different document\n");
#endif
    }
 
    /*
     * add the first element at the end of the children list.
     */
 
    if (parent->children == NULL) {
        parent->children = cur;
    } else {
    /*
     * If cur and parent->last both are TEXT nodes, then merge them.
     */
    if ((cur->type == XML_TEXT_NODE) &&
        (parent->last->type == XML_TEXT_NODE) &&
        (cur->name == parent->last->name)) {
        xmlNodeAddContent(parent->last, cur->content);
        /*
         * if it's the only child, nothing more to be done.
         */
        if (cur->next == NULL) {
        xmlFreeNode(cur);
        return(parent->last);
        }
        prev = cur;
        cur = cur->next;
        xmlFreeNode(prev);
    }
        prev = parent->last;
    prev->next = cur;
    cur->prev = prev;
    }
    while (cur->next != NULL) {
    cur->parent = parent;
    if (cur->doc != parent->doc) {
        xmlSetTreeDoc(cur, parent->doc);
    }
        cur = cur->next;
    }
    cur->parent = parent;
    /* the parent may not be linked to a doc ! */
    if (cur->doc != parent->doc) {
        xmlSetTreeDoc(cur, parent->doc);
    }
    parent->last = cur;
 
    return(cur);
}
 
xmlNodePtr
xmlAddChild(xmlNodePtr parent, xmlNodePtr cur) {
    xmlNodePtr prev;
 
    if ((parent == NULL) || (parent->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddChild : parent == NULL\n");
#endif
    return(NULL);
    }
 
    if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddChild : child == NULL\n");
#endif
    return(NULL);
    }
 
    if (parent == cur) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlAddChild : parent == cur\n");
#endif
    return(NULL);
    }
    /*
     * If cur is a TEXT node, merge its content with adjacent TEXT nodes
     * cur is then freed.
     */
    if (cur->type == XML_TEXT_NODE) {
    if ((parent->type == XML_TEXT_NODE) &&
        (parent->content != NULL) &&
        (parent->name == cur->name)) {
        xmlNodeAddContent(parent, cur->content);
        xmlFreeNode(cur);
        return(parent);
    }
    if ((parent->last != NULL) && (parent->last->type == XML_TEXT_NODE) &&
        (parent->last->name == cur->name) &&
        (parent->last != cur)) {
        xmlNodeAddContent(parent->last, cur->content);
        xmlFreeNode(cur);
        return(parent->last);
    }
    }
 
    /*
     * add the new element at the end of the children list.
     */
    prev = cur->parent;
    cur->parent = parent;
    if (cur->doc != parent->doc) {
    xmlSetTreeDoc(cur, parent->doc);
    }
    /* this check prevents a loop on tree-traversions if a developer
     * tries to add a node to its parent multiple times
     */
    if (prev == parent)
    return(cur);
 
    /*
     * Coalescing
     */
    if ((parent->type == XML_TEXT_NODE) &&
    (parent->content != NULL) &&
    (parent != cur)) {
    xmlNodeAddContent(parent, cur->content);
    xmlFreeNode(cur);
    return(parent);
    }
    if (cur->type == XML_ATTRIBUTE_NODE) {
        if (parent->type != XML_ELEMENT_NODE)
            return(NULL);
    if (parent->properties != NULL) {
        /* check if an attribute with the same name exists */
        xmlAttrPtr lastattr;
 
        if (cur->ns == NULL)
        lastattr = xmlHasNsProp(parent, cur->name, NULL);
        else
        lastattr = xmlHasNsProp(parent, cur->name, cur->ns->href);
        if ((lastattr != NULL) && (lastattr != (xmlAttrPtr) cur) && (lastattr->type != XML_ATTRIBUTE_DECL)) {
        /* different instance, destroy it (attributes must be unique) */
            xmlUnlinkNode((xmlNodePtr) lastattr);
        xmlFreeProp(lastattr);
        }
        if (lastattr == (xmlAttrPtr) cur)
            return(cur);
 
    }
    if (parent->properties == NULL) {
        parent->properties = (xmlAttrPtr) cur;
    } else {
        /* find the end */
        xmlAttrPtr lastattr = parent->properties;
        while (lastattr->next != NULL) {
        lastattr = lastattr->next;
        }
        lastattr->next = (xmlAttrPtr) cur;
        ((xmlAttrPtr) cur)->prev = lastattr;
    }
    } else {
    if (parent->children == NULL) {
        parent->children = cur;
        parent->last = cur;
    } else {
        prev = parent->last;
        prev->next = cur;
        cur->prev = prev;
        parent->last = cur;
    }
    }
    return(cur);
}
 
xmlNodePtr
xmlGetLastChild(const xmlNode *parent) {
    if ((parent == NULL) || (parent->type == XML_NAMESPACE_DECL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlGetLastChild : parent == NULL\n");
#endif
    return(NULL);
    }
    return(parent->last);
}
 
#ifdef LIBXML_TREE_ENABLED
/*
 * 5 interfaces from DOM ElementTraversal
 */
 
unsigned long
xmlChildElementCount(xmlNodePtr parent) {
    unsigned long ret = 0;
    xmlNodePtr cur = NULL;
 
    if (parent == NULL)
        return(0);
    switch (parent->type) {
        case XML_ELEMENT_NODE:
        case XML_ENTITY_NODE:
        case XML_DOCUMENT_NODE:
        case XML_DOCUMENT_FRAG_NODE:
        case XML_HTML_DOCUMENT_NODE:
            cur = parent->children;
            break;
        default:
            return(0);
    }
    while (cur != NULL) {
        if (cur->type == XML_ELEMENT_NODE)
            ret++;
        cur = cur->next;
    }
    return(ret);
}
 
xmlNodePtr
xmlFirstElementChild(xmlNodePtr parent) {
    xmlNodePtr cur = NULL;
 
    if (parent == NULL)
        return(NULL);
    switch (parent->type) {
        case XML_ELEMENT_NODE:
        case XML_ENTITY_NODE:
        case XML_DOCUMENT_NODE:
        case XML_DOCUMENT_FRAG_NODE:
        case XML_HTML_DOCUMENT_NODE:
            cur = parent->children;
            break;
        default:
            return(NULL);
    }
    while (cur != NULL) {
        if (cur->type == XML_ELEMENT_NODE)
            return(cur);
        cur = cur->next;
    }
    return(NULL);
}
 
xmlNodePtr
xmlLastElementChild(xmlNodePtr parent) {
    xmlNodePtr cur = NULL;
 
    if (parent == NULL)
        return(NULL);
    switch (parent->type) {
        case XML_ELEMENT_NODE:
        case XML_ENTITY_NODE:
        case XML_DOCUMENT_NODE:
        case XML_DOCUMENT_FRAG_NODE:
        case XML_HTML_DOCUMENT_NODE:
            cur = parent->last;
            break;
        default:
            return(NULL);
    }
    while (cur != NULL) {
        if (cur->type == XML_ELEMENT_NODE)
            return(cur);
        cur = cur->prev;
    }
    return(NULL);
}
 
xmlNodePtr
xmlPreviousElementSibling(xmlNodePtr node) {
    if (node == NULL)
        return(NULL);
    switch (node->type) {
        case XML_ELEMENT_NODE:
        case XML_TEXT_NODE:
        case XML_CDATA_SECTION_NODE:
        case XML_ENTITY_REF_NODE:
        case XML_ENTITY_NODE:
        case XML_PI_NODE:
        case XML_COMMENT_NODE:
        case XML_XINCLUDE_START:
        case XML_XINCLUDE_END:
            node = node->prev;
            break;
        default:
            return(NULL);
    }
    while (node != NULL) {
        if (node->type == XML_ELEMENT_NODE)
            return(node);
        node = node->prev;
    }
    return(NULL);
}
 
xmlNodePtr
xmlNextElementSibling(xmlNodePtr node) {
    if (node == NULL)
        return(NULL);
    switch (node->type) {
        case XML_ELEMENT_NODE:
        case XML_TEXT_NODE:
        case XML_CDATA_SECTION_NODE:
        case XML_ENTITY_REF_NODE:
        case XML_ENTITY_NODE:
        case XML_PI_NODE:
        case XML_COMMENT_NODE:
        case XML_DTD_NODE:
        case XML_XINCLUDE_START:
        case XML_XINCLUDE_END:
            node = node->next;
            break;
        default:
            return(NULL);
    }
    while (node != NULL) {
        if (node->type == XML_ELEMENT_NODE)
            return(node);
        node = node->next;
    }
    return(NULL);
}
 
#endif /* LIBXML_TREE_ENABLED */
 
void
xmlFreeNodeList(xmlNodePtr cur) {
    xmlNodePtr next;
    xmlNodePtr parent;
    xmlDictPtr dict = NULL;
    size_t depth = 0;
 
    if (cur == NULL) return;
    if (cur->type == XML_NAMESPACE_DECL) {
    xmlFreeNsList((xmlNsPtr) cur);
    return;
    }
    if (cur->doc != NULL) dict = cur->doc->dict;
    while (1) {
        while ((cur->children != NULL) &&
               (cur->type != XML_DOCUMENT_NODE) &&
               (cur->type != XML_HTML_DOCUMENT_NODE) &&
               (cur->type != XML_DTD_NODE) &&
               (cur->type != XML_ENTITY_REF_NODE)) {
            cur = cur->children;
            depth += 1;
        }
 
        next = cur->next;
        parent = cur->parent;
    if ((cur->type == XML_DOCUMENT_NODE) ||
            (cur->type == XML_HTML_DOCUMENT_NODE)) {
            xmlFreeDoc((xmlDocPtr) cur);
        } else if (cur->type != XML_DTD_NODE) {
 
        if ((__xmlRegisterCallbacks) && (xmlDeregisterNodeDefaultValue))
        xmlDeregisterNodeDefaultValue(cur);
 
        if (((cur->type == XML_ELEMENT_NODE) ||
         (cur->type == XML_XINCLUDE_START) ||
         (cur->type == XML_XINCLUDE_END)) &&
        (cur->properties != NULL))
        xmlFreePropList(cur->properties);
        if ((cur->type != XML_ELEMENT_NODE) &&
        (cur->type != XML_XINCLUDE_START) &&
        (cur->type != XML_XINCLUDE_END) &&
        (cur->type != XML_ENTITY_REF_NODE) &&
        (cur->content != (xmlChar *) &(cur->properties))) {
        DICT_FREE(cur->content)
        }
        if (((cur->type == XML_ELEMENT_NODE) ||
             (cur->type == XML_XINCLUDE_START) ||
         (cur->type == XML_XINCLUDE_END)) &&
        (cur->nsDef != NULL))
        xmlFreeNsList(cur->nsDef);
 
        /*
         * When a node is a text node or a comment, it uses a global static
         * variable for the name of the node.
         * Otherwise the node name might come from the document's
         * dictionary
         */
        if ((cur->name != NULL) &&
        (cur->type != XML_TEXT_NODE) &&
        (cur->type != XML_COMMENT_NODE))
        DICT_FREE(cur->name)
        xmlFree(cur);
    }
 
        if (next != NULL) {
        cur = next;
        } else {
            if ((depth == 0) || (parent == NULL))
                break;
            depth -= 1;
            cur = parent;
            cur->children = NULL;
        }
    }
}
 
void
xmlFreeNode(xmlNodePtr cur) {
    xmlDictPtr dict = NULL;
 
    if (cur == NULL) return;
 
    /* use xmlFreeDtd for DTD nodes */
    if (cur->type == XML_DTD_NODE) {
    xmlFreeDtd((xmlDtdPtr) cur);
    return;
    }
    if (cur->type == XML_NAMESPACE_DECL) {
    xmlFreeNs((xmlNsPtr) cur);
        return;
    }
    if (cur->type == XML_ATTRIBUTE_NODE) {
    xmlFreeProp((xmlAttrPtr) cur);
    return;
    }
 
    if ((__xmlRegisterCallbacks) && (xmlDeregisterNodeDefaultValue))
    xmlDeregisterNodeDefaultValue(cur);
 
    if (cur->doc != NULL) dict = cur->doc->dict;
 
    if (cur->type == XML_ENTITY_DECL) {
        xmlEntityPtr ent = (xmlEntityPtr) cur;
    DICT_FREE(ent->SystemID);
    DICT_FREE(ent->ExternalID);
    }
    if ((cur->children != NULL) &&
    (cur->type != XML_ENTITY_REF_NODE))
    xmlFreeNodeList(cur->children);
 
    if ((cur->type == XML_ELEMENT_NODE) ||
        (cur->type == XML_XINCLUDE_START) ||
        (cur->type == XML_XINCLUDE_END)) {
        if (cur->properties != NULL)
            xmlFreePropList(cur->properties);
        if (cur->nsDef != NULL)
            xmlFreeNsList(cur->nsDef);
    } else if ((cur->content != NULL) &&
               (cur->type != XML_ENTITY_REF_NODE) &&
               (cur->content != (xmlChar *) &(cur->properties))) {
        DICT_FREE(cur->content)
    }
 
    /*
     * When a node is a text node or a comment, it uses a global static
     * variable for the name of the node.
     * Otherwise the node name might come from the document's dictionary
     */
    if ((cur->name != NULL) &&
        (cur->type != XML_TEXT_NODE) &&
        (cur->type != XML_COMMENT_NODE))
    DICT_FREE(cur->name)
 
    xmlFree(cur);
}
 
void
xmlUnlinkNode(xmlNodePtr cur) {
    if (cur == NULL) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlUnlinkNode : node == NULL\n");
#endif
    return;
    }
    if (cur->type == XML_NAMESPACE_DECL)
        return;
    if (cur->type == XML_DTD_NODE) {
    xmlDocPtr doc;
    doc = cur->doc;
    if (doc != NULL) {
        if (doc->intSubset == (xmlDtdPtr) cur)
        doc->intSubset = NULL;
        if (doc->extSubset == (xmlDtdPtr) cur)
        doc->extSubset = NULL;
    }
    }
    if (cur->type == XML_ENTITY_DECL) {
        xmlDocPtr doc;
    doc = cur->doc;
    if (doc != NULL) {
        if (doc->intSubset != NULL) {
            if (xmlHashLookup(doc->intSubset->entities, cur->name) == cur)
            xmlHashRemoveEntry(doc->intSubset->entities, cur->name,
                               NULL);
            if (xmlHashLookup(doc->intSubset->pentities, cur->name) == cur)
            xmlHashRemoveEntry(doc->intSubset->pentities, cur->name,
                               NULL);
        }
        if (doc->extSubset != NULL) {
            if (xmlHashLookup(doc->extSubset->entities, cur->name) == cur)
            xmlHashRemoveEntry(doc->extSubset->entities, cur->name,
                               NULL);
            if (xmlHashLookup(doc->extSubset->pentities, cur->name) == cur)
            xmlHashRemoveEntry(doc->extSubset->pentities, cur->name,
                               NULL);
        }
    }
    }
    if (cur->parent != NULL) {
    xmlNodePtr parent;
    parent = cur->parent;
    if (cur->type == XML_ATTRIBUTE_NODE) {
        if (parent->properties == (xmlAttrPtr) cur)
        parent->properties = ((xmlAttrPtr) cur)->next;
    } else {
        if (parent->children == cur)
        parent->children = cur->next;
        if (parent->last == cur)
        parent->last = cur->prev;
    }
    cur->parent = NULL;
    }
    if (cur->next != NULL)
        cur->next->prev = cur->prev;
    if (cur->prev != NULL)
        cur->prev->next = cur->next;
    cur->next = cur->prev = NULL;
}
 
#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_WRITER_ENABLED)
xmlNodePtr
xmlReplaceNode(xmlNodePtr old, xmlNodePtr cur) {
    if (old == cur) return(NULL);
    if ((old == NULL) || (old->type == XML_NAMESPACE_DECL) ||
        (old->parent == NULL)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlReplaceNode : old == NULL or without parent\n");
#endif
    return(NULL);
    }
    if ((cur == NULL) || (cur->type == XML_NAMESPACE_DECL)) {
    xmlUnlinkNode(old);
    return(old);
    }
    if (cur == old) {
    return(old);
    }
    if ((old->type==XML_ATTRIBUTE_NODE) && (cur->type!=XML_ATTRIBUTE_NODE)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlReplaceNode : Trying to replace attribute node with other node type\n");
#endif
    return(old);
    }
    if ((cur->type==XML_ATTRIBUTE_NODE) && (old->type!=XML_ATTRIBUTE_NODE)) {
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
        "xmlReplaceNode : Trying to replace a non-attribute node with attribute node\n");
#endif
    return(old);
    }
    xmlUnlinkNode(cur);
    xmlSetTreeDoc(cur, old->doc);
    cur->parent = old->parent;
    cur->next = old->next;
    if (cur->next != NULL)
    cur->next->prev = cur;
    cur->prev = old->prev;
    if (cur->prev != NULL)
    cur->prev->next = cur;
    if (cur->parent != NULL) {
    if (cur->type == XML_ATTRIBUTE_NODE) {
        if (cur->parent->properties == (xmlAttrPtr)old)
        cur->parent->properties = ((xmlAttrPtr) cur);
    } else {
        if (cur->parent->children == old)
        cur->parent->children = cur;
        if (cur->parent->last == old)
        cur->parent->last = cur;
    }
    }
    old->next = old->prev = NULL;
    old->parent = NULL;
    return(old);
}
#endif /* LIBXML_TREE_ENABLED */
 
/************************************************************************
 *                                  *
 *      Copy operations                     *
 *                                  *
 ************************************************************************/
 
xmlNsPtr
xmlCopyNamespace(xmlNsPtr cur) {
    xmlNsPtr ret;
 
    if (cur == NULL) return(NULL);
    switch (cur->type) {
    case XML_LOCAL_NAMESPACE:
        ret = xmlNewNs(NULL, cur->href, cur->prefix);
        break;
    default:
#ifdef DEBUG_TREE
        xmlGenericError(xmlGenericErrorContext,
            "xmlCopyNamespace: invalid type %d\n", cur->type);
#endif
        return(NULL);
    }
    return(ret);
}
 
xmlNsPtr
xmlCopyNamespaceList(xmlNsPtr cur) {
    xmlNsPtr ret = NULL;
    xmlNsPtr p = NULL,q;
 
    while (cur != NULL) {
        q = xmlCopyNamespace(cur);
    if (p == NULL) {
        ret = p = q;
    } else {
        p->next = q;
        p = q;
    }
    cur = cur->next;
    }
    return(ret);
}
 
static xmlNodePtr
xmlStaticCopyNodeList(xmlNodePtr node, xmlDocPtr doc, xmlNodePtr parent);
 
static xmlAttrPtr
xmlCopyPropInternal(xmlDocPtr doc, xmlNodePtr target, xmlAttrPtr cur) {
    xmlAttrPtr ret;
 
    if (cur == NULL) return(NULL);
    if ((target != NULL) && (target->type != XML_ELEMENT_NODE))
        return(NULL);
    if (target != NULL)
    ret = xmlNewDocProp(target->doc, cur->name, NULL);
    else if (doc != NULL)
    ret = xmlNewDocProp(doc, cur->name, NULL);
    else if (cur->parent != NULL)
    ret = xmlNewDocProp(cur->parent->doc, cur->name, NULL);
    else if (cur->children != NULL)
    ret = xmlNewDocProp(cur->children->doc, cur->name, NULL);
    else
    ret = xmlNewDocProp(NULL, cur->name, NULL);
    if (ret == NULL) return(NULL);
    ret->parent = target;
 
    if ((cur->ns != NULL) && (target != NULL)) {
      xmlNsPtr ns;
 
      ns = xmlSearchNs(target->doc, target, cur->ns->prefix);
      if (ns == NULL) {
        /*
         * Humm, we are copying an element whose namespace is defined
         * out of the new tree scope. Search it in the original tree
         * and add it at the top of the new tree
         */
        ns = xmlSearchNs(cur->doc, cur->parent, cur->ns->prefix);
        if (ns != NULL) {
          xmlNodePtr root = target;
          xmlNodePtr pred = NULL;
 
          while (root->parent != NULL) {
            pred = root;
            root = root->parent;
          }
          if (root == (xmlNodePtr) target->doc) {
            /* correct possibly cycling above the document elt */
            root = pred;
          }
          ret->ns = xmlNewNs(root, ns->href, ns->prefix);
        }
      } else {
        /*
         * we have to find something appropriate here since
         * we can't be sure, that the namespace we found is identified
         * by the prefix
         */
        if (xmlStrEqual(ns->href, cur->ns->href)) {
          /* this is the nice case */
          ret->ns = ns;
        } else {
          /*
           * we are in trouble: we need a new reconciled namespace.
           * This is expensive
           */
          ret->ns = xmlNewReconciledNs(target->doc, target, cur->ns);
        }
      }
 
    } else
        ret->ns = NULL;
 
    if (cur->children != NULL) {
    xmlNodePtr tmp;
 
    ret->children = xmlStaticCopyNodeList(cur->children, ret->doc, (xmlNodePtr) ret);
    ret->last = NULL;
    tmp = ret->children;
    while (tmp != NULL) {
        /* tmp->parent = (xmlNodePtr)ret; */
        if (tmp->next == NULL)
            ret->last = tmp;
        tmp = tmp->next;
    }
    }
    /*
     * Try to handle IDs
     */
    if ((target!= NULL) && (cur!= NULL) &&
    (target->doc != NULL) && (cur->doc != NULL) &&
    (cur->doc->ids != NULL) && (cur->parent != NULL)) {
    if (xmlIsID(cur->doc, cur->parent, cur)) {
        xmlChar *id;
 
        id = xmlNodeListGetString(cur->doc, cur->children, 1);
        if (id != NULL) {
        xmlAddID(NULL, target->doc, id, ret);
        xmlFree(id);
        }
    }
    }
    return(ret);
}
 
xmlAttrPtr
xmlCopyProp(xmlNodePtr target, xmlAttrPtr cur) {
    return xmlCopyPropInternal(NULL, target, cur);
}
 
xmlAttrPtr
xmlCopyPropList(xmlNodePtr target, xmlAttrPtr cur) {
    xmlAttrPtr ret = NULL;
    xmlAttrPtr p = NULL,q;
 
    if ((target != NULL) && (target->type != XML_ELEMENT_NODE))
        return(NULL);
    while (cur != NULL) {
        q = xmlCopyProp(target, cur);
    if (q == NULL)
        return(NULL);
    if (p == NULL) {
        ret = p = q;
    } else {
        p->next = q;
        q->prev = p;
        p = q;
    }
    cur = cur->next;
    }
    return(ret);
}
 
/*
 * NOTE about the CopyNode operations !
 *
 * They are split into external and internal parts for one
 * tricky reason: namespaces. Doing a direct copy of a node
 * say RPM:Copyright without changing the namespace pointer to
 * something else can produce stale links. One way to do it is
 * to keep a reference counter but this doesn't work as soon
 * as one moves the element or the subtree out of the scope of
 * the existing namespace. The actual solution seems to be to add
 * a copy of the namespace at the top of the copied tree if
 * not available in the subtree.
 * Hence two functions, the public front-end call the inner ones
 * The argument "recursive" normally indicates a recursive copy
 * of the node with values 0 (no) and 1 (yes).  For XInclude,
 * however, we allow a value of 2 to indicate copy properties and
 * namespace info, but don't recurse on children.
 */
 
static xmlNodePtr
xmlStaticCopyNode(xmlNodePtr node, xmlDocPtr doc, xmlNodePtr parent,
                  int extended) {
    xmlNodePtr ret;
 
    if (node == NULL) return(NULL);
    switch (node->type) {
        case XML_TEXT_NODE:
        case XML_CDATA_SECTION_NODE:
        case XML_ELEMENT_NODE:
        case XML_DOCUMENT_FRAG_NODE:
        case XML_ENTITY_REF_NODE:
        case XML_ENTITY_NODE:
        case XML_PI_NODE:
        case XML_COMMENT_NODE:
        case XML_XINCLUDE_START:
        case XML_XINCLUDE_END:
        break;
        case XML_ATTRIBUTE_NODE:
        return((xmlNodePtr) xmlCopyPropInternal(doc, parent, (xmlAttrPtr) node));
        case XML_NAMESPACE_DECL:
        return((xmlNodePtr) xmlCopyNamespaceList((xmlNsPtr) node));
 
        case XML_DOCUMENT_NODE:
        case XML_HTML_DOCUMENT_NODE:
#ifdef LIBXML_TREE_ENABLED
        return((xmlNodePtr) xmlCopyDoc((xmlDocPtr) node, extended));
#endif /* LIBXML_TREE_ENABLED */
        case XML_DOCUMENT_TYPE_NODE:
        case XML_NOTATION_NODE:
        case XML_DTD_NODE:
        case XML_ELEMENT_DECL:
        case XML_ATTRIBUTE_DECL:
        case XML_ENTITY_DECL:
            return(NULL);
    }
 
    /*
     * Allocate a new node and fill the fields.
     */
    ret = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
    if (ret == NULL) {
    xmlTreeErrMemory("copying node");
    return(NULL);
    }
    memset(ret, 0, sizeof(xmlNode));
    ret->type = node->type;
 
    ret->doc = doc;
    ret->parent = parent;
    if (node->name == xmlStringText)
    ret->name = xmlStringText;
    else if (node->name == xmlStringTextNoenc)
    ret->name = xmlStringTextNoenc;
    else if (node->name == xmlStringComment)
    ret->name = xmlStringComment;
    else if (node->name != NULL) {
        if ((doc != NULL) && (doc->dict != NULL))
        ret->name = xmlDictLookup(doc->dict, node->name, -1);
    else
        ret->name = xmlStrdup(node->name);
    }
    if ((node->type != XML_ELEMENT_NODE) &&
    (node->content != NULL) &&
    (node->type != XML_ENTITY_REF_NODE) &&
    (node->type != XML_XINCLUDE_END) &&
    (node->type != XML_XINCLUDE_START)) {
    ret->content = xmlStrdup(node->content);
    }else{
      if (node->type == XML_ELEMENT_NODE)
        ret->line = node->line;
    }
    if (parent != NULL) {
    xmlNodePtr tmp;
 
    /*
     * this is a tricky part for the node register thing:
     * in case ret does get coalesced in xmlAddChild
     * the deregister-node callback is called; so we register ret now already
     */
    if ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue))
        xmlRegisterNodeDefaultValue((xmlNodePtr)ret);
 
        /*
         * Note that since ret->parent is already set, xmlAddChild will
         * return early and not actually insert the node. It will only
         * coalesce text nodes and unnecessarily call xmlSetTreeDoc.
         * Assuming that the subtree to be copied always has its text
         * nodes coalesced, the somewhat confusing call to xmlAddChild
         * could be removed.
         */
        tmp = xmlAddChild(parent, ret);
    /* node could have coalesced */
    if (tmp != ret)
        return(tmp);
    }
 
    if (!extended)
    goto out;
    if (((node->type == XML_ELEMENT_NODE) ||
         (node->type == XML_XINCLUDE_START)) && (node->nsDef != NULL))
        ret->nsDef = xmlCopyNamespaceList(node->nsDef);
 
    if (node->ns != NULL) {
        xmlNsPtr ns;
 
    ns = xmlSearchNs(doc, ret, node->ns->prefix);
    if (ns == NULL) {
        /*
         * Humm, we are copying an element whose namespace is defined
         * out of the new tree scope. Search it in the original tree
         * and add it at the top of the new tree
         */
        ns = xmlSearchNs(node->doc, node, node->ns->prefix);
        if (ns != NULL) {
            xmlNodePtr root = ret;
 
        while (root->parent != NULL) root = root->parent;
        ret->ns = xmlNewNs(root, ns->href, ns->prefix);
        } else {
            ret->ns = xmlNewReconciledNs(doc, ret, node->ns);
        }
    } else {
        /*
         * reference the existing namespace definition in our own tree.
         */
        ret->ns = ns;
    }
    }
    if (((node->type == XML_ELEMENT_NODE) ||
         (node->type == XML_XINCLUDE_START)) && (node->properties != NULL))
        ret->properties = xmlCopyPropList(ret, node->properties);
    if (node->type == XML_ENTITY_REF_NODE) {
    if ((doc == NULL) || (node->doc != doc)) {
        /*
         * The copied node will go into a separate document, so
         * to avoid dangling references to the ENTITY_DECL node
         * we cannot keep the reference. Try to find it in the
         * target document.
         */
        ret->children = (xmlNodePtr) xmlGetDocEntity(doc, ret->name);
    } else {
            ret->children = node->children;
    }
    ret->last = ret->children;
    } else if ((node->children != NULL) && (extended != 2)) {
        xmlNodePtr cur, insert;
 
        cur = node->children;
        insert = ret;
        while (cur != NULL) {
            xmlNodePtr copy = xmlStaticCopyNode(cur, doc, insert, 2);
            if (copy == NULL) {
                xmlFreeNode(ret);
                return(NULL);
            }
 
            /* Check for coalesced text nodes */
            if (insert->last != copy) {
                if (insert->last == NULL) {
                    insert->children = copy;
                } else {
                    copy->prev = insert->last;
                    insert->last->next = copy;
                }
                insert->last = copy;
            }
 
            if ((cur->type != XML_ENTITY_REF_NODE) &&
                (cur->children != NULL)) {
                cur = cur->children;
                insert = copy;
                continue;
            }
 
            while (1) {
                if (cur->next != NULL) {
                    cur = cur->next;
                    break;
                }
 
                cur = cur->parent;
                insert = insert->parent;
                if (cur == node) {
                    cur = NULL;
                    break;
                }
            }
        }
    }
 
out:
    /* if parent != NULL we already registered the node above */
    if ((parent == NULL) &&
        ((__xmlRegisterCallbacks) && (xmlRegisterNodeDefaultValue)))
    xmlRegisterNodeDefaultValue((xmlNodePtr)ret);
    return(ret);
}
 
static xmlNodePtr
xmlStaticCopyNodeList(xmlNodePtr node, xmlDocPtr doc, xmlNodePtr parent) {
    xmlNodePtr ret = NULL;
    xmlNodePtr p = NULL,q;
 
    while (node != NULL) {
#ifdef LIBXML_TREE_ENABLED
    if (node->type == XML_DTD_NODE ) {
        if (doc == NULL) {
        node = node->next;
        continue;
        }
        if (doc->intSubset == NULL) {
        q = (xmlNodePtr) xmlCopyDtd( (xmlDtdPtr) node );
        if (q == NULL) return(NULL);
        q->doc = doc;
        q->parent = parent;
        doc->intSubset = (xmlDtdPtr) q;
        xmlAddChild(parent, q);
        } else {
        q = (xmlNodePtr) doc->intSubset;
        xmlAddChild(parent, q);
        }
    } else
#endif /* LIBXML_TREE_ENABLED */
        q = xmlStaticCopyNode(node, doc, parent, 1);
    if (q == NULL) return(NULL);
    if (ret == NULL) {
        q->prev = NULL;
        ret = p = q;
    } else if (p != q) {
    /* the test is required if xmlStaticCopyNode coalesced 2 text nodes */
        p->next = q;
        q->prev = p;
        p = q;
    }
    node = node->next;
    }
    return(ret);
}
 
xmlNodePtr
xmlCopyNode(xmlNodePtr node, int extended) {
    xmlNodePtr ret;
 
    ret = xmlStaticCopyNode(node, NULL, NULL, extended);
    return(ret);
}
 
xmlNodePtr
xmlDocCopyNode(xmlNodePtr node, xmlDocPtr doc, int extended) {
    xmlNodePtr ret;
 
    ret = xmlStaticCopyNode(node, doc, NULL, extended);
    return(ret);
}
 
xmlNodePtr xmlDocCopyNodeList(xmlDocPtr doc, xmlNodePtr node) {
    xmlNodePtr ret = xmlStaticCopyNodeList(node, doc, NULL);
    return(ret);
}
 
xmlNodePtr xmlCopyNodeList(xmlNodePtr node) {
    xmlNodePtr ret = xmlStaticCopyNodeList(node, NULL, NULL);
    return(ret);
}
 
#if defined(LIBXML_TREE_ENABLED)
xmlDtdPtr
xmlCopyDtd(xmlDtdPtr dtd) {
    xmlDtdPtr ret;
    xmlNodePtr cur, p = NULL, q;
 
    if (dtd == NULL) return(NULL);
    ret = xmlNewDtd(NULL, dtd->name, dtd->ExternalID, dtd->SystemID);
    if (ret == NULL) return(NULL);
    if (dtd->entities != NULL)
        ret->entities = (void *) xmlCopyEntitiesTable(
                        (xmlEntitiesTablePtr) dtd->entities);
    if (dtd->notations != NULL)
        ret->notations = (void *) xmlCopyNotationTable(
                        (xmlNotationTablePtr) dtd->notations);
    if (dtd->elements != NULL)
        ret->elements = (void *) xmlCopyElementTable(
                        (xmlElementTablePtr) dtd->elements);
    if (dtd->attributes != NULL)
        ret->attributes = (void *) xmlCopyAttributeTable(
                        (xmlAttributeTablePtr) dtd->attributes);
    if (dtd->pentities != NULL)
    ret->pentities = (void *) xmlCopyEntitiesTable(
                (xmlEntitiesTablePtr) dtd->pentities);
 
    cur = dtd->children;
    while (cur != NULL) {
    q = NULL;
 
    if (cur->type == XML_ENTITY_DECL) {
        xmlEntityPtr tmp = (xmlEntityPtr) cur;
        switch (tmp->etype) {
        case XML_INTERNAL_GENERAL_ENTITY:
        case XML_EXTERNAL_GENERAL_PARSED_ENTITY:
        case XML_EXTERNAL_GENERAL_UNPARSED_ENTITY:
            q = (xmlNodePtr) xmlGetEntityFromDtd(ret, tmp->name);
            break;
        case XML_INTERNAL_PARAMETER_ENTITY:
        case XML_EXTERNAL_PARAMETER_ENTITY:
            q = (xmlNodePtr)
            xmlGetParameterEntityFromDtd(ret, tmp->name);
            break;
        case XML_INTERNAL_PREDEFINED_ENTITY:
            break;
        }
    } else if (cur->type == XML_ELEMENT_DECL) {
        xmlElementPtr tmp = (xmlElementPtr) cur;
        q = (xmlNodePtr)
        xmlGetDtdQElementDesc(ret, tmp->name, tmp->prefix);
    } else if (cur->type == XML_ATTRIBUTE_DECL) {
        xmlAttributePtr tmp = (xmlAttributePtr) cur;
        q = (xmlNodePtr)
        xmlGetDtdQAttrDesc(ret, tmp->elem, tmp->name, tmp->prefix);
    } else if (cur->type == XML_COMMENT_NODE) {
        q = xmlCopyNode(cur, 0);
    }
 
    if (q == NULL) {
        cur = cur->next;
        continue;
    }
 
    if (p == NULL)
        ret->children = q;
    else
        p->next = q;
 
    q->prev = p;
    q->parent = (xmlNodePtr) ret;
    q->next = NULL;
    ret->last = q;
    p = q;
    cur = cur->next;
    }
 
    return(ret);
}
#endif
 
#if defined(LIBXML_TREE_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED)
xmlDocPtr
xmlCopyDoc(xmlDocPtr doc, int recursive) {
    xmlDocPtr ret;
 
    if (doc == NULL) return(NULL);
    ret = xmlNewDoc(doc->version);
    if (ret == NULL) return(NULL);
    ret->type = doc->type;
    if (doc->name != NULL)
        ret->name = xmlMemStrdup(doc->name);
    if (doc->encoding != NULL)
        ret->encoding = xmlStrdup(doc->encoding);
    if (doc->URL != NULL)
        ret->URL = xmlStrdup(doc->URL);
    ret->charset = doc->charset;
    ret->compression = doc->compression;
    ret->standalone = doc->standalone;
    if (!recursive) return(ret);