Annotation of gpl/axl/src/axl_stack.c, revision 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