3c4566f84b9f45402fdc362dd9c505311191b02b
[asterisk/asterisk.git] / mxml / mxml-index.c
1 /*
2  * "$Id$"
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$".
649  */