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