Line data Source code
1 : /*
2 : COLLECTION LIBRARY
3 :
4 : Implementation of the collection library iterator functions.
5 :
6 : Copyright (C) Dmitri Pal <dpal@redhat.com> 2009
7 :
8 : Collection Library is free software: you can redistribute it and/or modify
9 : it under the terms of the GNU Lesser General Public License as published by
10 : the Free Software Foundation, either version 3 of the License, or
11 : (at your option) any later version.
12 :
13 : Collection Library 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 Lesser General Public License for more details.
17 :
18 : You should have received a copy of the GNU Lesser General Public License
19 : along with Collection Library. If not, see <http://www.gnu.org/licenses/>.
20 : */
21 :
22 : #include "config.h"
23 : #include <string.h>
24 : #include <stdlib.h>
25 : #include <errno.h>
26 : #include <ctype.h>
27 : #include <time.h>
28 : #include "trace.h"
29 :
30 : /* The collection should use the real structures */
31 : #include "collection_priv.h"
32 : #include "collection.h"
33 :
34 : /* Depth for iterator depth allocation block */
35 : #define STACK_DEPTH_BLOCK 15
36 :
37 : /* Grow iteration stack */
38 266 : static int col_grow_stack(struct collection_iterator *iterator, unsigned desired)
39 : {
40 266 : int grow_by = 0;
41 : struct collection_item **temp;
42 :
43 : TRACE_FLOW_STRING("col_grow_stack", "Entry.");
44 :
45 266 : if (desired > iterator->stack_size) {
46 82 : grow_by = (((desired - iterator->stack_size) / STACK_DEPTH_BLOCK) + 1) * STACK_DEPTH_BLOCK;
47 82 : temp = (struct collection_item **)realloc(iterator->stack, grow_by * sizeof(struct collection_item *));
48 82 : if (temp == NULL) {
49 : TRACE_ERROR_NUMBER("Failed to allocate memory", ENOMEM);
50 0 : return ENOMEM;
51 : }
52 82 : iterator->stack = temp;
53 82 : iterator->stack_size += grow_by;
54 : }
55 : TRACE_FLOW_STRING("col_grow_stack", "Exit.");
56 266 : return EOK;
57 : }
58 :
59 :
60 :
61 : /* Bind iterator to a collection */
62 82 : int col_bind_iterator(struct collection_iterator **iterator,
63 : struct collection_item *ci,
64 : int mode_flags)
65 : {
66 : int error;
67 : struct collection_header *header;
68 82 : struct collection_iterator *iter = NULL;
69 :
70 : TRACE_FLOW_STRING("col_bind_iterator", "Entry.");
71 :
72 : /* Do some argument checking first */
73 82 : if ((iterator == NULL) || (ci == NULL)) {
74 : TRACE_ERROR_NUMBER("Invalid parameter.", EINVAL);
75 0 : return EINVAL;
76 : }
77 :
78 82 : iter = (struct collection_iterator *)malloc(sizeof(struct collection_iterator));
79 82 : if (iter == NULL) {
80 : TRACE_ERROR_NUMBER("Error allocating memory for the iterator.", ENOMEM);
81 0 : return ENOMEM;
82 : }
83 :
84 : /* Allocate memory for the stack */
85 82 : iter->stack = NULL;
86 82 : iter->stack_size = 0;
87 82 : iter->stack_depth = 0;
88 82 : iter->item_level = 0;
89 82 : iter->flags = mode_flags;
90 82 : iter->pin_level = 0;
91 82 : iter->can_break = 0;
92 :
93 : TRACE_INFO_NUMBER("Iterator flags", iter->flags);
94 :
95 : /* Allocate memory for stack */
96 82 : error = col_grow_stack(iter, 1);
97 82 : if(error) {
98 0 : free(iter);
99 : TRACE_ERROR_NUMBER("Error growing stack.", error);
100 0 : return error;
101 : }
102 :
103 : /* Create a special end item */
104 82 : error = col_allocate_item(&(iter->end_item), "", NULL, 0, COL_TYPE_END);
105 82 : if(error) {
106 0 : free(iter);
107 : TRACE_ERROR_NUMBER("Error allocating end item.", error);
108 0 : return error;
109 : }
110 :
111 : /* Make sure that we tie iterator to the collection */
112 82 : header = (struct collection_header *)ci->data;
113 82 : header->reference_count++;
114 82 : iter->top = ci;
115 82 : iter->pin = ci;
116 82 : *(iter->stack) = ci;
117 82 : iter->stack_depth++;
118 :
119 82 : *iterator = iter;
120 :
121 : TRACE_FLOW_STRING("col_bind_iterator", "Exit");
122 82 : return EOK;
123 : }
124 :
125 : /* Stop processing this subcollection and move to the next item in the
126 : * collection 'level' levels up.*/
127 3 : int col_iterate_up(struct collection_iterator *iterator, unsigned level)
128 : {
129 : TRACE_FLOW_STRING("iterate_up", "Entry");
130 :
131 3 : if (iterator == NULL) {
132 : TRACE_ERROR_NUMBER("Invalid parameter.", EINVAL);
133 0 : return EINVAL;
134 : }
135 :
136 : TRACE_INFO_NUMBER("Going up:", level);
137 : TRACE_INFO_NUMBER("Current stack depth:", iterator->stack_depth);
138 :
139 : /* If level is big just move to the top,
140 : * that will end the iteration process.
141 : */
142 3 : if (level >= iterator->stack_depth) iterator->stack_depth = 0;
143 1 : else iterator->stack_depth -= level;
144 :
145 : TRACE_INFO_NUMBER("Stack depth at the end:", iterator->stack_depth);
146 : TRACE_FLOW_STRING("col_iterate_up", "Exit");
147 3 : return EOK;
148 : }
149 :
150 : /* How deep are we relative to the top level.*/
151 27 : int col_get_iterator_depth(struct collection_iterator *iterator, int *depth)
152 : {
153 : TRACE_FLOW_STRING("col_get_iterator_depth", "Entry");
154 :
155 27 : if ((iterator == NULL) || (depth == NULL)) {
156 : TRACE_ERROR_NUMBER("Invalid parameter.", EINVAL);
157 0 : return EINVAL;
158 : }
159 :
160 27 : *depth = iterator->stack_depth - 1;
161 :
162 : TRACE_INFO_NUMBER("Stack depth at the end:", iterator->stack_depth);
163 : TRACE_FLOW_STRING("col_get_iterator_depth","Exit");
164 27 : return EOK;
165 : }
166 :
167 : /* What was the level of the last item we got? */
168 751 : int col_get_item_depth(struct collection_iterator *iterator, int *depth)
169 : {
170 : TRACE_FLOW_STRING("col_get_item_depth", "Entry");
171 :
172 751 : if ((iterator == NULL) || (depth == NULL)) {
173 : TRACE_ERROR_NUMBER("Invalid parameter.", EINVAL);
174 0 : return EINVAL;
175 : }
176 :
177 751 : *depth = iterator->item_level;
178 :
179 : TRACE_INFO_NUMBER("Item level at the end:", iterator->item_level);
180 : TRACE_FLOW_STRING("col_get_item_depth","Exit");
181 751 : return EOK;
182 : }
183 :
184 :
185 :
186 : /* Unbind the iterator from the collection */
187 82 : void col_unbind_iterator(struct collection_iterator *iterator)
188 : {
189 : TRACE_FLOW_STRING("col_unbind_iterator", "Entry.");
190 82 : if (iterator != NULL) {
191 82 : col_destroy_collection(iterator->top);
192 82 : col_delete_item(iterator->end_item);
193 82 : free(iterator->stack);
194 82 : free(iterator);
195 : }
196 : TRACE_FLOW_STRING("col_unbind_iterator", "Exit");
197 82 : }
198 :
199 : /* Get items from the collection one by one following the tree */
200 1556 : int col_iterate_collection(struct collection_iterator *iterator,
201 : struct collection_item **item)
202 : {
203 : int error;
204 : struct collection_item *current;
205 : struct collection_item *other;
206 :
207 : TRACE_FLOW_STRING("col_iterate_collection", "Entry.");
208 :
209 : /* Check if we have storage for item */
210 1556 : if (item == NULL) {
211 : TRACE_ERROR_NUMBER("Invalid parameter.", EINVAL);
212 0 : return EINVAL;
213 : }
214 :
215 : while (1) {
216 :
217 : TRACE_INFO_NUMBER("Stack depth:", iterator->stack_depth);
218 :
219 1758 : if (iterator->stack_depth == 0) {
220 : /* Re-init so if we continue looping we start over */
221 78 : iterator->stack[0] = iterator->top;
222 78 : iterator->stack_depth++;
223 78 : iterator->item_level = 0;
224 : }
225 :
226 : /* Is current item available */
227 1758 : current = iterator->stack[iterator->stack_depth - 1];
228 1758 : iterator->item_level = iterator->stack_depth - 1;
229 :
230 : /* Are we done? */
231 3025 : if (((iterator->stack_depth - 1) == iterator->pin_level) &&
232 1267 : (iterator->pin == current)) {
233 196 : if (iterator->can_break) {
234 : TRACE_FLOW_STRING("We are done.", "");
235 78 : *item = NULL;
236 78 : iterator->can_break = 0;
237 78 : return EOK;
238 : }
239 118 : else iterator->can_break = 1;
240 : }
241 :
242 : /* We are not done so check if we have an item */
243 1680 : if (current != NULL) {
244 :
245 : TRACE_INFO_STRING("Current item:", current->property);
246 : TRACE_INFO_NUMBER("Current item type:", current->type);
247 :
248 : /* Is this a collection reference */
249 1465 : if (current->type == COL_TYPE_COLLECTIONREF) {
250 : /* We do follow references? */
251 : TRACE_INFO_STRING("Current item:", "collection reference");
252 184 : if ((iterator->flags & COL_TRAVERSE_IGNORE) == 0) {
253 : /* We should not ignore - then move on */
254 : TRACE_INFO_STRING("Collection references are not ignored", "");
255 184 : error = col_grow_stack(iterator, iterator->stack_depth + 1);
256 184 : if (error) {
257 : TRACE_ERROR_NUMBER("Error growing stack.", error);
258 0 : return error;
259 : }
260 : /* Do we need to go deeper than one level ? */
261 184 : if ((iterator->flags & COL_TRAVERSE_ONELEVEL) == 0) {
262 : TRACE_INFO_STRING("Need to go deeper", "");
263 : /* We need to go deeper... */
264 : /* Do we need to show headers but not reference? */
265 144 : if ((iterator->flags & COL_TRAVERSE_ONLYSUB) != 0) {
266 : TRACE_INFO_STRING("Instructed to show header not reference", "");
267 3 : other = *((struct collection_item **)current->data);
268 3 : iterator->stack[iterator->stack_depth] = other->next;
269 3 : iterator->item_level = iterator->stack_depth;
270 3 : *item = other;
271 : }
272 : /* Do we need to show both? */
273 141 : else if ((iterator->flags & COL_TRAVERSE_SHOWSUB) != 0) {
274 : TRACE_INFO_STRING("Instructed to show header and reference","");
275 6 : iterator->stack[iterator->stack_depth] = *((struct collection_item **)(current->data));
276 6 : *item = current;
277 : /* Do not need to adjust level here */
278 : }
279 : /* Do not show either */
280 135 : else if ((iterator->flags & COL_TRAVERSE_FLAT) != 0) {
281 : TRACE_INFO_STRING("Instructed not to show header and reference","");
282 77 : other = *((struct collection_item **)current->data);
283 77 : iterator->stack[iterator->stack_depth] = other->next;
284 77 : iterator->stack[iterator->stack_depth - 1] = current->next;
285 77 : iterator->stack_depth++;
286 : /* Do not need to adjust level here */
287 77 : continue;
288 : }
289 : /* We need to show reference only */
290 : else {
291 : TRACE_INFO_STRING("Instructed to show reference only", "");
292 58 : other = *((struct collection_item **)current->data);
293 : TRACE_INFO_STRING("Sub collection:", other->property);
294 : TRACE_INFO_NUMBER("Sub collection type:", other->type);
295 58 : iterator->stack[iterator->stack_depth] = other->next;
296 58 : if (other->next != NULL) {
297 : TRACE_INFO_STRING("Will show this item next time:", other->next->property);
298 : TRACE_INFO_NUMBER("Will show this item next time type:", other->next->type);
299 : }
300 58 : *item = current;
301 : TRACE_INFO_NUMBER("Level of the reference:", iterator->item_level);
302 : /* Do not need to adjust level here */
303 : }
304 :
305 : TRACE_INFO_STRING("We return item:", (*item)->property);
306 : TRACE_INFO_NUMBER("We return item type:", (*item)->type);
307 : TRACE_INFO_STRING("Moving to the next item on the previous item in stack", "");
308 67 : iterator->stack[iterator->stack_depth - 1] = current->next;
309 67 : iterator->stack_depth++;
310 :
311 : }
312 : else {
313 : TRACE_INFO_STRING("Instructed to parse just one level", "");
314 : /* On one level - just return current */
315 40 : *item = current;
316 : TRACE_INFO_STRING("Moving to the next item on one level", "");
317 40 : iterator->stack[iterator->stack_depth - 1] = current->next;
318 : }
319 107 : break;
320 : }
321 : else {
322 : /* We need to ignore references so move to the next item */
323 : TRACE_INFO_STRING("Stepping over the reference", "");
324 0 : iterator->stack[iterator->stack_depth - 1] = current->next;
325 0 : continue;
326 : }
327 : }
328 : else {
329 : /* Got a normal item - return it and move to the next one */
330 1403 : if ((current->type == COL_TYPE_COLLECTION) &&
331 149 : ((iterator->flags & COL_TRAVERSE_FLAT) != 0) &&
332 27 : (iterator->stack_depth > 1)) {
333 : TRACE_INFO_STRING("Header of the sub collection in flat case ", "");
334 0 : iterator->stack[iterator->stack_depth - 1] = current->next;
335 0 : continue;
336 : }
337 : else {
338 : TRACE_INFO_STRING("Simple item", "");
339 1281 : *item = current;
340 1281 : iterator->stack[iterator->stack_depth - 1] = current->next;
341 : }
342 1281 : break;
343 : }
344 : }
345 : else {
346 : /* Item is NULL */
347 : TRACE_INFO_STRING("Finished level", "moving to upper level");
348 215 : iterator->stack_depth--;
349 : /* Remember that item_level is zero based while depth is size
350 : * so we decrease and then assign. */
351 : TRACE_INFO_NUMBER("Stack depth at the end:", iterator->stack_depth);
352 215 : if ((iterator->flags & COL_TRAVERSE_END) != 0) {
353 :
354 : /* Show end element
355 : * a) If we are flattening but at the top
356 : * b) We are not flattening
357 : */
358 255 : if ((((iterator->flags & COL_TRAVERSE_FLAT) != 0) &&
359 232 : (iterator->stack_depth == 0)) ||
360 138 : ((iterator->flags & COL_TRAVERSE_FLAT) == 0)) {
361 :
362 : /* Return dummy entry to indicate the end of the collection */
363 : TRACE_INFO_STRING("Finished level", "told to return END");
364 90 : *item = iterator->end_item;
365 90 : break;
366 : }
367 : }
368 : else {
369 : /* Move to next level */
370 54 : continue;
371 : }
372 : }
373 202 : }
374 :
375 : TRACE_FLOW_STRING("col_iterate_collection", "Exit");
376 1478 : return EOK;
377 : }
378 :
379 :
380 : /* Pins down the iterator to loop around this point */
381 2 : void col_pin_iterator(struct collection_iterator *iterator)
382 : {
383 : TRACE_FLOW_STRING("col_iterator_add_pin", "Entry");
384 :
385 2 : if ((!iterator) || (!iterator->stack)) {
386 : TRACE_FLOW_STRING("Invalid itertor", "Ingoring");
387 2 : return;
388 : }
389 :
390 10 : while ((iterator->stack_depth) &&
391 4 : (iterator->stack[iterator->stack_depth - 1] == NULL)) {
392 2 : iterator->stack_depth--;
393 : }
394 :
395 2 : if (iterator->stack_depth == 0) {
396 0 : iterator->pin = iterator->top;
397 0 : iterator->pin_level = 0;
398 : }
399 : else {
400 2 : iterator->pin = iterator->stack[iterator->stack_depth - 1];
401 2 : iterator->pin_level = iterator->stack_depth - 1;
402 : }
403 2 : iterator->can_break = 0;
404 :
405 : TRACE_FLOW_STRING("col_iterator_add_pin", "Exit");
406 : }
407 :
408 :
409 : /* Rewinds iterator to the beginning */
410 41 : void col_rewind_iterator(struct collection_iterator *iterator)
411 : {
412 : TRACE_FLOW_STRING("col_rewind_iterator", "Entry");
413 :
414 41 : if ((!iterator) || (!iterator->stack)) {
415 : TRACE_FLOW_STRING("Invalid itertor", "Ingoring");
416 41 : return;
417 : }
418 :
419 41 : iterator->pin = iterator->top;
420 41 : iterator->stack[0] = iterator->top;
421 41 : iterator->stack_depth = 1;
422 41 : iterator->item_level = 0;
423 41 : iterator->pin_level = 0;
424 41 : iterator->can_break = 0;
425 :
426 : TRACE_FLOW_STRING("col_rewind_iterator", "Exit");
427 : }
|
