root / logic / trunk / src / mxml / mxml-index.c @ 73
History | View | Annotate | Download (13.7 KB)
1 | 49 | Janez1 | /*
|
---|---|---|---|
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 | */ |