root / logic / trunk / src / mxml / mxml-index.c @ 84
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 |
*/
|