root / logic / trunk / src / mxml / mxml-index.c @ 49
History | View | Annotate | Download (13.7 KB)
| 1 |
/*
|
|---|---|
| 2 |
* "$Id: mxml-index.c 184 2005-01-29 07:21:44Z mike $"
|
| 3 |
*
|
| 4 |
* Index support code for Mini-XML, a small XML-like file parsing library.
|
| 5 |
*
|
| 6 |
* Copyright 2003-2005 by Michael Sweet.
|
| 7 |
*
|
| 8 |
* This program is free software; you can redistribute it and/or
|
| 9 |
* modify it under the terms of the GNU Library General Public
|
| 10 |
* License as published by the Free Software Foundation; either
|
| 11 |
* version 2, or (at your option) any later version.
|
| 12 |
*
|
| 13 |
* This program is distributed in the hope that it will be useful,
|
| 14 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
| 15 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
| 16 |
* GNU General Public License for more details.
|
| 17 |
*
|
| 18 |
* Contents:
|
| 19 |
*
|
| 20 |
* mxmlIndexDelete() - Delete an index.
|
| 21 |
* mxmlIndexEnum() - Return the next node in the index.
|
| 22 |
* mxmlIndexFind() - Find the next matching node.
|
| 23 |
* mxmlIndexNew() - Create a new index.
|
| 24 |
* mxmlIndexReset() - Reset the enumeration/find pointer in the index and
|
| 25 |
* return the first node in the index.
|
| 26 |
* index_compare() - Compare two nodes.
|
| 27 |
* index_find() - Compare a node with index values.
|
| 28 |
* index_sort() - Sort the nodes in the index...
|
| 29 |
*/
|
| 30 |
|
| 31 |
/*
|
| 32 |
* Include necessary headers...
|
| 33 |
*/
|
| 34 |
|
| 35 |
#include "config.h" |
| 36 |
#include "mxml.h" |
| 37 |
|
| 38 |
|
| 39 |
/*
|
| 40 |
* Sort functions...
|
| 41 |
*/
|
| 42 |
|
| 43 |
static int index_compare(mxml_index_t *ind, mxml_node_t *first, |
| 44 |
mxml_node_t *second); |
| 45 |
static int index_find(mxml_index_t *ind, const char *element, |
| 46 |
const char *value, mxml_node_t *node); |
| 47 |
static void index_sort(mxml_index_t *ind, int left, int right); |
| 48 |
|
| 49 |
|
| 50 |
/*
|
| 51 |
* 'mxmlIndexDelete()' - Delete an index.
|
| 52 |
*/
|
| 53 |
|
| 54 |
void
|
| 55 |
mxmlIndexDelete(mxml_index_t *ind) /* I - Index to delete */
|
| 56 |
{
|
| 57 |
/*
|
| 58 |
* Range check input..
|
| 59 |
*/
|
| 60 |
|
| 61 |
if (!ind)
|
| 62 |
return;
|
| 63 |
|
| 64 |
/*
|
| 65 |
* Free memory...
|
| 66 |
*/
|
| 67 |
|
| 68 |
if (ind->attr)
|
| 69 |
free(ind->attr); |
| 70 |
|
| 71 |
if (ind->alloc_nodes)
|
| 72 |
free(ind->nodes); |
| 73 |
|
| 74 |
free(ind); |
| 75 |
} |
| 76 |
|
| 77 |
|
| 78 |
/*
|
| 79 |
* 'mxmlIndexEnum()' - Return the next node in the index.
|
| 80 |
*
|
| 81 |
* Nodes are returned in the sorted order of the index.
|
| 82 |
*/
|
| 83 |
|
| 84 |
mxml_node_t * /* O - Next node or NULL if there is none */
|
| 85 |
mxmlIndexEnum(mxml_index_t *ind) /* I - Index to enumerate */
|
| 86 |
{
|
| 87 |
/*
|
| 88 |
* Range check input...
|
| 89 |
*/
|
| 90 |
|
| 91 |
if (!ind)
|
| 92 |
return (NULL); |
| 93 |
|
| 94 |
/*
|
| 95 |
* Return the next node...
|
| 96 |
*/
|
| 97 |
|
| 98 |
if (ind->cur_node < ind->num_nodes)
|
| 99 |
return (ind->nodes[ind->cur_node ++]);
|
| 100 |
else
|
| 101 |
return (NULL); |
| 102 |
} |
| 103 |
|
| 104 |
|
| 105 |
/*
|
| 106 |
* 'mxmlIndexFind()' - Find the next matching node.
|
| 107 |
*
|
| 108 |
* You should call mxmlIndexReset() prior to using this function for
|
| 109 |
* the first time with a particular set of "element" and "value"
|
| 110 |
* strings. Passing NULL for both "element" and "value" is equivalent
|
| 111 |
* to calling mxmlIndexEnum().
|
| 112 |
*/
|
| 113 |
|
| 114 |
mxml_node_t * /* O - Node or NULL if none found */
|
| 115 |
mxmlIndexFind(mxml_index_t *ind, /* I - Index to search */
|
| 116 |
const char *element, /* I - Element name to find, if any */ |
| 117 |
const char *value) /* I - Attribute value, if any */ |
| 118 |
{
|
| 119 |
int diff, /* Difference between names */ |
| 120 |
current, /* Current entity in search */
|
| 121 |
first, /* First entity in search */
|
| 122 |
last; /* Last entity in search */
|
| 123 |
|
| 124 |
|
| 125 |
#ifdef DEBUG
|
| 126 |
printf("mxmlIndexFind(ind=%p, element=\"%s\", value=\"%s\")\n",
|
| 127 |
ind, element ? element : "(null)", value ? value : "(null)"); |
| 128 |
#endif /* DEBUG */ |
| 129 |
|
| 130 |
/*
|
| 131 |
* Range check input...
|
| 132 |
*/
|
| 133 |
|
| 134 |
if (!ind || (!ind->attr && value))
|
| 135 |
{
|
| 136 |
#ifdef DEBUG
|
| 137 |
puts(" returning NULL...");
|
| 138 |
printf(" ind->attr=\"%s\"\n", ind->attr ? ind->attr : "(null)"); |
| 139 |
#endif /* DEBUG */ |
| 140 |
|
| 141 |
return (NULL); |
| 142 |
} |
| 143 |
|
| 144 |
/*
|
| 145 |
* If both element and value are NULL, just enumerate the nodes in the
|
| 146 |
* index...
|
| 147 |
*/
|
| 148 |
|
| 149 |
if (!element && !value)
|
| 150 |
return (mxmlIndexEnum(ind));
|
| 151 |
|
| 152 |
/*
|
| 153 |
* If there are no nodes in the index, return NULL...
|
| 154 |
*/
|
| 155 |
|
| 156 |
if (!ind->num_nodes)
|
| 157 |
{
|
| 158 |
#ifdef DEBUG
|
| 159 |
puts(" returning NULL...");
|
| 160 |
puts(" no nodes!");
|
| 161 |
#endif /* DEBUG */ |
| 162 |
|
| 163 |
return (NULL); |
| 164 |
} |
| 165 |
|
| 166 |
/*
|
| 167 |
* If cur_node == 0, then find the first matching node...
|
| 168 |
*/
|
| 169 |
|
| 170 |
if (ind->cur_node == 0) |
| 171 |
{
|
| 172 |
/*
|
| 173 |
* Find the first node using a modified binary search algorithm...
|
| 174 |
*/
|
| 175 |
|
| 176 |
first = 0;
|
| 177 |
last = ind->num_nodes - 1;
|
| 178 |
|
| 179 |
#ifdef DEBUG
|
| 180 |
printf(" find first time, num_nodes=%d...\n", ind->num_nodes);
|
| 181 |
#endif /* DEBUG */ |
| 182 |
|
| 183 |
while ((last - first) > 1) |
| 184 |
{
|
| 185 |
current = (first + last) / 2;
|
| 186 |
|
| 187 |
#ifdef DEBUG
|
| 188 |
printf(" first=%d, last=%d, current=%d\n", first, last, current);
|
| 189 |
#endif /* DEBUG */ |
| 190 |
|
| 191 |
if ((diff = index_find(ind, element, value, ind->nodes[current])) == 0) |
| 192 |
{
|
| 193 |
/*
|
| 194 |
* Found a match, move back to find the first...
|
| 195 |
*/
|
| 196 |
|
| 197 |
#ifdef DEBUG
|
| 198 |
puts(" match!");
|
| 199 |
#endif /* DEBUG */ |
| 200 |
|
| 201 |
while (current > 0 && |
| 202 |
!index_find(ind, element, value, ind->nodes[current - 1]))
|
| 203 |
current --; |
| 204 |
|
| 205 |
#ifdef DEBUG
|
| 206 |
printf(" returning first match=%d\n", current);
|
| 207 |
#endif /* DEBUG */ |
| 208 |
|
| 209 |
/*
|
| 210 |
* Return the first match and save the index to the next...
|
| 211 |
*/
|
| 212 |
|
| 213 |
ind->cur_node = current + 1;
|
| 214 |
|
| 215 |
return (ind->nodes[current]);
|
| 216 |
} |
| 217 |
else if (diff < 0) |
| 218 |
last = current; |
| 219 |
else
|
| 220 |
first = current; |
| 221 |
|
| 222 |
#ifdef DEBUG
|
| 223 |
printf(" diff=%d\n", diff);
|
| 224 |
#endif /* DEBUG */ |
| 225 |
} |
| 226 |
|
| 227 |
/*
|
| 228 |
* If we get this far, then we found exactly 0 or 1 matches...
|
| 229 |
*/
|
| 230 |
|
| 231 |
for (current = first; current <= last; current ++)
|
| 232 |
if (!index_find(ind, element, value, ind->nodes[current]))
|
| 233 |
{
|
| 234 |
/*
|
| 235 |
* Found exactly one (or possibly two) match...
|
| 236 |
*/
|
| 237 |
|
| 238 |
#ifdef DEBUG
|
| 239 |
printf(" returning only match %d...\n", current);
|
| 240 |
#endif /* DEBUG */ |
| 241 |
|
| 242 |
ind->cur_node = current + 1;
|
| 243 |
|
| 244 |
return (ind->nodes[current]);
|
| 245 |
} |
| 246 |
|
| 247 |
/*
|
| 248 |
* No matches...
|
| 249 |
*/
|
| 250 |
|
| 251 |
ind->cur_node = ind->num_nodes; |
| 252 |
|
| 253 |
#ifdef DEBUG
|
| 254 |
puts(" returning NULL...");
|
| 255 |
#endif /* DEBUG */ |
| 256 |
|
| 257 |
return (NULL); |
| 258 |
} |
| 259 |
else if (ind->cur_node < ind->num_nodes && |
| 260 |
!index_find(ind, element, value, ind->nodes[ind->cur_node])) |
| 261 |
{
|
| 262 |
/*
|
| 263 |
* Return the next matching node...
|
| 264 |
*/
|
| 265 |
|
| 266 |
#ifdef DEBUG
|
| 267 |
printf(" returning next match %d...\n", ind->cur_node);
|
| 268 |
#endif /* DEBUG */ |
| 269 |
|
| 270 |
return (ind->nodes[ind->cur_node ++]);
|
| 271 |
} |
| 272 |
|
| 273 |
/*
|
| 274 |
* If we get this far, then we have no matches...
|
| 275 |
*/
|
| 276 |
|
| 277 |
ind->cur_node = ind->num_nodes; |
| 278 |
|
| 279 |
#ifdef DEBUG
|
| 280 |
puts(" returning NULL...");
|
| 281 |
#endif /* DEBUG */ |
| 282 |
|
| 283 |
return (NULL); |
| 284 |
} |
| 285 |
|
| 286 |
|
| 287 |
/*
|
| 288 |
* 'mxmlIndexNew()' - Create a new index.
|
| 289 |
*
|
| 290 |
* The index will contain all nodes that contain the named element and/or
|
| 291 |
* attribute. If both "element" and "attr" are NULL, then the index will
|
| 292 |
* contain a sorted list of the elements in the node tree. Nodes are
|
| 293 |
* sorted by element name and optionally by attribute value if the "attr"
|
| 294 |
* argument is not NULL.
|
| 295 |
*/
|
| 296 |
|
| 297 |
mxml_index_t * /* O - New index */
|
| 298 |
mxmlIndexNew(mxml_node_t *node, /* I - XML node tree */
|
| 299 |
const char *element, /* I - Element to index or NULL for all */ |
| 300 |
const char *attr) /* I - Attribute to index or NULL for none */ |
| 301 |
{
|
| 302 |
mxml_index_t *ind; /* New index */
|
| 303 |
mxml_node_t *current, /* Current node in index */
|
| 304 |
**temp; /* Temporary node pointer array */
|
| 305 |
|
| 306 |
|
| 307 |
/*
|
| 308 |
* Range check input...
|
| 309 |
*/
|
| 310 |
|
| 311 |
#ifdef DEBUG
|
| 312 |
printf("mxmlIndexNew(node=%p, element=\"%s\", attr=\"%s\")\n",
|
| 313 |
node, element ? element : "(null)", attr ? attr : "(null)"); |
| 314 |
#endif /* DEBUG */ |
| 315 |
|
| 316 |
if (!node)
|
| 317 |
return (NULL); |
| 318 |
|
| 319 |
/*
|
| 320 |
* Create a new index...
|
| 321 |
*/
|
| 322 |
|
| 323 |
if ((ind = calloc(1, sizeof(mxml_index_t))) == NULL) |
| 324 |
{
|
| 325 |
mxml_error("Unable to allocate %d bytes for index - %s",
|
| 326 |
sizeof(mxml_index_t), strerror(errno));
|
| 327 |
return (NULL); |
| 328 |
} |
| 329 |
|
| 330 |
if (attr)
|
| 331 |
ind->attr = strdup(attr); |
| 332 |
|
| 333 |
if (!element && !attr)
|
| 334 |
current = node; |
| 335 |
else
|
| 336 |
current = mxmlFindElement(node, node, element, attr, NULL, MXML_DESCEND);
|
| 337 |
|
| 338 |
while (current)
|
| 339 |
{
|
| 340 |
if (ind->num_nodes >= ind->alloc_nodes)
|
| 341 |
{
|
| 342 |
if (!ind->alloc_nodes)
|
| 343 |
temp = malloc(64 * sizeof(mxml_node_t *)); |
| 344 |
else
|
| 345 |
temp = realloc(ind->nodes, (ind->alloc_nodes + 64) * sizeof(mxml_node_t *)); |
| 346 |
|
| 347 |
if (!temp)
|
| 348 |
{
|
| 349 |
/*
|
| 350 |
* Unable to allocate memory for the index, so abort...
|
| 351 |
*/
|
| 352 |
|
| 353 |
mxml_error("Unable to allocate %d bytes for index: %s",
|
| 354 |
(ind->alloc_nodes + 64) * sizeof(mxml_node_t *), |
| 355 |
strerror(errno)); |
| 356 |
|
| 357 |
mxmlIndexDelete(ind); |
| 358 |
return (NULL); |
| 359 |
} |
| 360 |
|
| 361 |
ind->nodes = temp; |
| 362 |
ind->alloc_nodes += 64;
|
| 363 |
} |
| 364 |
|
| 365 |
ind->nodes[ind->num_nodes ++] = current; |
| 366 |
|
| 367 |
current = mxmlFindElement(current, node, element, attr, NULL, MXML_DESCEND);
|
| 368 |
} |
| 369 |
|
| 370 |
/*
|
| 371 |
* Sort nodes based upon the search criteria...
|
| 372 |
*/
|
| 373 |
|
| 374 |
#ifdef DEBUG
|
| 375 |
{
|
| 376 |
int i; /* Looping var */ |
| 377 |
|
| 378 |
|
| 379 |
printf("%d node(s) in index.\n\n", ind->num_nodes);
|
| 380 |
|
| 381 |
if (attr)
|
| 382 |
{
|
| 383 |
printf("Node Address Element %s\n", attr);
|
| 384 |
puts("-------- -------- -------------- ------------------------------");
|
| 385 |
|
| 386 |
for (i = 0; i < ind->num_nodes; i ++) |
| 387 |
printf("%8d %-8p %-14.14s %s\n", i, ind->nodes[i],
|
| 388 |
ind->nodes[i]->value.element.name, |
| 389 |
mxmlElementGetAttr(ind->nodes[i], attr)); |
| 390 |
} |
| 391 |
else
|
| 392 |
{
|
| 393 |
puts("Node Address Element");
|
| 394 |
puts("-------- -------- --------------");
|
| 395 |
|
| 396 |
for (i = 0; i < ind->num_nodes; i ++) |
| 397 |
printf("%8d %-8p %s\n", i, ind->nodes[i],
|
| 398 |
ind->nodes[i]->value.element.name); |
| 399 |
} |
| 400 |
|
| 401 |
putchar('\n');
|
| 402 |
} |
| 403 |
#endif /* DEBUG */ |
| 404 |
|
| 405 |
if (ind->num_nodes > 1) |
| 406 |
index_sort(ind, 0, ind->num_nodes - 1); |
| 407 |
|
| 408 |
#ifdef DEBUG
|
| 409 |
{
|
| 410 |
int i; /* Looping var */ |
| 411 |
|
| 412 |
|
| 413 |
puts("After sorting:\n");
|
| 414 |
|
| 415 |
if (attr)
|
| 416 |
{
|
| 417 |
printf("Node Address Element %s\n", attr);
|
| 418 |
puts("-------- -------- -------------- ------------------------------");
|
| 419 |
|
| 420 |
for (i = 0; i < ind->num_nodes; i ++) |
| 421 |
printf("%8d %-8p %-14.14s %s\n", i, ind->nodes[i],
|
| 422 |
ind->nodes[i]->value.element.name, |
| 423 |
mxmlElementGetAttr(ind->nodes[i], attr)); |
| 424 |
} |
| 425 |
else
|
| 426 |
{
|
| 427 |
puts("Node Address Element");
|
| 428 |
puts("-------- -------- --------------");
|
| 429 |
|
| 430 |
for (i = 0; i < ind->num_nodes; i ++) |
| 431 |
printf("%8d %-8p %s\n", i, ind->nodes[i],
|
| 432 |
ind->nodes[i]->value.element.name); |
| 433 |
} |
| 434 |
|
| 435 |
putchar('\n');
|
| 436 |
} |
| 437 |
#endif /* DEBUG */ |
| 438 |
|
| 439 |
/*
|
| 440 |
* Return the new index...
|
| 441 |
*/
|
| 442 |
|
| 443 |
return (ind);
|
| 444 |
} |
| 445 |
|
| 446 |
|
| 447 |
/*
|
| 448 |
* 'mxmlIndexReset()' - Reset the enumeration/find pointer in the index and
|
| 449 |
* return the first node in the index.
|
| 450 |
*
|
| 451 |
* This function should be called prior to using mxmlIndexEnum() or
|
| 452 |
* mxmlIndexFind() for the first time.
|
| 453 |
*/
|
| 454 |
|
| 455 |
mxml_node_t * /* O - First node or NULL if there is none */
|
| 456 |
mxmlIndexReset(mxml_index_t *ind) /* I - Index to reset */
|
| 457 |
{
|
| 458 |
#ifdef DEBUG
|
| 459 |
printf("mxmlIndexReset(ind=%p)\n", ind);
|
| 460 |
#endif /* DEBUG */ |
| 461 |
|
| 462 |
/*
|
| 463 |
* Range check input...
|
| 464 |
*/
|
| 465 |
|
| 466 |
if (!ind)
|
| 467 |
return (NULL); |
| 468 |
|
| 469 |
/*
|
| 470 |
* Set the index to the first element...
|
| 471 |
*/
|
| 472 |
|
| 473 |
ind->cur_node = 0;
|
| 474 |
|
| 475 |
/*
|
| 476 |
* Return the first node...
|
| 477 |
*/
|
| 478 |
|
| 479 |
if (ind->num_nodes)
|
| 480 |
return (ind->nodes[0]); |
| 481 |
else
|
| 482 |
return (NULL); |
| 483 |
} |
| 484 |
|
| 485 |
|
| 486 |
/*
|
| 487 |
* 'index_compare()' - Compare two nodes.
|
| 488 |
*/
|
| 489 |
|
| 490 |
static int /* O - Result of comparison */ |
| 491 |
index_compare(mxml_index_t *ind, /* I - Index */
|
| 492 |
mxml_node_t *first, /* I - First node */
|
| 493 |
mxml_node_t *second) /* I - Second node */
|
| 494 |
{
|
| 495 |
int diff; /* Difference */ |
| 496 |
|
| 497 |
|
| 498 |
/*
|
| 499 |
* Check the element name...
|
| 500 |
*/
|
| 501 |
|
| 502 |
if ((diff = strcmp(first->value.element.name,
|
| 503 |
second->value.element.name)) != 0)
|
| 504 |
return (diff);
|
| 505 |
|
| 506 |
/*
|
| 507 |
* Check the attribute value...
|
| 508 |
*/
|
| 509 |
|
| 510 |
if (ind->attr)
|
| 511 |
{
|
| 512 |
if ((diff = strcmp(mxmlElementGetAttr(first, ind->attr),
|
| 513 |
mxmlElementGetAttr(second, ind->attr))) != 0)
|
| 514 |
return (diff);
|
| 515 |
} |
| 516 |
|
| 517 |
/*
|
| 518 |
* No difference, return 0...
|
| 519 |
*/
|
| 520 |
|
| 521 |
return (0); |
| 522 |
} |
| 523 |
|
| 524 |
|
| 525 |
/*
|
| 526 |
* 'index_find()' - Compare a node with index values.
|
| 527 |
*/
|
| 528 |
|
| 529 |
static int /* O - Result of comparison */ |
| 530 |
index_find(mxml_index_t *ind, /* I - Index */
|
| 531 |
const char *element, /* I - Element name or NULL */ |
| 532 |
const char *value, /* I - Attribute value or NULL */ |
| 533 |
mxml_node_t *node) /* I - Node */
|
| 534 |
{
|
| 535 |
int diff; /* Difference */ |
| 536 |
|
| 537 |
|
| 538 |
/*
|
| 539 |
* Check the element name...
|
| 540 |
*/
|
| 541 |
|
| 542 |
if (element)
|
| 543 |
{
|
| 544 |
if ((diff = strcmp(element, node->value.element.name)) != 0) |
| 545 |
return (diff);
|
| 546 |
} |
| 547 |
|
| 548 |
/*
|
| 549 |
* Check the attribute value...
|
| 550 |
*/
|
| 551 |
|
| 552 |
if (value)
|
| 553 |
{
|
| 554 |
if ((diff = strcmp(value, mxmlElementGetAttr(node, ind->attr))) != 0) |
| 555 |
return (diff);
|
| 556 |
} |
| 557 |
|
| 558 |
/*
|
| 559 |
* No difference, return 0...
|
| 560 |
*/
|
| 561 |
|
| 562 |
return (0); |
| 563 |
} |
| 564 |
|
| 565 |
|
| 566 |
/*
|
| 567 |
* 'index_sort()' - Sort the nodes in the index...
|
| 568 |
*
|
| 569 |
* This function implements the classic quicksort algorithm...
|
| 570 |
*/
|
| 571 |
|
| 572 |
static void |
| 573 |
index_sort(mxml_index_t *ind, /* I - Index to sort */
|
| 574 |
int left, /* I - Left node in partition */ |
| 575 |
int right) /* I - Right node in partition */ |
| 576 |
{
|
| 577 |
mxml_node_t *pivot, /* Pivot node */
|
| 578 |
*temp; /* Swap node */
|
| 579 |
int templ, /* Temporary left node */ |
| 580 |
tempr; /* Temporary right node */
|
| 581 |
|
| 582 |
|
| 583 |
/*
|
| 584 |
* Loop until we have sorted all the way to the right...
|
| 585 |
*/
|
| 586 |
|
| 587 |
do
|
| 588 |
{
|
| 589 |
/*
|
| 590 |
* Sort the pivot in the current partition...
|
| 591 |
*/
|
| 592 |
|
| 593 |
pivot = ind->nodes[left]; |
| 594 |
|
| 595 |
for (templ = left, tempr = right; templ < tempr;)
|
| 596 |
{
|
| 597 |
/*
|
| 598 |
* Move left while left node <= pivot node...
|
| 599 |
*/
|
| 600 |
|
| 601 |
while ((templ < right) &&
|
| 602 |
index_compare(ind, ind->nodes[templ], pivot) <= 0)
|
| 603 |
templ ++; |
| 604 |
|
| 605 |
/*
|
| 606 |
* Move right while right node > pivot node...
|
| 607 |
*/
|
| 608 |
|
| 609 |
while ((tempr > left) &&
|
| 610 |
index_compare(ind, ind->nodes[tempr], pivot) > 0)
|
| 611 |
tempr --; |
| 612 |
|
| 613 |
/*
|
| 614 |
* Swap nodes if needed...
|
| 615 |
*/
|
| 616 |
|
| 617 |
if (templ < tempr)
|
| 618 |
{
|
| 619 |
temp = ind->nodes[templ]; |
| 620 |
ind->nodes[templ] = ind->nodes[tempr]; |
| 621 |
ind->nodes[tempr] = temp; |
| 622 |
} |
| 623 |
} |
| 624 |
|
| 625 |
/*
|
| 626 |
* When we get here, the right (tempr) node is the new position for the
|
| 627 |
* pivot node...
|
| 628 |
*/
|
| 629 |
|
| 630 |
if (index_compare(ind, pivot, ind->nodes[tempr]) > 0) |
| 631 |
{
|
| 632 |
ind->nodes[left] = ind->nodes[tempr]; |
| 633 |
ind->nodes[tempr] = pivot; |
| 634 |
} |
| 635 |
|
| 636 |
/*
|
| 637 |
* Recursively sort the left partition as needed...
|
| 638 |
*/
|
| 639 |
|
| 640 |
if (left < (tempr - 1)) |
| 641 |
index_sort(ind, left, tempr - 1);
|
| 642 |
} |
| 643 |
while (right > (left = tempr + 1)); |
| 644 |
} |
| 645 |
|
| 646 |
|
| 647 |
/*
|
| 648 |
* End of "$Id: mxml-index.c 184 2005-01-29 07:21:44Z mike $".
|
| 649 |
*/
|