Annotation of gpl/axl/src/axl_list.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_list.h>
! 42: #include <axl_log.h>
! 43: #include <axl_stream.h>
! 44:
! 45: #define LOG_DOMAIN "axl-list"
! 46:
! 47: typedef struct _axlListNode axlListNode;
! 48:
! 49: struct _axlList {
! 50: /* functions used by the list to properly order elements
! 51: * inside it and how they are destroyed */
! 52: axlEqualFunc are_equal;
! 53: axlDestroyFunc destroy_data;
! 54:
! 55: /* pointers to the list content */
! 56: axlListNode * first_node;
! 57: axlListNode * last_node;
! 58:
! 59: /* list length */
! 60: int length;
! 61:
! 62: /* memory management functions */
! 63: axlListNode ** preallocated;
! 64: int available;
! 65: int allocated;
! 66: };
! 67:
! 68: struct _axlListNode {
! 69: axlListNode * previous;
! 70: axlListNode * next;
! 71: axlPointer data;
! 72: };
! 73:
! 74: struct _axlListCursor {
! 75: axlList * list;
! 76: axlListNode * current;
! 77: };
! 78:
! 79: /**
! 80: * \defgroup axl_list_module Axl List: A configurable double-linked list used across the library.
! 81: */
! 82:
! 83: /**
! 84: * \addtogroup axl_list_module
! 85: * @{
! 86: */
! 87:
! 88: /**
! 89: * @internal
! 90: *
! 91: * Internal are equal handler implementation for the axl list module
! 92: * that always return 0.
! 93: */
! 94: int __axl_list_always_true (axlPointer a, axlPointer b)
! 95: {
! 96: return 0;
! 97: }
! 98:
! 99: /**
! 100: * @internal
! 101: *
! 102: * Preallocates nodes to be used to store data on the lists.
! 103: *
! 104: * @param list The list where the preallocation operation will be
! 105: * performed.
! 106: */
! 107: void __axl_list_allocate_nodes (axlList * list)
! 108: {
! 109: int iterator;
! 110:
! 111: list->available = 1;
! 112: list->allocated += list->available;
! 113:
! 114: /* allocate enough memory to hold all nodes already
! 115: * allocated */
! 116: if (list->preallocated == NULL)
! 117: list->preallocated = axl_new (axlListNode *, list->allocated);
! 118: else
! 119: list->preallocated = realloc (list->preallocated, (sizeof (axlListNode *)) * list->allocated);
! 120:
! 121: /* allocate a node for each available position */
! 122: for (iterator = 0; iterator < list->available; iterator++) {
! 123: list->preallocated[iterator] = axl_new (axlListNode, 1);
! 124: }
! 125:
! 126: return;
! 127: }
! 128:
! 129: /**
! 130: * @internal
! 131: *
! 132: * Disposes the node provided, reusing on the next operation
! 133: * requested.
! 134: */
! 135: void __axl_list_dispose_node (axlList * list, axlListNode * node)
! 136: {
! 137: /* store the node to be usable again */
! 138: list->preallocated [list->available] = node;
! 139:
! 140: /* increase current available nodes */
! 141: list->available++;
! 142:
! 143: return;
! 144: }
! 145:
! 146: /**
! 147: * @internal
! 148: *
! 149: * Returns a reference to an list node to be used.
! 150: */
! 151: axlListNode * __axl_list_get_next_node_available (axlList * list)
! 152: {
! 153: axlListNode * node;
! 154:
! 155: /* check that there are nodes available */
! 156: if (list->available == 0)
! 157: __axl_list_allocate_nodes (list);
! 158:
! 159: /* get the next node available */
! 160: node = list->preallocated[list->available - 1];
! 161: list->available--;
! 162:
! 163: /* clean node */
! 164: node->next = NULL;
! 165: node->previous = NULL;
! 166: node->data = NULL;
! 167:
! 168: return node;
! 169: }
! 170:
! 171:
! 172: /**
! 173: * @brief Creates a new \ref axlList, using provided handlers.
! 174: *
! 175: * An \ref axlList is a double linked list, with the hability to
! 176: * recognize elements inside its list by providing the \ref
! 177: * axlEqualFunc "are_equal" function and the ability to release
! 178: * memory allocated by the data stored by providing a \ref
! 179: * axlDestroyFunc "destroy_data" handler.
! 180: *
! 181: * The destroy handler is a optional value. If not provided, any
! 182: * automatic deallocation function will not provided.
! 183: *
! 184: * The "are equal" handler is not optinal. You must provide it to make
! 185: * the list work. In the case you don't like a ordering feature you
! 186: * can provide an are equal that just return 0 when elements are equal
! 187: * and always -1 for the rest of the cases if element should be
! 188: * appended or 1 if the element should be prepended.
! 189: *
! 190: * The list is not prepared to be managed at the same type by several
! 191: * threads. If the list is created and then used by several threads it
! 192: * will work properly. However, if several threads add and removes
! 193: * elements at the same time rainy days will come and you'll get funny
! 194: * behaviours.
! 195: *
! 196: * To create the list you must provide two function that performs some
! 197: * minimal functions required by the list o properly order the data
! 198: * inside the list and how this data is deallocated (this is
! 199: * optional).
! 200: *
! 201: * For example, to create a list that will hold strings dinamically
! 202: * allocated you can use:
! 203: * \code
! 204: * axlList * list = axl_list_new (axl_list_equal_string, axl_free);
! 205: * \endcode
! 206: *
! 207: * For a list that will holds integer values you can use: \ref
! 208: * axl_list_equal_int.
! 209: *
! 210: * Previous list will cause all strings inside to be deallocated once
! 211: * called to \ref axl_list_free. If you don't like this, do not
! 212: * provide the deallocation function.
! 213: *
! 214: * You can always use the following function to make the list to allways
! 215: * add all data at the end of the list: \ref axl_list_always_return_1,
! 216: * which, as its names indicates, allways return 1, causing the item
! 217: * to be added at the end of the list. See \ref axlEqualFunc
! 218: * documentation to know more about creating ordenation functions.
! 219: *
! 220: * Now you have your list created, you can use the following functions
! 221: * to add items:
! 222: *
! 223: * - \ref axl_list_add
! 224: * - \ref axl_list_add_at
! 225: * - \ref axl_list_prepend
! 226: * - \ref axl_list_append
! 227: *
! 228: * Once you have inserted some data, you can use the following piece
! 229: * of code to perform an iteration:
! 230: *
! 231: * \code
! 232: * int iterator = 0;
! 233: * while (iterator < axl_list_length (list)) {
! 234: * // get the data at the given position
! 235: * data = axl_list_get_nth (list, iterator);
! 236: *
! 237: * // update the iterator
! 238: * iterator++;
! 239: * }
! 240: * \endcode
! 241: *
! 242: * However, it is preferred to use the \ref axlListCursor, which is
! 243: * far more efficient. See the following function to get more
! 244: * information: \ref axl_list_cursor_new.
! 245: *
! 246: * In general, if you are going to perform a lookup for a single item
! 247: * you can use \ref axl_list_lookup (by providing a handler) or \ref
! 248: * axl_list_get_nth if you know the position.
! 249: *
! 250: *
! 251: * @param are_equal The equal function to be used by the list to find
! 252: * and order elements inside the list.
! 253: *
! 254: * @param destroy_data An optional handler to destroy nodes in the
! 255: * case the list is unrefered.
! 256: *
! 257: * @return A newly allocated list, that must be destroy by calling to
! 258: * \ref axl_list_free.
! 259: */
! 260: axlList * axl_list_new (axlEqualFunc are_equal, axlDestroyFunc destroy_data)
! 261: {
! 262: axlList * result;
! 263:
! 264: axl_return_val_if_fail (are_equal, NULL);
! 265:
! 266: result = axl_new (axlList, 1);
! 267: result->are_equal = are_equal;
! 268: result->destroy_data = destroy_data;
! 269:
! 270: /* preallocate memory for nodes */
! 271: /* __axl_list_allocate_nodes (result); */
! 272:
! 273: return result;
! 274: }
! 275:
! 276: /**
! 277: * @brief Allows to reconfigure the destroy function to be used on
! 278: * this list. This function can be useful to disable the destroy
! 279: * function associated to the list.
! 280: *
! 281: * @param list The list to reconfigure or disable (NULL) the destroy function.
! 282: *
! 283: * @param destroy_data The reference to the destroy function to be
! 284: * used or NULL to disable it.
! 285: */
! 286: void axl_list_set_destroy_func (axlList * list, axlDestroyFunc destroy_data)
! 287: {
! 288: axl_return_if_fail (list);
! 289: list->destroy_data = destroy_data;
! 290: return;
! 291: }
! 292:
! 293: /**
! 294: * @brief Allows to copy the provided list, returning a newly
! 295: * allocated structure.
! 296: *
! 297: * The copy process can also perform a deep copy for all data stored
! 298: * inside the \ref axlList. However, for this purpose it is required
! 299: * to provide a duplication function that is able to implement the
! 300: * duplication operation over the data received.
! 301: *
! 302: * This handler is optional, and in the case it is not provided, the
! 303: * list returned will be a copy having reference to the content
! 304: * stored.
! 305: *
! 306: * NOTE: the function also copy the destroy and equal function
! 307: * configured at \ref axl_list_new. If you want to disable destroy
! 308: * function on the copy returned you must use \ref
! 309: * axl_list_set_destroy_func, passing NULL as destroy handler.
! 310: *
! 311: * @param list The list to copy.
! 312: * @param func The duplication function used to perform a deep copy (optional handler).
! 313: *
! 314: * @return A newly allocated \ref axlList with the same configuration
! 315: * as the one provided.
! 316: */
! 317: axlList * axl_list_copy (axlList * list, axlDuplicateFunc func)
! 318: {
! 319: axlList * result;
! 320: int iterator;
! 321: axlPointer data;
! 322:
! 323: axl_return_val_if_fail (list, NULL);
! 324:
! 325: /* create a new axl list */
! 326: result = axl_list_new (list->are_equal, list->destroy_data);
! 327:
! 328: /* if the duplicate function is NULL, remove the destroy
! 329: * function */
! 330: if (func == NULL)
! 331: result->destroy_data = NULL;
! 332:
! 333: /* add all elements */
! 334: iterator = 0;
! 335: while (iterator < axl_list_length (list)) {
! 336: /* get data pointer from the list */
! 337: data = axl_list_get_nth (list, iterator);
! 338:
! 339: /* try to make a copy */
! 340: if (func != NULL)
! 341: data = func (data);
! 342:
! 343: /* add the data to the new list */
! 344: axl_list_add (result, data);
! 345:
! 346: /* update index */
! 347: iterator++;
! 348: }
! 349:
! 350: return result;
! 351: }
! 352:
! 353: /**
! 354: * @brief Equal function that is prepared to receive two strings a
! 355: * return if they are equal.
! 356: *
! 357: * This function is provided as a convenience implementation for the
! 358: * \ref axl_list_new function, allowing to store strings inside the
! 359: * given list.
! 360: *
! 361: * The function will return 0 if the string are equal and 1 if
! 362: * not. This will cause strings to be append at the end of the list.
! 363: *
! 364: * @param a The first string to compare.
! 365: * @param b The second string to compare.
! 366: */
! 367: int axl_list_equal_string (axlPointer a, axlPointer b)
! 368: {
! 369: int length;
! 370:
! 371: axl_return_val_if_fail (a, 1);
! 372: axl_return_val_if_fail (b, 1);
! 373:
! 374: /* get length */
! 375: length = strlen (a);
! 376:
! 377: /* check first that both strings have the same length */
! 378: if (length != strlen (b))
! 379: return 1;
! 380:
! 381: if (axl_stream_cmp (a, b, length))
! 382: return 0;
! 383: /* differs */
! 384: return 1;
! 385: }
! 386:
! 387: /**
! 388: * @brief Equal function that is preprated to receive to integers and
! 389: * return if they are equal.
! 390: *
! 391: * It is assumed that integers are stored in the list using the
! 392: * following:
! 393: * \code
! 394: * axl_list_add (list, INT_TO_PTR (integer));
! 395: * \endcode
! 396: *
! 397: * You can use this function to create an \ref axlList that stores
! 398: * integer values as follows:
! 399: * \code
! 400: * list = axl_list_new (axl_list_equal_int, NULL);
! 401: * \endcode
! 402: *
! 403: * The list created with this function will order data from litter to
! 404: * greater values.
! 405: *
! 406: *
! 407: * @param a A reference to the first integer.
! 408: * @param b A reference to the second integer.
! 409: *
! 410: * @return 0 if values received are equal, and 1 if b is greater than
! 411: * b. Otherwise -1 is returned.
! 412: */
! 413: int axl_list_equal_int (axlPointer a, axlPointer b)
! 414: {
! 415: /* especial case where a 0 is stored */
! 416: if (PTR_TO_INT (a) == PTR_TO_INT (b))
! 417: return 0;
! 418: else if (PTR_TO_INT (a) < PTR_TO_INT (b))
! 419: return -1;
! 420: else
! 421: return 1;
! 422: }
! 423:
! 424: /**
! 425: * @brief An equal function that could be used to make elements to be
! 426: * stored inside an \ref axlList at the end as the are added, without
! 427: * replacing any previously added item.
! 428: *
! 429: *
! 430: * If it is needed to create a list that stores elements at the end as
! 431: * they are added, this function could be used as the \ref
! 432: * axlEqualFunc, while calling to axl_list_new.
! 433: *
! 434: * @param a First item.
! 435: * @param b Second item.
! 436: *
! 437: * @return The function always return 1.
! 438: *
! 439: * NOTE: If you use this function and your intention is to remove
! 440: * items (without calling to axl_list_free) you must use \ref
! 441: * axl_list_remove_ptr or \ref axl_list_unlink_ptr since \ref
! 442: * axl_list_remove and \ref axl_list_unlink relays on the equal
! 443: * function to find and remove the item. Because this function never
! 444: * return 0, the item is never removed.
! 445: */
! 446: int axl_list_always_return_1 (axlPointer a, axlPointer b)
! 447: {
! 448: return 1;
! 449: }
! 450:
! 451: /**
! 452: * @brief Allows to store a new element inside the list, using the
! 453: * provided data.
! 454: *
! 455: * The function will fail to perform any action if a null reference is
! 456: * provided to the function.
! 457: *
! 458: * @param list The list where the element will be added.
! 459: *
! 460: * @param pointer The pointer to store.
! 461: *
! 462: * NOTE: The function uses the equal function defined at \ref
! 463: * axl_list_new. If the function shows that the item to be added is
! 464: * already added (because the equal function returns 0, then the item
! 465: * won't be added.
! 466: *
! 467: */
! 468: void axl_list_add (axlList * list, axlPointer pointer)
! 469: {
! 470: axlListNode * new_node;
! 471: axlListNode * node;
! 472: axlListNode * node2;
! 473:
! 474:
! 475: /* perform some environment checkings */
! 476: axl_return_if_fail (list);
! 477:
! 478: new_node = __axl_list_get_next_node_available (list);
! 479: new_node->data = pointer;
! 480:
! 481: /* check basic case */
! 482: if (list->first_node == NULL) {
! 483: list->first_node = new_node;
! 484: list->last_node = new_node;
! 485: list->length = 1;
! 486: return;
! 487: }
! 488:
! 489: /* complex case */
! 490: node = list->first_node;
! 491: node2 = list->last_node;
! 492:
! 493: /* lookup */
! 494: while ((node != NULL) || (node2 != NULL)) {
! 495: /* lookup the head */
! 496: if (node != NULL) {
! 497: switch (list->are_equal (node->data, pointer)) {
! 498: case -1:
! 499: /* the node should be added before node */
! 500: new_node->next = node;
! 501: new_node->previous = node->previous;
! 502: node->previous = new_node;
! 503:
! 504: /* if new previous is null do not update it */
! 505: if (new_node->previous != NULL)
! 506: new_node->previous->next = new_node;
! 507: else
! 508: list->first_node = new_node;
! 509:
! 510: /* update list length */
! 511: list->length ++;
! 512: return;
! 513: case 0:
! 514: /* the node found is equal, do not perform any operation */
! 515: return;
! 516: case 1:
! 517: default:
! 518: /* the node should be added after */
! 519: node = node->next;
! 520: break;
! 521: }
! 522: } /* end if */
! 523:
! 524: /* lookup from the tail */
! 525: if (node2 != NULL) {
! 526: switch (list->are_equal (node2->data, pointer)) {
! 527: case -1:
! 528: default:
! 529: /* the node should be added before node */
! 530: node2 = node2->previous;
! 531: break;
! 532: case 0:
! 533:
! 534: /* the node found is equal, do not perform any operation */
! 535: return;
! 536: case 1:
! 537: /* the node should be added after */
! 538: new_node->previous = node2;
! 539: new_node->next = node2->next;
! 540: node2->next = new_node;
! 541:
! 542: /* do not update if next is NULL */
! 543: if (new_node->next != NULL)
! 544: new_node->next->previous = new_node;
! 545: else
! 546: list->last_node = new_node;
! 547:
! 548: /* update length size */
! 549: list->length ++;
! 550: return;
! 551: }
! 552: } /* end if */
! 553: } /* end while */
! 554:
! 555: /* nothing more to do */
! 556: return;
! 557: }
! 558:
! 559: /**
! 560: * @brief Allows to adds the provided item to the given list at the
! 561: * selected position.
! 562: *
! 563: * The function will perform an indexed addition, using the value
! 564: * <b>position</b>, by-passing current list configuration (\ref
! 565: * axl_list_new).
! 566: *
! 567: * If the position is greater than the length of the list, the item is
! 568: * added at the end of the list. If the position is 0, the item is
! 569: * added at the begin (equivalent to call \ref axl_list_prepend).
! 570: *
! 571: * If an item is found at the provided position, the element is added
! 572: * before the already found.
! 573: *
! 574: * @param list The list where the addition operation will be performed.
! 575: *
! 576: * @param pointer The item to add to the list.
! 577: *
! 578: * @param position Position where the addition operation will be
! 579: * performed. Values allowed ranges from 0 up to list length - 1.
! 580: */
! 581: void axl_list_add_at (axlList * list, axlPointer pointer, int position)
! 582: {
! 583: int iterator;
! 584: axlListNode * node;
! 585: axlListNode * new_node;
! 586:
! 587: /* check incoming values */
! 588: axl_return_if_fail (list);
! 589:
! 590: /* check if we have a prepend operation */
! 591: if (position <= 0) {
! 592: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "adding item using prepend");
! 593: /* prepend */
! 594: axl_list_prepend (list, pointer);
! 595:
! 596: return;
! 597: }
! 598: /* check if we have an append operation */
! 599: if (position >= list->length) {
! 600: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "adding item using append (position=%d >= length=%d)",
! 601: position, list->length);
! 602: /* append */
! 603: axl_list_append (list, pointer);
! 604:
! 605: return;
! 606: }
! 607:
! 608: /* allocate a new node */
! 609: new_node = __axl_list_get_next_node_available (list);
! 610: new_node->data = pointer;
! 611:
! 612:
! 613: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "looking node position: %d", position);
! 614:
! 615: /* basic case isn't reached here (remove first and last
! 616: * cases) */
! 617: iterator = 1;
! 618: node = list->first_node->next;
! 619: while (iterator < position) {
! 620:
! 621: /* get the next element */
! 622: node = node->next;
! 623:
! 624: /* update the iterator */
! 625: iterator++;
! 626: }
! 627:
! 628: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "adding item at: %d", iterator);
! 629:
! 630: /* add the element */
! 631: new_node->previous = node->previous;
! 632: if (node->previous != NULL)
! 633: node->previous->next = new_node;
! 634:
! 635: new_node->next = node;
! 636: node->previous = new_node;
! 637:
! 638: /* update number of items inside */
! 639: list->length++;
! 640: return;
! 641: }
! 642:
! 643: /**
! 644: * @brief Allows to add a node to the provided list, at the first
! 645: * position, without taking into consideration current \ref axlList
! 646: * configuration (\ref axlEqualFunc at \ref axl_list_new).
! 647: *
! 648: * @param list The list where the data will be added at the first
! 649: * position.
! 650: *
! 651: * @param pointer The pointer to add.
! 652: */
! 653: void axl_list_prepend (axlList * list, axlPointer pointer)
! 654: {
! 655: axlListNode * new_node;
! 656:
! 657: axl_return_if_fail (list);
! 658:
! 659: /* simulate adding the node at the first position */
! 660: new_node = __axl_list_get_next_node_available (list);
! 661: new_node->data = pointer;
! 662:
! 663: /* make the new node the be the first one */
! 664: if (list->first_node == NULL) {
! 665: list->first_node = new_node;
! 666: list->last_node = new_node;
! 667: }else {
! 668: list->first_node->previous = new_node;
! 669: new_node->next = list->first_node;
! 670: list->first_node = new_node;
! 671: }
! 672:
! 673: /* update number of items inside */
! 674: list->length++;
! 675:
! 676: return;
! 677: }
! 678:
! 679:
! 680: /**
! 681: * @brief Allows to add a node to the provided list, at the last
! 682: * position, without taking into consideration current \ref axlList
! 683: * configuration (\ref axlEqualFunc at \ref axl_list_new).
! 684: *
! 685: * @param list The list where the data will be added at the last
! 686: * position.
! 687: *
! 688: * @param pointer The pointer to add.
! 689: */
! 690: void axl_list_append (axlList * list, axlPointer pointer)
! 691: {
! 692: axlListNode * new_node;
! 693:
! 694: axl_return_if_fail (list);
! 695:
! 696: /* simulate adding the node at the first position */
! 697: new_node = __axl_list_get_next_node_available (list);
! 698: new_node->data = pointer;
! 699:
! 700: /* make the new node the be the first one */
! 701: if (list->last_node == NULL) {
! 702: list->first_node = new_node;
! 703: list->last_node = new_node;
! 704: }else {
! 705: list->last_node->next = new_node;
! 706: new_node->previous = list->last_node;
! 707: list->last_node = new_node;
! 708: }
! 709:
! 710: /* update number of items inside */
! 711: list->length++;
! 712:
! 713: return;
! 714: }
! 715:
! 716: /**
! 717: * @internal Internal list lookup using a linear search, checking all
! 718: * items inside the list taking into considerations hints provided by
! 719: * equal function.
! 720: *
! 721: * @param list The list where the linear search will be performed.
! 722: * @param pointer The pointer that is being looked up.
! 723: *
! 724: * @return A reference to the internal axl list node containing the
! 725: * pointer.
! 726: */
! 727: axlListNode * axl_list_internal_linear_lookup (axlList * list,
! 728: axlPointer pointer)
! 729: {
! 730: axlListNode * node;
! 731:
! 732: axl_return_val_if_fail (list, NULL);
! 733:
! 734: /* complex case */
! 735: node = list->first_node;
! 736:
! 737: /* lookup */
! 738: while (node != NULL) {
! 739: if (list->are_equal (node->data, pointer) == 0)
! 740: return node;
! 741:
! 742: /* the node should be after this one */
! 743: node = node->next;
! 744:
! 745: } /* end while */
! 746:
! 747: return NULL;
! 748: }
! 749:
! 750: /**
! 751: * @internal Internal list lookup using a linear search, checking all
! 752: * items inside the list withtout taking into considerations hints
! 753: * provided by equal function (search by pointer).
! 754: *
! 755: * @param list The list where the linear search will be performed.
! 756: * @param pointer The pointer that is being looked up.
! 757: *
! 758: * @return A reference to the internal axl list node containing the
! 759: * pointer.
! 760: */
! 761: axlListNode * axl_list_internal_linear_lookup_ptr (axlList * list,
! 762: axlPointer pointer)
! 763: {
! 764: axlListNode * node;
! 765:
! 766: axl_return_val_if_fail (list, NULL);
! 767:
! 768: /* complex case */
! 769: node = list->first_node;
! 770:
! 771: /* lookup */
! 772: while (node && node->data != pointer) {
! 773: /* the node should be after this one */
! 774: node = node->next;
! 775: } /* end while */
! 776:
! 777: /* return current result */
! 778: return node;
! 779: }
! 780:
! 781: /**
! 782: * @internal
! 783: * @brief Internal lookup function to locate the axlListNode that contains the pointer.
! 784: *
! 785: *
! 786: * @param list The list where the lookup will be performed.
! 787: * @param pointer The pointer data to lookup.
! 788: *
! 789: * @return A reference to the \ref axlListNode or NULL if no pointer
! 790: * is found.
! 791: */
! 792: axlListNode * axl_list_internal_lookup (axlList * list, axlPointer pointer)
! 793: {
! 794: axlListNode * node;
! 795: axlListNode * node2;
! 796:
! 797: axl_return_val_if_fail (list, NULL);
! 798: axl_return_val_if_fail (pointer, NULL);
! 799:
! 800: /* complex case */
! 801: node = list->first_node;
! 802: node2 = list->last_node;
! 803:
! 804: /* lookup */
! 805: while ((node != NULL) || (node2 != NULL)) {
! 806: /* lookup the head */
! 807: if (node != NULL) {
! 808: switch (list->are_equal (node->data, pointer)) {
! 809: case -1:
! 810: default:
! 811: /* node should be before the node
! 812: * found. So we are not going to find
! 813: * a node that is lower, the element
! 814: * is not in the list.
! 815: */
! 816: return NULL;
! 817: case 0:
! 818: return node;
! 819: case 1:
! 820: /* the node should be after this one */
! 821: node = node->next;
! 822: break;
! 823: }
! 824: } /* end if */
! 825:
! 826: /* lookup from the tail */
! 827: if (node2 != NULL) {
! 828: switch (list->are_equal (node2->data, pointer)) {
! 829: case -1:
! 830: /* the node should be added before node */
! 831: node2 = node2->next;
! 832: break;
! 833: case 0:
! 834: return node2;
! 835: case 1:
! 836: default:
! 837: /* it seems that the node should be
! 838: * found after this node but this is
! 839: * not going to be possible. The node is not in the list.
! 840: */
! 841: return NULL;
! 842: }
! 843: } /* end if */
! 844: } /* end while */
! 845:
! 846: return NULL;
! 847: }
! 848:
! 849:
! 850: /**
! 851: * @internal
! 852: *
! 853: * @brief Allows to lookup the pointer stored, inside the provided
! 854: * list, on the given position.
! 855: *
! 856: * @param list The list where the operation will be performed.
! 857: * @param position The position to lookup for stored data.
! 858: *
! 859: * @return A reference or NULL if fails.
! 860: */
! 861: axlListNode * axl_list_internal_get_nth (axlList * list, int position)
! 862: {
! 863: axlListNode * node;
! 864: int iterator = 0;
! 865:
! 866: axl_return_val_if_fail (list, NULL);
! 867: axl_return_val_if_fail (position >= 0 && position < list->length, NULL);
! 868:
! 869: /* iterate until the node is found */
! 870: node = list->first_node;
! 871: while (node != NULL && (iterator != position)) {
! 872: iterator ++;
! 873: node = node->next;
! 874: }
! 875:
! 876: /* return data found */
! 877: if (iterator == position)
! 878: return node;
! 879: return NULL;
! 880: }
! 881:
! 882: /* remove the selected node */
! 883: void __axl_list_common_remove_selected_node (axlList * list, axlListNode * node,
! 884: axl_bool alsoRemove)
! 885: {
! 886: axlPointer pointer;
! 887:
! 888: /* do not remove anything if a null reference is received */
! 889: if (node == NULL)
! 890: return;
! 891:
! 892: /* get a reference to the pointer */
! 893: pointer = node->data;
! 894:
! 895: if (node->previous == NULL)
! 896: list->first_node = node->next;
! 897: else
! 898: node->previous->next = node->next;
! 899:
! 900: if (node->next == NULL)
! 901: list->last_node = node->previous;
! 902: else
! 903: node->next->previous = node->previous;
! 904:
! 905: /* release user space allocated memory
! 906: * if defined destroy function */
! 907: if (alsoRemove && (list->destroy_data != NULL))
! 908: list->destroy_data (pointer);
! 909:
! 910: /* release memory allocated by the node */
! 911: __axl_list_dispose_node (list, node);
! 912:
! 913: /* decrease list length */
! 914: list->length--;
! 915:
! 916: /* nothing more to do */
! 917: return;
! 918: }
! 919:
! 920: /**
! 921: * @internal
! 922: *
! 923: * Internal support for axl_list_remove and axl_list_unlink
! 924: * function. The function perform a node removing, the one that
! 925: * contains the node pointed by the provided pointer, and making a
! 926: * node deallocation according to the configuration of the
! 927: * <b>alsoRemove</b>.
! 928: *
! 929: * @param list The list where the operation will be performed.
! 930: *
! 931: * @param pointer The pointer to remove
! 932: *
! 933: * @param alsoRemove Also call to destroy function.
! 934: *
! 935: * @param byPtr Makes the linear search to be done by pointer.
! 936: */
! 937: void axl_list_common_remove (axlList * list, axlPointer pointer, axl_bool alsoRemove, axl_bool byPtr)
! 938: {
! 939: axlListNode * node;
! 940:
! 941: axl_return_if_fail (list);
! 942:
! 943: /* complex case */
! 944: if (byPtr)
! 945: node = axl_list_internal_linear_lookup_ptr (list, pointer);
! 946: else
! 947: node = axl_list_internal_linear_lookup (list, pointer);
! 948: if (node == NULL) {
! 949: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "unable to find item by pointer (0x%x)",
! 950: pointer);
! 951: return;
! 952: }
! 953:
! 954: /* remove the selected node */
! 955: __axl_list_common_remove_selected_node (list, node, alsoRemove);
! 956:
! 957: return;
! 958: }
! 959:
! 960:
! 961: /**
! 962: * @brief Allows to remove the given pointer from the list.
! 963: *
! 964: * The element referenced by <b>pointer</b> will be removed from the
! 965: * list, include the memory allocated if a destroy function were
! 966: * provided.
! 967: *
! 968: * If it is required to remove a pointer from the list, without
! 969: * calling to the destroy function, you can use \ref axl_list_unlink.
! 970: *
! 971: * The function will fail to work if references provided are NULL.
! 972: *
! 973: * @param list The list where the removal operation will be performed.
! 974: * @param pointer The pointer where the
! 975: *
! 976: * NOTE: The function uses the current equal function configured. A
! 977: * not properly configured equal function will make this function to
! 978: * not remove the item selected. If you are trying to remove by
! 979: * pointer, you can use \ref axl_list_remove_ptr.
! 980: */
! 981: void axl_list_remove (axlList * list, axlPointer pointer)
! 982: {
! 983:
! 984: /* perform a complete removing */
! 985: axl_list_common_remove (list, pointer,
! 986: /* alsoRemove */
! 987: axl_true,
! 988: /* byPtr */
! 989: axl_false);
! 990:
! 991: return;
! 992: }
! 993:
! 994: /**
! 995: * @internal Implementation that removes or unlinks a selected node at
! 996: * a particular position.
! 997: */
! 998: void __axl_list_remove_at_common (axlList * list, int position, axl_bool remove_node)
! 999: {
! 1000: axlListNode * node;
! 1001: int iterator = 0;
! 1002:
! 1003: axl_return_if_fail (list);
! 1004:
! 1005: /* find the item by position */
! 1006: node = list->first_node;
! 1007:
! 1008: /* lookup */
! 1009: while (node) {
! 1010: /* return selected node */
! 1011: if (iterator == position)
! 1012: break;
! 1013:
! 1014: /* the node should be after this one */
! 1015: node = node->next;
! 1016:
! 1017: /* next iterator */
! 1018: iterator++;
! 1019: } /* end while */
! 1020:
! 1021: if (node) {
! 1022: /* remove selected node */
! 1023: __axl_list_common_remove_selected_node (list, node, remove_node);
! 1024: } /* end if */
! 1025: return;
! 1026: }
! 1027:
! 1028: /**
! 1029: * @brief Allows to remove a particular item inside the list at a
! 1030: * selected position.
! 1031: *
! 1032: * This function also deallocates the memory used by the node located
! 1033: * at the particular position. In the case only a removal operation is
! 1034: * required use \ref axl_list_unlink_at.
! 1035: *
! 1036: * @param list The list where the remove operation will take place.
! 1037: *
! 1038: * @param position The position where the removal operation will take
! 1039: * place. Position values ranges from 0 up to (N - 1).
! 1040: */
! 1041: void axl_list_remove_at (axlList * list, int position)
! 1042: {
! 1043: /* call to common implementation */
! 1044: __axl_list_remove_at_common (list, position, axl_true);
! 1045: return;
! 1046: }
! 1047:
! 1048: /**
! 1049: * @brief Allows to remove the provided pointer from the list (calling
! 1050: * to the destroy function defined).
! 1051: *
! 1052: * Unlike \ref axl_list_remove, which removes the element selected by
! 1053: * using the equal function configured at \ref axl_list_new, this
! 1054: * function allows to perform a remove operation by pointer.
! 1055: *
! 1056: * @param list The list on which the operation is performed.
! 1057: *
! 1058: * @param pointer The pointer to remove from the list.
! 1059: */
! 1060: void axl_list_remove_ptr (axlList * list, axlPointer pointer)
! 1061: {
! 1062: /* perform a complete removing */
! 1063: axl_list_common_remove (list, pointer,
! 1064: /* alsoRemove */
! 1065: axl_true,
! 1066: /* byPtr */
! 1067: axl_true);
! 1068: }
! 1069:
! 1070: /**
! 1071: * @brief Removes the given pointer from the list, without calling the
! 1072: * destroy function, even when it is configured.
! 1073: *
! 1074: * @param list The list where the operation will be performed.
! 1075: *
! 1076: * @param pointer The pointer to remove.
! 1077: */
! 1078: void axl_list_unlink (axlList * list, axlPointer pointer)
! 1079: {
! 1080: /* perform a complete removing */
! 1081: axl_list_common_remove (list, pointer,
! 1082: /* alsoRemove */
! 1083: axl_false,
! 1084: /* byPtr */
! 1085: axl_false);
! 1086:
! 1087: return;
! 1088: }
! 1089:
! 1090: /**
! 1091: * @brief Allows to remove the provided item from the axl list
! 1092: * withtout using the equal function provided (remove by pointer) and
! 1093: * without calling to the associated destroy function.
! 1094: *
! 1095: * @param list The list where the operation will be implemented.
! 1096: *
! 1097: * @param pointer the pointer to remove from the list without calling
! 1098: * to the destroy function.
! 1099: */
! 1100: void axl_list_unlink_ptr (axlList * list, axlPointer pointer)
! 1101: {
! 1102:
! 1103: /* perform an unlink operation, without using equal
! 1104: * function */
! 1105: /* perform a complete removing */
! 1106: axl_list_common_remove (list, pointer,
! 1107: /* alsoRemove */
! 1108: axl_false,
! 1109: /* byPtr */
! 1110: axl_true);
! 1111:
! 1112: return;
! 1113: }
! 1114:
! 1115: /**
! 1116: * @brief Allows to unlink a particular item inside the list at a
! 1117: * selected position.
! 1118: *
! 1119: * This function DO NOT deallocates the memory used by the node located
! 1120: * at the particular position. In the case a complete removal operation is
! 1121: * required use \ref axl_list_remove_at.
! 1122: *
! 1123: * @param list The list where the unlink operation will take place.
! 1124: *
! 1125: * @param position The position where the unlink operation will take
! 1126: * place. Position values ranges from 0 up to (N - 1).
! 1127: */
! 1128: void axl_list_unlink_at (axlList * list, int position)
! 1129: {
! 1130: /* call to common implementation */
! 1131: __axl_list_remove_at_common (list, position, axl_false);
! 1132: return;
! 1133: }
! 1134:
! 1135:
! 1136: /**
! 1137: * @brief Allows to remove the first element, calling to the destroy
! 1138: * function if defined.
! 1139: *
! 1140: * @param list The list where the first element will be removed.
! 1141: */
! 1142: void axl_list_remove_first (axlList * list)
! 1143: {
! 1144:
! 1145: axl_return_if_fail (list);
! 1146:
! 1147: /* do not perform any operation if no node is stored */
! 1148: if (list->first_node == NULL)
! 1149: return;
! 1150:
! 1151: /* remove the selected node */
! 1152: __axl_list_common_remove_selected_node (list, list->first_node, axl_true);
! 1153:
! 1154: return;
! 1155: }
! 1156:
! 1157: /**
! 1158: * @brief Allows to remove the first element from the list without
! 1159: * calling to the destroy function, even with it is defined.
! 1160: *
! 1161: * @param list The list where the first element will be removed.
! 1162: */
! 1163: void axl_list_unlink_first (axlList * list)
! 1164: {
! 1165:
! 1166: axl_return_if_fail (list);
! 1167:
! 1168: /* do not perform any operation if no node is stored */
! 1169: if (list->first_node == NULL)
! 1170: return;
! 1171:
! 1172: /* remove the selected node */
! 1173: __axl_list_common_remove_selected_node (list, list->first_node, axl_false);
! 1174:
! 1175: return;
! 1176: }
! 1177:
! 1178: /**
! 1179: * @brief Allows to remove the last element, calling to the destroy
! 1180: * function if defined.
! 1181: *
! 1182: * @param list The list where the last element will be removed.
! 1183: */
! 1184: void axl_list_remove_last (axlList * list)
! 1185: {
! 1186: axl_return_if_fail (list);
! 1187:
! 1188: /* do not perform any operation if no node is stored */
! 1189: if (list->last_node == NULL)
! 1190: return;
! 1191:
! 1192: /* remove the selected node */
! 1193: __axl_list_common_remove_selected_node (list, list->last_node, axl_true);
! 1194:
! 1195: return;
! 1196: }
! 1197:
! 1198: /**
! 1199: * @brief Allows to remove the last element from the list without
! 1200: * calling to the destroy function, even with it is defined.
! 1201: *
! 1202: * @param list The list where the last element will be removed.
! 1203: */
! 1204: void axl_list_unlink_last (axlList * list)
! 1205: {
! 1206: axl_return_if_fail (list);
! 1207:
! 1208: /* do not perform any operation if no node is stored */
! 1209: if (list->last_node == NULL)
! 1210: return;
! 1211:
! 1212: /* remove the selected node */
! 1213: __axl_list_common_remove_selected_node (list, list->last_node, axl_false);
! 1214:
! 1215: return;
! 1216: }
! 1217:
! 1218: /**
! 1219: * @brief Allows to check if the given pointer is stored on the given
! 1220: * list.
! 1221: *
! 1222: * @param list The list where the lookup will be performed.
! 1223: *
! 1224: * @param pointer The pointer to lookup.
! 1225: *
! 1226: * @return \ref axl_true if the element is stored on the list,
! 1227: * otherwise axl_false is returned. The function will fail to lookup
! 1228: * if a NULL reference is received, either the list or the pointer.
! 1229: */
! 1230: axl_bool axl_list_exists (axlList * list, axlPointer pointer)
! 1231: {
! 1232: axl_return_val_if_fail (list, axl_false);
! 1233: axl_return_val_if_fail (pointer, axl_false);
! 1234:
! 1235: if (axl_list_internal_lookup (list, pointer) != NULL)
! 1236: return axl_true;
! 1237: return axl_false;
! 1238: }
! 1239:
! 1240: /**
! 1241: * @brief Allows to check if the provided list is empty (no element
! 1242: * stored).
! 1243: *
! 1244: * @param list The list to check for emptyness.
! 1245: *
! 1246: * @return axl_true if the list is empty, axl_false if not. The function
! 1247: * return axl_false in the case a null reference is provided.
! 1248: */
! 1249: axl_bool axl_list_is_empty (axlList * list)
! 1250: {
! 1251: axl_return_val_if_fail (list, axl_false);
! 1252:
! 1253: /* check if the first node is defined */
! 1254: return (list->first_node == NULL);
! 1255: }
! 1256:
! 1257: /**
! 1258: * @brief Allows to check if the given pointer is stored on the given position.
! 1259: *
! 1260: * @param list The list where the operation will be run.
! 1261: * @param pointer The pointer to check.
! 1262: * @param position The position where is expected to find the pointer.
! 1263: *
! 1264: * @return axl_true if the given data, referenced by the pointer, is
! 1265: * stored on the given position.
! 1266: */
! 1267: axl_bool axl_list_exists_at (axlList * list, axlPointer pointer, int position)
! 1268: {
! 1269: axlListNode * node;
! 1270:
! 1271: node = axl_list_internal_get_nth (list, position);
! 1272: if (node != NULL) {
! 1273: if (! list->are_equal (node->data, pointer))
! 1274: return axl_true;
! 1275: }
! 1276: return axl_false;
! 1277: }
! 1278:
! 1279: /**
! 1280: * @brief Returns the first element stored on the list.
! 1281: *
! 1282: *
! 1283: * @param list The list where the first element stored will be
! 1284: * returned.
! 1285: *
! 1286: * @return An \ref axlPointer containing the data stored on the list.
! 1287: */
! 1288: axlPointer axl_list_get_first (axlList * list)
! 1289: {
! 1290: axl_return_val_if_fail (list, NULL);
! 1291:
! 1292: if (list->first_node == NULL)
! 1293: return NULL;
! 1294: return list->first_node->data;
! 1295: }
! 1296:
! 1297: /**
! 1298: * @brief Returns the last element stored on the list.
! 1299: *
! 1300: * @param list The list where the last element will be returned.
! 1301: *
! 1302: * @return An \ref axlPointer reference containing the last stored
! 1303: * value.
! 1304: */
! 1305: axlPointer axl_list_get_last (axlList * list)
! 1306: {
! 1307: axl_return_val_if_fail (list, NULL);
! 1308:
! 1309: if (list->last_node == NULL)
! 1310: return NULL;
! 1311: return list->last_node->data;
! 1312: }
! 1313:
! 1314: /**
! 1315: * @brief Allows to get current pointer stored at the given position.
! 1316: *
! 1317: * @param list The list where the data will be retrieved.
! 1318: *
! 1319: * @param position A value ranging from 0 up to the the list lenght -
! 1320: * 1.
! 1321: *
! 1322: * @return The \ref axlPointer stored on the given position or NULL if
! 1323: * fail.
! 1324: */
! 1325: axlPointer axl_list_get_nth (axlList * list, int position)
! 1326: {
! 1327: axlListNode * node;
! 1328:
! 1329: node = axl_list_internal_get_nth (list, position);
! 1330: if (node != NULL)
! 1331: return node->data;
! 1332: return NULL;
! 1333: }
! 1334:
! 1335: /**
! 1336: * @brief Allows to perform a linear lookup on the list provided,
! 1337: * givin a function that is used to now the object to return due to
! 1338: * the lookup.
! 1339: *
! 1340: * The function can also be used as a foreach function. The following
! 1341: * example shows how to launch the function and perform a tasks on the
! 1342: * lookup function:
! 1343: * \code
! 1344: * // perform the lookup
! 1345: * return axl_list_lookup (list, __find_item, name);
! 1346: *
! 1347: * // the lookup function
! 1348: * axl_bool __find_item (axlPointer _element, axlPointer data)
! 1349: * {
! 1350: * SomeItem * element = _element;
! 1351: * char * name = data;
! 1352: *
! 1353: * // check the name
! 1354: * if (axl_cmp (element->name, name))
! 1355: * return axl_true;
! 1356: *
! 1357: * // it is not the element
! 1358: * return axl_false;
! 1359: * }
! 1360: * \endcode
! 1361: *
! 1362: * In the case you create a list to hold string values, you can use
! 1363: * \ref axl_list_find_string as lookup function predefined to perform
! 1364: * the search.
! 1365: *
! 1366: * @param list The list where the lookup will be performed.
! 1367: *
! 1368: * @param func The function to use to perform the lookup.
! 1369: *
! 1370: * @param data User defined data that will be passed to the func provided.
! 1371: *
! 1372: * @return A pointer to the object found or NULL if no item was found.
! 1373: */
! 1374: axlPointer axl_list_lookup (axlList * list, axlLookupFunc func, axlPointer data)
! 1375: {
! 1376: axlListNode * node;
! 1377: axl_return_val_if_fail (list, NULL);
! 1378: axl_return_val_if_fail (func, NULL);
! 1379:
! 1380: /* get the first pointer */
! 1381: node = list->first_node;
! 1382: do {
! 1383: /* if the next node to check is NULL, terminate the
! 1384: * lookup. */
! 1385: if (node == NULL)
! 1386: return NULL;
! 1387:
! 1388: /* check if the node found is the one looked up */
! 1389: if (func (node->data, data))
! 1390: return node->data;
! 1391:
! 1392: /* seems not, update to the next reference */
! 1393: node = node->next;
! 1394:
! 1395: }while (1);
! 1396:
! 1397: /* return no node found */
! 1398: return NULL;
! 1399: }
! 1400:
! 1401: /**
! 1402: * @brief Helper function that could be used at \ref axl_list_lookup if
! 1403: * the list created only contains strings.
! 1404: *
! 1405: * Use this function as a parameter for the lookup function at \ref
! 1406: * axl_list_lookup.
! 1407: *
! 1408: * @param element The element at the list, in this case, an string value.
! 1409: *
! 1410: * @param data The data provided at \ref axl_list_lookup, in this
! 1411: * case, the value we are looking.
! 1412: *
! 1413: * @return \ref axl_true if the string was found, \ref axl_false if not.
! 1414: */
! 1415: axl_bool axl_list_find_string (axlPointer element, axlPointer data)
! 1416: {
! 1417: /* if the string received is null, just return axl_false */
! 1418: if (data == NULL)
! 1419: return axl_false;
! 1420:
! 1421: /* return the comparison status */
! 1422: return axl_cmp ((char *) element, (char *) data);
! 1423: }
! 1424:
! 1425: /**
! 1426: * @brief Allows to get current list length.
! 1427: *
! 1428: * @param list The list to operate.
! 1429: *
! 1430: * @return The list length or -1 if fail (the list reference received
! 1431: * is null).
! 1432: */
! 1433: int axl_list_length (axlList * list)
! 1434: {
! 1435: axl_return_val_if_fail (list, -1);
! 1436: return list->length;
! 1437: }
! 1438:
! 1439: /**
! 1440: * @brief Allows to destroy the given list, and all user space
! 1441: * associated memory if a destroy handler was provided.
! 1442: *
! 1443: * @param list The list to destroy
! 1444: */
! 1445: void axl_list_free (axlList * list)
! 1446: {
! 1447: axlListNode * node;
! 1448: axlListNode * node2;
! 1449: int iterator;
! 1450:
! 1451: /* if a null reference is received do not oper */
! 1452: if (list == NULL)
! 1453: return;
! 1454:
! 1455: node = list->first_node;
! 1456: while (node != NULL) {
! 1457: if (list->destroy_data != NULL) {
! 1458: list->destroy_data (node->data);
! 1459: }
! 1460: node2 = node;
! 1461: node = node->next;
! 1462:
! 1463: axl_free (node2);
! 1464: }
! 1465:
! 1466: /* allocate a node for each available position */
! 1467: for (iterator = 0; iterator < list->available; iterator++) {
! 1468: axl_free (list->preallocated[iterator]);
! 1469: }
! 1470:
! 1471: /* free the array */
! 1472: axl_free (list->preallocated);
! 1473:
! 1474: /* free the list itself */
! 1475: axl_free (list);
! 1476:
! 1477: return;
! 1478: }
! 1479:
! 1480: /* @} */
! 1481:
! 1482: /**
! 1483: * \defgroup axl_list_cursor_module Axl List Cursor: Iterator support for the Axl List
! 1484: */
! 1485:
! 1486: /**
! 1487: * \addtogroup axl_list_cursor_module
! 1488: * @{
! 1489: */
! 1490:
! 1491: /**
! 1492: * @brief Allows to get a cursor to iterate the list in a linear and
! 1493: * efficient way.
! 1494: *
! 1495: * The \ref axlListCursor could be used to iterate an \ref axlList in
! 1496: * an efficient way because it stores current state (position). Then
! 1497: * using the following functions you can modify the state (current
! 1498: * position to get):
! 1499: *
! 1500: * - \ref axl_list_cursor_first
! 1501: * - \ref axl_list_cursor_last
! 1502: * - \ref axl_list_cursor_next
! 1503: * - \ref axl_list_cursor_previous
! 1504: *
! 1505: * Finally, a function is provided to get the data stored at a
! 1506: * particular position, pointed by the current status of the cursor:
! 1507: *
! 1508: * - \ref axl_list_cursor_get
! 1509: *
! 1510: * You are allowed to remove elements from the list (\ref axlList)
! 1511: * having a cursor created (\ref axlListCursor), using \ref
! 1512: * axl_list_cursor_unlink.
! 1513: *
! 1514: * Here is an example:
! 1515: * \code
! 1516: * axlPointer value;
! 1517: * axlListCursor * cursor;
! 1518: *
! 1519: * // create the cursor
! 1520: * cursor = axl_list_cursor_new (list);
! 1521: *
! 1522: * // while there are more elements
! 1523: * while (axl_list_cursor_has_item (cursor)) {
! 1524: *
! 1525: * // get the value
! 1526: * value = axl_list_cursor_get (cursor);
! 1527: *
! 1528: *
! 1529: * // get the next
! 1530: * axl_list_cursor_next (cursor);
! 1531: *
! 1532: * // update the iterator
! 1533: * iterator++;
! 1534: *
! 1535: * }
! 1536: *
! 1537: * // free the cursor
! 1538: * axl_list_cursor_free (cursor);
! 1539: * \endcode
! 1540: *
! 1541: * @param list The list that the new cursor (\ref axlListCursor) will
! 1542: * provide access.
! 1543: *
! 1544: * @return A newly created \ref axlListCursor used to iterate the
! 1545: * list. Once finished you must call to \ref axl_list_cursor_free.
! 1546: */
! 1547: axlListCursor * axl_list_cursor_new (axlList * list)
! 1548: {
! 1549: axlListCursor * cursor;
! 1550:
! 1551: axl_return_val_if_fail (list, NULL);
! 1552:
! 1553: /* create the cursor */
! 1554: cursor = axl_new (axlListCursor, 1);
! 1555:
! 1556: /* initial configuration */
! 1557: cursor->list = list;
! 1558: cursor->current = list->first_node;
! 1559:
! 1560: return cursor;
! 1561: }
! 1562:
! 1563: /**
! 1564: * @brief Allows to configure the cursor to point to the first item of
! 1565: * the list (if there are any).
! 1566: *
! 1567: * @param cursor The cursor that is required to be configured to point the first item.
! 1568: */
! 1569: void axl_list_cursor_first (axlListCursor * cursor)
! 1570: {
! 1571: axl_return_if_fail (cursor);
! 1572:
! 1573: if (cursor->list->length == 0) {
! 1574: cursor->current = NULL;
! 1575: return;
! 1576: } /* end if */
! 1577:
! 1578: /* set the first node */
! 1579: cursor->current = cursor->list->first_node;
! 1580:
! 1581: return;
! 1582: }
! 1583:
! 1584: /**
! 1585: * @brief Allows to configure the cursor to point to the last item of
! 1586: * the list (if there are any).
! 1587: *
! 1588: * @param cursor The cursor that is required to be configured to point
! 1589: * to the last item.
! 1590: */
! 1591: void axl_list_cursor_last (axlListCursor * cursor)
! 1592: {
! 1593: axl_return_if_fail (cursor);
! 1594:
! 1595: /* set the first node */
! 1596: cursor->current = cursor->list->last_node;
! 1597:
! 1598: return;
! 1599: }
! 1600:
! 1601: /**
! 1602: * @brief Allows to configure the cursor to point to the next item of
! 1603: * the list (if there are any).
! 1604: *
! 1605: * @param cursor The cursor that is required to be configured to point
! 1606: * to the next item.
! 1607: */
! 1608: void axl_list_cursor_next (axlListCursor * cursor)
! 1609: {
! 1610: axl_return_if_fail (cursor);
! 1611:
! 1612: /* set the next node */
! 1613: if (cursor->current != NULL)
! 1614: cursor->current = cursor->current->next;
! 1615:
! 1616: return;
! 1617: }
! 1618:
! 1619: /**
! 1620: * @brief Allows to configure the cursor to point to the previous item
! 1621: * of the list (if there are any).
! 1622: *
! 1623: * @param cursor The cursor that is required to be configured to point
! 1624: * to the previous item.
! 1625: */
! 1626: void axl_list_cursor_previous (axlListCursor * cursor)
! 1627: {
! 1628: axl_return_if_fail (cursor);
! 1629:
! 1630: /* set the next node */
! 1631: if (cursor->current != NULL)
! 1632: cursor->current = cursor->current->previous;
! 1633:
! 1634: return;
! 1635: }
! 1636:
! 1637: /**
! 1638: * @brief Allows to check if there are more elements next to the
! 1639: * current element pointed by the cursor.
! 1640: *
! 1641: * @param cursor The cursor that is required to return if there are
! 1642: * next items.
! 1643: *
! 1644: * @return \ref axl_true if more items are found, otherwise \ref axl_false is
! 1645: * returned.
! 1646: */
! 1647: axl_bool axl_list_cursor_has_next (axlListCursor * cursor)
! 1648: {
! 1649: axl_return_val_if_fail (cursor, axl_false);
! 1650:
! 1651: /* check for empty list */
! 1652: if (cursor->current == NULL)
! 1653: return axl_false;
! 1654:
! 1655: /* return if the next element isn't null */
! 1656: return (cursor->current->next != NULL);
! 1657: }
! 1658:
! 1659: /**
! 1660: * @brief Allows to check if there are more elements next to the
! 1661: * current element pointed by the cursor.
! 1662: *
! 1663: * @param cursor The cursor that is required to return if there are
! 1664: * next items.
! 1665: *
! 1666: * @return \ref axl_true if more items are found, otherwise \ref axl_false is
! 1667: * returned.
! 1668: */
! 1669: axl_bool axl_list_cursor_has_previous (axlListCursor * cursor)
! 1670: {
! 1671: axl_return_val_if_fail (cursor, axl_false);
! 1672:
! 1673: /* check for empty list */
! 1674: if (cursor->current == NULL)
! 1675: return axl_false;
! 1676:
! 1677: /* return if the next element isn't null */
! 1678: return (cursor->current->previous != NULL);
! 1679: }
! 1680:
! 1681: /**
! 1682: * @brief Allows to know if the current position has items.
! 1683: *
! 1684: * @param cursor The cursor that is requested to return if a call to
! 1685: * \ref axl_list_cursor_get will return data.
! 1686: *
! 1687: * @return \ref axl_true if the list that is iterated can return data at
! 1688: * the current position, otherwise \ref axl_false is returned.
! 1689: */
! 1690: axl_bool axl_list_cursor_has_item (axlListCursor * cursor)
! 1691: {
! 1692: axl_return_val_if_fail (cursor, axl_false);
! 1693:
! 1694: /* return if there are current */
! 1695: return (cursor->current != NULL);
! 1696: }
! 1697:
! 1698: /**
! 1699: * @brief Allows to remove current element pointed by the cursor,
! 1700: * maintainig internal state of the cursor.
! 1701: *
! 1702: * The function won't call to the destroy function asociated to the
! 1703: * list. If you want the item stored to be also destroyed call \ref
! 1704: * axl_list_cursor_remove.
! 1705: *
! 1706: * @param cursor The cursor pointing to the item inside the list that
! 1707: * must be removed.
! 1708: */
! 1709: void axl_list_cursor_unlink (axlListCursor * cursor)
! 1710: {
! 1711: axlListNode * node;
! 1712:
! 1713: axl_return_if_fail (cursor);
! 1714:
! 1715: /* if current cursor is pointing nowhere, just do nothing */
! 1716: if (cursor->current == NULL)
! 1717: return;
! 1718:
! 1719: /* remember node */
! 1720: node = cursor->current;
! 1721:
! 1722: /* configure the cursor to point to the next element (or the previous if the next element is null) */
! 1723: cursor->current = (node->next != NULL) ? node->next : node->previous;
! 1724:
! 1725: /* call to unlik */
! 1726: __axl_list_common_remove_selected_node (cursor->list, node, axl_false);
! 1727:
! 1728: return;
! 1729: }
! 1730:
! 1731: /**
! 1732: * @brief Allows to remove current element pointed by the cursor,
! 1733: * maintainig internal state of the cursor, calling to the destroy
! 1734: * function associated in the list.
! 1735: *
! 1736: * The function will call to the destroy function asociated to the
! 1737: * list. If you don't want the item stored to be also destroyed call \ref
! 1738: * axl_list_cursor_unlink.
! 1739: *
! 1740: * @param cursor The cursor pointing to the item inside the list that
! 1741: * must be removed.
! 1742: */
! 1743: void axl_list_cursor_remove (axlListCursor * cursor)
! 1744: {
! 1745: axlListNode * node;
! 1746:
! 1747: axl_return_if_fail (cursor);
! 1748:
! 1749: /* if current cursor is pointing nowhere, just do nothing */
! 1750: if (cursor->current == NULL)
! 1751: return;
! 1752:
! 1753: /* remember node */
! 1754: node = cursor->current;
! 1755:
! 1756: /* configure the cursor to point to the next element (or the previous if the next element is null) */
! 1757: cursor->current = (node->next != NULL) ? node->next : node->previous;
! 1758:
! 1759: /* call to remove */
! 1760: __axl_list_common_remove_selected_node (cursor->list, node, axl_true);
! 1761:
! 1762: return;
! 1763: }
! 1764:
! 1765: /**
! 1766: * @brief Allows to get current data at the current cursor state.
! 1767: *
! 1768: * @param cursor The cursor that will be used to return the data
! 1769: * located at the list, using cursor current state.
! 1770: */
! 1771: axlPointer axl_list_cursor_get (axlListCursor * cursor)
! 1772: {
! 1773: axl_return_val_if_fail (cursor, NULL);
! 1774:
! 1775: /* nothing to return if current is NULL */
! 1776: if (cursor->current == NULL)
! 1777: return NULL;
! 1778:
! 1779: /* return data */
! 1780: return cursor->current->data;
! 1781: }
! 1782:
! 1783: /**
! 1784: * @brief Allows to get the reference to the list that is associated
! 1785: * to the cursor received.
! 1786: *
! 1787: * @param cursor The cursor that is required to return the list associated.
! 1788: *
! 1789: * @return A reference to the list being iterated or NULL if fails.
! 1790: */
! 1791: axlList * axl_list_cursor_list (axlListCursor * cursor)
! 1792: {
! 1793: /* check incoming cursor */
! 1794: axl_return_val_if_fail (cursor, NULL);
! 1795:
! 1796: /* return the list */
! 1797: return cursor->list;
! 1798: }
! 1799:
! 1800: /**
! 1801: * @brief Deallocates memory used by the cursor.
! 1802: *
! 1803: * @param cursor The cursor to be deallocated.
! 1804: */
! 1805: void axl_list_cursor_free (axlListCursor * cursor)
! 1806: {
! 1807: axl_return_if_fail (cursor);
! 1808:
! 1809: /* free the cursor */
! 1810: axl_free (cursor);
! 1811:
! 1812: return;
! 1813: }
! 1814:
! 1815: /* @} */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>