1: /*
2: * LibAxl: Another XML library
3: * Copyright (C) 2006 Advanced Software Production Line, S.L.
4: *
5: * This program is free software; you can redistribute it and/or
6: * modify it under the terms of the GNU Lesser General Public License
7: * as published by the Free Software Foundation; either version 2.1 of
8: * the License, or (at your option) any later version.
9: *
10: * This program is distributed in the hope that it will be useful,
11: * but WITHOUT ANY WARRANTY; without even the implied warranty of
12: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13: * GNU Lesser General Public License for more details.
14: *
15: * You should have received a copy of the GNU Lesser General Public
16: * License along with this program; if not, write to the Free
17: * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
18: * 02111-1307 USA
19: *
20: * You may find a copy of the license under this software is released
21: * at COPYING file. This is LGPL software: you are welcome to
22: * develop proprietary applications using this library without any
23: * royalty or fee but returning back any change, improvement or
24: * addition in the form of source code, project image, documentation
25: * patches, etc.
26: *
27: * For commercial support on build XML enabled solutions contact us:
28: *
29: * Postal address:
30: * Advanced Software Production Line, S.L.
31: * Edificio Alius A, Oficina 102,
32: * C/ Antonio Suarez Nº 10,
33: * Alcalá de Henares 28802 Madrid
34: * Spain
35: *
36: * Email address:
37: * info@aspl.es - http://www.aspl.es/xml
38: */
39:
40: #include <axl_decl.h>
41: #include <axl_stack.h>
42: #include <axl_list.h>
43: #include <axl_log.h>
44: #define LOG_DOMAIN "axl-stack"
45:
46: struct _axlStack {
47: axlPointer * stack;
48: int size;
49: int items;
50: axlDestroyFunc destroy;
51: };
52:
53: /**
54: * \defgroup axl_stack_module Axl Stack: A stack built used across AXL library
55: */
56:
57: /**
58: * \addtogroup axl_stack_module
59: * @{
60: */
61:
62: /**
63: * @brief Creates a new stack.
64: *
65: * Creates a new \ref axlStack object, which will accept to store a
66: * retrieve objects in a FIFO manner.
67: *
68: * @param destroy_data A function to be used to destroy data stored on
69: * the stack is the stack is deallocated containing data. This
70: * parameter is optional. If not provided, no automatic memory
71: * deallocation will peformed.
72: *
73: * @return A newly allocated stack that must be deallocated by using
74: * axl_stack_destroy.
75: */
76: axlStack * axl_stack_new (axlDestroyFunc destroy_data)
77: {
78: axlStack * stack;
79:
80: /* create an empty stack */
81: stack = axl_new (axlStack, 1);
82: /* check returned value */
83: if (stack == NULL)
84: return NULL;
85: stack->destroy = destroy_data;
86:
87: return stack;
88: }
89:
90: /**
91: * @brief Push data on top of the stack.
92: *
93: * The stack doesn't support storing NULL references. If a null
94: * reference is provided the function won't perform any operation on
95: * the stack.
96: *
97: * @param stack The stack where the data will be pushed.
98: * @param data The data to push.
99: */
100: void axl_stack_push (axlStack * stack, axlPointer data)
101: {
102: axlPointer * temp;
103:
104: axl_return_if_fail (stack);
105: axl_return_if_fail (data);
106:
107: /* check if we have enough space to store the pointer */
108: if (stack->size == stack->items) {
109: if (stack->size == 0) {
110: /* ask for a single pointer */
111: stack->stack = axl_new (axlPointer, 1);
112:
113: /* check allocated result */
114: if (stack->stack == NULL)
115: return;
116: }else {
117: /* ask to grow the memory already allocated */
118: temp = stack->stack;
119: stack->stack = realloc (stack->stack, sizeof (axlPointer) * (stack->size + 1));
120: /* check allocated value */
121: if (stack->stack == NULL) {
122: stack->stack = temp;
123: return;
124: } /* end if */
125:
126: }
127: /* update the size available */
128: stack->size++;
129: }
130:
131: /* store the item */
132: stack->stack[stack->items] = data;
133:
134: /* update items stored */
135: stack->items++;
136:
137: return;
138: }
139:
140: /**
141: * @brief Pop data from the stack.
142: *
143: * @param stack The stack where the pop operation will be performed.
144: *
145: * @return A \ref axlPointer containing previously pushed data or NULL
146: * if fails.
147: */
148: axlPointer axl_stack_pop (axlStack * stack)
149: {
150: axlPointer pointer;
151:
152: axl_return_val_if_fail (stack, NULL);
153:
154: /* do not perform any operation if the stack is empty */
155: if (axl_stack_is_empty (stack))
156: return NULL;
157:
158: /* reduce the items stored */
159: stack->items--;
160:
161: /* return the pointer */
162: pointer = stack->stack[stack->items];
163:
164: return pointer;
165: }
166:
167: /**
168: * @brief Allows to get current current element at the top of the
169: * stack without removing it.
170: *
171: * This function allows to perform the same operation like pop (\ref
172: * axl_stack_pop) function, but without removing the element from the
173: * top.
174: *
175: * @param stack The stack where the element from the top will be returned.
176: *
177: * @return An \ref axlPointer reference or NULL if fails.
178: */
179: axlPointer axl_stack_peek (axlStack * stack)
180: {
181: axl_return_val_if_fail (stack, NULL);
182:
183: /* do not perform any operation if the stack is empty */
184: if (axl_stack_is_empty (stack)) {
185: return NULL;
186: }
187:
188: /* return the very first element without poping */
189: return stack->stack[stack->items - 1];
190: }
191:
192: /**
193: * @internal Common support function for foreach over an stack for all
194: * foreach functions defined.
195: */
196: axl_bool __axl_stack_foreach_common (axlStack * stack,
197: axlStackForeach2 func,
198: axlStackForeach3 func3,
199: axlPointer user_data,
200: axlPointer user_data2,
201: axlPointer user_data3)
202: {
203: int iterator;
204:
205: axl_return_val_if_fail (stack, axl_false);
206:
207: /* for each item inside the stack */
208: iterator = 0;
209: while (iterator < stack->items) {
210: /* call fo the function and check returning value */
211: if (func != NULL && func (stack->stack [stack->items - iterator - 1], user_data, user_data2))
212: return axl_false;
213:
214: /* call fo the function and check returning value */
215: if (func3 != NULL && func3 (stack->stack [stack->items - iterator - 1], user_data, user_data2, user_data3))
216: return axl_false;
217:
218: /* update the iterator */
219: iterator ++;
220: }
221:
222: /* iteration performed completely */
223: return axl_true;
224: }
225:
226: /**
227: * @brief Allows to perform a foreach operation from the head of the
228: * stack (the next item to be poped) to the tail of the stack (the
229: * very first item pushed).
230: *
231: * The foreach process is non intrusive: it doesn't perform any change
232: * of the stack, but allows to traverse all items in the natural order
233: * in which items are stored (push) and removed (pop).
234: *
235: * The function provided to perform the foreach operation will be
236: * called providing the stack data found, and the two user defined
237: * pointers provided.
238: *
239: * @param stack The stack where the foreach operation will be
240: * performed.
241: *
242: * @param func The foreach function to be called for each item found
243: * in the stack.
244: *
245: * @param user_data User defined pointer to be passed to the function
246: * provided.
247: *
248: * @param user_data2 User defined pointer to be passed to the function
249: * provided.
250: *
251: * @return \ref axl_true if the foreach process was performed completely
252: * through all items inside the stack or \ref axl_false if not. The
253: * function will also return \ref axl_false to indicate a failure the
254: * stack and func parameters are null.
255: */
256: axl_bool axl_stack_foreach (axlStack * stack,
257: axlStackForeach2 func,
258: axlPointer user_data,
259: axlPointer user_data2)
260: {
261: /* call to common function */
262: return __axl_stack_foreach_common (stack, func, NULL, user_data, user_data2, NULL);
263: }
264:
265:
266: /**
267: * @brief Allows to perform a foreach operation from the head of the
268: * stack (the next item to be poped) to the tail of the stack (the
269: * very first item pushed).
270: *
271: * The foreach process is non intrusive: it doesn't perform any change
272: * of the stack, but allows to traverse all items in the natural order
273: * in which items are stored (push) and removed (pop).
274: *
275: * The function provided to perform the foreach operation will be
276: * called providing the stack data found, and the three user defined
277: * pointers provided.
278: *
279: * @param stack The stack where the foreach operation will be
280: * performed.
281: *
282: * @param func The foreach function to be called for each item found
283: * in the stack.
284: *
285: * @param user_data User defined pointer to be passed to the function
286: * provided.
287: *
288: * @param user_data2 User defined pointer to be passed to the function
289: * provided.
290: *
291: * @param user_data3 User defined pointer to be passed to the function
292: * provided.
293: *
294: * @return \ref axl_true if the foreach process was performed completely
295: * through all items inside the stack or \ref axl_false if not. The
296: * function will also return \ref axl_false to indicate a failure the
297: * stack and func parameters are null.
298: */
299: axl_bool axl_stack_foreach3 (axlStack * stack,
300: axlStackForeach3 func,
301: axlPointer user_data,
302: axlPointer user_data2,
303: axlPointer user_data3)
304: {
305: /* call to common function */
306: return __axl_stack_foreach_common (stack, NULL, func, user_data, user_data2, user_data3);
307: }
308:
309: /**
310: * @brief Returns current stack size, that is, elements stored on the
311: * stack.
312: *
313: * @param stack The stack where the operation will performed.
314: *
315: * @return The number of items stored.
316: */
317: int axl_stack_size (axlStack * stack)
318: {
319: axl_return_val_if_fail (stack, -1);
320:
321: /* current items stored */
322: return stack->items;
323: }
324:
325:
326: /**
327: * @brief Allows to check if the given stack is empty.
328: *
329: * @param stack The stack to check.
330: *
331: * @return \ref axl_true if the stack is empty or axl_false if not.
332: */
333: axl_bool axl_stack_is_empty (axlStack * stack)
334: {
335: axl_return_val_if_fail (stack, axl_false);
336:
337: /* return if there are stored items in the stack */
338: return (stack->items == 0);
339: }
340:
341: /**
342: * @brief Destroy the given stack.
343: *
344: * @param stack The stack to destroy.
345: */
346: void axl_stack_free (axlStack * stack)
347: {
348: axl_return_if_fail (stack);
349:
350: /* destroy the list inside (if the destroy function is
351: * defined) */
352: if (stack->destroy) {
353: while (! axl_stack_is_empty (stack)) {
354:
355: /* destroy */
356: stack->destroy (axl_stack_pop (stack));
357:
358: } /* end while */
359: } /* end if */
360:
361: /* free stack array */
362: axl_free (stack->stack);
363:
364: /* destroy the stack */
365: axl_free (stack);
366:
367: return;
368: }
369:
370: /* @} */
371:
372: typedef struct _axlBinaryStackNode {
373: int count;
374: axl_bool state;
375: } axlBinaryStackNode;
376:
377:
378: struct _axlBinaryStack {
379: axlBinaryStackNode * last;
380: axlStack * stack;
381: axlFactory * factory;
382: int count;
383: };
384:
385: /**
386: * \defgroup axl_binary_stack_module Axl Binary Stack: A compact binary state stack
387: */
388:
389: /**
390: * \addtogroup axl_binary_stack_module
391: * @{
392: */
393:
394: /**
395: * @brief Allows to create a compact binary state stack.
396: *
397: * To stack is designed to store boolean values in an efficient
398: * way. In idea behind this structure is that storing 10 boolean axl_true
399: * values only holds a node, with the axl_true value and the count of
400: * items that previously was signaled with the same value.
401: *
402: * The intention is to compact a binary succession of data into a list
403: * of touples signaling the state and the number of times it was
404: * signaled.
405: *
406: * This structure is meant to be more efficient than a plain \ref
407: * axlStack but there is a case where is not more efficient, that is,
408: * when all stored boolean values alternates.
409: *
410: * @return A newly allocated binary stack. Push boolean values with
411: * \ref axl_binary_stack_push. Pop previous stored value with \ref
412: * axl_binary_stack_pop. Once finished, use \ref axl_binary_stack_free
413: * to free the binary stack.
414: */
415: axlBinaryStack * axl_binary_stack_new (void)
416: {
417: axlBinaryStack * result;
418:
419: result = axl_new (axlBinaryStack, 1);
420: /* check allocated value */
421: if (result == NULL)
422: return NULL;
423: result->stack = axl_stack_new (axl_free);
424:
425: /* return stack created */
426: return result;
427: }
428:
429: /**
430: * @brief Push a new boolean item into the binary stack.
431: *
432: * @param bstack The binary stack
433: *
434: * @param state The state to push into the queue.
435: */
436: void axl_binary_stack_push (axlBinaryStack * bstack, axl_bool state)
437: {
438: axlBinaryStackNode * node;
439:
440: /* check references */
441: axl_return_if_fail (bstack);
442:
443: /* check basic case */
444: if (bstack->last == NULL) {
445:
446: axl_binary_stack_push_create_and_return:
447:
448: /* configure last */
449: node = axl_new (axlBinaryStackNode, 1);
450: /* check allocated value */
451: if (node == NULL)
452: return;
453: node->count = 1;
454: node->state = state;
455:
456: /* configure */
457: bstack->last = node;
458:
459: /* store in the stack */
460: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Storing first item: 0x%x", node); */
461: axl_stack_push (bstack->stack, node);
462:
463: /* update count */
464: bstack->count++;
465:
466: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Storing item state=%d, count=%d, bcount=%d",
467: node->state, node->count, bstack->count); */
468:
469: return;
470: } /* end if */
471:
472: /* default case, check current state */
473: if (bstack->last->state == state) {
474:
475: /* found same state, increase count and return */
476: bstack->last->count++;
477:
478: /* update count */
479: bstack->count++;
480:
481: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Found same state, reusing..state=%d, count=%d, bcount=%d",
482: bstack->last->state, bstack->last->count, bstack->count); */
483:
484: return;
485: } /* end if */
486:
487: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Found state changed, creating..state=%d (previuos state: %d), count=%d, bcount=%d",
488: state, bstack->last->state, bstack->last->count, bstack->count); */
489:
490: /* if reached this place, create a new node */
491: goto axl_binary_stack_push_create_and_return;
492: }
493:
494: /**
495: * @brief Convenience function that allows to push a new value using
496: * the last one pushed in the stack. This function allows to implement
497: * the same feature provided by peeking (\ref axl_binary_stack_peek)
498: * the next visible value on the stack head and then pushing it again.
499: *
500: * @param bstack The binary stack where to perform the operation.
501: *
502: * NOTE: The stack must not be empty before calling to this
503: * function. It has to have at least one value already pushed.
504: */
505: void axl_binary_stack_push_the_same (axlBinaryStack * bstack)
506: {
507: axl_return_if_fail (bstack);
508: axl_return_if_fail (bstack->last);
509:
510: /* update stack */
511: bstack->last->count++;
512: bstack->count++;
513:
514: return;
515: }
516:
517: /**
518: * @brief Allows to pop the next value from the stack.
519: *
520: * @param bstack The binary stack where the next value will be
521: * restored.
522: *
523: * @return The next value stored in the stack. You must check if the
524: * stack is empty before calling to this function since you won't be
525: * able to differenciate a axl_false value stored from a axl_false value
526: * returned by an error.
527: */
528: axl_bool axl_binary_stack_pop (axlBinaryStack * bstack)
529: {
530: axlBinaryStackNode * node;
531: axl_bool state;
532: axl_return_val_if_fail (bstack, axl_false);
533:
534: /* get last value */
535: node = bstack->last;
536: if (node == NULL) {
537: /* return axl_false because the stack is empty */
538: return axl_false;
539: } /* end if */
540:
541: /* check if there are more than 1 item, that is, at least
542: * 2. */
543: if (node->count > 1) {
544:
545: /* update count */
546: bstack->count--;
547:
548: /* decrease the counter and return */
549: node->count--;
550:
551: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: found state with more than 1 item, poping: state=%d, count=%d, bcount=%d",
552: node->state, node->count, bstack->count); */
553:
554: return node->state;
555:
556: } else if (node->count == 1) {
557:
558: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: found state with only 1 item, poping: state=%d, count=%d, bcount=%d",
559: node->state, node->count, bstack->count); */
560:
561: /* get the value */
562: state = node->state;
563:
564: /* update the next last (remove the current last) and
565: * use the next */
566: axl_stack_pop (bstack->stack);
567: bstack->last = axl_stack_peek (bstack->stack);
568:
569: /* release to the factory */
570: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: new node to use: 0x%x, about to release 0x%x",
571: bstack->last, node); */
572: axl_free (node);
573:
574: /* update count */
575: bstack->count--;
576:
577: node = bstack->last;
578: /* if (node != NULL) {
579: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: after poping: state=%d, count=%d, bcount=%d",
580: node->state, node->count, bstack->count);
581: } */
582:
583: return state;
584: } /* end if */
585:
586: /* this shouldn't be reached */
587: return axl_false;
588: }
589:
590: /**
591: * @brief Allows to get the current stack head value stored without
592: * removing it from the stack.
593: *
594: * @param bstack The binary stack where to perform the operation.
595: *
596: * @return The value stored in the stack head. The stack must contain
597: * at least one value, otherwise the returned value is not
598: * reliable. See \ref axl_binary_stack_is_empty to avoid calling to this function.
599: */
600: axl_bool axl_binary_stack_peek (axlBinaryStack * bstack)
601: {
602: axl_return_val_if_fail (bstack, axl_false);
603:
604: /* return current state */
605: return (bstack->last && bstack->last->state);
606: }
607:
608: /**
609: * @brief Check current emptyness status for the provided binary
610: * stack.
611: *
612: * @param bstack The binary stack to check.
613: *
614: * @return axl_true if the binary stack is empty, otherwise axl_false is
615: * returned.
616: */
617: axl_bool axl_binary_stack_is_empty (axlBinaryStack * bstack)
618: {
619: axl_return_val_if_fail (bstack, axl_false);
620:
621: /* return current emptyness status */
622: return (bstack->last == NULL && axl_stack_is_empty (bstack->stack));
623: }
624:
625: /**
626: * @brief Allows to get current number of items stored.
627: *
628: * @param bstack The binary stack to check current number of items
629: * stored.
630: *
631: * @return The number of items stored or -1 if it fails.
632: */
633: int axl_binary_stack_size (axlBinaryStack * bstack)
634: {
635: axl_return_val_if_fail (bstack, -1);
636:
637: /* return item count */
638: return bstack->count;
639: }
640:
641: /**
642: * @brief Release the provided binary stack.
643: *
644: * @param bstack The binary stack to release.
645: */
646: void axl_binary_stack_free (axlBinaryStack * bstack)
647: {
648: if (bstack == NULL)
649: return;
650:
651: /* free resources */
652: axl_stack_free (bstack->stack);
653: axl_free (bstack);
654:
655: return;
656: }
657:
658: /**
659: * @}
660: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to axl_stack.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / gpl / axl / src