palacios/src/palacios/vmm_xml.c

   1 /* ezxml.c
   2  *
   3  * Copyright 2004-2006 Aaron Voisine <aaron@voisine.org>
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining
   6  * a copy of this software and associated documentation files (the
   7  * "Software"), to deal in the Software without restriction, including
   8  * without limitation the rights to use, copy, modify, merge, publish,
   9  * distribute, sublicense, and/or sell copies of the Software, and to
  10  * permit persons to whom the Software is furnished to do so, subject to
  11  * the following conditions:
  12  *
  13  * The above copyright notice and this permission notice shall be included
  14  * in all copies or substantial portions of the Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  17  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  19  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  20  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  21  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  22  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23  */
  24
  25 /*
  26  * Modified for Palacios by Jack Lange <jarusl@cs.northwestern.edu>
  27  */
  28
  29
  30
  31 #include <palacios/vmm_xml.h>
  32 #include <palacios/vmm_sprintf.h>
  33 #include <stdarg.h>
  34 #include <palacios/vmm.h>
  35
  36 #define V3_XML_BUFSIZE 1024 // size of internal memory buffers
  37
  38 // Flags for struct v3_xml
  39 #define V3_XML_NAMEM   0x80 // name is malloced
  40 #define V3_XML_TXTM    0x40 // txt is malloced
  41 #define V3_XML_DUP     0x20 // attribute name and value are strduped
  42 //
  43
  44 static char * V3_XML_NIL[] = { NULL }; // empty, null terminated array of strings
  45
  46
  47 #define V3_XML_WS   "\t\r\n "  // whitespace
  48 #define V3_XML_ERRL 128        // maximum error string length
  49
  50 struct v3_xml_root {       // additional data for the root tag
  51     struct v3_xml xml;     // is a super-struct built on top of v3_xml struct
  52     struct v3_xml * cur;          // current xml tree insertion point
  53     char *str_ptr;         // original xml string
  54     char *tmp_start;              // start of work area
  55     char *tmp_end;              // end of work area
  56     char **ent;           // general entities (ampersand sequences)
  57     char ***attr;         // default attributes
  58     short standalone;     // non-zero if <?xml standalone="yes"?>
  59     char err[V3_XML_ERRL]; // error string
  60 };
  61
  62 static char * empty_attrib_list[] = { NULL }; // empty, null terminated array of strings
  63
  64
  65 static void * tmp_realloc(void * old_ptr, size_t old_size, size_t new_size) {
  66     void * new_buf = V3_Malloc(new_size);
  67
  68     if (new_buf == NULL) {
  69         return NULL;
  70     }
  71
  72     memcpy(new_buf, old_ptr, old_size);
  73     V3_Free(old_ptr);
  74
  75     return new_buf;
  76 }
  77
  78
  79
  80
  81
  82 // set an error string and return root
  83 static void v3_xml_err(struct v3_xml_root * root, char * xml_str, const char * err, ...) {
  84     va_list ap;
  85     int line = 1;
  86     char * tmp;
  87     char fmt[V3_XML_ERRL];
  88
  89     for (tmp = root->tmp_start; tmp < xml_str; tmp++) {
  90         if (*tmp == '\n') {
  91             line++;
  92         }
  93     }
  94
  95     snprintf(fmt, V3_XML_ERRL, "[error near line %d]: %s", line, err);
  96
  97     va_start(ap, err);
  98     vsnprintf(root->err, V3_XML_ERRL, fmt, ap);
  99     va_end(ap);
 100
 101     PrintError("XML Error: %s\n", root->err);
 102
 103     // free memory
 104     v3_xml_free(&(root->xml));
 105
 106     return;
 107 }
 108
 109
 110
 111 // returns the first child tag with the given name or NULL if not found
 112 struct v3_xml * v3_xml_child(struct v3_xml * xml, const char * name) {
 113     struct v3_xml * child = NULL;
 114
 115     if (xml != NULL) {
 116         child = xml->child;
 117     }
 118
 119     while ((child) && (strcasecmp(name, child->name) != 0)) {
 120         child = child->sibling;
 121     }
 122
 123     return child;
 124 }
 125
 126 // returns the Nth tag with the same name in the same subsection or NULL if not
 127 // found
 128 struct v3_xml * v3_xml_idx(struct v3_xml * xml, int idx) {
 129     for (; xml && idx; idx--) {
 130         xml = xml->next;
 131     }
 132
 133     return xml;
 134 }
 135
 136 // returns the value of the requested tag attribute or NULL if not found
 137 const char * v3_xml_attr(struct v3_xml * xml, const char * attr) {
 138     int i = 0;
 139     int j = 1;
 140     struct v3_xml_root * root = (struct v3_xml_root *)xml;
 141
 142     if ((!xml) || (!xml->attr)) {
 143         return NULL;
 144     }
 145
 146     while ((xml->attr[i]) && (strcasecmp(attr, xml->attr[i]) != 0)) {
 147         i += 2;
 148     }
 149
 150     if (xml->attr[i] != NULL) {
 151         return xml->attr[i + 1]; // found attribute
 152     }
 153
 154     while (root->xml.parent != NULL) {
 155         root = (struct v3_xml_root *)root->xml.parent; // root tag
 156     }
 157
 158     for (i = 0;
 159          ( (root->attr[i] != NULL) &&
 160            (strcasecmp(xml->name, root->attr[i][0]) != 0) );
 161          i++);
 162
 163     if (! root->attr[i]) {
 164         return NULL; // no matching default attributes
 165     }
 166
 167     while ((root->attr[i][j] != NULL) && (strcasecmp(attr, root->attr[i][j]) != 0)) {
 168         j += 3;
 169     }
 170
 171     return (root->attr[i][j] != NULL) ? root->attr[i][j + 1] : NULL; // found default
 172 }
 173
 174 // same as v3_xml_get but takes an already initialized va_list
 175 static struct v3_xml * v3_xml_vget(struct v3_xml * xml, va_list ap) {
 176     char * name = va_arg(ap, char *);
 177     int idx = -1;
 178
 179     if ((name != NULL) && (*name != 0)) {
 180         idx = va_arg(ap, int);
 181         xml = v3_xml_child(xml, name);
 182     }
 183     return (idx < 0) ? xml : v3_xml_vget(v3_xml_idx(xml, idx), ap);
 184 }
 185
 186 // Traverses the xml tree to retrieve a specific subtag. Takes a variable
 187 // length list of tag names and indexes. The argument list must be terminated
 188 // by either an index of -1 or an empty string tag name. Example:
 189 // title = v3_xml_get(library, "shelf", 0, "book", 2, "title", -1);
 190 // This retrieves the title of the 3rd book on the 1st shelf of library.
 191 // Returns NULL if not found.
 192 struct v3_xml * v3_xml_get(struct v3_xml * xml, ...) {
 193     va_list ap;
 194     struct v3_xml * r;
 195
 196     va_start(ap, xml);
 197     r = v3_xml_vget(xml, ap);
 198     va_end(ap);
 199     return r;
 200 }
 201
 202
 203 // sets a flag for the given tag and returns the tag
 204 static struct v3_xml * v3_xml_set_flag(struct v3_xml * xml, short flag)
 205 {
 206     if (xml) {
 207         xml->flags |= flag;
 208     }
 209     return xml;
 210 }
 211
 212
 213
 214
 215
 216 // Recursively decodes entity and character references and normalizes new lines
 217 // ent is a null terminated array of alternating entity names and values. set t
 218 // to '&' for general entity decoding, '%' for parameter entity decoding, 'c'
 219 // for cdata sections, ' ' for attribute normalization, or '*' for non-cdata
 220 // attribute normalization. Returns s, or if the decoded string is longer than
 221 // s, returns a malloced string that must be freed.
 222 static char * v3_xml_decode(char * s, char ** ent, char t) {
 223     char * e;
 224     char * r = s;
 225     char * m = s;
 226     long b, c, d, l;
 227
 228     // normalize line endings
 229     for (; *s; s++) {
 230         while (*s == '\r') {
 231             *(s++) = '\n';
 232
 233             if (*s == '\n') {
 234                 memmove(s, (s + 1), strlen(s));
 235             }
 236         }
 237     }
 238
 239     for (s = r; ; ) {
 240
 241         while ( (*s) &&
 242                 (*s != '&') &&
 243                 ( (*s != '%') ||
 244                   (t != '%')) &&
 245                 (!isspace(*s))) {
 246             s++;
 247         }
 248
 249         if (*s == '\0') {
 250             break;
 251         }
 252
 253         if ((t != 'c') && (strncmp(s, "&#", 2) == 0)) { // character reference
 254             if (s[2] == 'x') {
 255                 c = strtox(s + 3, &e); // base 16
 256             } else {
 257                 c = strtoi(s + 2, &e); // base 10
 258             }
 259
 260             if ((!c) || (*e != ';')) {
 261                 // not a character ref
 262                 s++;
 263                 continue;
 264             }
 265
 266             *(s++) = c;
 267
 268             memmove(s, strchr(s, ';') + 1, strlen(strchr(s, ';')));
 269         } else if ( ( (*s == '&') &&
 270                       ((t == '&') || (t == ' ') || (t == '*'))) ||
 271                     ( (*s == '%') && (t == '%'))) {
 272             // entity reference`
 273
 274             for ( (b = 0);
 275                   (ent[b]) && (strncmp(s + 1, ent[b], strlen(ent[b])) != 0);
 276                   (b += 2)); // find entity in entity list
 277
 278             if (ent[b++]) { // found a match
 279                 if (((c = strlen(ent[b])) - 1) > ((e = strchr(s, ';')) - s)) {
 280                     l = (d = (s - r)) + c + strlen(e); // new length
 281                     r = ((r == m) ? strcpy(V3_Malloc(l), r) : tmp_realloc(r, strlen(r), l));
 282                     e = strchr((s = r + d), ';'); // fix up pointers
 283                 }
 284
 285                 memmove(s + c, e + 1, strlen(e)); // shift rest of string
 286                 strncpy(s, ent[b], c); // copy in replacement text
 287             } else {
 288                 // not a known entity
 289                 s++;
 290             }
 291         } else if ( ( (t == ' ') || (t == '*')) &&
 292                     (isspace(*s))) {
 293             *(s++) = ' ';
 294         } else {
 295             // no decoding needed
 296             s++;
 297         }
 298     }
 299
 300     if (t == '*') {
 301         // normalize spaces for non-cdata attributes
 302         for (s = r; *s; s++) {
 303             if ((l = strspn(s, " "))) {
 304                 memmove(s, s + l, strlen(s + l) + 1);
 305             }
 306
 307             while ((*s) && (*s != ' ')) {
 308                 s++;
 309             }
 310         }
 311
 312         if ((--s >= r) && (*s == ' ')) {
 313             // trim any trailing space
 314             *s = '\0';
 315         }
 316     }
 317     return r;
 318 }
 319
 320
 321
 322 // called when parser finds character content between open and closing tag
 323 static void v3_xml_char_content(struct v3_xml_root * root, char * s, size_t len, char t) {
 324     struct v3_xml * xml = root->cur;
 325     char * m = s;
 326     size_t l = 0;
 327
 328     if ((xml == NULL) || (xml->name == NULL) || (len == 0)) {
 329         // sanity check
 330         return;
 331     }
 332
 333     s[len] = '\0'; // null terminate text (calling functions anticipate this)
 334     len = strlen(s = v3_xml_decode(s, root->ent, t)) + 1;
 335
 336     if (! *(xml->txt)) {
 337         // initial character content
 338         xml->txt = s;
 339     } else {
 340         // allocate our own memory and make a copy
 341         xml->txt = (xml->flags & V3_XML_TXTM) ?
 342             (tmp_realloc(xml->txt, strlen(xml->txt), (l = strlen(xml->txt)) + len)) :
 343             (strcpy(V3_Malloc((l = strlen(xml->txt)) + len), xml->txt));
 344
 345         strcpy(xml->txt + l, s); // add new char content
 346
 347         if (s != m) {
 348             V3_Free(s); // free s if it was malloced by v3_xml_decode()
 349         }
 350     }
 351
 352     if (xml->txt != m) {
 353         v3_xml_set_flag(xml, V3_XML_TXTM);
 354     }
 355 }
 356
 357 // called when parser finds closing tag
 358 static int v3_xml_close_tag(struct v3_xml_root * root, char * name, char * s) {
 359     if ( (root->cur == NULL) ||
 360          (root->cur->name == NULL) ||
 361          (strcasecmp(name, root->cur->name))) {
 362         v3_xml_err(root, s, "unexpected closing tag </%s>", name);
 363         return -1;
 364     }
 365
 366     root->cur = root->cur->parent;
 367     return 0;
 368 }
 369
 370 #if 0
 371 // checks for circular entity references, returns non-zero if no circular
 372 // references are found, zero otherwise
 373 static int v3_xml_ent_ok(char * name, char * s, char ** ent) {
 374     int i;
 375
 376     for (; ; s++) {
 377         while ((*s != '\0') && (*s != '&')) {
 378             // find next entity reference
 379             s++;
 380         }
 381
 382         if (*s == '\0') {
 383             return 1;
 384         }
 385
 386         if (strncmp(s + 1, name, strlen(name)) == 0) {
 387             // circular ref.
 388             return 0;
 389         }
 390
 391         for (i = 0; (ent[i]) && (strncmp(ent[i], s + 1, strlen(ent[i]))); i += 2);
 392
 393         if ((ent[i] != NULL) && (v3_xml_ent_ok(name, ent[i + 1], ent) == 0)) {
 394             return 0;
 395         }
 396     }
 397 }
 398 #endif
 399
 400
 401
 402 // frees a tag attribute list
 403 static void v3_xml_free_attr(char **attr) {
 404     int i = 0;
 405     char * m;
 406
 407     if ((attr == NULL) || (attr == empty_attrib_list)) {
 408         // nothing to free
 409         return;
 410     }
 411
 412     while (attr[i]) {
 413         // find end of attribute list
 414         i += 2;
 415     }
 416
 417     m = attr[i + 1]; // list of which names and values are malloced
 418
 419     for (i = 0; m[i]; i++) {
 420         if (m[i] & V3_XML_NAMEM) {
 421             V3_Free(attr[i * 2]);
 422         }
 423
 424         if (m[i] & V3_XML_TXTM) {
 425             V3_Free(attr[(i * 2) + 1]);
 426         }
 427     }
 428
 429     V3_Free(m);
 430     V3_Free(attr);
 431 }
 432
 433
 434
 435
 436
 437
 438 // returns a new empty v3_xml structure with the given root tag name
 439 static struct v3_xml * v3_xml_new(const char * name) {
 440     static char * ent[] = { "lt;", "&#60;", "gt;", "&#62;", "quot;", "&#34;",
 441                            "apos;", "&#39;", "amp;", "&#38;", NULL };
 442
 443     struct v3_xml_root * root = (struct v3_xml_root *)V3_Malloc(sizeof(struct v3_xml_root));
 444     memset(root, 0, sizeof(struct v3_xml_root));
 445
 446     root->xml.name = (char *)name;
 447     root->cur = &root->xml;
 448     root->xml.txt = "";
 449     memset(root->err, 0, V3_XML_ERRL);
 450
 451     root->ent = V3_Malloc(sizeof(ent));
 452     memcpy(root->ent, ent, sizeof(ent));
 453
 454     root->xml.attr = empty_attrib_list;
 455     root->attr = (char ***)(empty_attrib_list);
 456
 457     return &root->xml;
 458 }
 459
 460 // inserts an existing tag into an v3_xml structure
 461 struct v3_xml * v3_xml_insert(struct v3_xml * xml, struct v3_xml * dest, size_t off) {
 462     struct v3_xml * cur, * prev, * head;
 463
 464     xml->next = NULL;
 465     xml->sibling = NULL;
 466     xml->ordered = NULL;
 467
 468     xml->off = off;
 469     xml->parent = dest;
 470
 471     if ((head = dest->child)) {
 472         // already have sub tags
 473
 474         if (head->off <= off) {
 475             // not first subtag
 476
 477             for (cur = head;
 478                  ((cur->ordered) && (cur->ordered->off <= off));
 479                  cur = cur->ordered);
 480
 481             xml->ordered = cur->ordered;
 482             cur->ordered = xml;
 483         } else {
 484             // first subtag
 485             xml->ordered = head;
 486             dest->child = xml;
 487         }
 488
 489         // find tag type
 490         for (cur = head, prev = NULL;
 491              ((cur) && (strcasecmp(cur->name, xml->name) != 0));
 492              prev = cur, cur = cur->sibling);
 493
 494
 495         if (cur && cur->off <= off) {
 496             // not first of type
 497
 498             while (cur->next && cur->next->off <= off) {
 499                 cur = cur->next;
 500             }
 501
 502             xml->next = cur->next;
 503             cur->next = xml;
 504         } else {
 505             // first tag of this type
 506
 507             if (prev && cur) {
 508                 // remove old first
 509                 prev->sibling = cur->sibling;
 510             }
 511
 512             xml->next = cur; // old first tag is now next
 513
 514             // new sibling insert point
 515             for (cur = head, prev = NULL;
 516                  ((cur) && (cur->off <= off));
 517                  prev = cur, cur = cur->sibling);
 518
 519             xml->sibling = cur;
 520
 521             if (prev) {
 522                 prev->sibling = xml;
 523             }
 524         }
 525     } else {
 526         // only sub tag
 527         dest->child = xml;
 528     }
 529
 530     return xml;
 531 }
 532
 533
 534 // Adds a child tag. off is the offset of the child tag relative to the start
 535 // of the parent tag's character content. Returns the child tag.
 536 static struct v3_xml * v3_xml_add_child(struct v3_xml * xml, const char * name, size_t off) {
 537     struct v3_xml * child;
 538
 539     if (xml == NULL) {
 540         return NULL;
 541     }
 542
 543     child = (struct v3_xml *)V3_Malloc(sizeof(struct v3_xml));
 544     memset(child, 0, sizeof(struct v3_xml));
 545
 546     child->name = (char *)name;
 547     child->attr = empty_attrib_list;
 548     child->txt = "";
 549
 550     return v3_xml_insert(child, xml, off);
 551 }
 552
 553
 554 // called when parser finds start of new tag
 555 static void v3_xml_open_tag(struct v3_xml_root * root, char * name, char ** attr) {
 556     struct v3_xml * xml = root->cur;
 557
 558     if (xml->name) {
 559         xml = v3_xml_add_child(xml, name, strlen(xml->txt));
 560     } else {
 561         // first open tag
 562         xml->name = name;
 563     }
 564
 565     xml->attr = attr;
 566     root->cur = xml; // update tag insertion point
 567 }
 568
 569
 570
 571
 572
 573
 574
 575 // parse the given xml string and return an v3_xml structure
 576 static struct v3_xml * parse_str(char * buf, size_t len) {
 577     struct v3_xml_root * root = (struct v3_xml_root *)v3_xml_new(NULL);
 578     char quote_char;
 579     char last_char;
 580     char * tag_ptr;
 581     char ** attr;
 582     char ** tmp_attr = NULL; // initialize a to avoid compile warning
 583     int attr_idx;
 584     int i, j;
 585
 586     root->str_ptr = buf;
 587
 588     if (len == 0) {
 589         v3_xml_err(root, NULL, "Empty XML String\n");
 590         return NULL;
 591     }
 592
 593     root->tmp_start = buf;
 594     root->tmp_end = buf + len; // record start and end of work area
 595
 596     last_char = buf[len - 1]; // save end char
 597     buf[len - 1] = '\0'; // turn end char into null terminator
 598
 599     while ((*buf) && (*buf != '<')) {
 600         // find first tag
 601         buf++;
 602     }
 603
 604     if (*buf == '\0') {
 605         v3_xml_err(root, buf, "root tag missing");
 606         return NULL;
 607     }
 608
 609     for (; ; ) {
 610         attr = (char **)empty_attrib_list;
 611         tag_ptr = ++buf; // skip first '<'
 612
 613         if (isalpha(*buf) || (*buf == '_') || (*buf == ':') || (*buf < '\0')) {
 614             // new tag
 615
 616             if (root->cur == NULL) {
 617                 v3_xml_err(root, tag_ptr, "markup outside of root element");
 618                 return NULL;
 619             }
 620
 621             buf += strcspn(buf, V3_XML_WS "/>");
 622
 623             while (isspace(*buf)) {
 624                 // null terminate tag name,
 625                 // this writes '\0' to spaces after first tag
 626                 *(buf++) = '\0';
 627             }
 628
 629             // check if attribute follows tag
 630             if ((*buf) && (*buf != '/') && (*buf != '>')) {
 631                 // there is an attribute
 632                 // find attributes for correct tag
 633                 for ((i = 0);
 634                      ((tmp_attr = root->attr[i]) &&
 635                       (strcasecmp(tmp_attr[0], tag_ptr) != 0));
 636                      (i++)) ;
 637
 638                 // 'tmp_attr' now points to the attribute list associated with 'tag_ptr'
 639             }
 640
 641             // attributes are name value pairs,
 642             //     2nd to last entry is null  (end of list)
 643             //     last entry points to a string map marking whether values have been malloced...
 644             // loop through attributes until hitting the closing bracket
 645             for (attr_idx = 0;
 646                  (*buf) && (*buf != '/') && (*buf != '>');
 647                  attr_idx += 2) {
 648                 // buf is incremented later on
 649                 // new attrib
 650                 int attr_cnt = (attr_idx / 2) + 1;
 651                 int val_idx = attr_idx + 1;
 652                 int term_idx = attr_idx + 2;
 653                 int last_idx = attr_idx + 3;
 654
 655                 // attr = allocated space
 656                 // attr[val_idx] = mem for list of maloced vals
 657                 if (attr_cnt > 1) {
 658                     attr = tmp_realloc(attr,
 659                                        (((attr_cnt - 1) * (2 * sizeof(char *))) +
 660                                         (2 * sizeof(char *))),
 661                                        ((attr_cnt * (2 * sizeof(char *))) +
 662                                         (2 * sizeof(char *))));
 663
 664                     attr[last_idx] = tmp_realloc(attr[last_idx - 2],
 665                                                  attr_cnt,
 666                                                  (attr_cnt + 1));
 667                 } else {
 668                     attr = V3_Malloc(4 * sizeof(char *));
 669                     attr[last_idx] = V3_Malloc(2);
 670                 }
 671
 672
 673                 attr[attr_idx] = buf; // set attribute name
 674                 attr[val_idx] = ""; // temporary attribute value
 675                 attr[term_idx] = NULL; // null terminate list
 676                 strcpy(attr[last_idx] + attr_cnt, " "); // value is not malloc'd, offset into the stringmap
 677
 678                 buf += strcspn(buf, V3_XML_WS "=/>");
 679
 680                 if ((*buf == '=') || isspace(*buf)) {
 681
 682                     *(buf++) = '\0'; // null terminate tag attribute name
 683
 684                     // eat whitespace (and more multiple '=' ?)
 685                     buf += strspn(buf, V3_XML_WS "=");
 686
 687                     quote_char = *buf;
 688
 689                     if ((quote_char == '"') || (quote_char == '\'')) { // attribute value
 690                         attr[val_idx] = ++buf;
 691
 692                         while ((*buf) && (*buf != quote_char)) {
 693                             buf++;
 694                         }
 695
 696                         if (*buf) {
 697                             // null terminate attribute val
 698                             *(buf++) = '\0';
 699                         } else {
 700                             v3_xml_free_attr(attr);
 701                             v3_xml_err(root, tag_ptr, "missing %c", quote_char);
 702                             return NULL;
 703                         }
 704
 705                         for (j = 1;
 706                              ( (tmp_attr) && (tmp_attr[j]) &&
 707                                (strcasecmp(tmp_attr[j], attr[attr_idx]) != 0));
 708                              j += 3);
 709
 710                         attr[val_idx] = v3_xml_decode(attr[val_idx], root->ent,
 711                                                       ((tmp_attr && tmp_attr[j]) ?
 712                                                        *tmp_attr[j + 2] :
 713                                                        ' '));
 714
 715                         if ( (attr[val_idx] < tag_ptr) ||
 716                              (attr[val_idx] > buf) ) {
 717                             attr[last_idx][attr_cnt - 1] = V3_XML_TXTM; // value malloced
 718                         }
 719                     }
 720                 }
 721
 722                 while (isspace(*buf)) {
 723                     buf++;
 724                 }
 725             }
 726
 727             if (*buf == '/') {
 728                 // self closing tag
 729                 *(buf++) = '\0';
 730
 731                 if ( ((*buf) && (*buf != '>')) ||
 732                      ((!*buf) && (last_char != '>'))) {
 733
 734                     if (attr_idx > 0) {
 735                         v3_xml_free_attr(attr);
 736                     }
 737                     v3_xml_err(root, tag_ptr, "missing >");
 738                     return NULL;
 739                 }
 740                 v3_xml_open_tag(root, tag_ptr, attr);
 741                 v3_xml_close_tag(root, tag_ptr, buf);
 742             } else if (((quote_char = *buf) == '>') ||
 743                        ((!*buf) && (last_char == '>'))) {
 744                 // open tag
 745                 *buf = '\0'; // temporarily null terminate tag name
 746                 v3_xml_open_tag(root, tag_ptr, attr);
 747                 *buf = quote_char;
 748             } else {
 749                 if (attr_idx > 0) {
 750                     v3_xml_free_attr(attr);
 751                 }
 752                 v3_xml_err(root, tag_ptr, "missing >");
 753                 return NULL;
 754             }
 755         } else if (*buf == '/') {
 756             // close tag
 757
 758             buf += strcspn(tag_ptr = buf + 1, V3_XML_WS ">") + 1;
 759
 760             quote_char = *buf;
 761             if ((*buf == '\0') && (last_char != '>')) {
 762                 v3_xml_err(root, tag_ptr, "missing >");
 763                 return NULL;
 764             }
 765
 766             *buf = '\0'; // temporarily null terminate tag name
 767
 768             if (v3_xml_close_tag(root, tag_ptr, buf) == -1) {
 769                 return NULL;
 770             }
 771
 772             *buf = quote_char;
 773             if (isspace(*buf)) {
 774                 buf += strspn(buf, V3_XML_WS);
 775             }
 776         } else if (strncmp(buf, "!--", 3) == 0) {
 777             // xml comment
 778             if ( ((buf = strstr(buf + 3, "--")) == 0) ||
 779                  ((*(buf += 2) != '>') && (*buf)) ||
 780                  ((!*buf) && (last_char != '>'))) {
 781                 v3_xml_err(root, tag_ptr, "unclosed <!--");
 782                 return NULL;
 783             }
 784         } else if (! strncmp(buf, "![CDATA[", 8)) {
 785             // cdata
 786             if ((buf = strstr(buf, "]]>"))) {
 787                 v3_xml_char_content(root, tag_ptr + 8, (buf += 2) - tag_ptr - 10, 'c');
 788             } else {
 789                 v3_xml_err(root, tag_ptr, "unclosed <![CDATA[");
 790                 return NULL;
 791             }
 792         } else {
 793             v3_xml_err(root, tag_ptr, "unexpected <");
 794             return NULL;
 795         }
 796
 797         if (! buf || ! *buf) {
 798             break;
 799         }
 800
 801         *buf = '\0';
 802         tag_ptr = ++buf;
 803
 804         if (*buf && (*buf != '<')) {
 805             // tag character content
 806             while (*buf && (*buf != '<')) {
 807                 buf++;
 808             }
 809
 810             if (*buf) {
 811                 v3_xml_char_content(root, tag_ptr, buf - tag_ptr, '&');
 812             } else {
 813                 break;
 814             }
 815         } else if (*buf == '\0') {
 816             break;
 817         }
 818     }
 819
 820     if (root->cur == NULL) {
 821         return &root->xml;
 822     } else if (root->cur->name == NULL) {
 823         v3_xml_err(root, tag_ptr, "root tag missing");
 824         return NULL;
 825     } else {
 826         v3_xml_err(root, tag_ptr, "unclosed tag <%s>", root->cur->name);
 827         return NULL;
 828     }
 829 }
 830
 831
 832 struct v3_xml * v3_xml_parse(char * buf) {
 833     int str_len = 0;
 834     char * xml_buf = NULL;
 835
 836     if (!buf) {
 837         return NULL;
 838     }
 839
 840     str_len = strlen(buf);
 841     xml_buf = (char *)V3_Malloc(str_len + 1);
 842     strcpy(xml_buf, buf);
 843
 844     return parse_str(xml_buf, str_len);
 845 }
 846
 847
 848
 849 // free the memory allocated for the v3_xml structure
 850 void v3_xml_free(struct v3_xml * xml) {
 851     struct v3_xml_root * root = (struct v3_xml_root *)xml;
 852     int i, j;
 853     char **a, *s;
 854
 855     if (xml == NULL) {
 856         return;
 857     }
 858
 859     v3_xml_free(xml->child);
 860     v3_xml_free(xml->ordered);
 861
 862     if (xml->parent == NULL) {
 863         // free root tag allocations
 864
 865         for (i = 10; root->ent[i]; i += 2) {
 866             // 0 - 9 are default entites (<>&"')
 867             if ((s = root->ent[i + 1]) < root->tmp_start || s > root->tmp_end) {
 868                 V3_Free(s);
 869             }
 870         }
 871
 872         V3_Free(root->ent); // free list of general entities
 873
 874         for (i = 0; (a = root->attr[i]); i++) {
 875             for (j = 1; a[j++]; j += 2) {
 876                 // free malloced attribute values
 877                 if (a[j] && (a[j] < root->tmp_start || a[j] > root->tmp_end)) {
 878                     V3_Free(a[j]);
 879                 }
 880             }
 881             V3_Free(a);
 882         }
 883
 884         if (root->attr[0]) {
 885             // free default attribute list
 886             V3_Free(root->attr);
 887         }
 888
 889         V3_Free(root->str_ptr); // malloced xml data
 890     }
 891
 892     v3_xml_free_attr(xml->attr); // tag attributes
 893
 894     if ((xml->flags & V3_XML_TXTM)) {
 895         // character content
 896         V3_Free(xml->txt);
 897     }
 898
 899     if ((xml->flags & V3_XML_NAMEM)) {
 900         // tag name
 901         V3_Free(xml->name);
 902     }
 903
 904     V3_Free(xml);
 905 }
 906
 907
 908
 909
 910
 911
 912
 913 // sets the character content for the given tag and returns the tag
 914 struct v3_xml *  v3_xml_set_txt(struct v3_xml * xml, const char *txt) {
 915     if (! xml) {
 916         return NULL;
 917     }
 918
 919     if (xml->flags & V3_XML_TXTM) {
 920         // existing txt was malloced
 921         V3_Free(xml->txt);
 922     }
 923
 924     xml->flags &= ~V3_XML_TXTM;
 925     xml->txt = (char *)txt;
 926     return xml;
 927 }
 928
 929 // Sets the given tag attribute or adds a new attribute if not found. A value
 930 // of NULL will remove the specified attribute. Returns the tag given.
 931 struct v3_xml * v3_xml_set_attr(struct v3_xml * xml, const char * name, const char * value) {
 932     int l = 0;
 933     int c;
 934
 935     if (! xml) {
 936         return NULL;
 937     }
 938
 939     while (xml->attr[l] && strcmp(xml->attr[l], name)) {
 940         l += 2;
 941     }
 942
 943     if (! xml->attr[l]) {
 944         // not found, add as new attribute
 945
 946         if (! value) {
 947             // nothing to do
 948             return xml;
 949         }
 950
 951         if (xml->attr == V3_XML_NIL) {
 952             // first attribute
 953             xml->attr = V3_Malloc(4 * sizeof(char *));
 954
 955             // empty list of malloced names/vals
 956             xml->attr[1] = strdup("");
 957         } else {
 958             xml->attr = tmp_realloc(xml->attr, l * sizeof(char *), (l + 4) * sizeof(char *));
 959         }
 960
 961         // set attribute name
 962         xml->attr[l] = (char *)name;
 963
 964         // null terminate attribute list
 965         xml->attr[l + 2] = NULL;
 966
 967         xml->attr[l + 3] = tmp_realloc(xml->attr[l + 1],
 968                                        strlen(xml->attr[l + 1]),
 969                                        (c = strlen(xml->attr[l + 1])) + 2);
 970
 971         // set name/value as not malloced
 972         strcpy(xml->attr[l + 3] + c, " ");
 973
 974         if (xml->flags & V3_XML_DUP) {
 975             xml->attr[l + 3][c] = V3_XML_NAMEM;
 976         }
 977     } else if (xml->flags & V3_XML_DUP) {
 978         // name was strduped
 979         V3_Free((char *)name);
 980     }
 981
 982
 983     // find end of attribute list
 984     for (c = l; xml->attr[c]; c += 2);
 985
 986     if (xml->attr[c + 1][l / 2] & V3_XML_TXTM) {
 987         //old val
 988         V3_Free(xml->attr[l + 1]);
 989     }
 990
 991     if (xml->flags & V3_XML_DUP) {
 992         xml->attr[c + 1][l / 2] |= V3_XML_TXTM;
 993     } else {
 994         xml->attr[c + 1][l / 2] &= ~V3_XML_TXTM;
 995     }
 996
 997
 998     if (value) {
 999         // set attribute value
1000         xml->attr[l + 1] = (char *)value;
1001     } else {
1002         // remove attribute
1003
1004         if (xml->attr[c + 1][l / 2] & V3_XML_NAMEM) {
1005             V3_Free(xml->attr[l]);
1006         }
1007
1008         memmove(xml->attr + l, xml->attr + l + 2, (c - l + 2) * sizeof(char*));
1009
1010         xml->attr = tmp_realloc(xml->attr, c * sizeof(char *), (c + 2) * sizeof(char *));
1011
1012         // fix list of which name/vals are malloced
1013         memmove(xml->attr[c + 1] + (l / 2), xml->attr[c + 1] + (l / 2) + 1,
1014                 (c / 2) - (l / 2));
1015     }
1016
1017     // clear strdup() flag
1018     xml->flags &= ~V3_XML_DUP;
1019
1020     return xml;
1021 }
1022
1023 // removes a tag along with its subtags without freeing its memory
1024 struct v3_xml * v3_xml_cut(struct v3_xml * xml) {
1025     struct v3_xml * cur;
1026
1027     if (! xml) {
1028         // nothing to do
1029         return NULL;
1030     }
1031
1032     if (xml->next) {
1033         // patch sibling list
1034         xml->next->sibling = xml->sibling;
1035     }
1036
1037
1038     if (xml->parent) {
1039         // not root tag
1040
1041         // find head of subtag list
1042         cur = xml->parent->child;
1043
1044         if (cur == xml) {
1045             // first subtag
1046             xml->parent->child = xml->ordered;
1047         } else {
1048         // not first subtag
1049
1050             while (cur->ordered != xml) {
1051                 cur = cur->ordered;
1052             }
1053
1054             // patch ordered list
1055             cur->ordered = cur->ordered->ordered;
1056
1057             // go back to head of subtag list
1058             cur = xml->parent->child;
1059
1060             if (strcmp(cur->name, xml->name)) {
1061                 // not in first sibling list
1062
1063                 while (strcmp(cur->sibling->name, xml->name)) {
1064                     cur = cur->sibling;
1065                 }
1066
1067                 if (cur->sibling == xml) {
1068                     // first of a sibling list
1069                     cur->sibling = (xml->next) ? xml->next
1070                                                : cur->sibling->sibling;
1071                 } else {
1072                     // not first of a sibling list
1073                     cur = cur->sibling;
1074                 }
1075             }
1076
1077             while (cur->next && cur->next != xml) {
1078                 cur = cur->next;
1079             }
1080
1081             if (cur->next) {
1082                 // patch next list
1083                 cur->next = cur->next->next;
1084             }
1085         }
1086    }
1087     xml->ordered = xml->sibling = xml->next = NULL;
1088     return xml;
1089 }
1090
1091
1092
1093
1094 /* ************************** */
1095 /* *** XML ENCODING       *** */
1096 /* ************************** */
1097
1098 // Encodes ampersand sequences appending the results to *dst, reallocating *dst
1099 // if length excedes max. a is non-zero for attribute encoding. Returns *dst
1100 static char *ampencode(const char *s, size_t len, char **dst, size_t *dlen,
1101                       size_t * max, short a)
1102 {
1103     const char * e;
1104
1105     for (e = s + len; s != e; s++) {
1106         while (*dlen + 10 > *max) {
1107             *dst = tmp_realloc(*dst, *max, *max + V3_XML_BUFSIZE);
1108             *max += V3_XML_BUFSIZE;
1109         }
1110
1111         switch (*s) {
1112         case '\0': return *dst;
1113         case '&': *dlen += sprintf(*dst + *dlen, "&amp;"); break;
1114         case '<': *dlen += sprintf(*dst + *dlen, "&lt;"); break;
1115         case '>': *dlen += sprintf(*dst + *dlen, "&gt;"); break;
1116         case '"': *dlen += sprintf(*dst + *dlen, (a) ? "&quot;" : "\""); break;
1117         case '\n': *dlen += sprintf(*dst + *dlen, (a) ? "&#xA;" : "\n"); break;
1118         case '\t': *dlen += sprintf(*dst + *dlen, (a) ? "&#x9;" : "\t"); break;
1119         case '\r': *dlen += sprintf(*dst + *dlen, "&#xD;"); break;
1120         default: (*dst)[(*dlen)++] = *s;
1121         }
1122     }
1123     return *dst;
1124 }
1125
1126
1127
1128 // Recursively converts each tag to xml appending it to *s. Reallocates *s if
1129 // its length excedes max. start is the location of the previous tag in the
1130 // parent tag's character content. Returns *s.
1131 static char *toxml_r(struct v3_xml * xml, char **s, size_t *len, size_t *max,
1132                     size_t start, char ***attr) {
1133     int i, j;
1134     char *txt = (xml->parent) ? xml->parent->txt : "";
1135     size_t off = 0;
1136
1137     // parent character content up to this tag
1138     *s = ampencode(txt + start, xml->off - start, s, len, max, 0);
1139
1140     while (*len + strlen(xml->name) + 4 > *max) {
1141         // reallocate s
1142         *s = tmp_realloc(*s, *max, *max + V3_XML_BUFSIZE);
1143         *max += V3_XML_BUFSIZE;
1144     }
1145
1146
1147     *len += sprintf(*s + *len, "<%s", xml->name); // open tag
1148     for (i = 0; xml->attr[i]; i += 2) { // tag attributes
1149         if (v3_xml_attr(xml, xml->attr[i]) != xml->attr[i + 1]) continue;
1150         while (*len + strlen(xml->attr[i]) + 7 > *max) {
1151             // reallocate s
1152             *s = tmp_realloc(*s, *max, *max + V3_XML_BUFSIZE);
1153             *max += V3_XML_BUFSIZE;
1154         }
1155
1156         *len += sprintf(*s + *len, " %s=\"", xml->attr[i]);
1157         ampencode(xml->attr[i + 1], -1, s, len, max, 1);
1158         *len += sprintf(*s + *len, "\"");
1159     }
1160
1161     for (i = 0; attr[i] && strcmp(attr[i][0], xml->name); i++);
1162     for (j = 1; attr[i] && attr[i][j]; j += 3) { // default attributes
1163         if (! attr[i][j + 1] || v3_xml_attr(xml, attr[i][j]) != attr[i][j + 1])
1164             continue; // skip duplicates and non-values
1165         while (*len + strlen(attr[i][j]) + 7 > *max) {
1166             // reallocate s
1167             *s = tmp_realloc(*s, *max, *max + V3_XML_BUFSIZE);
1168             *max += V3_XML_BUFSIZE;
1169         }
1170
1171         *len += sprintf(*s + *len, " %s=\"", attr[i][j]);
1172         ampencode(attr[i][j + 1], -1, s, len, max, 1);
1173         *len += sprintf(*s + *len, "\"");
1174     }
1175     *len += sprintf(*s + *len, ">");
1176
1177     *s = (xml->child) ? toxml_r(xml->child, s, len, max, 0, attr) //child
1178                       : ampencode(xml->txt, -1, s, len, max, 0);  //data
1179
1180     while (*len + strlen(xml->name) + 4 > *max) {
1181         // reallocate s
1182         *s = tmp_realloc(*s, *max, *max + V3_XML_BUFSIZE);
1183         *max += V3_XML_BUFSIZE;
1184     }
1185
1186     *len += sprintf(*s + *len, "</%s>", xml->name); // close tag
1187
1188     while (txt[off] && off < xml->off) off++; // make sure off is within bounds
1189     return (xml->ordered) ? toxml_r(xml->ordered, s, len, max, off, attr)
1190                           : ampencode(txt + off, -1, s, len, max, 0);
1191 }
1192
1193 // Converts an xml structure back to xml. Returns a string of xml data that
1194 // must be freed.
1195 char * v3_xml_tostr(struct v3_xml * xml) {
1196     struct v3_xml * p = (xml) ? xml->parent : NULL;
1197     struct v3_xml * o = (xml) ? xml->ordered : NULL;
1198     struct v3_xml_root * root = (struct v3_xml_root *)xml;
1199     size_t len = 0, max = V3_XML_BUFSIZE;
1200     char *s = strcpy(V3_Malloc(max), "");
1201
1202     if (! xml || ! xml->name) return tmp_realloc(s, max, len + 1);
1203     while (root->xml.parent) root = (struct v3_xml_root *)root->xml.parent; // root tag
1204
1205
1206     xml->parent = xml->ordered = NULL;
1207     s = toxml_r(xml, &s, &len, &max, 0, root->attr);
1208     xml->parent = p;
1209     xml->ordered = o;
1210
1211
1212     return tmp_realloc(s, max, len + 1);
1213 }