| /* |
| * "$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 $". |
| */ |