Lines Matching refs:list
2 /* dbus-list.c Generic linked list utility (internal to D-Bus implementation)
26 #include "dbus-list.h"
31 * @defgroup DBusList Linked list
39 _DBUS_DEFINE_GLOBAL_LOCK (list);
42 * @defgroup DBusListInternals Linked list implementation details
59 _DBUS_LOCK (list);
67 _DBUS_UNLOCK (list);
76 _DBUS_UNLOCK (list);
88 _DBUS_UNLOCK (list);
96 _DBUS_LOCK (list);
103 _DBUS_UNLOCK (list);
107 link_before (DBusList **list,
111 if (*list == NULL)
115 *list = link;
124 if (before_this_link == *list)
125 *list = link;
130 link_after (DBusList **list,
134 if (*list == NULL)
138 *list = link;
155 _DBUS_LOCK (list);
157 _DBUS_UNLOCK (list);
171 * A node in a linked list.
173 * DBusList is a circular list; that is, the tail of the list
174 * points back to the head of the list. The empty list is
181 * Gets the next link in the list, or #NULL if
186 * link = _dbus_list_get_first_link (&list);
194 * @param list address of the list head.
203 * Gets the previous link in the list, or #NULL if
208 * link = _dbus_list_get_last_link (&list);
216 * @param list address of the list head.
223 * Allocates a linked list node. Useful for preallocating
237 * Frees a linked list node allocated with _dbus_list_alloc_link.
240 * @param link the list node
250 * Appends a value to the list. May return #FALSE
251 * if insufficient memory exists to add a list link.
254 * @param list address of the list head.
259 _dbus_list_append (DBusList **list,
262 if (!_dbus_list_prepend (list, data))
265 /* Now cycle the list forward one so the prepended node is the tail */
266 *list = (*list)->next;
272 * Prepends a value to the list. May return #FALSE
273 * if insufficient memory exists to add a list link.
276 * @param list address of the list head.
281 _dbus_list_prepend (DBusList **list,
290 link_before (list, *list, link);
296 * Appends a link to the list.
300 * @param list address of the list head.
304 _dbus_list_append_link (DBusList **list,
307 _dbus_list_prepend_link (list, link);
309 /* Now cycle the list forward one so the prepended node is the tail */
310 *list = (*list)->next;
314 * Prepends a link to the list.
318 * @param list address of the list head.
322 _dbus_list_prepend_link (DBusList **list,
325 link_before (list, *list, link);
329 * Inserts data into the list after the given existing link.
331 * @param list the list to modify
337 _dbus_list_insert_after (DBusList **list,
344 return _dbus_list_prepend (list, data);
351 link_after (list, after_this_link, link);
358 * Inserts a link into the list before the given existing link.
360 * @param list the list to modify
365 _dbus_list_insert_before_link (DBusList **list,
370 _dbus_list_append_link (list, link);
372 link_before (list, before_this_link, link);
376 * Inserts a link into the list after the given existing link.
378 * @param list the list to modify
383 _dbus_list_insert_after_link (DBusList **list,
388 _dbus_list_prepend_link (list, link);
390 link_after (list, after_this_link, link);
394 * Removes a value from the list. Only removes the
399 * @param list address of the list head.
404 _dbus_list_remove (DBusList **list,
409 link = *list;
414 _dbus_list_remove_link (list, link);
418 link = _dbus_list_get_next_link (list, link);
425 * Removes a value from the list. Only removes the
430 * @param list address of the list head.
435 _dbus_list_remove_last (DBusList **list,
440 link = _dbus_list_find_last (list, data);
443 _dbus_list_remove_link (list, link);
451 * Finds a value in the list. Returns the last link
456 * @param list address of the list head.
461 _dbus_list_find_last (DBusList **list,
466 link = _dbus_list_get_last_link (list);
473 link = _dbus_list_get_prev_link (list, link);
480 * Removes the given link from the list, but doesn't
484 * @param list the list
485 * @param link the link in the list
488 _dbus_list_unlink (DBusList **list,
493 /* one-element list */
494 *list = NULL;
501 if (*list == link)
502 *list = link->next;
510 * Removes a link from the list. This is a constant-time operation.
512 * @param list address of the list head.
513 * @param link the list link to remove.
516 _dbus_list_remove_link (DBusList **list,
519 _dbus_list_unlink (list, link);
524 * Frees all links in the list and sets the list head to #NULL. Does
528 * @param list address of the list head.
531 _dbus_list_clear (DBusList **list)
535 link = *list;
538 DBusList *next = _dbus_list_get_next_link (list, link);
545 *list = NULL;
549 * Gets the first link in the list.
552 * @param list address of the list head.
553 * @returns the first link, or #NULL for an empty list.
556 _dbus_list_get_first_link (DBusList **list)
558 return *list;
562 * Gets the last link in the list.
565 * @param list address of the list head.
566 * @returns the last link, or #NULL for an empty list.
569 _dbus_list_get_last_link (DBusList **list)
571 if (*list == NULL)
574 return (*list)->prev;
578 * Gets the last data in the list.
581 * @param list address of the list head.
582 * @returns the last data in the list, or #NULL for an empty list.
585 _dbus_list_get_last (DBusList **list)
587 if (*list == NULL)
590 return (*list)->prev->data;
594 * Gets the first data in the list.
597 * @param list address of the list head.
598 * @returns the first data in the list, or #NULL for an empty list.
601 _dbus_list_get_first (DBusList **list)
603 if (*list == NULL)
606 return (*list)->data;
610 * Removes the first link in the list and returns it. This is a
613 * @param list address of the list head.
614 * @returns the first link in the list, or #NULL for an empty list.
617 _dbus_list_pop_first_link (DBusList **list)
621 link = _dbus_list_get_first_link (list);
625 _dbus_list_unlink (list, link);
631 * Removes the first value in the list and returns it. This is a
634 * @param list address of the list head.
635 * @returns the first data in the list, or #NULL for an empty list.
638 _dbus_list_pop_first (DBusList **list)
643 link = _dbus_list_get_first_link (list);
648 _dbus_list_remove_link (list, link);
654 * Removes the last value in the list and returns it. This is a
657 * @param list address of the list head.
658 * @returns the last data in the list, or #NULL for an empty list.
661 _dbus_list_pop_last (DBusList **list)
666 link = _dbus_list_get_last_link (list);
671 _dbus_list_remove_link (list, link);
677 * Copies a list. This is a linear-time operation. If there isn't
678 * enough memory to copy the entire list, the destination list will be
681 * @param list address of the head of the list to copy.
682 * @param dest address where the copied list should be placed.
686 _dbus_list_copy (DBusList **list,
691 _dbus_assert (list != dest);
695 link = *list;
705 link = _dbus_list_get_next_link (list, link);
712 * Gets the length of a list. This is a linear-time
715 * @param list address of the head of the list
716 * @returns number of elements in the list.
719 _dbus_list_get_length (DBusList **list)
726 link = *list;
731 link = _dbus_list_get_next_link (list, link);
738 * Calls the given function for each element in the list. The
739 * function is passed the list element as its first argument, and the
742 * @param list address of the head of the list.
748 _dbus_list_foreach (DBusList **list,
754 link = *list;
757 DBusList *next = _dbus_list_get_next_link (list, link);
768 * @param list the list
772 _dbus_list_length_is_one (DBusList **list)
774 return (*list != NULL &&
775 (*list)->next == *list);
785 verify_list (DBusList **list)
790 link = *list;
798 _dbus_assert (*list == link);
810 while (link != *list);
812 _dbus_assert (length == _dbus_list_get_length (list));
815 _dbus_assert (_dbus_list_length_is_one (list));
817 _dbus_assert (!_dbus_list_length_is_one (list));
821 is_ascending_sequence (DBusList **list)
828 link = _dbus_list_get_first_link (list);
838 link = _dbus_list_get_next_link (list, link);
845 is_descending_sequence (DBusList **list)
852 link = _dbus_list_get_first_link (list);
862 link = _dbus_list_get_next_link (list, link);
869 all_even_values (DBusList **list)
873 link = _dbus_list_get_first_link (list);
881 link = _dbus_list_get_next_link (list, link);
888 all_odd_values (DBusList **list)
892 link = _dbus_list_get_first_link (list);
900 link = _dbus_list_get_next_link (list, link);
971 /* Test list clear */
1147 _dbus_assert_not_reached ("element should have been in list");
1149 _dbus_assert_not_reached ("element should have been in list");
1179 _dbus_assert_not_reached ("element should have been in list");
1181 _dbus_assert_not_reached ("element should have been in list");
1192 /* clear list using remove_link */
1253 /* Test copying a list */
1299 /* insert_after on empty list */