daemon/mxml/mxml-index.c

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