ezxml.c

用于学术研究的FPGA布局布线软件VPR

/* ezxml.c
 *
 * Copyright 2004-2006 Aaron Voisine <[e-mail]>
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

/* Ted Campbell, Aug 14 2007 */
#if defined(WIN32) || defined(_WIN32)
#include <io.h>

#ifndef EZXML_NOMMAP
#define EZXML_NOMMAP
#endif /* EXXML_NOMMAP */
#endif /* WIN32 */

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <ctype.h>

/* Ted Campbell, Aug 14 2007 */
#if !defined(WIN32) && !defined(_WIN32)
#include <unistd.h>
#endif

#include <sys/types.h>
#ifndef EZXML_NOMMAP
#include <sys/mman.h>
#endif /* EZXML_NOMMAP */
#include <sys/stat.h>
#include "ezxml.h"

/* Ted Campbell, Aug 14, 2007 */
#include "util.h"

/* Ted Campbell, Aug 14, 2007 */
#if defined(WIN32) || defined(_WIN32)
#define snprintf _snprintf
#define open _open
#define read _read
#define write _write
#define close _close
#endif /* WIN32 */

#define EZXML_WS   "\t\r\n "	/* whitespace */
#define EZXML_ERRL 128		/* maximum error string length */

typedef struct ezxml_root *ezxml_root_t;
struct ezxml_root
{				/* additional data for the root tag */
    struct ezxml xml;		/* is a super-struct built on top of ezxml struct */
    ezxml_t cur;		/* current xml tree insertion point */
    char *m;			/* original xml string */
    size_t len;			/* length of allocated memory for mmap, -1 for malloc */
    char *u;			/* UTF-8 conversion of string if original was UTF-16 */
    char *s;			/* start of work area */
    char *e;			/* end of work area */
    char **ent;			/* general entities (ampersand sequences) */
    char ***attr;		/* default attributes */
    char ***pi;			/* processing instructions */
    short standalone;		/* non-zero if <?xml standalone="yes"?> */
    char err[EZXML_ERRL];	/* error string */
};

char *EZXML_NIL[] = { NULL };	/* empty, null terminated array of strings */

/* returns the first child tag with the given name or NULL if not found */
ezxml_t
ezxml_child(ezxml_t xml,
	    const char *name)
{
    xml = (xml) ? xml->child : NULL;
    while(xml && strcmp(name, xml->name))
	xml = xml->sibling;
    return xml;
}

/* returns the Nth tag with the same name in the same subsection or NULL if not */
/* found */
ezxml_t
ezxml_idx(ezxml_t xml,
	  int idx)
{
    for(; xml && idx; idx--)
	xml = xml->next;
    return xml;
}

/* returns the value of the requested tag attribute or NULL if not found */
const char *
ezxml_attr(ezxml_t xml,
	   const char *attr)
{
    int i = 0, j = 1;
    ezxml_root_t root = (ezxml_root_t) xml;

    if(!xml || !xml->attr)
	return NULL;
    while(xml->attr[i] && strcmp(attr, xml->attr[i]))
	i += 2;
    if(xml->attr[i])
	return xml->attr[i + 1];	/* found attribute */

    while(root->xml.parent)
	root = (ezxml_root_t) root->xml.parent;	/* root tag */
    for(i = 0; root->attr[i] && strcmp(xml->name, root->attr[i][0]); i++);
    if(!root->attr[i])
	return NULL;		/* no matching default attributes */
    while(root->attr[i][j] && strcmp(attr, root->attr[i][j]))
	j += 3;
    return (root->attr[i][j]) ? root->attr[i][j + 1] : NULL;	/* found default */
}

/* same as ezxml_get but takes an already initialized va_list */
ezxml_t
ezxml_vget(ezxml_t xml,
	   va_list ap)
{
    char *name = va_arg(ap, char *);
    int idx = -1;

    if(name && *name)
	{
	    idx = va_arg(ap, int);

	    xml = ezxml_child(xml, name);
	}
    return (idx < 0) ? xml : ezxml_vget(ezxml_idx(xml, idx), ap);
}

/* Traverses the xml tree to retrieve a specific subtag. Takes a variable */
/* length list of tag names and indexes. The argument list must be terminated */
/* by either an index of -1 or an empty string tag name. Example:  */
/* title = ezxml_get(library, "shelf", 0, "book", 2, "title", -1); */
/* This retrieves the title of the 3rd book on the 1st shelf of library. */
/* Returns NULL if not found. */
ezxml_t
ezxml_get(ezxml_t xml,
	  ...)
{
    va_list ap;
    ezxml_t r;

    va_start(ap, xml);
    r = ezxml_vget(xml, ap);
    va_end(ap);
    return r;
}

/* returns a null terminated array of processing instructions for the given */
/* target */
const char **
ezxml_pi(ezxml_t xml,
	 const char *target)
{
    ezxml_root_t root = (ezxml_root_t) xml;
    int i = 0;

    if(!root)
	return (const char **)EZXML_NIL;
    while(root->xml.parent)
	root = (ezxml_root_t) root->xml.parent;	/* root tag */
    while(root->pi[i] && strcmp(target, root->pi[i][0]))
	i++;			/* find target */
    return (const char **)((root->pi[i]) ? root->pi[i] + 1 : EZXML_NIL);
}

/* set an error string and return root */
ezxml_t
ezxml_err(ezxml_root_t root,
	  char *s,
	  const char *err,
	  ...)
{
    va_list ap;
    int line = 1;
    char *t, fmt[EZXML_ERRL];

    for(t = root->s; t < s; t++)
	if(*t == '\n')
	    line++;
    snprintf(fmt, EZXML_ERRL, "[error near line %d]: %s", line, err);

    va_start(ap, err);
    vsnprintf(root->err, EZXML_ERRL, fmt, ap);
    va_end(ap);

    return &root->xml;
}

/* Recursively decodes entity and character references and normalizes new lines */
/* ent is a null terminated array of alternating entity names and values. set t */
/* to '&' for general entity decoding, '%' for parameter entity decoding, 'c' */
/* for cdata sections, ' ' for attribute normalization, or '*' for non-cdata */
/* attribute normalization. Returns s, or if the decoded string is longer than */
/* s, returns a malloced string that must be freed. */
char *
ezxml_decode(char *s,
	     char **ent,
	     char t)
{
    char *e, *r = s, *m = s;
    long b, c, d, l;

    for(; *s; s++)
	{			/* normalize line endings */
	    while(*s == '\r')
		{
		    *(s++) = '\n';
		    if(*s == '\n')
			memmove(s, (s + 1), strlen(s));
		}
	}

    for(s = r;;)
	{
	    while(*s && *s != '&' && (*s != '%' || t != '%') && !isspace(*s))
		s++;

	    if(!*s)
		break;
	    else if(t != 'c' && !strncmp(s, "&#", 2))
		{		/* character reference */
		    if(s[2] == 'x')
			c = strtol(s + 3, &e, 16);	/* base 16 */
		    else
			c = strtol(s + 2, &e, 10);	/* base 10 */
		    if(!c || *e != ';')
			{
			    s++;
			    continue;
			}
		    /* not a character ref */
		    if(c < 0x80)
			*(s++) = c;	/* US-ASCII subset */
		    else
			{	/* multi-byte UTF-8 sequence */
			    for(b = 0, d = c; d; d /= 2)
				b++;	/* number of bits in c */
			    b = (b - 2) / 5;	/* number of bytes in payload */
			    *(s++) = (0xFF << (7 - b)) | (c >> (6 * b));	/* head */
			    while(b)
				*(s++) = 0x80 | ((c >> (6 * --b)) & 0x3F);	/* payload */
			}

		    memmove(s, strchr(s, ';') + 1, strlen(strchr(s, ';')));
		}
	    else if((*s == '&' && (t == '&' || t == ' ' || t == '*'))
		    || (*s == '%' && t == '%'))
		{		/* entity reference */
		    for(b = 0; ent[b] && strncmp(s + 1, ent[b], strlen(ent[b])); b += 2);	/* find entity in entity list */

		    if(ent[b++])
			{	/* found a match */
			    if((c = strlen(ent[b])) - 1 > (e =
							   strchr(s,
								  ';')) - s)
				{
				    l = (d = (s - r)) + c + strlen(e);	/* new length */
				    r = (r == m) ? strcpy(malloc(l),
							  r) : realloc(r, l);
				    e = strchr((s = r + d), ';');	/* fix up pointers */
				}

			    memmove(s + c, e + 1, strlen(e));	/* shift rest of string */
			    strncpy(s, ent[b], c);	/* copy in replacement text */
			}
		    else
			s++;	/* not a known entity */
		}
	    else if((t == ' ' || t == '*') && isspace(*s))
		*(s++) = ' ';
	    else
		s++;		/* no decoding needed */
	}

    if(t == '*')
	{			/* normalize spaces for non-cdata attributes */
	    for(s = r; *s; s++)
		{
		    /* Jason Luu, Aug 29, 2007. Removed assignment in conditional statement */
		    l = strspn(s, " ");
		    if(l)
			memmove(s, s + l, strlen(s + l) + 1);
		    while(*s && *s != ' ')
			s++;
		}
	    if(--s >= r && *s == ' ')
		*s = '\0';	/* trim any trailing space */
	}
    return r;
}

/* called when parser finds start of new tag */
void
ezxml_open_tag(ezxml_root_t root,
	       char *name,
	       char **attr)
{
    ezxml_t xml = root->cur;

    if(xml->name)
	xml = ezxml_add_child(xml, name, strlen(xml->txt));
    else
	xml->name = name;	/* first open tag */

    xml->attr = attr;
    root->cur = xml;		/* update tag insertion point */
}

/* called when parser finds character content between open and closing tag */
void
ezxml_char_content(ezxml_root_t root,
		   char *s,
		   size_t len,
		   char t)
{
    ezxml_t xml = root->cur;
    char *m = s;
    size_t l;

    if(!xml || !xml->name || !len)
	return;			/* sanity check */

    s[len] = '\0';		/* null terminate text (calling functions anticipate this) */
    len = strlen(s = ezxml_decode(s, root->ent, t)) + 1;

    if(!*(xml->txt))
	xml->txt = s;		/* initial character content */
    else
	{			/* allocate our own memory and make a copy */
	    xml->txt = (xml->flags & EZXML_TXTM)	/* allocate some space */
		? realloc(xml->txt, (l = strlen(xml->txt)) + len)
		: strcpy(malloc((l = strlen(xml->txt)) + len), xml->txt);
	    strcpy(xml->txt + l, s);	/* add new char content */
	    if(s != m)
		free(s);	/* free s if it was malloced by ezxml_decode() */
	}

    if(xml->txt != m)
	ezxml_set_flag(xml, EZXML_TXTM);
}

/* called when parser finds closing tag */
ezxml_t
ezxml_close_tag(ezxml_root_t root,
		char *name,
		char *s)
{
    if(!root->cur || !root->cur->name || strcmp(name, root->cur->name))
	return ezxml_err(root, s, "unexpected closing tag </%s>", name);

    root->cur = root->cur->parent;
    return NULL;
}

/* checks for circular entity references, returns non-zero if no circular */
/* references are found, zero otherwise */
int
ezxml_ent_ok(char *name,
	     char *s,
	     char **ent)
{
    int i;

    for(;; s++)
	{
	    while(*s && *s != '&')
		s++;		/* find next entity reference */
	    if(!*s)
		return 1;
	    if(!strncmp(s + 1, name, strlen(name)))
		return 0;	/* circular ref. */
	    for(i = 0; ent[i] && strncmp(ent[i], s + 1, strlen(ent[i]));
		i += 2);
	    if(ent[i] && !ezxml_ent_ok(name, ent[i + 1], ent))
		return 0;
	}
}

/* called when the parser finds a processing instruction */
void
ezxml_proc_inst(ezxml_root_t root,
		char *s,
		size_t len)
{
    int i = 0, j = 1;
    char *target = s;

    s[len] = '\0';		/* null terminate instruction */
    if(*(s += strcspn(s, EZXML_WS)))
	{
	    *s = '\0';		/* null terminate target */
	    s += strspn(s + 1, EZXML_WS) + 1;	/* skip whitespace after target */
	}

    if(!strcmp(target, "xml"))
	{			/* <?xml ... ?> */
	    /* Jason Luu, Aug 29, 2007. Removed assignment in conditional statement */
	    s = strstr(s, "standalone");
	    if(s && !strncmp(s + strspn(s + 10,
					EZXML_WS "='\"") + 10, "yes", 3))
		root->standalone = 1;
	    return;
	}

    if(!root->pi[0])
	*(root->pi = malloc(sizeof(char **))) = NULL;	/*first pi */

    while(root->pi[i] && strcmp(target, root->pi[i][0]))
	i++;			/* find target */
    if(!root->pi[i])
	{			/* new target */
	    root->pi = realloc(root->pi, sizeof(char **) * (i + 2));
	    root->pi[i] = malloc(sizeof(char *) * 3);
	    root->pi[i][0] = target;
	    root->pi[i][1] = (char *)(root->pi[i + 1] = NULL);	/* terminate pi list */
	    /* Ted Campbell, Aug 14, 2007. Changed to use 'my_strdup' */
	    root->pi[i][2] = my_strdup("");	/* empty document position list */
	}

    while(root->pi[i][j])
	j++;			/* find end of instruction list for this target */
    root->pi[i] = realloc(root->pi[i], sizeof(char *) * (j + 3));
    root->pi[i][j + 2] = realloc(root->pi[i][j + 1], j + 1);
    strcpy(root->pi[i][j + 2] + j - 1, (root->xml.name) ? ">" : "<");
    root->pi[i][j + 1] = NULL;	/* null terminate pi list for this target */
    root->pi[i][j] = s;		/* set instruction */
}

/* called when the parser finds an internal doctype subset */
short
ezxml_internal_dtd(ezxml_root_t root,
		   char *s,
		   size_t len)
{
    char q, *c, *t, *n = NULL, *v, **ent, **pe;
    int i, j;

    pe = memcpy(malloc(sizeof(EZXML_NIL)), EZXML_NIL, sizeof(EZXML_NIL));

    for(s[len] = '\0'; s;)
	{
	    while(*s && *s != '<' && *s != '%')
		s++;		/* find next declaration */

	    if(!*s)
		break;
	    else if(!strncmp(s, "<!ENTITY", 8))
		{		/* parse entity definitions */
		    c = s += strspn(s + 8, EZXML_WS) + 8;	/* skip white space separator */
		    n = s + strspn(s, EZXML_WS "%");	/* find name */
		    *(s = n + strcspn(n, EZXML_WS)) = ';';	/* append ; to name */

		    v = s + strspn(s + 1, EZXML_WS) + 1;	/* find value */
		    if((q = *(v++)) != '"' && q != '\'')
			{	/* skip externals */
			    s = strchr(s, '>');
			    continue;
			}

		    for(i = 0, ent = (*c == '%') ? pe : root->ent; ent[i];
			i++);
		    ent = realloc(ent, (i + 3) * sizeof(char *));	/* space for next ent */
		    if(*c == '%')
			pe = ent;
		    else
			root->ent = ent;

		    *(++s) = '\0';	/* null terminate name */