Annotation of gpl/axl/src/axl_stack.c, revision 1.1.1.1
1.1 misho 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: stack->destroy = destroy_data;
83:
84: return stack;
85: }
86:
87: /**
88: * @brief Push data on top of the stack.
89: *
90: * The stack doesn't support storing NULL references. If a null
91: * reference is provided the function won't perform any operation on
92: * the stack.
93: *
94: * @param stack The stack where the data will be pushed.
95: * @param data The data to push.
96: */
97: void axl_stack_push (axlStack * stack, axlPointer data)
98: {
99: axl_return_if_fail (stack);
100: axl_return_if_fail (data);
101:
102: /* check if we have enough space to store the pointer */
103: if (stack->size == stack->items) {
104: if (stack->size == 0) {
105: /* ask for a single pointer */
106: stack->stack = axl_new (axlPointer, 1);
107: }else {
108: /* ask to grow the memory already allocated */
109: stack->stack = realloc (stack->stack, sizeof (axlPointer) * (stack->size + 1));
110: }
111: /* update the size available */
112: stack->size++;
113: }
114:
115: /* store the item */
116: stack->stack[stack->items] = data;
117:
118: /* update items stored */
119: stack->items++;
120:
121: return;
122: }
123:
124: /**
125: * @brief Pop data from the stack.
126: *
127: * @param stack The stack where the pop operation will be performed.
128: *
129: * @return A \ref axlPointer containing previously pushed data or NULL
130: * if fails.
131: */
132: axlPointer axl_stack_pop (axlStack * stack)
133: {
134: axlPointer pointer;
135:
136: axl_return_val_if_fail (stack, NULL);
137:
138: /* do not perform any operation if the stack is empty */
139: if (axl_stack_is_empty (stack))
140: return NULL;
141:
142: /* reduce the items stored */
143: stack->items--;
144:
145: /* return the pointer */
146: pointer = stack->stack[stack->items];
147:
148: return pointer;
149: }
150:
151: /**
152: * @brief Allows to get current current element at the top of the
153: * stack without removing it.
154: *
155: * This function allows to perform the same operation like pop (\ref
156: * axl_stack_pop) function, but without removing the element from the
157: * top.
158: *
159: * @param stack The stack where the element from the top will be returned.
160: *
161: * @return An \ref axlPointer reference or NULL if fails.
162: */
163: axlPointer axl_stack_peek (axlStack * stack)
164: {
165: axl_return_val_if_fail (stack, NULL);
166:
167: /* do not perform any operation if the stack is empty */
168: if (axl_stack_is_empty (stack)) {
169: return NULL;
170: }
171:
172: /* return the very first element without poping */
173: return stack->stack[stack->items - 1];
174: }
175:
176: /**
177: * @internal Common support function for foreach over an stack for all
178: * foreach functions defined.
179: */
180: axl_bool __axl_stack_foreach_common (axlStack * stack,
181: axlStackForeach2 func,
182: axlStackForeach3 func3,
183: axlPointer user_data,
184: axlPointer user_data2,
185: axlPointer user_data3)
186: {
187: int iterator;
188:
189: axl_return_val_if_fail (stack, axl_false);
190:
191: /* for each item inside the stack */
192: iterator = 0;
193: while (iterator < stack->items) {
194: /* call fo the function and check returning value */
195: if (func != NULL && func (stack->stack [stack->items - iterator - 1], user_data, user_data2))
196: return axl_false;
197:
198: /* call fo the function and check returning value */
199: if (func3 != NULL && func3 (stack->stack [stack->items - iterator - 1], user_data, user_data2, user_data3))
200: return axl_false;
201:
202: /* update the iterator */
203: iterator ++;
204: }
205:
206: /* iteration performed completely */
207: return axl_true;
208: }
209:
210: /**
211: * @brief Allows to perform a foreach operation from the head of the
212: * stack (the next item to be poped) to the tail of the stack (the
213: * very first item pushed).
214: *
215: * The foreach process is non intrusive: it doesn't perform any change
216: * of the stack, but allows to traverse all items in the natural order
217: * in which items are stored (push) and removed (pop).
218: *
219: * The function provided to perform the foreach operation will be
220: * called providing the stack data found, and the two user defined
221: * pointers provided.
222: *
223: * @param stack The stack where the foreach operation will be
224: * performed.
225: *
226: * @param func The foreach function to be called for each item found
227: * in the stack.
228: *
229: * @param user_data User defined pointer to be passed to the function
230: * provided.
231: *
232: * @param user_data2 User defined pointer to be passed to the function
233: * provided.
234: *
235: * @return \ref axl_true if the foreach process was performed completely
236: * through all items inside the stack or \ref axl_false if not. The
237: * function will also return \ref axl_false to indicate a failure the
238: * stack and func parameters are null.
239: */
240: axl_bool axl_stack_foreach (axlStack * stack,
241: axlStackForeach2 func,
242: axlPointer user_data,
243: axlPointer user_data2)
244: {
245: /* call to common function */
246: return __axl_stack_foreach_common (stack, func, NULL, user_data, user_data2, NULL);
247: }
248:
249:
250: /**
251: * @brief Allows to perform a foreach operation from the head of the
252: * stack (the next item to be poped) to the tail of the stack (the
253: * very first item pushed).
254: *
255: * The foreach process is non intrusive: it doesn't perform any change
256: * of the stack, but allows to traverse all items in the natural order
257: * in which items are stored (push) and removed (pop).
258: *
259: * The function provided to perform the foreach operation will be
260: * called providing the stack data found, and the three user defined
261: * pointers provided.
262: *
263: * @param stack The stack where the foreach operation will be
264: * performed.
265: *
266: * @param func The foreach function to be called for each item found
267: * in the stack.
268: *
269: * @param user_data User defined pointer to be passed to the function
270: * provided.
271: *
272: * @param user_data2 User defined pointer to be passed to the function
273: * provided.
274: *
275: * @param user_data3 User defined pointer to be passed to the function
276: * provided.
277: *
278: * @return \ref axl_true if the foreach process was performed completely
279: * through all items inside the stack or \ref axl_false if not. The
280: * function will also return \ref axl_false to indicate a failure the
281: * stack and func parameters are null.
282: */
283: axl_bool axl_stack_foreach3 (axlStack * stack,
284: axlStackForeach3 func,
285: axlPointer user_data,
286: axlPointer user_data2,
287: axlPointer user_data3)
288: {
289: /* call to common function */
290: return __axl_stack_foreach_common (stack, NULL, func, user_data, user_data2, user_data3);
291: }
292:
293: /**
294: * @brief Returns current stack size, that is, elements stored on the
295: * stack.
296: *
297: * @param stack The stack where the operation will performed.
298: *
299: * @return The number of items stored.
300: */
301: int axl_stack_size (axlStack * stack)
302: {
303: axl_return_val_if_fail (stack, -1);
304:
305: /* current items stored */
306: return stack->items;
307: }
308:
309:
310: /**
311: * @brief Allows to check if the given stack is empty.
312: *
313: * @param stack The stack to check.
314: *
315: * @return \ref axl_true if the stack is empty or axl_false if not.
316: */
317: axl_bool axl_stack_is_empty (axlStack * stack)
318: {
319: axl_return_val_if_fail (stack, axl_false);
320:
321: /* return if there are stored items in the stack */
322: return (stack->items == 0);
323: }
324:
325: /**
326: * @brief Destroy the given stack.
327: *
328: * @param stack The stack to destroy.
329: */
330: void axl_stack_free (axlStack * stack)
331: {
332: axl_return_if_fail (stack);
333:
334: /* destroy the list inside (if the destroy function is
335: * defined) */
336: if (stack->destroy) {
337: while (! axl_stack_is_empty (stack)) {
338:
339: /* destroy */
340: stack->destroy (axl_stack_pop (stack));
341:
342: } /* end while */
343: } /* end if */
344:
345: /* free stack array */
346: axl_free (stack->stack);
347:
348: /* destroy the stack */
349: axl_free (stack);
350:
351: return;
352: }
353:
354: /* @} */
355:
356: typedef struct _axlBinaryStackNode {
357: int count;
358: axl_bool state;
359: } axlBinaryStackNode;
360:
361:
362: struct _axlBinaryStack {
363: axlBinaryStackNode * last;
364: axlStack * stack;
365: axlFactory * factory;
366: int count;
367: };
368:
369: /**
370: * \defgroup axl_binary_stack_module Axl Binary Stack: A compact binary state stack
371: */
372:
373: /**
374: * \addtogroup axl_binary_stack_module
375: * @{
376: */
377:
378: /**
379: * @brief Allows to create a compact binary state stack.
380: *
381: * To stack is designed to store boolean values in an efficient
382: * way. In idea behind this structure is that storing 10 boolean axl_true
383: * values only holds a node, with the axl_true value and the count of
384: * items that previously was signaled with the same value.
385: *
386: * The intention is to compact a binary succession of data into a list
387: * of touples signaling the state and the number of times it was
388: * signaled.
389: *
390: * This structure is meant to be more efficient than a plain \ref
391: * axlStack but there is a case where is not more efficient, that is,
392: * when all stored boolean values alternates.
393: *
394: * @return A newly allocated binary stack. Push boolean values with
395: * \ref axl_binary_stack_push. Pop previous stored value with \ref
396: * axl_binary_stack_pop. Once finished, use \ref axl_binary_stack_free
397: * to free the binary stack.
398: */
399: axlBinaryStack * axl_binary_stack_new (void)
400: {
401: axlBinaryStack * result;
402:
403: result = axl_new (axlBinaryStack, 1);
404: result->stack = axl_stack_new (axl_free);
405:
406: /* return stack created */
407: return result;
408: }
409:
410: /**
411: * @brief Push a new boolean item into the binary stack.
412: *
413: * @param bstack The binary stack
414: *
415: * @param state The state to push into the queue.
416: */
417: void axl_binary_stack_push (axlBinaryStack * bstack, axl_bool state)
418: {
419: axlBinaryStackNode * node;
420:
421: /* check references */
422: axl_return_if_fail (bstack);
423:
424: /* check basic case */
425: if (bstack->last == NULL) {
426:
427: axl_binary_stack_push_create_and_return:
428:
429: /* configure last */
430: node = axl_new (axlBinaryStackNode, 1);
431: node->count = 1;
432: node->state = state;
433:
434: /* configure */
435: bstack->last = node;
436:
437: /* store in the stack */
438: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Storing first item: 0x%x", node); */
439: axl_stack_push (bstack->stack, node);
440:
441: /* update count */
442: bstack->count++;
443:
444: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Storing item state=%d, count=%d, bcount=%d",
445: node->state, node->count, bstack->count); */
446:
447: return;
448: } /* end if */
449:
450: /* default case, check current state */
451: if (bstack->last->state == state) {
452:
453: /* found same state, increase count and return */
454: bstack->last->count++;
455:
456: /* update count */
457: bstack->count++;
458:
459: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Found same state, reusing..state=%d, count=%d, bcount=%d",
460: bstack->last->state, bstack->last->count, bstack->count); */
461:
462: return;
463: } /* end if */
464:
465: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "Found state changed, creating..state=%d (previuos state: %d), count=%d, bcount=%d",
466: state, bstack->last->state, bstack->last->count, bstack->count); */
467:
468: /* if reached this place, create a new node */
469: goto axl_binary_stack_push_create_and_return;
470: }
471:
472: /**
473: * @brief Convenience function that allows to push a new value using
474: * the last one pushed in the stack. This function allows to implement
475: * the same feature provided by peeking (\ref axl_binary_stack_peek)
476: * the next visible value on the stack head and then pushing it again.
477: *
478: * @param bstack The binary stack where to perform the operation.
479: *
480: * NOTE: The stack must not be empty before calling to this
481: * function. It has to have at least one value already pushed.
482: */
483: void axl_binary_stack_push_the_same (axlBinaryStack * bstack)
484: {
485: axl_return_if_fail (bstack);
486: axl_return_if_fail (bstack->last);
487:
488: /* update stack */
489: bstack->last->count++;
490: bstack->count++;
491:
492: return;
493: }
494:
495: /**
496: * @brief Allows to pop the next value from the stack.
497: *
498: * @param bstack The binary stack where the next value will be
499: * restored.
500: *
501: * @return The next value stored in the stack. You must check if the
502: * stack is empty before calling to this function since you won't be
503: * able to differenciate a axl_false value stored from a axl_false value
504: * returned by an error.
505: */
506: axl_bool axl_binary_stack_pop (axlBinaryStack * bstack)
507: {
508: axlBinaryStackNode * node;
509: axl_bool state;
510: axl_return_val_if_fail (bstack, axl_false);
511:
512: /* get last value */
513: node = bstack->last;
514: if (node == NULL) {
515: /* return axl_false because the stack is empty */
516: return axl_false;
517: } /* end if */
518:
519: /* check if there are more than 1 item, that is, at least
520: * 2. */
521: if (node->count > 1) {
522:
523: /* update count */
524: bstack->count--;
525:
526: /* decrease the counter and return */
527: node->count--;
528:
529: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: found state with more than 1 item, poping: state=%d, count=%d, bcount=%d",
530: node->state, node->count, bstack->count); */
531:
532: return node->state;
533:
534: } else if (node->count == 1) {
535:
536: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: found state with only 1 item, poping: state=%d, count=%d, bcount=%d",
537: node->state, node->count, bstack->count); */
538:
539: /* get the value */
540: state = node->state;
541:
542: /* update the next last (remove the current last) and
543: * use the next */
544: axl_stack_pop (bstack->stack);
545: bstack->last = axl_stack_peek (bstack->stack);
546:
547: /* release to the factory */
548: /* __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: new node to use: 0x%x, about to release 0x%x",
549: bstack->last, node); */
550: axl_free (node);
551:
552: /* update count */
553: bstack->count--;
554:
555: node = bstack->last;
556: /* if (node != NULL) {
557: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "POP: after poping: state=%d, count=%d, bcount=%d",
558: node->state, node->count, bstack->count);
559: } */
560:
561: return state;
562: } /* end if */
563:
564: /* this shouldn't be reached */
565: return axl_false;
566: }
567:
568: /**
569: * @brief Allows to get the current stack head value stored without
570: * removing it from the stack.
571: *
572: * @param bstack The binary stack where to perform the operation.
573: *
574: * @return The value stored in the stack head. The stack must contain
575: * at least one value, otherwise the returned value is not
576: * reliable. See \ref axl_binary_stack_is_empty to avoid calling to this function.
577: */
578: axl_bool axl_binary_stack_peek (axlBinaryStack * bstack)
579: {
580: axl_return_val_if_fail (bstack, axl_false);
581:
582: /* return current state */
583: return (bstack->last && bstack->last->state);
584: }
585:
586: /**
587: * @brief Check current emptyness status for the provided binary
588: * stack.
589: *
590: * @param bstack The binary stack to check.
591: *
592: * @return axl_true if the binary stack is empty, otherwise axl_false is
593: * returned.
594: */
595: axl_bool axl_binary_stack_is_empty (axlBinaryStack * bstack)
596: {
597: axl_return_val_if_fail (bstack, axl_false);
598:
599: /* return current emptyness status */
600: return (bstack->last == NULL && axl_stack_is_empty (bstack->stack));
601: }
602:
603: /**
604: * @brief Allows to get current number of items stored.
605: *
606: * @param bstack The binary stack to check current number of items
607: * stored.
608: *
609: * @return The number of items stored or -1 if it fails.
610: */
611: int axl_binary_stack_size (axlBinaryStack * bstack)
612: {
613: axl_return_val_if_fail (bstack, -1);
614:
615: /* return item count */
616: return bstack->count;
617: }
618:
619: /**
620: * @brief Release the provided binary stack.
621: *
622: * @param bstack The binary stack to release.
623: */
624: void axl_binary_stack_free (axlBinaryStack * bstack)
625: {
626: if (bstack == NULL)
627: return;
628:
629: /* free resources */
630: axl_stack_free (bstack->stack);
631: axl_free (bstack);
632:
633: return;
634: }
635:
636: /**
637: * @}
638: */
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