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