- Makefile.am valid.c list.[ch]: Gary Pennington provided a
better handling of ID/IDREF and the list modules associated
- configure.in: small CFLAGS cleanup
Daniel
diff --git a/ChangeLog b/ChangeLog
index 4917f56..45cc456 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+Mon Feb 19 19:01:57 CET 2001 Daniel Veillard <Daniel.Veillard@imag.fr>
+
+ * Makefile.am valid.c list.[ch]: Gary Pennington provided a
+ better handling of ID/IDREF and the list modules associated
+ * configure.in: small CFLAGS cleanup
+
Mon Feb 19 16:13:22 CET 2001 Daniel Veillard <Daniel.Veillard@imag.fr>
* configure.in: fixed iconv detection on AIX (stric)
diff --git a/Makefile.am b/Makefile.am
index d67942a..a682971 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -24,6 +24,7 @@
parser.c \
tree.c \
hash.c \
+ list.c \
xmlIO.c \
xmlmemory.c \
uri.c \
diff --git a/configure.in b/configure.in
index f5d56dd..a505a80 100644
--- a/configure.in
+++ b/configure.in
@@ -157,6 +157,7 @@
dnl http://bugs.gnome.org/db/31/3163.html
dnl
if test "${GCC}" != "yes" ; then
+ CFLAGS="${CFLAGS} -Wall "
case "${host}" in
*-*-hpux* )
CFLAGS="${CFLAGS} -Wp,-H30000"
diff --git a/include/libxml/list.h b/include/libxml/list.h
new file mode 100644
index 0000000..a708ef2
--- /dev/null
+++ b/include/libxml/list.h
@@ -0,0 +1,81 @@
+/*
+ * list.h: lists interfaces
+ *
+ * Copyright (C) 2000 Gary Pennington and Daniel Veillard.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
+ * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
+ * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
+ *
+ * Author: Gary.Pennington@uk.sun.com
+ */
+
+typedef struct _xmlLink xmlLink;
+typedef xmlLink *xmlLinkPtr;
+
+typedef struct _xmlList xmlList;
+typedef xmlList *xmlListPtr;
+
+typedef void (*xmlListDeallocator) (xmlLinkPtr lk);
+typedef int (*xmlListDataCompare) (const void *data0, const void *data1);
+typedef int (*xmlListWalker) (const void *data, const void *user);
+
+/* Creation/Deletion */
+xmlListPtr xmlListCreate (xmlListDeallocator deallocator,
+ xmlListDataCompare compare);
+void xmlListDelete (xmlListPtr l);
+
+/* Basic Operators */
+void * xmlListSearch (xmlListPtr l,
+ void *data);
+void * xmlListReverseSearch (xmlListPtr l,
+ void *data);
+int xmlListInsert (xmlListPtr l,
+ void *data) ;
+int xmlListAppend (xmlListPtr l,
+ void *data) ;
+int xmlListRemoveFirst (xmlListPtr l,
+ void *data);
+int xmlListRemoveLast (xmlListPtr l,
+ void *data);
+int xmlListRemoveAll (xmlListPtr l,
+ void *data);
+void xmlListClear (xmlListPtr l);
+int xmlListEmpty (xmlListPtr l);
+xmlLinkPtr xmlListFront (xmlListPtr l);
+xmlLinkPtr xmlListEnd (xmlListPtr l);
+int xmlListSize (xmlListPtr l);
+
+void xmlListPopFront (xmlListPtr l);
+void xmlListPopBack (xmlListPtr l);
+int xmlListPushFront (xmlListPtr l,
+ void *data);
+int xmlListPushBack (xmlListPtr l,
+ void *data);
+
+/* Advanced Operators */
+void xmlListReverse (xmlListPtr l);
+void xmlListSort (xmlListPtr l);
+void xmlListWalk (xmlListPtr l,
+ xmlListWalker walker,
+ const void *user);
+void xmlListReverseWalk (xmlListPtr l,
+ xmlListWalker walker,
+ const void *user);
+void xmlListMerge (xmlListPtr l1,
+ xmlListPtr l2);
+xmlListPtr xmlListDup (const xmlListPtr old);
+int xmlListCopy (xmlListPtr cur,
+ const xmlListPtr old);
+/* Link operators */
+void * xmlLinkGetData (xmlLinkPtr lk);
+
+/* xmlListUnique() */
+/* xmlListSwap */
+
+
diff --git a/list.c b/list.c
new file mode 100644
index 0000000..bbe6144
--- /dev/null
+++ b/list.c
@@ -0,0 +1,706 @@
+/*
+ * list.c: lists handling implementation
+ *
+ * Copyright (C) 2000 Gary Pennington and Daniel Veillard.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
+ * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
+ * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
+ *
+ * Author: Gary.Pennington@uk.sun.com
+ */
+
+#ifdef WIN32
+#include "win32config.h"
+#else
+#include "config.h"
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+#include <libxml/xmlmemory.h>
+#include <libxml/list.h>
+
+/*
+ * Type definition are kept internal
+ */
+
+struct _xmlLink
+{
+ struct _xmlLink *next;
+ struct _xmlLink *prev;
+ void *data;
+};
+
+struct _xmlList
+{
+ xmlLinkPtr sentinel;
+ void (*linkDeallocator)(xmlLinkPtr );
+ int (*linkCompare)(const void *, const void*);
+};
+
+/************************************************************************
+ * *
+ * Interfaces *
+ * *
+ ************************************************************************/
+
+/**
+ * xmlLinkDeallocator:
+ * @l: a list
+ * @lk: a link
+ *
+ * Unlink and deallocate @lk from list @l
+ */
+static void
+xmlLinkDeallocator(xmlListPtr l, xmlLinkPtr lk)
+{
+ (lk->prev)->next = lk->next;
+ (lk->next)->prev = lk->prev;
+ if(l->linkDeallocator)
+ l->linkDeallocator(lk);
+ xmlFree(lk);
+}
+
+/**
+ * xmlLinkCompare:
+ * @data0: first data
+ * @data1: second data
+ *
+ * Compares two arbitrary data
+ *
+ * Returns -1, 0 or 1 depending on whether data1 is greater equal or smaller
+ * than data0
+ */
+static int
+xmlLinkCompare(const void *data0, const void *data1)
+{
+ if (data0 < data1)
+ return (-1);
+ else if (data0 == data1)
+ return (0);
+ return (1);
+}
+
+/**
+ * xmlListLowerSearch:
+ * @l: a list
+ * @data: a data
+ *
+ * Search data in the ordered list walking from the beginning
+ *
+ * Returns the link containing the data or NULL
+ */
+static xmlLinkPtr
+xmlListLowerSearch(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+
+ for(lk = l->sentinel->next;lk != l->sentinel && l->linkCompare(lk->data, data) <0 ;lk = lk->next);
+ return lk;
+}
+
+/**
+ * xmlListHigherSearch:
+ * @l: a list
+ * @data: a data
+ *
+ * Search data in the ordered list walking backward from the end
+ *
+ * Returns the link containing the data or NULL
+ */
+static xmlLinkPtr
+xmlListHigherSearch(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+
+ for(lk = l->sentinel->prev;lk != l->sentinel && l->linkCompare(lk->data, data) >0 ;lk = lk->prev);
+ return lk;
+}
+
+/**
+ * xmlListSearch:
+ * @l: a list
+ * @data: a data
+ *
+ * Search data in the list
+ *
+ * Returns the link containing the data or NULL
+ */
+static xmlLinkPtr
+xmlListLinkSearch(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+ lk = xmlListLowerSearch(l, data);
+ if (lk == l->sentinel)
+ return NULL;
+ else {
+ if (l->linkCompare(lk->data, data) ==0)
+ return lk;
+ return NULL;
+ }
+}
+
+/**
+ * xmlListLinkReverseSearch:
+ * @l: a list
+ * @data: a data
+ *
+ * Search data in the list processing backward
+ *
+ * Returns the link containing the data or NULL
+ */
+xmlLinkPtr
+xmlListLinkReverseSearch(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+ lk = xmlListHigherSearch(l, data);
+ if (lk == l->sentinel)
+ return NULL;
+ else {
+ if (l->linkCompare(lk->data, data) ==0)
+ return lk;
+ return NULL;
+ }
+}
+
+/**
+ * xmlListCreate:
+ * @deallocator: an optional deallocator function
+ * @compare: an optional comparison function
+ *
+ * Create a new list
+ *
+ * Returns the new list or NULL in case of error
+ */
+xmlListPtr
+xmlListCreate(xmlListDeallocator deallocator, xmlListDataCompare compare)
+{
+ xmlListPtr l;
+ if (NULL == (l = (xmlListPtr )xmlMalloc( sizeof(xmlList)))) {
+ perror("Cannot initialize memory for list");
+ return (NULL);
+ }
+ /* Initialize the list to NULL */
+ memset(l, 0, sizeof(xmlList));
+
+ /* Add the sentinel */
+ if (NULL ==(l->sentinel = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
+ perror("Cannot initialize memory for sentinel");
+ xmlFree(l);
+ return (NULL);
+ }
+ l->sentinel->next = l->sentinel;
+ l->sentinel->prev = l->sentinel;
+ l->sentinel->data = NULL;
+
+ /* If there is a link deallocator, use it */
+ if (deallocator != NULL)
+ l->linkDeallocator = deallocator;
+ /* If there is a link comparator, use it */
+ if (compare != NULL)
+ l->linkCompare = compare;
+ else /* Use our own */
+ l->linkCompare = xmlLinkCompare;
+ return l;
+}
+
+/**
+ * xmlListSearch:
+ * @l: a list
+ * @data: a search value
+ *
+ * Search the list for an existing value of @data
+ *
+ * Returns the value associated to @data or NULL in case of error
+ */
+void *
+xmlListSearch(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+ lk = xmlListLinkSearch(l, data);
+ if (lk)
+ return (lk->data);
+ return NULL;
+}
+
+/**
+ * xmlListLinkReverseSearch:
+ * @l: a list
+ * @data: a search value
+ *
+ * Search the list in reverse order for an existing value of @data
+ *
+ * Returns the value associated to @data or NULL in case of error
+ */
+void *
+xmlListReverseSearch(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+ lk = xmlListLinkReverseSearch(l, data);
+ if (lk)
+ return (lk->data);
+ return NULL;
+}
+
+/**
+ * xmlListInsert:
+ * @l: a list
+ * @data: the data
+ *
+ * Insert data in the ordered list at the beginning for this value
+ *
+ * Returns 0 in case of success, 1 in case of failure
+ */
+int
+xmlListInsert(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lkPlace, lkNew;
+
+ lkPlace = xmlListLowerSearch(l, data);
+ /* Add the new link */
+ lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
+ if (lkNew == NULL) {
+ perror("Cannot initialize memory for new link");
+ return (1);
+ }
+ lkNew->data = data;
+ lkPlace = lkPlace->prev;
+ lkNew->next = lkPlace->next;
+ (lkPlace->next)->prev = lkNew;
+ lkPlace->next = lkNew;
+ lkNew->prev = lkPlace;
+ return 0;
+}
+
+/**
+ * xmlListAppend:
+ * @l: a list
+ * @data: the data
+ *
+ * Insert data in the ordered list at the end for this value
+ *
+ * Returns 0 in case of success, 1 in case of failure
+ */
+int xmlListAppend(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lkPlace, lkNew;
+
+ lkPlace = xmlListHigherSearch(l, data);
+ /* Add the new link */
+ lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
+ if (lkNew == NULL) {
+ perror("Cannot initialize memory for new link");
+ return (0);
+ }
+ lkNew->data = data;
+ lkNew->next = lkPlace->next;
+ (lkPlace->next)->prev = lkNew;
+ lkPlace->next = lkNew;
+ lkNew->prev = lkPlace;
+ return 1;
+}
+
+/**
+ * xmlListDelete:
+ * @l: a list
+ *
+ * Deletes the list and its associated data
+ */
+void xmlListDelete(xmlListPtr l)
+{
+ xmlListClear(l);
+ xmlFree(l->sentinel);
+ xmlFree(l);
+}
+
+/**
+ * xmlListRemoveFirst:
+ * @l: a list
+ * @data: list data
+ *
+ * Remove the first instance associated to data in the list
+ *
+ * Returns 1 if a deallocation occured, or 0 if not found
+ */
+int
+xmlListRemoveFirst(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+
+ /*Find the first instance of this data */
+ lk = xmlListLinkSearch(l, data);
+ if (lk != NULL) {
+ xmlLinkDeallocator(l, lk);
+ return 1;
+ }
+ return 0;
+}
+
+/**
+ * xmlListRemoveLast:
+ * @l: a list
+ * @data: list data
+ *
+ * Remove the last instance associated to data in the list
+ *
+ * Returns 1 if a deallocation occured, or 0 if not found
+ */
+int
+xmlListRemoveLast(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lk;
+
+ /*Find the last instance of this data */
+ lk = xmlListLinkReverseSearch(l, data);
+ if (lk != NULL) {
+ xmlLinkDeallocator(l, lk);
+ return 1;
+ }
+ return 0;
+}
+
+/**
+ * xmlListRemoveAll:
+ * @l: a list
+ * @data: list data
+ *
+ * Remove the all instance associated to data in the list
+ *
+ * Returns the number of deallocation, or 0 if not found
+ */
+int
+xmlListRemoveAll(xmlListPtr l, void *data)
+{
+ int count=0;
+
+
+ while(xmlListRemoveFirst(l, data))
+ count++;
+ return count;
+}
+
+/**
+ * xmlListClear:
+ * @l: a list
+ *
+ * Remove the all data in the list
+ */
+void
+xmlListClear(xmlListPtr l)
+{
+ xmlLinkPtr lk = l->sentinel->next;
+
+ while(lk != l->sentinel) {
+ xmlLinkPtr next = lk->next;
+
+ xmlLinkDeallocator(l, lk);
+ lk = next;
+ }
+}
+
+/**
+ * xmlListEmpty:
+ * @l: a list
+ *
+ * Returns 1 if the list is empty, 0 otherwise
+ */
+int
+xmlListEmpty(xmlListPtr l)
+{
+ return (l->sentinel->next == l->sentinel);
+}
+
+/**
+ * xmlListFront:
+ * @l: a list
+ *
+ * Returns the first element in the list, or NULL
+ */
+xmlLinkPtr
+xmlListFront(xmlListPtr l)
+{
+ return (l->sentinel->next);
+}
+
+/**
+ * xmlListFront:
+ * @l: a list
+ *
+ * Returns the last element in the list, or NULL
+ */
+xmlLinkPtr
+xmlListEnd(xmlListPtr l)
+{
+ return (l->sentinel->prev);
+}
+
+/**
+ * xmlListSize:
+ * @l: a list
+ *
+ * Returns the number of elements in the list
+ */
+int
+xmlListSize(xmlListPtr l)
+{
+ xmlLinkPtr lk;
+ int count=0;
+
+ /* TODO: keep a counter in xmlList instead */
+ for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next, count++);
+ return count;
+}
+
+/**
+ * xmlListPopFront:
+ * @l: a list
+ *
+ * Removes the first element in the list
+ */
+void
+xmlListPopFront(xmlListPtr l)
+{
+ if(!xmlListEmpty(l))
+ xmlLinkDeallocator(l, l->sentinel->next);
+}
+
+/**
+ * xmlListPopBack:
+ * @l: a list
+ *
+ * Removes the last element in the list
+ */
+void
+xmlListPopBack(xmlListPtr l)
+{
+ if(!xmlListEmpty(l))
+ xmlLinkDeallocator(l, l->sentinel->prev);
+}
+
+/**
+ * xmlListPushFront:
+ * @l: a list
+ * @data: new data
+ *
+ * add the new data at the beginning of the list
+ *
+ * Returns 1 if successful, 0 otherwise
+ */
+int
+xmlListPushFront(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lkPlace, lkNew;
+
+ lkPlace = l->sentinel;
+ /* Add the new link */
+ lkNew = (xmlLinkPtr) xmlMalloc(sizeof(xmlLink));
+ if (lkNew == NULL) {
+ perror("Cannot initialize memory for new link");
+ return (0);
+ }
+ lkNew->data = data;
+ lkNew->next = lkPlace->next;
+ (lkPlace->next)->prev = lkNew;
+ lkPlace->next = lkNew;
+ lkNew->prev = lkPlace;
+ return 1;
+}
+
+/**
+ * xmlListPushBack:
+ * @l: a list
+ * @data: new data
+ *
+ * add the new data at the end of the list
+ *
+ * Returns 1 if successful, 0 otherwise
+ */
+int
+xmlListPushBack(xmlListPtr l, void *data)
+{
+ xmlLinkPtr lkPlace, lkNew;
+
+ lkPlace = l->sentinel->prev;
+ /* Add the new link */
+ if (NULL ==(lkNew = (xmlLinkPtr )xmlMalloc(sizeof(xmlLink)))) {
+ perror("Cannot initialize memory for new link");
+ return (0);
+ }
+ lkNew->data = data;
+ lkNew->next = lkPlace->next;
+ (lkPlace->next)->prev = lkNew;
+ lkPlace->next = lkNew;
+ lkNew->prev = lkPlace;
+ return 1;
+}
+
+/**
+ * xmlLinkGetData:
+ * @lk: a link
+ *
+ * See Returns.
+ *
+ * Returns a pointer to the data referenced from this link
+ */
+void *
+xmlLinkGetData(xmlLinkPtr lk)
+{
+ return lk->data;
+}
+
+/**
+ * xmlListReverse:
+ * @l: a list
+ *
+ * Reverse the order of the elements in the list
+ */
+void
+xmlListReverse(xmlListPtr l) {
+ xmlLinkPtr lk;
+ xmlLinkPtr lkPrev = l->sentinel;
+
+ for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
+ lkPrev->next = lkPrev->prev;
+ lkPrev->prev = lk;
+ lkPrev = lk;
+ }
+ /* Fix up the last node */
+ lkPrev->next = lkPrev->prev;
+ lkPrev->prev = lk;
+}
+
+/**
+ * xmlListSort:
+ * @l: a list
+ *
+ * Sort all the elements in the list
+ */
+void
+xmlListSort(xmlListPtr l)
+{
+ xmlListPtr lTemp;
+
+ if(xmlListEmpty(l))
+ return;
+
+ /* I think that the real answer is to implement quicksort, the
+ * alternative is to implement some list copying procedure which
+ * would be based on a list copy followed by a clear followed by
+ * an insert. This is slow...
+ */
+
+ if (NULL ==(lTemp = xmlListDup(l)))
+ return;
+ xmlListClear(l);
+ xmlListMerge(l, lTemp);
+ xmlListDelete(lTemp);
+ return;
+}
+
+/**
+ * xmlListWalk:
+ * @l: a list
+ * @walker: a processing function
+ *
+ * Walk all the element of the first from first to last and
+ * apply the walker function to it
+ */
+void
+xmlListWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
+ xmlLinkPtr lk;
+
+ for(lk = l->sentinel->next; lk != l->sentinel; lk = lk->next) {
+ if((walker(lk->data, user)) == 0)
+ break;
+ }
+}
+
+/**
+ * xmlListReverseWalk:
+ * @l: a list
+ * @walker: a processing function
+ *
+ * Walk all the element of the list in reverse order and
+ * apply the walker function to it
+ */
+void
+xmlListReverseWalk(xmlListPtr l, xmlListWalker walker, const void *user) {
+ xmlLinkPtr lk;
+
+ for(lk = l->sentinel->prev; lk != l->sentinel; lk = lk->prev) {
+ if((walker(lk->data, user)) == 0)
+ break;
+ }
+}
+
+/**
+ * xmlListMerge:
+ * @l1: the original list
+ * @l2: the new list
+ *
+ * include all the elements of the second list in the first one and
+ * clear the second list
+ */
+void
+xmlListMerge(xmlListPtr l1, xmlListPtr l2)
+{
+ xmlListCopy(l1, l2);
+ xmlListClear(l2);
+}
+
+/**
+ * xmlListDup:
+ * @old: the list
+ *
+ * Duplicate the list
+ *
+ * Returns a new copy of the list or NULL in case of error
+ */
+xmlListPtr
+xmlListDup(const xmlListPtr old)
+{
+ xmlListPtr cur;
+ /* Hmmm, how to best deal with allocation issues when copying
+ * lists. If there is a de-allocator, should responsibility lie with
+ * the new list or the old list. Surely not both. I'll arbitrarily
+ * set it to be the old list for the time being whilst I work out
+ * the answer
+ */
+ if (NULL ==(cur = xmlListCreate(NULL, old->linkCompare)))
+ return (NULL);
+ if (0 != xmlListCopy(cur, old))
+ return NULL;
+ return cur;
+}
+
+/**
+ * xmlListCopy:
+ * @cur: the new list
+ * @old: the old list
+ *
+ * Move all the element from the old list in the new list
+ *
+ * Returns 0 in case of success 1 in case of error
+ */
+int
+xmlListCopy(xmlListPtr cur, const xmlListPtr old)
+{
+ /* Walk the old tree and insert the data into the new one */
+ xmlLinkPtr lk;
+
+ for(lk = old->sentinel->next; lk != old->sentinel; lk = lk->next) {
+ if (0 !=xmlListInsert(cur, lk->data)) {
+ xmlListDelete(cur);
+ return (1);
+ }
+ }
+ return (0);
+}
+/* xmlListUnique() */
+/* xmlListSwap */
diff --git a/list.h b/list.h
new file mode 100644
index 0000000..a708ef2
--- /dev/null
+++ b/list.h
@@ -0,0 +1,81 @@
+/*
+ * list.h: lists interfaces
+ *
+ * Copyright (C) 2000 Gary Pennington and Daniel Veillard.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
+ * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
+ * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
+ *
+ * Author: Gary.Pennington@uk.sun.com
+ */
+
+typedef struct _xmlLink xmlLink;
+typedef xmlLink *xmlLinkPtr;
+
+typedef struct _xmlList xmlList;
+typedef xmlList *xmlListPtr;
+
+typedef void (*xmlListDeallocator) (xmlLinkPtr lk);
+typedef int (*xmlListDataCompare) (const void *data0, const void *data1);
+typedef int (*xmlListWalker) (const void *data, const void *user);
+
+/* Creation/Deletion */
+xmlListPtr xmlListCreate (xmlListDeallocator deallocator,
+ xmlListDataCompare compare);
+void xmlListDelete (xmlListPtr l);
+
+/* Basic Operators */
+void * xmlListSearch (xmlListPtr l,
+ void *data);
+void * xmlListReverseSearch (xmlListPtr l,
+ void *data);
+int xmlListInsert (xmlListPtr l,
+ void *data) ;
+int xmlListAppend (xmlListPtr l,
+ void *data) ;
+int xmlListRemoveFirst (xmlListPtr l,
+ void *data);
+int xmlListRemoveLast (xmlListPtr l,
+ void *data);
+int xmlListRemoveAll (xmlListPtr l,
+ void *data);
+void xmlListClear (xmlListPtr l);
+int xmlListEmpty (xmlListPtr l);
+xmlLinkPtr xmlListFront (xmlListPtr l);
+xmlLinkPtr xmlListEnd (xmlListPtr l);
+int xmlListSize (xmlListPtr l);
+
+void xmlListPopFront (xmlListPtr l);
+void xmlListPopBack (xmlListPtr l);
+int xmlListPushFront (xmlListPtr l,
+ void *data);
+int xmlListPushBack (xmlListPtr l,
+ void *data);
+
+/* Advanced Operators */
+void xmlListReverse (xmlListPtr l);
+void xmlListSort (xmlListPtr l);
+void xmlListWalk (xmlListPtr l,
+ xmlListWalker walker,
+ const void *user);
+void xmlListReverseWalk (xmlListPtr l,
+ xmlListWalker walker,
+ const void *user);
+void xmlListMerge (xmlListPtr l1,
+ xmlListPtr l2);
+xmlListPtr xmlListDup (const xmlListPtr old);
+int xmlListCopy (xmlListPtr cur,
+ const xmlListPtr old);
+/* Link operators */
+void * xmlLinkGetData (xmlLinkPtr lk);
+
+/* xmlListUnique() */
+/* xmlListSwap */
+
+
diff --git a/valid.c b/valid.c
index bdb7074..1b7e6f6 100644
--- a/valid.c
+++ b/valid.c
@@ -26,6 +26,7 @@
#include <libxml/parser.h>
#include <libxml/parserInternals.h>
#include <libxml/xmlerror.h>
+#include <libxml/list.h>
/*
* Generic function for accessing stacks in the Validity Context
@@ -1685,6 +1686,12 @@
* Refs *
* *
************************************************************************/
+typedef struct xmlRemove_t
+{
+ xmlListPtr l;
+ xmlAttrPtr ap;
+} xmlRemove;
+
/**
* xmlCreateRefTable:
*
@@ -1700,17 +1707,51 @@
/**
* xmlFreeRef:
- * @ref: A ref
+ * @lk: A list link
*
- * Deallocate the memory used by an ref definition
+ * Deallocate the memory used by a ref definition
*/
-void
-xmlFreeRef(xmlRefPtr ref) {
- if (ref == NULL) return;
- if (ref->value != NULL)
- xmlFree((xmlChar *) ref->value);
- memset(ref, -1, sizeof(xmlRef));
- xmlFree(ref);
+static void
+xmlFreeRef(xmlLinkPtr lk) {
+ xmlRefPtr ref = (xmlRefPtr)xmlLinkGetData(lk);
+ if (ref == NULL) return;
+ if (ref->value != NULL)
+ xmlFree((xmlChar *)ref->value);
+ memset(ref, -1, sizeof(xmlRef));
+ xmlFree(ref);
+}
+
+/**
+ * xmlFreeRefList:
+ * @list_ref: A list of references.
+ *
+ * Deallocate the memory used by a list of references
+ */
+static void
+xmlFreeRefList(xmlListPtr list_ref) {
+ if (list_ref == NULL) return;
+ xmlListDelete(list_ref);
+}
+
+/**
+ * xmlWalkRemoveRef:
+ * @data: Contents of current link
+ * @user: Value supplied by the user
+ *
+ * Return 0 to abort the walk or 1 to continue
+ */
+static int
+xmlWalkRemoveRef(const void *data, const void *user)
+{
+ xmlAttrPtr attr0 = ((xmlRefPtr)data)->attr;
+ xmlAttrPtr attr1 = ((xmlRemove *)user)->ap;
+ xmlListPtr ref_list = ((xmlRemove *)user)->l;
+
+ if (attr0 == attr1) { /* Matched: remove and terminate walk */
+ xmlListRemoveFirst(ref_list, (void *)data);
+ return 0;
+ }
+ return 1;
}
/**
@@ -1726,63 +1767,74 @@
*/
xmlRefPtr
xmlAddRef(xmlValidCtxtPtr ctxt, xmlDocPtr doc, const xmlChar *value,
- xmlAttrPtr attr) {
- xmlRefPtr ret;
- xmlRefTablePtr table;
+ xmlAttrPtr attr) {
+ xmlRefPtr ret;
+ xmlRefTablePtr table;
+ xmlListPtr ref_list;
- if (doc == NULL) {
- xmlGenericError(xmlGenericErrorContext,
- "xmlAddRefDecl: doc == NULL\n");
- return(NULL);
- }
- if (value == NULL) {
- xmlGenericError(xmlGenericErrorContext,
- "xmlAddRefDecl: value == NULL\n");
- return(NULL);
- }
- if (attr == NULL) {
- xmlGenericError(xmlGenericErrorContext,
- "xmlAddRefDecl: attr == NULL\n");
- return(NULL);
- }
+ if (doc == NULL) {
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlAddRefDecl: doc == NULL\n");
+ return(NULL);
+ }
+ if (value == NULL) {
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlAddRefDecl: value == NULL\n");
+ return(NULL);
+ }
+ if (attr == NULL) {
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlAddRefDecl: attr == NULL\n");
+ return(NULL);
+ }
- /*
+ /*
* Create the Ref table if needed.
*/
- table = (xmlRefTablePtr) doc->refs;
- if (table == NULL)
- doc->refs = table = xmlCreateRefTable();
- if (table == NULL) {
- xmlGenericError(xmlGenericErrorContext,
- "xmlAddRef: Table creation failed!\n");
- return(NULL);
- }
+ table = (xmlRefTablePtr) doc->refs;
+ if (table == NULL)
+ doc->refs = table = xmlCreateRefTable();
+ if (table == NULL) {
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlAddRef: Table creation failed!\n");
+ return(NULL);
+ }
- ret = (xmlRefPtr) xmlMalloc(sizeof(xmlRef));
- if (ret == NULL) {
- xmlGenericError(xmlGenericErrorContext,
- "xmlAddRef: out of memory\n");
- return(NULL);
- }
+ ret = (xmlRefPtr) xmlMalloc(sizeof(xmlRef));
+ if (ret == NULL) {
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlAddRef: out of memory\n");
+ return(NULL);
+ }
- /*
+ /*
* fill the structure.
*/
- ret->value = xmlStrdup(value);
- ret->attr = attr;
+ ret->value = xmlStrdup(value);
+ ret->attr = attr;
- /*
- * !!! Should we keep track of all refs ? and use xmlHashAddEntry2 ?
- */
- if (xmlHashAddEntry(table, value, ret) < 0) {
- /*
- * Since there is no discrimination on error returns
- * from xmlHashAddEntry, I'm presuming <0 means the
- * key already exists.
+ /* To add a reference :-
+ * References are maintained as a list of references,
+ * Lookup the entry, if no entry create new nodelist
+ * Add the owning node to the NodeList
+ * Return the ref
*/
- xmlHashUpdateEntry(table, value, ret, (xmlHashDeallocator) xmlFreeRef);
- }
- return(ret);
+
+ if(NULL == (ref_list = xmlHashLookup(table, value))) {
+ if(NULL == (ref_list = xmlListCreate(xmlFreeRef, NULL))) {
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlAddRef: Reference list creation failed!\n");
+ return(NULL);
+ }
+ if (xmlHashAddEntry(table, value, ref_list) < 0) {
+ xmlListDelete(ref_list);
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlAddRef: Reference list insertion failed!\n");
+ return(NULL);
+ }
+ }
+ xmlListInsert(ref_list, ret);
+ return(ret);
}
/**
@@ -1793,7 +1845,7 @@
*/
void
xmlFreeRefTable(xmlRefTablePtr table) {
- xmlHashFree(table, (xmlHashDeallocator) xmlFreeRef);
+ xmlHashFree(table, (xmlHashDeallocator) xmlFreeRefList);
}
/**
@@ -1810,23 +1862,23 @@
*/
int
xmlIsRef(xmlDocPtr doc, xmlNodePtr elem, xmlAttrPtr attr) {
- if ((doc->intSubset == NULL) && (doc->extSubset == NULL)) {
- return(0);
- } else if (doc->type == XML_HTML_DOCUMENT_NODE) {
- /* TODO @@@ */
- return(0);
- } else {
- xmlAttributePtr attrDecl;
+ if ((doc->intSubset == NULL) && (doc->extSubset == NULL)) {
+ return(0);
+ } else if (doc->type == XML_HTML_DOCUMENT_NODE) {
+ /* TODO @@@ */
+ return(0);
+ } else {
+ xmlAttributePtr attrDecl;
- attrDecl = xmlGetDtdAttrDesc(doc->intSubset, elem->name, attr->name);
- if ((attrDecl == NULL) && (doc->extSubset != NULL))
- attrDecl = xmlGetDtdAttrDesc(doc->extSubset, elem->name,
- attr->name);
+ attrDecl = xmlGetDtdAttrDesc(doc->intSubset, elem->name, attr->name);
+ if ((attrDecl == NULL) && (doc->extSubset != NULL))
+ attrDecl = xmlGetDtdAttrDesc(doc->extSubset, elem->name,
+ attr->name);
- if ((attrDecl != NULL) && (attrDecl->atype == XML_ATTRIBUTE_IDREF))
- return(1);
- }
- return(0);
+ if ((attrDecl != NULL) && (attrDecl->atype == XML_ATTRIBUTE_IDREF))
+ return(1);
+ }
+ return(0);
}
/**
@@ -1840,59 +1892,80 @@
*/
int
xmlRemoveRef(xmlDocPtr doc, xmlAttrPtr attr) {
- xmlAttrPtr cur;
- xmlRefTablePtr table;
- xmlChar *ID;
+ xmlListPtr ref_list;
+ xmlRefTablePtr table;
+ xmlChar *ID;
+ xmlRemove target;
- if (doc == NULL) return(-1);
- if (attr == NULL) return(-1);
- table = (xmlRefTablePtr) doc->refs;
- if (table == NULL)
- return(-1);
+ if (doc == NULL) return(-1);
+ if (attr == NULL) return(-1);
+ table = (xmlRefTablePtr) doc->refs;
+ if (table == NULL)
+ return(-1);
- if (attr == NULL)
- return(-1);
- ID = xmlNodeListGetString(doc, attr->children, 1);
- if (ID == NULL)
- return(-1);
- cur = xmlHashLookup(table, ID);
- if (cur != attr) {
+ if (attr == NULL)
+ return(-1);
+ ID = xmlNodeListGetString(doc, attr->children, 1);
+ if (ID == NULL)
+ return(-1);
+ ref_list = xmlHashLookup(table, ID);
+
+ if(ref_list == NULL) {
+ xmlFree(ID);
+ return (-1);
+ }
+ /* At this point, ref_list refers to a list of references which
+ * have the same key as the supplied attr. Our list of references
+ * is ordered by reference address and we don't have that information
+ * here to use when removing. We'll have to walk the list and
+ * check for a matching attribute, when we find one stop the walk
+ * and remove the entry.
+ * The list is ordered by reference, so that means we don't have the
+ * key. Passing the list and the reference to the walker means we
+ * will have enough data to be able to remove the entry.
+ */
+ target.l = ref_list;
+ target.ap = attr;
+
+ /* Remove the supplied attr from our list */
+ xmlListWalk(ref_list, xmlWalkRemoveRef, &target);
+
+ /*If the list is empty then remove the list entry in the hash */
+ if (xmlListEmpty(ref_list))
+ xmlHashUpdateEntry(table, ID, NULL, (xmlHashDeallocator)
+ xmlFreeRefList);
xmlFree(ID);
- return(-1);
- }
- xmlHashUpdateEntry(table, ID, NULL, (xmlHashDeallocator) xmlFreeRef);
- xmlFree(ID);
- return(0);
+ return(0);
}
/**
- * xmlGetRef:
+ * xmlGetRefs:
* @doc: pointer to the document
- * @Ref: the Ref value
+ * @ID: the ID value
*
- * Search the next attribute declaring the given Ref
+ * Find the set of references for the supplied ID.
*
- * Returns NULL if not found, otherwise the xmlAttrPtr defining the Ref
+ * Returns NULL if not found, otherwise node set for the ID.
*/
-xmlAttrPtr
-xmlGetRef(xmlDocPtr doc, const xmlChar *Ref) {
- xmlRefTablePtr table;
+xmlListPtr
+xmlGetRefs(xmlDocPtr doc, const xmlChar *ID) {
+ xmlRefTablePtr table;
- if (doc == NULL) {
- xmlGenericError(xmlGenericErrorContext, "xmlGetRef: doc == NULL\n");
- return(NULL);
- }
+ if (doc == NULL) {
+ xmlGenericError(xmlGenericErrorContext, "xmlGetRef: doc == NULL\n");
+ return(NULL);
+ }
- if (Ref == NULL) {
- xmlGenericError(xmlGenericErrorContext, "xmlGetRef: Ref == NULL\n");
- return(NULL);
- }
+ if (ID == NULL) {
+ xmlGenericError(xmlGenericErrorContext, "xmlGetRef: ID == NULL\n");
+ return(NULL);
+ }
- table = (xmlRefTablePtr) doc->refs;
- if (table == NULL)
- return(NULL);
+ table = (xmlRefTablePtr) doc->refs;
+ if (table == NULL)
+ return(NULL);
- return(xmlHashLookup(table, Ref));
+ return (xmlHashLookup(table, ID));
}
/************************************************************************