summaryrefslogtreecommitdiff
path: root/xml/mxml-index.c
diff options
context:
space:
mode:
Diffstat (limited to 'xml/mxml-index.c')
-rw-r--r--xml/mxml-index.c662
1 files changed, 662 insertions, 0 deletions
diff --git a/xml/mxml-index.c b/xml/mxml-index.c
new file mode 100644
index 0000000..b6efc66
--- /dev/null
+++ b/xml/mxml-index.c
@@ -0,0 +1,662 @@
+/*
+ * "$Id: mxml-index.c 426 2011-01-01 23:42:17Z mike $"
+ *
+ * Index support code for Mini-XML, a small XML-like file parsing library.
+ *
+ * Copyright 2003-2011 by Michael R Sweet.
+ *
+ * These coded instructions, statements, and computer programs are the
+ * property of Michael R Sweet and are protected by Federal copyright
+ * law. Distribution and use rights are outlined in the file "COPYING"
+ * which should have been included with this file. If this file is
+ * missing or damaged, see the license at:
+ *
+ * http://www.minixml.org/
+ *
+ * Contents:
+ *
+ */
+
+/*
+ * Include necessary headers...
+ */
+
+#include "config.h"
+#include "mxml.h"
+
+
+/*
+ * Sort functions...
+ */
+
+static int index_compare(mxml_index_t *ind, mxml_node_t *first,
+ mxml_node_t *second);
+static int index_find(mxml_index_t *ind, const char *element,
+ const char *value, mxml_node_t *node);
+static void index_sort(mxml_index_t *ind, int left, int right);
+
+
+/*
+ * 'mxmlIndexDelete()' - Delete an index.
+ */
+
+void
+mxmlIndexDelete(mxml_index_t *ind) /* I - Index to delete */
+{
+ /*
+ * Range check input..
+ */
+
+ if (!ind)
+ return;
+
+ /*
+ * Free memory...
+ */
+
+ if (ind->attr)
+ free(ind->attr);
+
+ if (ind->alloc_nodes)
+ free(ind->nodes);
+
+ free(ind);
+}
+
+
+/*
+ * 'mxmlIndexEnum()' - Return the next node in the index.
+ *
+ * Nodes are returned in the sorted order of the index.
+ */
+
+mxml_node_t * /* O - Next node or NULL if there is none */
+mxmlIndexEnum(mxml_index_t *ind) /* I - Index to enumerate */
+{
+ /*
+ * Range check input...
+ */
+
+ if (!ind)
+ return (NULL);
+
+ /*
+ * Return the next node...
+ */
+
+ if (ind->cur_node < ind->num_nodes)
+ return (ind->nodes[ind->cur_node ++]);
+ else
+ return (NULL);
+}
+
+
+/*
+ * 'mxmlIndexFind()' - Find the next matching node.
+ *
+ * You should call mxmlIndexReset() prior to using this function for
+ * the first time with a particular set of "element" and "value"
+ * strings. Passing NULL for both "element" and "value" is equivalent
+ * to calling mxmlIndexEnum().
+ */
+
+mxml_node_t * /* O - Node or NULL if none found */
+mxmlIndexFind(mxml_index_t *ind, /* I - Index to search */
+ const char *element, /* I - Element name to find, if any */
+ const char *value) /* I - Attribute value, if any */
+{
+ int diff, /* Difference between names */
+ current, /* Current entity in search */
+ first, /* First entity in search */
+ last; /* Last entity in search */
+
+
+#ifdef DEBUG
+ printf("mxmlIndexFind(ind=%p, element=\"%s\", value=\"%s\")\n",
+ ind, element ? element : "(null)", value ? value : "(null)");
+#endif /* DEBUG */
+
+ /*
+ * Range check input...
+ */
+
+ if (!ind || (!ind->attr && value))
+ {
+#ifdef DEBUG
+ puts(" returning NULL...");
+ printf(" ind->attr=\"%s\"\n", ind->attr ? ind->attr : "(null)");
+#endif /* DEBUG */
+
+ return (NULL);
+ }
+
+ /*
+ * If both element and value are NULL, just enumerate the nodes in the
+ * index...
+ */
+
+ if (!element && !value)
+ return (mxmlIndexEnum(ind));
+
+ /*
+ * If there are no nodes in the index, return NULL...
+ */
+
+ if (!ind->num_nodes)
+ {
+#ifdef DEBUG
+ puts(" returning NULL...");
+ puts(" no nodes!");
+#endif /* DEBUG */
+
+ return (NULL);
+ }
+
+ /*
+ * If cur_node == 0, then find the first matching node...
+ */
+
+ if (ind->cur_node == 0)
+ {
+ /*
+ * Find the first node using a modified binary search algorithm...
+ */
+
+ first = 0;
+ last = ind->num_nodes - 1;
+
+#ifdef DEBUG
+ printf(" find first time, num_nodes=%d...\n", ind->num_nodes);
+#endif /* DEBUG */
+
+ while ((last - first) > 1)
+ {
+ current = (first + last) / 2;
+
+#ifdef DEBUG
+ printf(" first=%d, last=%d, current=%d\n", first, last, current);
+#endif /* DEBUG */
+
+ if ((diff = index_find(ind, element, value, ind->nodes[current])) == 0)
+ {
+ /*
+ * Found a match, move back to find the first...
+ */
+
+#ifdef DEBUG
+ puts(" match!");
+#endif /* DEBUG */
+
+ while (current > 0 &&
+ !index_find(ind, element, value, ind->nodes[current - 1]))
+ current --;
+
+#ifdef DEBUG
+ printf(" returning first match=%d\n", current);
+#endif /* DEBUG */
+
+ /*
+ * Return the first match and save the index to the next...
+ */
+
+ ind->cur_node = current + 1;
+
+ return (ind->nodes[current]);
+ }
+ else if (diff < 0)
+ last = current;
+ else
+ first = current;
+
+#ifdef DEBUG
+ printf(" diff=%d\n", diff);
+#endif /* DEBUG */
+ }
+
+ /*
+ * If we get this far, then we found exactly 0 or 1 matches...
+ */
+
+ for (current = first; current <= last; current ++)
+ if (!index_find(ind, element, value, ind->nodes[current]))
+ {
+ /*
+ * Found exactly one (or possibly two) match...
+ */
+
+#ifdef DEBUG
+ printf(" returning only match %d...\n", current);
+#endif /* DEBUG */
+
+ ind->cur_node = current + 1;
+
+ return (ind->nodes[current]);
+ }
+
+ /*
+ * No matches...
+ */
+
+ ind->cur_node = ind->num_nodes;
+
+#ifdef DEBUG
+ puts(" returning NULL...");
+#endif /* DEBUG */
+
+ return (NULL);
+ }
+ else if (ind->cur_node < ind->num_nodes &&
+ !index_find(ind, element, value, ind->nodes[ind->cur_node]))
+ {
+ /*
+ * Return the next matching node...
+ */
+
+#ifdef DEBUG
+ printf(" returning next match %d...\n", ind->cur_node);
+#endif /* DEBUG */
+
+ return (ind->nodes[ind->cur_node ++]);
+ }
+
+ /*
+ * If we get this far, then we have no matches...
+ */
+
+ ind->cur_node = ind->num_nodes;
+
+#ifdef DEBUG
+ puts(" returning NULL...");
+#endif /* DEBUG */
+
+ return (NULL);
+}
+
+
+/*
+ * 'mxmlIndexGetCount()' - Get the number of nodes in an index.
+ *
+ * @since Mini-XML 2.7@
+ */
+
+int /* I - Number of nodes in index */
+mxmlIndexGetCount(mxml_index_t *ind) /* I - Index of nodes */
+{
+ /*
+ * Range check input...
+ */
+
+ if (!ind)
+ return (0);
+
+ /*
+ * Return the number of nodes in the index...
+ */
+
+ return (ind->num_nodes);
+}
+
+
+/*
+ * 'mxmlIndexNew()' - Create a new index.
+ *
+ * The index will contain all nodes that contain the named element and/or
+ * attribute. If both "element" and "attr" are NULL, then the index will
+ * contain a sorted list of the elements in the node tree. Nodes are
+ * sorted by element name and optionally by attribute value if the "attr"
+ * argument is not NULL.
+ */
+
+mxml_index_t * /* O - New index */
+mxmlIndexNew(mxml_node_t *node, /* I - XML node tree */
+ const char *element, /* I - Element to index or NULL for all */
+ const char *attr) /* I - Attribute to index or NULL for none */
+{
+ mxml_index_t *ind; /* New index */
+ mxml_node_t *current, /* Current node in index */
+ **temp; /* Temporary node pointer array */
+
+
+ /*
+ * Range check input...
+ */
+
+#ifdef DEBUG
+ printf("mxmlIndexNew(node=%p, element=\"%s\", attr=\"%s\")\n",
+ node, element ? element : "(null)", attr ? attr : "(null)");
+#endif /* DEBUG */
+
+ if (!node)
+ return (NULL);
+
+ /*
+ * Create a new index...
+ */
+
+ if ((ind = calloc(1, sizeof(mxml_index_t))) == NULL)
+ {
+ mxml_error("Unable to allocate %d bytes for index - %s",
+ sizeof(mxml_index_t), strerror(errno));
+ return (NULL);
+ }
+
+ if (attr)
+ ind->attr = strdup(attr);
+
+ if (!element && !attr)
+ current = node;
+ else
+ current = mxmlFindElement(node, node, element, attr, NULL, MXML_DESCEND);
+
+ while (current)
+ {
+ if (ind->num_nodes >= ind->alloc_nodes)
+ {
+ if (!ind->alloc_nodes)
+ temp = malloc(64 * sizeof(mxml_node_t *));
+ else
+ temp = realloc(ind->nodes, (ind->alloc_nodes + 64) * sizeof(mxml_node_t *));
+
+ if (!temp)
+ {
+ /*
+ * Unable to allocate memory for the index, so abort...
+ */
+
+ mxml_error("Unable to allocate %d bytes for index: %s",
+ (ind->alloc_nodes + 64) * sizeof(mxml_node_t *),
+ strerror(errno));
+
+ mxmlIndexDelete(ind);
+ return (NULL);
+ }
+
+ ind->nodes = temp;
+ ind->alloc_nodes += 64;
+ }
+
+ ind->nodes[ind->num_nodes ++] = current;
+
+ current = mxmlFindElement(current, node, element, attr, NULL, MXML_DESCEND);
+ }
+
+ /*
+ * Sort nodes based upon the search criteria...
+ */
+
+#ifdef DEBUG
+ {
+ int i; /* Looping var */
+
+
+ printf("%d node(s) in index.\n\n", ind->num_nodes);
+
+ if (attr)
+ {
+ printf("Node Address Element %s\n", attr);
+ puts("-------- -------- -------------- ------------------------------");
+
+ for (i = 0; i < ind->num_nodes; i ++)
+ printf("%8d %-8p %-14.14s %s\n", i, ind->nodes[i],
+ ind->nodes[i]->value.element.name,
+ mxmlElementGetAttr(ind->nodes[i], attr));
+ }
+ else
+ {
+ puts("Node Address Element");
+ puts("-------- -------- --------------");
+
+ for (i = 0; i < ind->num_nodes; i ++)
+ printf("%8d %-8p %s\n", i, ind->nodes[i],
+ ind->nodes[i]->value.element.name);
+ }
+
+ putchar('\n');
+ }
+#endif /* DEBUG */
+
+ if (ind->num_nodes > 1)
+ index_sort(ind, 0, ind->num_nodes - 1);
+
+#ifdef DEBUG
+ {
+ int i; /* Looping var */
+
+
+ puts("After sorting:\n");
+
+ if (attr)
+ {
+ printf("Node Address Element %s\n", attr);
+ puts("-------- -------- -------------- ------------------------------");
+
+ for (i = 0; i < ind->num_nodes; i ++)
+ printf("%8d %-8p %-14.14s %s\n", i, ind->nodes[i],
+ ind->nodes[i]->value.element.name,
+ mxmlElementGetAttr(ind->nodes[i], attr));
+ }
+ else
+ {
+ puts("Node Address Element");
+ puts("-------- -------- --------------");
+
+ for (i = 0; i < ind->num_nodes; i ++)
+ printf("%8d %-8p %s\n", i, ind->nodes[i],
+ ind->nodes[i]->value.element.name);
+ }
+
+ putchar('\n');
+ }
+#endif /* DEBUG */
+
+ /*
+ * Return the new index...
+ */
+
+ return (ind);
+}
+
+
+/*
+ * 'mxmlIndexReset()' - Reset the enumeration/find pointer in the index and
+ * return the first node in the index.
+ *
+ * This function should be called prior to using mxmlIndexEnum() or
+ * mxmlIndexFind() for the first time.
+ */
+
+mxml_node_t * /* O - First node or NULL if there is none */
+mxmlIndexReset(mxml_index_t *ind) /* I - Index to reset */
+{
+#ifdef DEBUG
+ printf("mxmlIndexReset(ind=%p)\n", ind);
+#endif /* DEBUG */
+
+ /*
+ * Range check input...
+ */
+
+ if (!ind)
+ return (NULL);
+
+ /*
+ * Set the index to the first element...
+ */
+
+ ind->cur_node = 0;
+
+ /*
+ * Return the first node...
+ */
+
+ if (ind->num_nodes)
+ return (ind->nodes[0]);
+ else
+ return (NULL);
+}
+
+
+/*
+ * 'index_compare()' - Compare two nodes.
+ */
+
+static int /* O - Result of comparison */
+index_compare(mxml_index_t *ind, /* I - Index */
+ mxml_node_t *first, /* I - First node */
+ mxml_node_t *second) /* I - Second node */
+{
+ int diff; /* Difference */
+
+
+ /*
+ * Check the element name...
+ */
+
+ if ((diff = strcmp(first->value.element.name,
+ second->value.element.name)) != 0)
+ return (diff);
+
+ /*
+ * Check the attribute value...
+ */
+
+ if (ind->attr)
+ {
+ if ((diff = strcmp(mxmlElementGetAttr(first, ind->attr),
+ mxmlElementGetAttr(second, ind->attr))) != 0)
+ return (diff);
+ }
+
+ /*
+ * No difference, return 0...
+ */
+
+ return (0);
+}
+
+
+/*
+ * 'index_find()' - Compare a node with index values.
+ */
+
+static int /* O - Result of comparison */
+index_find(mxml_index_t *ind, /* I - Index */
+ const char *element, /* I - Element name or NULL */
+ const char *value, /* I - Attribute value or NULL */
+ mxml_node_t *node) /* I - Node */
+{
+ int diff; /* Difference */
+
+
+ /*
+ * Check the element name...
+ */
+
+ if (element)
+ {
+ if ((diff = strcmp(element, node->value.element.name)) != 0)
+ return (diff);
+ }
+
+ /*
+ * Check the attribute value...
+ */
+
+ if (value)
+ {
+ if ((diff = strcmp(value, mxmlElementGetAttr(node, ind->attr))) != 0)
+ return (diff);
+ }
+
+ /*
+ * No difference, return 0...
+ */
+
+ return (0);
+}
+
+
+/*
+ * 'index_sort()' - Sort the nodes in the index...
+ *
+ * This function implements the classic quicksort algorithm...
+ */
+
+static void
+index_sort(mxml_index_t *ind, /* I - Index to sort */
+ int left, /* I - Left node in partition */
+ int right) /* I - Right node in partition */
+{
+ mxml_node_t *pivot, /* Pivot node */
+ *temp; /* Swap node */
+ int templ, /* Temporary left node */
+ tempr; /* Temporary right node */
+
+
+ /*
+ * Loop until we have sorted all the way to the right...
+ */
+
+ do
+ {
+ /*
+ * Sort the pivot in the current partition...
+ */
+
+ pivot = ind->nodes[left];
+
+ for (templ = left, tempr = right; templ < tempr;)
+ {
+ /*
+ * Move left while left node <= pivot node...
+ */
+
+ while ((templ < right) &&
+ index_compare(ind, ind->nodes[templ], pivot) <= 0)
+ templ ++;
+
+ /*
+ * Move right while right node > pivot node...
+ */
+
+ while ((tempr > left) &&
+ index_compare(ind, ind->nodes[tempr], pivot) > 0)
+ tempr --;
+
+ /*
+ * Swap nodes if needed...
+ */
+
+ if (templ < tempr)
+ {
+ temp = ind->nodes[templ];
+ ind->nodes[templ] = ind->nodes[tempr];
+ ind->nodes[tempr] = temp;
+ }
+ }
+
+ /*
+ * When we get here, the right (tempr) node is the new position for the
+ * pivot node...
+ */
+
+ if (index_compare(ind, pivot, ind->nodes[tempr]) > 0)
+ {
+ ind->nodes[left] = ind->nodes[tempr];
+ ind->nodes[tempr] = pivot;
+ }
+
+ /*
+ * Recursively sort the left partition as needed...
+ */
+
+ if (left < (tempr - 1))
+ index_sort(ind, left, tempr - 1);
+ }
+ while (right > (left = tempr + 1));
+}
+
+
+/*
+ * End of "$Id: mxml-index.c 426 2011-01-01 23:42:17Z mike $".
+ */
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-10 04:12:19 +0000