123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650 |
- /*
- * Index support code for Mini-XML, a small XML file parsing library.
- *
- * https://www.msweet.org/mxml
- *
- * Copyright © 2003-2019 by Michael R Sweet.
- *
- * Licensed under Apache License v2.0. See the file "LICENSE" for more
- * information.
- */
- /*
- * Include necessary headers...
- */
- #include "config.h"
- #include "mxml-private.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.
- *
- * You should call @link mxmlIndexReset@ prior to using this function to get
- * the first node in the index. Nodes are returned in the sorted order of the
- * index.
- */
- mxml_node_t * /* O - Next node or @code 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 @link mxmlIndexReset@ prior to using this function for
- * the first time with a particular set of "element" and "value"
- * strings. Passing @code NULL@ for both "element" and "value" is equivalent
- * to calling @link mxmlIndexEnum@.
- */
- mxml_node_t * /* O - Node or @code 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...");
- if (ind)
- 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 @code 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 @code NULL@ for all */
- const char *attr) /* I - Attribute to index or @code 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", (int)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", (int)((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 @link mxmlIndexEnum@ or
- * @link mxmlIndexFind@ for the first time.
- */
- mxml_node_t * /* O - First node or @code 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 @code NULL@ */
- const char *value, /* I - Attribute value or @code 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));
- }
|