EPSIAE » eneraptor

/*

 * "$Id: mxml-index.c 184 2005-01-29 07:21:44Z mike $"

 *

 * Index support code for Mini-XML, a small XML-like file parsing library.

 *

 * Copyright 2003-2005 by Michael Sweet.

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Library General Public

 * License as published by the Free Software Foundation; either

 * version 2, or (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * Contents:

 *

 *   mxmlIndexDelete()   - Delete an index.

 *   mxmlIndexEnum()     - Return the next node in the index.

 *   mxmlIndexFind()     - Find the next matching node.

 *   mxmlIndexNew()      - Create a new index.

 *   mxmlIndexReset()    - Reset the enumeration/find pointer in the index and

 *                         return the first node in the index.

 *   index_compare()     - Compare two nodes.

 *   index_find()        - Compare a node with index values.

 *   index_sort()        - Sort the nodes in the index...

 */

/*

 * 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);

}

/*

 * '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 184 2005-01-29 07:21:44Z mike $".

 */