00001 /* SVN FILE INFO 00002 * $Revision: 174 $ : Last Committed Revision 00003 * $Date: 2008年06月24日 10:50:29 -0700 (2008年6月24日) $ : Last Committed Date */ 00004 /* 00005 * "$Id: mxml-index.c,v 1.1 2007年05月23日 20:43:27 david_ko Exp $" 00006 * 00007 * Index support code for Mini-XML, a small XML-like file parsing library. 00008 * 00009 * Copyright 2003-2005 by Michael Sweet. 00010 * 00011 * This program is free software; you can redistribute it and/or 00012 * modify it under the terms of the GNU Library General Public 00013 * License as published by the Free Software Foundation; either 00014 * version 2, or (at your option) any later version. 00015 * 00016 * This program is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00019 * GNU General Public License for more details. 00020 * 00021 * Contents: 00022 * 00023 * mxmlIndexDelete() - Delete an index. 00024 * mxmlIndexEnum() - Return the next node in the index. 00025 * mxmlIndexFind() - Find the next matching node. 00026 * mxmlIndexNew() - Create a new index. 00027 * mxmlIndexReset() - Reset the enumeration/find pointer in the index and 00028 * return the first node in the index. 00029 * index_compare() - Compare two nodes. 00030 * index_find() - Compare a node with index values. 00031 * index_sort() - Sort the nodes in the index... 00032 */ 00033 00034 /* 00035 * Include necessary headers... 00036 */ 00037 00038 #include "config.h" 00039 #include "mxml.h" 00040 00041 00042 /* 00043 * Sort functions... 00044 */ 00045 00046 static int index_compare(mxml_index_t *ind, mxml_node_t *first, 00047 mxml_node_t *second); 00048 static int index_find(mxml_index_t *ind, const char *element, 00049 const char *value, mxml_node_t *node); 00050 static void index_sort(mxml_index_t *ind, int left, int right); 00051 00052 00053 /* 00054 * 'mxmlIndexDelete()' - Delete an index. 00055 */ 00056 00057 void 00058 mxmlIndexDelete(mxml_index_t *ind) /* I - Index to delete */ 00059 { 00060 /* 00061 * Range check input.. 00062 */ 00063 00064 if (!ind) 00065 return; 00066 00067 /* 00068 * Free memory... 00069 */ 00070 00071 if (ind->attr) 00072 free(ind->attr); 00073 00074 if (ind->alloc_nodes) 00075 free(ind->nodes); 00076 00077 free(ind); 00078 } 00079 00080 00081 /* 00082 * 'mxmlIndexEnum()' - Return the next node in the index. 00083 * 00084 * Nodes are returned in the sorted order of the index. 00085 */ 00086 00087 mxml_node_t * /* O - Next node or NULL if there is none */ 00088 mxmlIndexEnum(mxml_index_t *ind) /* I - Index to enumerate */ 00089 { 00090 /* 00091 * Range check input... 00092 */ 00093 00094 if (!ind) 00095 return (NULL); 00096 00097 /* 00098 * Return the next node... 00099 */ 00100 00101 if (ind->cur_node < ind->num_nodes) 00102 return (ind->nodes[ind->cur_node ++]); 00103 else 00104 return (NULL); 00105 } 00106 00107 00108 /* 00109 * 'mxmlIndexFind()' - Find the next matching node. 00110 * 00111 * You should call mxmlIndexReset() prior to using this function for 00112 * the first time with a particular set of "element" and "value" 00113 * strings. Passing NULL for both "element" and "value" is equivalent 00114 * to calling mxmlIndexEnum(). 00115 */ 00116 00117 mxml_node_t * /* O - Node or NULL if none found */ 00118 mxmlIndexFind(mxml_index_t *ind, /* I - Index to search */ 00119 const char *element, /* I - Element name to find, if any */ 00120 const char *value) /* I - Attribute value, if any */ 00121 { 00122 int diff, /* Difference between names */ 00123 current, /* Current entity in search */ 00124 first, /* First entity in search */ 00125 last; /* Last entity in search */ 00126 00127 00128 #ifdef DEBUG 00129 printf("mxmlIndexFind(ind=%p, element=\"%s\", value=\"%s\")\n", 00130 ind, element ? element : "(null)", value ? value : "(null)"); 00131 #endif /* DEBUG */ 00132 00133 /* 00134 * Range check input... 00135 */ 00136 00137 if (!ind || (!ind->attr && value)) 00138 { 00139 #ifdef DEBUG 00140 puts(" returning NULL..."); 00141 printf(" ind->attr=\"%s\"\n", ind->attr ? ind->attr : "(null)"); 00142 #endif /* DEBUG */ 00143 00144 return (NULL); 00145 } 00146 00147 /* 00148 * If both element and value are NULL, just enumerate the nodes in the 00149 * index... 00150 */ 00151 00152 if (!element && !value) 00153 return (mxmlIndexEnum(ind)); 00154 00155 /* 00156 * If there are no nodes in the index, return NULL... 00157 */ 00158 00159 if (!ind->num_nodes) 00160 { 00161 #ifdef DEBUG 00162 puts(" returning NULL..."); 00163 puts(" no nodes!"); 00164 #endif /* DEBUG */ 00165 00166 return (NULL); 00167 } 00168 00169 /* 00170 * If cur_node == 0, then find the first matching node... 00171 */ 00172 00173 if (ind->cur_node == 0) 00174 { 00175 /* 00176 * Find the first node using a modified binary search algorithm... 00177 */ 00178 00179 first = 0; 00180 last = ind->num_nodes - 1; 00181 00182 #ifdef DEBUG 00183 printf(" find first time, num_nodes=%d...\n", ind->num_nodes); 00184 #endif /* DEBUG */ 00185 00186 while ((last - first) > 1) 00187 { 00188 current = (first + last) / 2; 00189 00190 #ifdef DEBUG 00191 printf(" first=%d, last=%d, current=%d\n", first, last, current); 00192 #endif /* DEBUG */ 00193 00194 if ((diff = index_find(ind, element, value, ind->nodes[current])) == 0) 00195 { 00196 /* 00197 * Found a match, move back to find the first... 00198 */ 00199 00200 #ifdef DEBUG 00201 puts(" match!"); 00202 #endif /* DEBUG */ 00203 00204 while (current > 0 && 00205 !index_find(ind, element, value, ind->nodes[current - 1])) 00206 current --; 00207 00208 #ifdef DEBUG 00209 printf(" returning first match=%d\n", current); 00210 #endif /* DEBUG */ 00211 00212 /* 00213 * Return the first match and save the index to the next... 00214 */ 00215 00216 ind->cur_node = current + 1; 00217 00218 return (ind->nodes[current]); 00219 } 00220 else if (diff < 0) 00221 last = current; 00222 else 00223 first = current; 00224 00225 #ifdef DEBUG 00226 printf(" diff=%d\n", diff); 00227 #endif /* DEBUG */ 00228 } 00229 00230 /* 00231 * If we get this far, then we found exactly 0 or 1 matches... 00232 */ 00233 00234 for (current = first; current <= last; current ++) 00235 if (!index_find(ind, element, value, ind->nodes[current])) 00236 { 00237 /* 00238 * Found exactly one (or possibly two) match... 00239 */ 00240 00241 #ifdef DEBUG 00242 printf(" returning only match %d...\n", current); 00243 #endif /* DEBUG */ 00244 00245 ind->cur_node = current + 1; 00246 00247 return (ind->nodes[current]); 00248 } 00249 00250 /* 00251 * No matches... 00252 */ 00253 00254 ind->cur_node = ind->num_nodes; 00255 00256 #ifdef DEBUG 00257 puts(" returning NULL..."); 00258 #endif /* DEBUG */ 00259 00260 return (NULL); 00261 } 00262 else if (ind->cur_node < ind->num_nodes && 00263 !index_find(ind, element, value, ind->nodes[ind->cur_node])) 00264 { 00265 /* 00266 * Return the next matching node... 00267 */ 00268 00269 #ifdef DEBUG 00270 printf(" returning next match %d...\n", ind->cur_node); 00271 #endif /* DEBUG */ 00272 00273 return (ind->nodes[ind->cur_node ++]); 00274 } 00275 00276 /* 00277 * If we get this far, then we have no matches... 00278 */ 00279 00280 ind->cur_node = ind->num_nodes; 00281 00282 #ifdef DEBUG 00283 puts(" returning NULL..."); 00284 #endif /* DEBUG */ 00285 00286 return (NULL); 00287 } 00288 00289 00290 /* 00291 * 'mxmlIndexNew()' - Create a new index. 00292 * 00293 * The index will contain all nodes that contain the named element and/or 00294 * attribute. If both "element" and "attr" are NULL, then the index will 00295 * contain a sorted list of the elements in the node tree. Nodes are 00296 * sorted by element name and optionally by attribute value if the "attr" 00297 * argument is not NULL. 00298 */ 00299 00300 mxml_index_t * /* O - New index */ 00301 mxmlIndexNew(mxml_node_t *node, /* I - XML node tree */ 00302 const char *element, /* I - Element to index or NULL for all */ 00303 const char *attr) /* I - Attribute to index or NULL for none */ 00304 { 00305 mxml_index_t *ind; /* New index */ 00306 mxml_node_t *current, /* Current node in index */ 00307 **temp; /* Temporary node pointer array */ 00308 00309 00310 /* 00311 * Range check input... 00312 */ 00313 00314 #ifdef DEBUG 00315 printf("mxmlIndexNew(node=%p, element=\"%s\", attr=\"%s\")\n", 00316 node, element ? element : "(null)", attr ? attr : "(null)"); 00317 #endif /* DEBUG */ 00318 00319 if (!node) 00320 return (NULL); 00321 00322 /* 00323 * Create a new index... 00324 */ 00325 00326 if ((ind = calloc(1, sizeof(mxml_index_t))) == NULL) 00327 { 00328 mxml_error("Unable to allocate %d bytes for index - %s", 00329 sizeof(mxml_index_t), strerror(errno)); 00330 return (NULL); 00331 } 00332 00333 if (attr) 00334 ind->attr = strdup(attr); 00335 00336 if (!element && !attr) 00337 current = node; 00338 else 00339 current = mxmlFindElement(node, node, element, attr, NULL, MXML_DESCEND); 00340 00341 while (current) 00342 { 00343 if (ind->num_nodes >= ind->alloc_nodes) 00344 { 00345 if (!ind->alloc_nodes) 00346 temp = malloc(64 * sizeof(mxml_node_t *)); 00347 else 00348 temp = realloc(ind->nodes, (ind->alloc_nodes + 64) * sizeof(mxml_node_t *)); 00349 00350 if (!temp) 00351 { 00352 /* 00353 * Unable to allocate memory for the index, so abort... 00354 */ 00355 00356 mxml_error("Unable to allocate %d bytes for index: %s", 00357 (ind->alloc_nodes + 64) * sizeof(mxml_node_t *), 00358 strerror(errno)); 00359 00360 mxmlIndexDelete(ind); 00361 return (NULL); 00362 } 00363 00364 ind->nodes = temp; 00365 ind->alloc_nodes += 64; 00366 } 00367 00368 ind->nodes[ind->num_nodes ++] = current; 00369 00370 current = mxmlFindElement(current, node, element, attr, NULL, MXML_DESCEND); 00371 } 00372 00373 /* 00374 * Sort nodes based upon the search criteria... 00375 */ 00376 00377 #ifdef DEBUG 00378 { 00379 int i; /* Looping var */ 00380 00381 00382 printf("%d node(s) in index.\n\n", ind->num_nodes); 00383 00384 if (attr) 00385 { 00386 printf("Node Address Element %s\n", attr); 00387 puts("-------- -------- -------------- ------------------------------"); 00388 00389 for (i = 0; i < ind->num_nodes; i ++) 00390 printf("%8d %-8p %-14.14s %s\n", i, ind->nodes[i], 00391 ind->nodes[i]->value.element.name, 00392 mxmlElementGetAttr(ind->nodes[i], attr)); 00393 } 00394 else 00395 { 00396 puts("Node Address Element"); 00397 puts("-------- -------- --------------"); 00398 00399 for (i = 0; i < ind->num_nodes; i ++) 00400 printf("%8d %-8p %s\n", i, ind->nodes[i], 00401 ind->nodes[i]->value.element.name); 00402 } 00403 00404 putchar('\n'); 00405 } 00406 #endif /* DEBUG */ 00407 00408 if (ind->num_nodes > 1) 00409 index_sort(ind, 0, ind->num_nodes - 1); 00410 00411 #ifdef DEBUG 00412 { 00413 int i; /* Looping var */ 00414 00415 00416 puts("After sorting:\n"); 00417 00418 if (attr) 00419 { 00420 printf("Node Address Element %s\n", attr); 00421 puts("-------- -------- -------------- ------------------------------"); 00422 00423 for (i = 0; i < ind->num_nodes; i ++) 00424 printf("%8d %-8p %-14.14s %s\n", i, ind->nodes[i], 00425 ind->nodes[i]->value.element.name, 00426 mxmlElementGetAttr(ind->nodes[i], attr)); 00427 } 00428 else 00429 { 00430 puts("Node Address Element"); 00431 puts("-------- -------- --------------"); 00432 00433 for (i = 0; i < ind->num_nodes; i ++) 00434 printf("%8d %-8p %s\n", i, ind->nodes[i], 00435 ind->nodes[i]->value.element.name); 00436 } 00437 00438 putchar('\n'); 00439 } 00440 #endif /* DEBUG */ 00441 00442 /* 00443 * Return the new index... 00444 */ 00445 00446 return (ind); 00447 } 00448 00449 00450 /* 00451 * 'mxmlIndexReset()' - Reset the enumeration/find pointer in the index and 00452 * return the first node in the index. 00453 * 00454 * This function should be called prior to using mxmlIndexEnum() or 00455 * mxmlIndexFind() for the first time. 00456 */ 00457 00458 mxml_node_t * /* O - First node or NULL if there is none */ 00459 mxmlIndexReset(mxml_index_t *ind) /* I - Index to reset */ 00460 { 00461 #ifdef DEBUG 00462 printf("mxmlIndexReset(ind=%p)\n", ind); 00463 #endif /* DEBUG */ 00464 00465 /* 00466 * Range check input... 00467 */ 00468 00469 if (!ind) 00470 return (NULL); 00471 00472 /* 00473 * Set the index to the first element... 00474 */ 00475 00476 ind->cur_node = 0; 00477 00478 /* 00479 * Return the first node... 00480 */ 00481 00482 if (ind->num_nodes) 00483 return (ind->nodes[0]); 00484 else 00485 return (NULL); 00486 } 00487 00488 00489 /* 00490 * 'index_compare()' - Compare two nodes. 00491 */ 00492 00493 static int /* O - Result of comparison */ 00494 index_compare(mxml_index_t *ind, /* I - Index */ 00495 mxml_node_t *first, /* I - First node */ 00496 mxml_node_t *second) /* I - Second node */ 00497 { 00498 int diff; /* Difference */ 00499 00500 00501 /* 00502 * Check the element name... 00503 */ 00504 00505 if ((diff = strcmp(first->value.element.name, 00506 second->value.element.name)) != 0) 00507 return (diff); 00508 00509 /* 00510 * Check the attribute value... 00511 */ 00512 00513 if (ind->attr) 00514 { 00515 if ((diff = strcmp(mxmlElementGetAttr(first, ind->attr), 00516 mxmlElementGetAttr(second, ind->attr))) != 0) 00517 return (diff); 00518 } 00519 00520 /* 00521 * No difference, return 0... 00522 */ 00523 00524 return (0); 00525 } 00526 00527 00528 /* 00529 * 'index_find()' - Compare a node with index values. 00530 */ 00531 00532 static int /* O - Result of comparison */ 00533 index_find(mxml_index_t *ind, /* I - Index */ 00534 const char *element, /* I - Element name or NULL */ 00535 const char *value, /* I - Attribute value or NULL */ 00536 mxml_node_t *node) /* I - Node */ 00537 { 00538 int diff; /* Difference */ 00539 00540 00541 /* 00542 * Check the element name... 00543 */ 00544 00545 if (element) 00546 { 00547 if ((diff = strcmp(element, node->value.element.name)) != 0) 00548 return (diff); 00549 } 00550 00551 /* 00552 * Check the attribute value... 00553 */ 00554 00555 if (value) 00556 { 00557 if ((diff = strcmp(value, mxmlElementGetAttr(node, ind->attr))) != 0) 00558 return (diff); 00559 } 00560 00561 /* 00562 * No difference, return 0... 00563 */ 00564 00565 return (0); 00566 } 00567 00568 00569 /* 00570 * 'index_sort()' - Sort the nodes in the index... 00571 * 00572 * This function implements the classic quicksort algorithm... 00573 */ 00574 00575 static void 00576 index_sort(mxml_index_t *ind, /* I - Index to sort */ 00577 int left, /* I - Left node in partition */ 00578 int right) /* I - Right node in partition */ 00579 { 00580 mxml_node_t *pivot, /* Pivot node */ 00581 *temp; /* Swap node */ 00582 int templ, /* Temporary left node */ 00583 tempr; /* Temporary right node */ 00584 00585 00586 /* 00587 * Loop until we have sorted all the way to the right... 00588 */ 00589 00590 do 00591 { 00592 /* 00593 * Sort the pivot in the current partition... 00594 */ 00595 00596 pivot = ind->nodes[left]; 00597 00598 for (templ = left, tempr = right; templ < tempr;) 00599 { 00600 /* 00601 * Move left while left node <= pivot node... 00602 */ 00603 00604 while ((templ < right) && 00605 index_compare(ind, ind->nodes[templ], pivot) <= 0) 00606 templ ++; 00607 00608 /* 00609 * Move right while right node > pivot node... 00610 */ 00611 00612 while ((tempr > left) && 00613 index_compare(ind, ind->nodes[tempr], pivot) > 0) 00614 tempr --; 00615 00616 /* 00617 * Swap nodes if needed... 00618 */ 00619 00620 if (templ < tempr) 00621 { 00622 temp = ind->nodes[templ]; 00623 ind->nodes[templ] = ind->nodes[tempr]; 00624 ind->nodes[tempr] = temp; 00625 } 00626 } 00627 00628 /* 00629 * When we get here, the right (tempr) node is the new position for the 00630 * pivot node... 00631 */ 00632 00633 if (index_compare(ind, pivot, ind->nodes[tempr]) > 0) 00634 { 00635 ind->nodes[left] = ind->nodes[tempr]; 00636 ind->nodes[tempr] = pivot; 00637 } 00638 00639 /* 00640 * Recursively sort the left partition as needed... 00641 */ 00642 00643 if (left < (tempr - 1)) 00644 index_sort(ind, left, tempr - 1); 00645 } 00646 while (right > (left = tempr + 1)); 00647 } 00648 00649 00650 /* 00651 * End of "$Id: mxml-index.c,v 1.1 2007年05月23日 20:43:27 david_ko Exp $". 00652 */