src/patch/nad.c

   1 /*
   2  * jabberd - Jabber Open Source Server
   3  * Copyright (c) 2002 Jeremie Miller, Thomas Muldowney,
   4  *                    Ryan Eatmon, Robert Norris
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA02111-1307USA
  19  */
  20
  21
  22 /** ! ! ! Patched version to fix segfault issue for jabberd-2.0s4 ! ! ! */
  23
  24 /**
  25  * !!! Things to do (after 2.0)
  26  *
  27  * - make nad_find_scoped_namespace() take an element index, and only search
  28  *   the scope on that element (currently, it searchs all elements from
  29  *   end to start, which isn't really correct, though it works in most cases
  30  *
  31  * - new functions:
  32  *     * insert one nad (or part thereof) into another nad
  33  *     * clear a part of a nad (like xmlnode_hide)
  34  *
  35  * - audit use of depth array and parent (see j2 bug #792)
  36  */
  37
  38 #include "util.h"
  39
  40 #ifdef HAVE_EXPAT
  41 #include "expat/expat.h"
  42 #endif
  43
  44 /* define NAD_DEBUG to get pointer tracking - great for weird bugs that you can't reproduce */
  45 #ifdef NAD_DEBUG
  46
  47 static xht _nad_alloc_tracked = NULL;
  48 static xht _nad_free_tracked = NULL;
  49
  50 static void _nad_ptr_check(const char *func, nad_t nad) {
  51     char loc[24];
  52     snprintf(loc, sizeof(loc), "%x", (int) nad);
  53
  54     if(xhash_get(_nad_alloc_tracked, loc) == NULL) {
  55         fprintf(stderr, ">>> NAD OP %s: 0x%x not allocated!\n", func, (int) nad);
  56         abort();
  57     }
  58
  59     if(xhash_get(_nad_free_tracked, loc) != NULL) {
  60         fprintf(stderr, ">>> NAD OP %s: 0x%x previously freed!\n", func, (int) nad);
  61         abort();
  62     }
  63
  64     fprintf(stderr, ">>> NAD OP %s: 0x%x\n", func, (int) nad);
  65 }
  66 #else
  67 #define _nad_ptr_check(func,nad)
  68 #endif
  69
  70 #define BLOCKSIZE 1024
  71
  72 /** internal: do and return the math and ensure it gets realloc'd */
  73 int _nad_realloc(void **oblocks, int len)
  74 {
  75     void *nblocks;
  76     int nlen;
  77
  78     /* round up to standard block sizes */
  79     nlen = (((len-1)/BLOCKSIZE)+1)*BLOCKSIZE;
  80
  81     /* keep trying till we get it */
  82     while((nblocks = realloc(*oblocks, nlen)) == NULL) sleep(1);
  83     *oblocks = nblocks;
  84     return nlen;
  85 }
  86
  87 /** this is the safety check used to make sure there's always enough mem */
  88 #define NAD_SAFE(blocks, size, len) if((size) > len) len = _nad_realloc((void**)&(blocks),(size));
  89
  90 /** internal: append some cdata and return the index to it */
  91 int _nad_cdata(nad_t nad, const char *cdata, int len)
  92 {
  93     NAD_SAFE(nad->cdata, nad->ccur + len, nad->clen);
  94
  95     memcpy(nad->cdata + nad->ccur, cdata, len);
  96     nad->ccur += len;
  97     return nad->ccur - len;
  98 }
  99
 100 /** internal: create a new attr on any given elem */
 101 int _nad_attr(nad_t nad, int elem, int ns, const char *name, const char *val, int vallen)
 102 {
 103     int attr;
 104
 105     /* make sure there's mem for us */
 106     NAD_SAFE(nad->attrs, (nad->acur + 1) * sizeof(struct nad_attr_st), nad->alen);
 107
 108     attr = nad->acur;
 109     nad->acur++;
 110     nad->attrs[attr].next = nad->elems[elem].attr;
 111     nad->elems[elem].attr = attr;
 112     nad->attrs[attr].lname = strlen(name);
 113     nad->attrs[attr].iname = _nad_cdata(nad,name,nad->attrs[attr].lname);
 114     if(vallen > 0)
 115         nad->attrs[attr].lval = vallen;
 116     else
 117         nad->attrs[attr].lval = strlen(val);
 118     nad->attrs[attr].ival = _nad_cdata(nad,val,nad->attrs[attr].lval);
 119     nad->attrs[attr].my_ns = ns;
 120
 121     return attr;
 122 }
 123
 124 /** create a new cache, simple pointer to a list of nads */
 125 nad_cache_t nad_cache_new(void)
 126 {
 127     nad_cache_t cache;
 128     while((cache = malloc(sizeof(nad_cache_t))) == NULL) sleep(1);
 129     *cache = NULL;
 130
 131 #ifdef NAD_DEBUG
 132     if(_nad_alloc_tracked == NULL) _nad_alloc_tracked = xhash_new(501);
 133     if(_nad_free_tracked == NULL) _nad_free_tracked = xhash_new(501);
 134 #endif
 135
 136     return cache;
 137 }
 138
 139
 140 /** free the cache and any nads in it */
 141 void nad_cache_free(nad_cache_t cache)
 142 {
 143     nad_t cur;
 144     while((cur = *cache) != NULL)
 145     {
 146         *cache = cur->next;
 147         free(cur->elems);
 148         free(cur->attrs);
 149         free(cur->nss);
 150         free(cur->cdata);
 151         free(cur->depths);
 152         free(cur);
 153     }
 154     free(cache);
 155 }
 156
 157 /** get the next nad from the cache, or create some */
 158 nad_t nad_new(nad_cache_t cache)
 159 {
 160     nad_t nad;
 161
 162 #ifndef NAD_DEBUG
 163     /* If cache==NULL, then this NAD is not in a cache */
 164
 165     if ((cache!=NULL) && (*cache != NULL))
 166     {
 167         nad = *cache;
 168         *cache = nad->next;
 169         nad->ccur = nad->ecur = nad->acur = nad->ncur = 0;
 170         nad->scope = -1;
 171         nad->cache = cache;
 172         nad->next = NULL;
 173         return nad;
 174     }
 175 #endif
 176
 177     while((nad = malloc(sizeof(struct nad_st))) == NULL) sleep(1);
 178     memset(nad,0,sizeof(struct nad_st));
 179
 180     nad->scope = -1;
 181     nad->cache = cache;
 182
 183 #ifdef NAD_DEBUG
 184     {
 185     char loc[24];
 186     snprintf(loc, sizeof(loc), "%x", (int) nad);
 187     xhash_put(_nad_alloc_tracked, pstrdup(xhash_pool(_nad_alloc_tracked), loc), (void *) 1);
 188     }
 189     _nad_ptr_check(__func__, nad);
 190 #endif
 191
 192     return nad;
 193 }
 194
 195 nad_t nad_copy(nad_t nad)
 196 {
 197     nad_t copy;
 198
 199     _nad_ptr_check(__func__, nad);
 200
 201     if(nad == NULL) return NULL;
 202
 203     /* create a new nad not participating in a cache */
 204     copy = nad_new(NULL);
 205
 206     /* if it's not large enough, make bigger */
 207     NAD_SAFE(copy->elems, nad->elen, copy->elen);
 208     NAD_SAFE(copy->attrs, nad->alen, copy->alen);
 209     NAD_SAFE(copy->nss, nad->nlen, copy->nlen);
 210     NAD_SAFE(copy->cdata, nad->clen, copy->clen);
 211
 212     /* copy all data */
 213     memcpy(copy->elems, nad->elems, nad->elen);
 214     memcpy(copy->attrs, nad->attrs, nad->alen);
 215     memcpy(copy->nss, nad->nss, nad->nlen);
 216     memcpy(copy->cdata, nad->cdata, nad->clen);
 217
 218     /* sync data */
 219     copy->ecur = nad->ecur;
 220     copy->acur = nad->acur;
 221     copy->ncur = nad->ncur;
 222     copy->ccur = nad->ccur;
 223
 224     copy->scope = nad->scope;
 225
 226     return copy;
 227 }
 228
 229 /** free nad, or plug nad back in the cache */
 230 void nad_free(nad_t nad)
 231 {
 232     if(nad == NULL) return;
 233
 234 #ifdef NAD_DEBUG
 235     _nad_ptr_check(__func__, nad);
 236     {
 237     char loc[24];
 238     snprintf(loc, sizeof(loc), "%x", (int) nad);
 239     xhash_zap(_nad_alloc_tracked, loc);
 240     xhash_put(_nad_free_tracked, pstrdup(xhash_pool(_nad_free_tracked), loc), (void *) nad);
 241     }
 242 #else
 243     /* If nad->cache != NULL, then put back into cache, otherwise this nad is not in a cache */
 244
 245     if (nad->cache != NULL) {
 246        nad->next = *(nad->cache);
 247        *(nad->cache) = nad;
 248        return;
 249     }
 250 #endif
 251
 252     /* Free nad */
 253     free(nad->elems);
 254     free(nad->attrs);
 255     free(nad->cdata);
 256     free(nad->nss);
 257     free(nad->depths);
 258 }
 259
 260 /** locate the next elem at a given depth with an optional matching name */
 261 int nad_find_elem(nad_t nad, int elem, int ns, const char *name, int depth)
 262 {
 263     int my_ns;
 264     int lname = 0;
 265
 266     _nad_ptr_check(__func__, nad);
 267
 268     /* make sure there are valid args */
 269     if(elem >= nad->ecur || name == NULL) return -1;
 270
 271     /* set up args for searching */
 272     depth = nad->elems[elem].depth + depth;
 273     if(name != NULL) lname = strlen(name);
 274
 275     /* search */
 276     for(elem++;elem < nad->ecur;elem++)
 277     {
 278         /* if we hit one with a depth less than ours, then we don't have the
 279          * same parent anymore, bail */
 280         if(nad->elems[elem].depth < depth)
 281             return -1;
 282
 283         if(nad->elems[elem].depth == depth && (lname <= 0 || (lname == nad->elems[elem].lname && strncmp(name,nad->cdata + nad->elems[elem].iname, lname) == 0)) &&
 284           (ns < 0 || ((my_ns = nad->elems[elem].my_ns) >= 0 && NAD_NURI_L(nad, ns) == NAD_NURI_L(nad, my_ns) && strncmp(NAD_NURI(nad, ns), NAD_NURI(nad, my_ns), NAD_NURI_L(nad, ns)) == 0)))
 285             return elem;
 286     }
 287
 288     return -1;
 289 }
 290
 291 /** get a matching attr on this elem, both name and optional val */
 292 int nad_find_attr(nad_t nad, int elem, int ns, const char *name, const char *val)
 293 {
 294     int attr, my_ns;
 295     int lname, lval = 0;
 296
 297     _nad_ptr_check(__func__, nad);
 298
 299     /* make sure there are valid args */
 300     if(elem >= nad->ecur || name == NULL) return -1;
 301
 302     attr = nad->elems[elem].attr;
 303     lname = strlen(name);
 304     if(val != NULL) lval = strlen(val);
 305
 306     while(attr >= 0)
 307     {
 308         /* hefty, match name and if a val, also match that */
 309         if(lname == nad->attrs[attr].lname && strncmp(name,nad->cdata + nad->attrs[attr].iname, lname) == 0 &&
 310           (lval <= 0 || (lval == nad->attrs[attr].lval && strncmp(val,nad->cdata + nad->attrs[attr].ival, lval) == 0)) &&
 311           (ns < 0 || ((my_ns = nad->attrs[attr].my_ns) >= 0 && NAD_NURI_L(nad, ns) == NAD_NURI_L(nad, my_ns) && strncmp(NAD_NURI(nad, ns), NAD_NURI(nad, my_ns), NAD_NURI_L(nad, ns)) == 0)))
 312             return attr;
 313         attr = nad->attrs[attr].next;
 314     }
 315     return -1;
 316 }
 317
 318 /** get a matching ns on this elem, both uri and optional prefix */
 319 int nad_find_namespace(nad_t nad, int elem, const char *uri, const char *prefix)
 320 {
 321     int check, ns;
 322
 323     _nad_ptr_check(__func__, nad);
 324
 325     if(uri == NULL)
 326         return -1;
 327
 328     /* work backwards through our parents, looking for our namespace on each one.
 329      * if we find it, link it. if not, the namespace is undeclared - for now, just drop it */
 330     check = elem;
 331     while(check >= 0)
 332     {
 333         ns = nad->elems[check].ns;
 334         while(ns >= 0)
 335         {
 336             if(strlen(uri) == NAD_NURI_L(nad, ns) && strncmp(uri, NAD_NURI(nad, ns), NAD_NURI_L(nad, ns)) == 0 && (prefix == NULL || (nad->nss[ns].iprefix >= 0 && strlen(prefix) == NAD_NPREFIX_L(nad, ns) && strncmp(prefix, NAD_NPREFIX(nad, ns), NAD_NPREFIX_L(nad, ns)) == 0)))
 337                 return ns;
 338             ns = nad->nss[ns].next;
 339         }
 340         check = nad->elems[check].parent;
 341     }
 342
 343     return -1;
 344 }
 345
 346 /** find a namespace in scope */
 347 int nad_find_scoped_namespace(nad_t nad, const char *uri, const char *prefix)
 348 {
 349     int ns;
 350
 351     _nad_ptr_check(__func__, nad);
 352
 353     if(uri == NULL)
 354         return -1;
 355
 356     for(ns = 0; ns < nad->ncur; ns++)
 357     {
 358         if(strlen(uri) == NAD_NURI_L(nad, ns) && strncmp(uri, NAD_NURI(nad, ns), NAD_NURI_L(nad, ns)) == 0 &&
 359            (prefix == NULL ||
 360              (nad->nss[ns].iprefix >= 0 &&
 361               strlen(prefix) == NAD_NPREFIX_L(nad, ns) && strncmp(prefix, NAD_NPREFIX(nad, ns), NAD_NPREFIX_L(nad, ns)) == 0)))
 362             return ns;
 363     }
 364
 365     return -1;
 366 }
 367
 368 /** create, update, or zap any matching attr on this elem */
 369 void nad_set_attr(nad_t nad, int elem, int ns, const char *name, const char *val, int vallen)
 370 {
 371     int attr;
 372
 373     _nad_ptr_check(__func__, nad);
 374
 375     /* find one to replace first */
 376     if((attr = nad_find_attr(nad, elem, ns, name, NULL)) < 0)
 377     {
 378         /* only create new if there's a value to store */
 379         if(val != NULL)
 380             _nad_attr(nad, elem, ns, name, val, vallen);
 381         return;
 382     }
 383
 384     /* got matching, update value or zap */
 385     if(val == NULL)
 386     {
 387         nad->attrs[attr].lval = nad->attrs[attr].lname = 0;
 388     }else{
 389         if(vallen > 0)
 390             nad->attrs[attr].lval = vallen;
 391         else
 392             nad->attrs[attr].lval = strlen(val);
 393         nad->attrs[attr].ival = _nad_cdata(nad,val,nad->attrs[attr].lval);
 394     }
 395
 396 }
 397
 398 /** shove in a new child elem after the given one */
 399 int nad_insert_elem(nad_t nad, int parent, int ns, const char *name, const char *cdata)
 400 {
 401     int elem = parent + 1;
 402
 403     _nad_ptr_check(__func__, nad);
 404
 405     NAD_SAFE(nad->elems, (nad->ecur + 1) * sizeof(struct nad_elem_st), nad->elen);
 406
 407     /* relocate all the rest of the elems (unless we're at the end already) */
 408     if(nad->ecur != elem)
 409         memmove(&nad->elems[elem + 1], &nad->elems[elem], (nad->ecur - elem) * sizeof(struct nad_elem_st));
 410     nad->ecur++;
 411
 412     /* set up req'd parts of new elem */
 413     nad->elems[elem].parent = parent;
 414     nad->elems[elem].lname = strlen(name);
 415     nad->elems[elem].iname = _nad_cdata(nad,name,nad->elems[elem].lname);
 416     nad->elems[elem].attr = -1;
 417     nad->elems[elem].ns = nad->scope; nad->scope = -1;
 418     nad->elems[elem].itail = nad->elems[elem].ltail = 0;
 419     nad->elems[elem].my_ns = ns;
 420
 421     /* add cdata if given */
 422     if(cdata != NULL)
 423     {
 424         nad->elems[elem].lcdata = strlen(cdata);
 425         nad->elems[elem].icdata = _nad_cdata(nad,cdata,nad->elems[elem].lcdata);
 426     }else{
 427         nad->elems[elem].icdata = nad->elems[elem].lcdata = 0;
 428     }
 429
 430     /* parent/child */
 431     nad->elems[elem].depth = nad->elems[parent].depth + 1;
 432
 433     return elem;
 434 }
 435
 436 /** wrap an element with another element */
 437 void nad_wrap_elem(nad_t nad, int elem, int ns, const char *name)
 438 {
 439     int cur;
 440
 441     _nad_ptr_check(__func__, nad);
 442
 443     if(elem >= nad->ecur) return;
 444
 445     NAD_SAFE(nad->elems, (nad->ecur + 1) * sizeof(struct nad_elem_st), nad->elen);
 446
 447     /* relocate all the rest of the elems after us */
 448     memmove(&nad->elems[elem + 1], &nad->elems[elem], (nad->ecur - elem) * sizeof(struct nad_elem_st));
 449     nad->ecur++;
 450
 451     /* set up req'd parts of new elem */
 452     nad->elems[elem].lname = strlen(name);
 453     nad->elems[elem].iname = _nad_cdata(nad,name,nad->elems[elem].lname);
 454     nad->elems[elem].attr = -1;
 455     nad->elems[elem].ns = nad->scope; nad->scope = -1;
 456     nad->elems[elem].itail = nad->elems[elem].ltail = 0;
 457     nad->elems[elem].icdata = nad->elems[elem].lcdata = 0;
 458     nad->elems[elem].my_ns = ns;
 459
 460     /* raise the bar on all the children */
 461     nad->elems[elem+1].depth++;
 462     for(cur = elem + 2; cur < nad->ecur && nad->elems[cur].depth > nad->elems[elem].depth; cur++) nad->elems[cur].depth++;
 463
 464     /* relink the parents */
 465     nad->elems[elem].parent = nad->elems[elem + 1].parent;
 466     nad->elems[elem + 1].parent = elem;
 467 }
 468
 469 /** create a new elem on the list */
 470 int nad_append_elem(nad_t nad, int ns, const char *name, int depth)
 471 {
 472     int elem;
 473
 474     _nad_ptr_check(__func__, nad);
 475
 476     /* make sure there's mem for us */
 477     NAD_SAFE(nad->elems, (nad->ecur + 1) * sizeof(struct nad_elem_st), nad->elen);
 478
 479     elem = nad->ecur;
 480     nad->ecur++;
 481     nad->elems[elem].lname = strlen(name);
 482     nad->elems[elem].iname = _nad_cdata(nad,name,nad->elems[elem].lname);
 483     nad->elems[elem].icdata = nad->elems[elem].lcdata = 0;
 484     nad->elems[elem].itail = nad->elems[elem].ltail = 0;
 485     nad->elems[elem].attr = -1;
 486     nad->elems[elem].ns = nad->scope; nad->scope = -1;
 487     nad->elems[elem].depth = depth;
 488     nad->elems[elem].my_ns = ns;
 489
 490     /* make sure there's mem in the depth array, then track us */
 491     NAD_SAFE(nad->depths, (depth + 1) * sizeof(int), nad->dlen);
 492     nad->depths[depth] = elem;
 493
 494     /* our parent is the previous guy in the depth array */
 495     if(depth <= 0)
 496         nad->elems[elem].parent = -1;
 497     else
 498         nad->elems[elem].parent = nad->depths[depth - 1];
 499
 500     return elem;
 501 }
 502
 503 /** attach new attr to the last elem */
 504 int nad_append_attr(nad_t nad, int ns, const char *name, const char *val)
 505 {
 506     _nad_ptr_check(__func__, nad);
 507
 508     return _nad_attr(nad, nad->ecur - 1, ns, name, val, 0);
 509 }
 510
 511 /** append new cdata to the last elem */
 512 void nad_append_cdata(nad_t nad, const char *cdata, int len, int depth)
 513 {
 514     int elem = nad->ecur - 1;
 515
 516     _nad_ptr_check(__func__, nad);
 517
 518     /* make sure this cdata is the child of the last elem to append */
 519     if(nad->elems[elem].depth == depth - 1)
 520     {
 521         if(nad->elems[elem].icdata == 0)
 522             nad->elems[elem].icdata = nad->ccur;
 523         _nad_cdata(nad,cdata,len);
 524         nad->elems[elem].lcdata += len;
 525         return;
 526     }
 527
 528     /* otherwise, pin the cdata on the tail of the last element at this depth */
 529     elem = nad->depths[depth];
 530     if(nad->elems[elem].itail == 0)
 531         nad->elems[elem].itail = nad->ccur;
 532     _nad_cdata(nad,cdata,len);
 533     nad->elems[elem].ltail += len;
 534 }
 535
 536 /** bring a new namespace into scope */
 537 int nad_add_namespace(nad_t nad, const char *uri, const char *prefix)
 538 {
 539     int ns;
 540
 541     _nad_ptr_check(__func__, nad);
 542
 543     /* only add it if its not already in scope */
 544     ns = nad_find_scoped_namespace(nad, uri, NULL);
 545     if(ns >= 0)
 546         return ns;
 547
 548     /* make sure there's mem for us */
 549     NAD_SAFE(nad->nss, (nad->ncur + 1) * sizeof(struct nad_ns_st), nad->nlen);
 550
 551     ns = nad->ncur;
 552     nad->ncur++;
 553     nad->nss[ns].next = nad->scope;
 554     nad->scope = ns;
 555
 556     nad->nss[ns].luri = strlen(uri);
 557     nad->nss[ns].iuri = _nad_cdata(nad, uri, nad->nss[ns].luri);
 558     if(prefix != NULL)
 559     {
 560         nad->nss[ns].lprefix = strlen(prefix);
 561         nad->nss[ns].iprefix = _nad_cdata(nad, prefix, nad->nss[ns].lprefix);
 562     }
 563     else
 564         nad->nss[ns].iprefix = -1;
 565
 566     return ns;
 567 }
 568
 569 /** declare a namespace on an already-existing element */
 570 int nad_append_namespace(nad_t nad, int elem, const char *uri, const char *prefix) {
 571     int ns;
 572
 573     _nad_ptr_check(__func__, nad);
 574
 575     /* see if its already scoped on this element */
 576     ns = nad_find_namespace(nad, elem, uri, NULL);
 577     if(ns >= 0)
 578         return ns;
 579
 580     /* make some room */
 581     NAD_SAFE(nad->nss, (nad->ncur + 1) * sizeof(struct nad_ns_st), nad->nlen);
 582
 583     ns = nad->ncur;
 584     nad->ncur++;
 585     nad->nss[ns].next = nad->elems[elem].ns;
 586     nad->elems[elem].ns = ns;
 587
 588     nad->nss[ns].luri = strlen(uri);
 589     nad->nss[ns].iuri = _nad_cdata(nad, uri, nad->nss[ns].luri);
 590     if(prefix != NULL)
 591     {
 592         nad->nss[ns].lprefix = strlen(prefix);
 593         nad->nss[ns].iprefix = _nad_cdata(nad, prefix, nad->nss[ns].lprefix);
 594     }
 595     else
 596         nad->nss[ns].iprefix = -1;
 597
 598     return ns;
 599 }
 600
 601 void _nad_escape(nad_t nad, int data, int len, int flag)
 602 {
 603     char *c;
 604     int ic;
 605
 606     if(len <= 0) return;
 607
 608     /* first, if told, find and escape ' */
 609     while(flag >= 3 && (c = memchr(nad->cdata + data,'\'',len)) != NULL)
 610     {
 611         /* get offset */
 612         ic = c - nad->cdata;
 613
 614         /* cute, eh?  handle other data before this normally */
 615         _nad_escape(nad, data, ic - data, 2);
 616
 617         /* ensure enough space, and add our escaped &apos; */
 618         NAD_SAFE(nad->cdata, nad->ccur + 6, nad->clen);
 619         memcpy(nad->cdata + nad->ccur, "&apos;", 6);
 620         nad->ccur += 6;
 621
 622         /* just update and loop for more */
 623         len -= (ic+1) - data;
 624         data = ic+1;
 625     }
 626
 627     /* next look for < */
 628     while(flag >= 2 && (c = memchr(nad->cdata + data,'<',len)) != NULL)
 629     {
 630         ic = c - nad->cdata;
 631         _nad_escape(nad, data, ic - data, 1);
 632
 633         /* ensure enough space, and add our escaped &lt; */
 634         NAD_SAFE(nad->cdata, nad->ccur + 4, nad->clen);
 635         memcpy(nad->cdata + nad->ccur, "&lt;", 4);
 636         nad->ccur += 4;
 637
 638         /* just update and loop for more */
 639         len -= (ic+1) - data;
 640         data = ic+1;
 641     }
 642
 643     /* check for ]]>, we need to escape the > */
 644         /* WE DID THIS  (add the '0' as the first test to the while loop
 645                 because the loops dies 3 lines in... (and we don't reall
 646                 need this)) ...
 647          */
 648     while( 0 && flag >= 1 && (c = memchr(nad->cdata + data, '>', len)) != NULL)
 649     {
 650         ic = c - nad->cdata;
 651
 652         _nad_escape(nad, data, ic - data, 0);
 653
 654         /* check for the sequence */
 655
 656         if( c >= nad->cdata + 2 && c[-1] == ']' && c[-2] == ']')
 657         {
 658             /* ensure enough space, and add our escaped &gt; */
 659             NAD_SAFE(nad->cdata, nad->ccur + 4, nad->clen);
 660             memcpy(nad->cdata + nad->ccur, "&gt;", 4);
 661             nad->ccur += 4;
 662         }
 663
 664         /* otherwise, just plug the > in as-is */
 665         else
 666         {
 667             NAD_SAFE(nad->cdata, nad->ccur + 1, nad->clen);
 668             *(nad->cdata + nad->ccur) = '>';
 669             nad->ccur++;
 670         }
 671
 672         /* just update and loop for more */
 673         len -= (ic+1) - data;
 674         data = ic+1;
 675     }
 676
 677     /* if & is found, escape it */
 678     while((c = memchr(nad->cdata + data,'&',len)) != NULL)
 679     {
 680         ic = c - nad->cdata;
 681
 682         /* ensure enough space */
 683         NAD_SAFE(nad->cdata, nad->ccur + 5 + (ic - data), nad->clen);
 684
 685         /* handle normal data */
 686         memcpy(nad->cdata + nad->ccur, nad->cdata + data, (ic - data));
 687         nad->ccur += (ic - data);
 688
 689         /* append escaped &lt; */
 690         memcpy(nad->cdata + nad->ccur, "&amp;", 5);
 691         nad->ccur += 5;
 692
 693         /* just update and loop for more */
 694         len -= (ic+1) - data;
 695         data = ic+1;
 696     }
 697
 698     /* nothing exciting, just append normal cdata */
 699     NAD_SAFE(nad->cdata, nad->ccur + len, nad->clen);
 700     memcpy(nad->cdata + nad->ccur, nad->cdata + data, len);
 701     nad->ccur += len;
 702 }
 703
 704 /** internal recursive printing function */
 705 int _nad_lp0(nad_t nad, int elem)
 706 {
 707     int attr;
 708     int ndepth;
 709     int ns;
 710
 711     /* there's a lot of code in here, but don't let that scare you, it's just duplication in order to be a bit more efficient cpu-wise */
 712
 713     /* this whole thing is in a big loop for processing siblings */
 714     while(elem != nad->ecur)
 715     {
 716
 717     /* make enough space for the opening element */
 718     ns = nad->elems[elem].my_ns;
 719     if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 720     {
 721         NAD_SAFE(nad->cdata, nad->ccur + nad->elems[elem].lname + nad->nss[ns].lprefix + 2, nad->clen);
 722     } else {
 723         NAD_SAFE(nad->cdata, nad->ccur + nad->elems[elem].lname + 1, nad->clen);
 724     }
 725
 726     /* opening tag */
 727     *(nad->cdata + nad->ccur++) = '<';
 728
 729     /* add the prefix if necessary */
 730     if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 731     {
 732         memcpy(nad->cdata + nad->ccur, nad->cdata + nad->nss[ns].iprefix, nad->nss[ns].lprefix);
 733         nad->ccur += nad->nss[ns].lprefix;
 734         *(nad->cdata + nad->ccur++) = ':';
 735     }
 736
 737     /* copy in the name */
 738     memcpy(nad->cdata + nad->ccur, nad->cdata + nad->elems[elem].iname, nad->elems[elem].lname);
 739     nad->ccur += nad->elems[elem].lname;
 740
 741     /* add the namespaces */
 742     for(ns = nad->elems[elem].ns; ns >= 0; ns = nad->nss[ns].next)
 743     {
 744         /* never explicitly declare the implicit xml namespace */
 745         if(nad->nss[ns].luri == strlen(uri_XML) && strncmp(uri_XML, nad->cdata + nad->nss[ns].iuri, nad->nss[ns].luri) == 0)
 746             continue;
 747
 748         /* make space */
 749         if(nad->nss[ns].iprefix >= 0)
 750         {
 751             NAD_SAFE(nad->cdata, nad->ccur + nad->nss[ns].luri + nad->nss[ns].lprefix + 10, nad->clen);
 752         } else {
 753             NAD_SAFE(nad->cdata, nad->ccur + nad->nss[ns].luri + 9, nad->clen);
 754         }
 755
 756         /* start */
 757         memcpy(nad->cdata + nad->ccur, " xmlns", 6);
 758         nad->ccur += 6;
 759
 760         /* prefix if necessary */
 761         if(nad->nss[ns].iprefix >= 0)
 762         {
 763             *(nad->cdata + nad->ccur++) = ':';
 764             memcpy(nad->cdata + nad->ccur, nad->cdata + nad->nss[ns].iprefix, nad->nss[ns].lprefix);
 765             nad->ccur += nad->nss[ns].lprefix;
 766         }
 767
 768         *(nad->cdata + nad->ccur++) = '=';
 769         *(nad->cdata + nad->ccur++) = '\'';
 770
 771         /* uri */
 772         memcpy(nad->cdata + nad->ccur, nad->cdata + nad->nss[ns].iuri, nad->nss[ns].luri);
 773         nad->ccur += nad->nss[ns].luri;
 774
 775         *(nad->cdata + nad->ccur++) = '\'';
 776     }
 777
 778     for(attr = nad->elems[elem].attr; attr >= 0; attr = nad->attrs[attr].next)
 779     {
 780         if(nad->attrs[attr].lname <= 0) continue;
 781
 782         /* make enough space for the wrapper part */
 783         ns = nad->attrs[attr].my_ns;
 784         if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 785         {
 786             NAD_SAFE(nad->cdata, nad->ccur + nad->attrs[attr].lname + nad->nss[ns].lprefix + 4, nad->clen);
 787         } else {
 788             NAD_SAFE(nad->cdata, nad->ccur + nad->attrs[attr].lname + 3, nad->clen);
 789         }
 790
 791         *(nad->cdata + nad->ccur++) = ' ';
 792
 793         /* add the prefix if necessary */
 794         if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 795         {
 796             memcpy(nad->cdata + nad->ccur, nad->cdata + nad->nss[ns].iprefix, nad->nss[ns].lprefix);
 797             nad->ccur += nad->nss[ns].lprefix;
 798             *(nad->cdata + nad->ccur++) = ':';
 799         }
 800
 801         /* copy in the name parts */
 802         memcpy(nad->cdata + nad->ccur, nad->cdata + nad->attrs[attr].iname, nad->attrs[attr].lname);
 803         nad->ccur += nad->attrs[attr].lname;
 804         *(nad->cdata + nad->ccur++) = '=';
 805         *(nad->cdata + nad->ccur++) = '\'';
 806
 807         /* copy in the escaped value */
 808         _nad_escape(nad, nad->attrs[attr].ival, nad->attrs[attr].lval, 3);
 809
 810         /* make enough space for the closing quote and add it */
 811         NAD_SAFE(nad->cdata, nad->ccur + 1, nad->clen);
 812         *(nad->cdata + nad->ccur++) = '\'';
 813     }
 814
 815     /* figure out what's next */
 816     if(elem+1 == nad->ecur)
 817         ndepth = -1;
 818     else
 819         ndepth = nad->elems[elem+1].depth;
 820
 821     /* handle based on if there are children, update nelem after done */
 822     if(ndepth <= nad->elems[elem].depth)
 823     {
 824         /* make sure there's enough for what we could need */
 825         NAD_SAFE(nad->cdata, nad->ccur + 2, nad->clen);
 826         if(nad->elems[elem].lcdata == 0)
 827         {
 828             memcpy(nad->cdata + nad->ccur, "/>", 2);
 829             nad->ccur += 2;
 830         }else{
 831             *(nad->cdata + nad->ccur++) = '>';
 832
 833             /* copy in escaped cdata */
 834             _nad_escape(nad, nad->elems[elem].icdata, nad->elems[elem].lcdata,2);
 835
 836             /* make room */
 837             ns = nad->elems[elem].my_ns;
 838             if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 839             {
 840                 NAD_SAFE(nad->cdata, nad->ccur + 4 + nad->elems[elem].lname + nad->nss[ns].lprefix, nad->clen);
 841             } else {
 842                 NAD_SAFE(nad->cdata, nad->ccur + 3 + nad->elems[elem].lname, nad->clen);
 843             }
 844
 845             /* close tag */
 846             memcpy(nad->cdata + nad->ccur, "</", 2);
 847             nad->ccur += 2;
 848
 849             /* add the prefix if necessary */
 850             if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 851             {
 852                 memcpy(nad->cdata + nad->ccur, nad->cdata + nad->nss[ns].iprefix, nad->nss[ns].lprefix);
 853                 nad->ccur += nad->nss[ns].lprefix;
 854                 *(nad->cdata + nad->ccur++) = ':';
 855             }
 856
 857             memcpy(nad->cdata + nad->ccur, nad->cdata + nad->elems[elem].iname, nad->elems[elem].lname);
 858             nad->ccur += nad->elems[elem].lname;
 859             *(nad->cdata + nad->ccur++) = '>';
 860         }
 861
 862         /* always try to append the tail */
 863         _nad_escape(nad, nad->elems[elem].itail, nad->elems[elem].ltail,2);
 864
 865         /* if no siblings either, bail */
 866         if(ndepth < nad->elems[elem].depth)
 867             return elem+1;
 868
 869         /* next sibling */
 870         elem++;
 871     }else{
 872         int nelem;
 873         /* process any children */
 874
 875         /* close ourself and append any cdata first */
 876         NAD_SAFE(nad->cdata, nad->ccur + 1, nad->clen);
 877         *(nad->cdata + nad->ccur++) = '>';
 878         _nad_escape(nad, nad->elems[elem].icdata, nad->elems[elem].lcdata,2);
 879
 880         /* process children */
 881         nelem = _nad_lp0(nad,elem+1);
 882
 883         /* close and tail up */
 884         ns = nad->elems[elem].my_ns;
 885         if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 886         {
 887             NAD_SAFE(nad->cdata, nad->ccur + 4 + nad->elems[elem].lname + nad->nss[ns].lprefix, nad->clen);
 888         } else {
 889             NAD_SAFE(nad->cdata, nad->ccur + 3 + nad->elems[elem].lname, nad->clen);
 890         }
 891         memcpy(nad->cdata + nad->ccur, "</", 2);
 892         nad->ccur += 2;
 893         if(ns >= 0 && nad->nss[ns].iprefix >= 0)
 894         {
 895             memcpy(nad->cdata + nad->ccur, nad->cdata + nad->nss[ns].iprefix, nad->nss[ns].lprefix);
 896             nad->ccur += nad->nss[ns].lprefix;
 897             *(nad->cdata + nad->ccur++) = ':';
 898         }
 899         memcpy(nad->cdata + nad->ccur, nad->cdata + nad->elems[elem].iname, nad->elems[elem].lname);
 900         nad->ccur += nad->elems[elem].lname;
 901         *(nad->cdata + nad->ccur++) = '>';
 902         _nad_escape(nad, nad->elems[elem].itail, nad->elems[elem].ltail,2);
 903
 904         /* if the next element is not our sibling, we're done */
 905         if(nelem < nad->ecur && nad->elems[nelem].depth < nad->elems[elem].depth)
 906             return nelem;
 907
 908         /* for next sibling in while loop */
 909         elem = nelem;
 910     }
 911
 912     /* here's the end of that big while loop */
 913     }
 914
 915     return elem;
 916 }
 917
 918 void nad_print(nad_t nad, int elem, char **xml, int *len)
 919 {
 920     int ixml = nad->ccur;
 921
 922     _nad_ptr_check(__func__, nad);
 923
 924     _nad_lp0(nad,elem);
 925     *len = nad->ccur - ixml;
 926     *xml = nad->cdata + ixml;
 927 }
 928
 929 /**
 930  * nads serialize to a buffer of this form:
 931  *
 932  * [buflen][ecur][acur][ncur][ccur][elems][attrs][nss][cdata]
 933  *
 934  * nothing is done with endianness or word length, so the nad must be
 935  * serialized and deserialized on the same platform
 936  *
 937  * buflen is not actually used by deserialize(), but is provided as a
 938  * convenience to the application so it knows how many bytes to read before
 939  * passing them in to deserialize()
 940  *
 941  * the depths array is not stored, so after deserialization
 942  * nad_append_elem() and nad_append_cdata() will not work. this is rarely
 943  * a problem
 944  */
 945
 946 void nad_serialize(nad_t nad, char **buf, int *len) {
 947     char *pos;
 948
 949     _nad_ptr_check(__func__, nad);
 950
 951     *len = sizeof(int) * 5 + /* 4 ints in nad_t, plus one for len */
 952            sizeof(struct nad_elem_st) * nad->ecur +
 953            sizeof(struct nad_attr_st) * nad->acur +
 954            sizeof(struct nad_ns_st) * nad->ncur +
 955            sizeof(char) * nad->ccur;
 956
 957     *buf = (char *) malloc(*len);
 958     pos = *buf;
 959
 960     * (int *) pos = *len;       pos += sizeof(int);
 961     * (int *) pos = nad->ecur;  pos += sizeof(int);
 962     * (int *) pos = nad->acur;  pos += sizeof(int);
 963     * (int *) pos = nad->ncur;  pos += sizeof(int);
 964     * (int *) pos = nad->ccur;  pos += sizeof(int);
 965
 966     memcpy(pos, nad->elems, sizeof(struct nad_elem_st) * nad->ecur);    pos += sizeof(struct nad_elem_st) * nad->ecur;
 967     memcpy(pos, nad->attrs, sizeof(struct nad_attr_st) * nad->acur);    pos += sizeof(struct nad_attr_st) * nad->acur;
 968     memcpy(pos, nad->nss, sizeof(struct nad_ns_st) * nad->ncur);        pos += sizeof(struct nad_ns_st) * nad->ncur;
 969     memcpy(pos, nad->cdata, sizeof(char) * nad->ccur);
 970 }
 971
 972 nad_t nad_deserialize(nad_cache_t cache, const char *buf) {
 973     nad_t nad = nad_new(cache);
 974     const char *pos = buf + sizeof(int);  /* skip len */
 975
 976     _nad_ptr_check(__func__, nad);
 977
 978     nad->ecur = * (int *) pos; pos += sizeof(int);
 979     nad->acur = * (int *) pos; pos += sizeof(int);
 980     nad->ncur = * (int *) pos; pos += sizeof(int);
 981     nad->ccur = * (int *) pos; pos += sizeof(int);
 982     nad->elen = nad->ecur;
 983     nad->alen = nad->acur;
 984     nad->nlen = nad->ncur;
 985     nad->clen = nad->ccur;
 986
 987     if(nad->ecur > 0)
 988     {
 989         nad->elems = (struct nad_elem_st *) malloc(sizeof(struct nad_elem_st) * nad->ecur);
 990         memcpy(nad->elems, pos, sizeof(struct nad_elem_st) * nad->ecur);
 991         pos += sizeof(struct nad_elem_st) * nad->ecur;
 992     }
 993
 994     if(nad->acur > 0)
 995     {
 996         nad->attrs = (struct nad_attr_st *) malloc(sizeof(struct nad_attr_st) * nad->acur);
 997         memcpy(nad->attrs, pos, sizeof(struct nad_attr_st) * nad->acur);
 998         pos += sizeof(struct nad_attr_st) * nad->acur;
 999     }
1000
1001     if(nad->ncur > 0)
1002     {
1003         nad->nss = (struct nad_ns_st *) malloc(sizeof(struct nad_ns_st) * nad->ncur);
1004         memcpy(nad->nss, pos, sizeof(struct nad_ns_st) * nad->ncur);
1005         pos += sizeof(struct nad_ns_st) * nad->ncur;
1006     }
1007
1008     if(nad->ccur > 0)
1009     {
1010         nad->cdata = (char *) malloc(sizeof(char) * nad->ccur);
1011         memcpy(nad->cdata, pos, sizeof(char) * nad->ccur);
1012     }
1013
1014     return nad;
1015 }
1016
1017 #ifdef HAVE_EXPAT
1018
1019 /** parse a buffer into a nad */
1020
1021 struct build_data {
1022     nad_t               nad;
1023     int                 depth;
1024 };
1025
1026 static void _nad_parse_element_start(void *arg, const char *name, const char **atts) {
1027     struct build_data *bd = (struct build_data *) arg;
1028     char buf[1024];
1029     char *uri, *elem, *prefix;
1030     const char **attr;
1031     int ns;
1032
1033     /* make a copy */
1034     strncpy(buf, name, 1024);
1035     buf[1023] = '\0';
1036
1037     /* expat gives us:
1038          prefixed namespaced elem: uri|elem|prefix
1039           default namespaced elem: uri|elem
1040                un-namespaced elem: elem
1041      */
1042
1043     /* extract all the bits */
1044     uri = buf;
1045     elem = strchr(uri, '|');
1046     if(elem != NULL) {
1047         *elem = '\0';
1048         elem++;
1049         prefix = strchr(elem, '|');
1050         if(prefix != NULL) {
1051             *prefix = '\0';
1052             prefix++;
1053         }
1054         ns = nad_add_namespace(bd->nad, uri, prefix);
1055     } else {
1056         /* un-namespaced, just take it as-is */
1057         uri = NULL;
1058         elem = buf;
1059         prefix = NULL;
1060         ns = -1;
1061     }
1062
1063     /* add it */
1064     nad_append_elem(bd->nad, ns, elem, bd->depth);
1065
1066     /* now the attributes, one at a time */
1067     attr = atts;
1068     while(attr[0] != NULL) {
1069
1070         /* make a copy */
1071         strncpy(buf, attr[0], 1024);
1072         buf[1023] = '\0';
1073
1074         /* extract all the bits */
1075         uri = buf;
1076         elem = strchr(uri, '|');
1077         if(elem != NULL) {
1078             *elem = '\0';
1079             elem++;
1080             prefix = strchr(elem, '|');
1081             if(prefix != NULL) {
1082                 *prefix = '\0';
1083                 prefix++;
1084             }
1085             ns = nad_add_namespace(bd->nad, uri, prefix);
1086         } else {
1087             /* un-namespaced, just take it as-is */
1088             uri = NULL;
1089             elem = buf;
1090             prefix = NULL;
1091             ns = -1;
1092         }
1093
1094         /* add it */
1095         nad_append_attr(bd->nad, ns, elem, (char *) attr[1]);
1096
1097         attr += 2;
1098     }
1099
1100     bd->depth++;
1101 }
1102
1103 static void _nad_parse_element_end(void *arg, const char *name) {
1104     struct build_data *bd = (struct build_data *) arg;
1105
1106     bd->depth--;
1107 }
1108
1109 static void _nad_parse_cdata(void *arg, const char *str, int len) {
1110     struct build_data *bd = (struct build_data *) arg;
1111
1112     /* go */
1113     nad_append_cdata(bd->nad, (char *) str, len, bd->depth);
1114 }
1115
1116 static void _nad_parse_namespace_start(void *arg, const char *prefix, const char *uri) {
1117     struct build_data *bd = (struct build_data *) arg;
1118
1119     nad_add_namespace(bd->nad, (char *) uri, (char *) prefix);
1120 }
1121
1122 nad_t nad_parse(nad_cache_t cache, const char *buf, int len) {
1123     struct build_data bd;
1124     XML_Parser p;
1125
1126     if(len == 0)
1127         len = strlen(buf);
1128
1129     p = XML_ParserCreateNS(NULL, '|');
1130     if(p == NULL)
1131         return NULL;
1132
1133     bd.nad = nad_new(cache);
1134     bd.depth = 0;
1135
1136     XML_SetUserData(p, (void *) &bd);
1137     XML_SetElementHandler(p, _nad_parse_element_start, _nad_parse_element_end);
1138     XML_SetCharacterDataHandler(p, _nad_parse_cdata);
1139     XML_SetStartNamespaceDeclHandler(p, _nad_parse_namespace_start);
1140
1141     if(!XML_Parse(p, buf, len, 1)) {
1142         XML_ParserFree(p);
1143         nad_free(bd.nad);
1144         return NULL;
1145     }
1146
1147     XML_ParserFree(p);
1148
1149     if(bd.depth != 0)
1150         return NULL;
1151
1152     return bd.nad;
1153 }
1154
1155 #endif