Linked list
D-Bus secret internal implementation details

DBusList data structure. More...

## Data Structures

struct | DBusList
| A node in a linked list. More...

## Macros

#define | _dbus_list_get_next_link(list, link)
| Gets the next link in the list, or NULL if there are no more links.
#define | _dbus_list_get_prev_link(list, link)
| Gets the previous link in the list, or NULL if there are no more links.

## Functions

DBusList * | _dbus_list_alloc_link (void *data)
| Allocates a linked list node.
void | _dbus_list_free_link (DBusList *link)
| Frees a linked list node allocated with _dbus_list_alloc_link.
dbus_bool_t | _dbus_list_append (DBusList **list, void *data)
| Appends a value to the list.
dbus_bool_t | _dbus_list_prepend (DBusList **list, void *data)
| Prepends a value to the list.
void | _dbus_list_append_link (DBusList **list, DBusList *link)
| Appends a link to the list.
void | _dbus_list_prepend_link (DBusList **list, DBusList *link)
| Prepends a link to the list.
dbus_bool_t | _dbus_list_insert_after (DBusList **list, DBusList *after_this_link, void *data)
| Inserts data into the list after the given existing link.
void | _dbus_list_insert_before_link (DBusList **list, DBusList *before_this_link, DBusList *link)
| Inserts a link into the list before the given existing link.
void | _dbus_list_insert_after_link (DBusList **list, DBusList *after_this_link, DBusList *link)
| Inserts a link into the list after the given existing link.
dbus_bool_t | _dbus_list_remove (DBusList **list, void *data)
| Removes a value from the list.
dbus_bool_t | _dbus_list_remove_last (DBusList **list, void *data)
| Removes a value from the list.
DBusList * | _dbus_list_find_last (DBusList **list, void *data)
| Finds a value in the list.
void | _dbus_list_unlink (DBusList **list, DBusList *link)
| Removes the given link from the list, but doesn't free it.
void | _dbus_list_remove_link (DBusList **list, DBusList *link)
| Removes a link from the list.
void | _dbus_list_clear (DBusList **list)
| Frees all links in the list and sets the list head to NULL.
void | _dbus_list_clear_full (DBusList **list, DBusFreeFunction function)
| Free every link and every element in the list.
DBusList * | _dbus_list_get_first_link (DBusList **list)
| Gets the first link in the list.
DBusList * | _dbus_list_get_last_link (DBusList **list)
| Gets the last link in the list.
void * | _dbus_list_get_last (DBusList **list)
| Gets the last data in the list.
void * | _dbus_list_get_first (DBusList **list)
| Gets the first data in the list.
DBusList * | _dbus_list_pop_first_link (DBusList **list)
| Removes the first link in the list and returns it.
void * | _dbus_list_pop_first (DBusList **list)
| Removes the first value in the list and returns it.
void * | _dbus_list_pop_last (DBusList **list)
| Removes the last value in the list and returns it.
dbus_bool_t | _dbus_list_copy (DBusList **list, DBusList **dest)
| Copies a list.
int | _dbus_list_get_length (DBusList **list)
| Gets the length of a list.
void | _dbus_list_foreach (DBusList **list, DBusForeachFunction function, void *data)
| Calls the given function for each element in the list.
dbus_bool_t | _dbus_list_length_is_one (DBusList **list)
| Check whether length is exactly one.

## Detailed Description

DBusList data structure.

Types and functions related to DBusList.

## Macro Definition Documentation

## _dbus_list_get_next_link

#define _dbus_list_get_next_link | ( |  | list,
|  |  | link )

Value:
((link)->next == *(list) ? NULL : (link)->next)
NULL
#define NULL
A null pointer, defined appropriately for C or C++.
Definition dbus-macros.h:51

Gets the next link in the list, or NULL if there are no more links.

Used for iteration.

DBusList *link;
link = _dbus_list_get_first_link (&list);
while (link != NULL)
{
printf ("value is %p\n", link->data);
link = _dbus_list_get_next_link (&link);
}
_dbus_list_get_first_link
DBusList * _dbus_list_get_first_link(DBusList **list)
Gets the first link in the list.
Definition dbus-list.c:597
_dbus_list_get_next_link
#define _dbus_list_get_next_link(list, link)
Gets the next link in the list, or NULL if there are no more links.
Definition dbus-list.h:121
DBusList
A node in a linked list.
Definition dbus-list.h:37
DBusList::data
void * data
Data stored at this element.
Definition dbus-list.h:40

Parameters

  list | address of the list head.
  link | current link.

Returns
  the next link, or NULL if none.

Definition at line 121 of file dbus-list.h.

Referenced by _dbus_list_clear(), _dbus_list_clear_full(), _dbus_list_copy(), _dbus_list_foreach(), _dbus_list_get_length(), _dbus_list_remove(), _dbus_object_tree_dispatch_and_unlock(), _dbus_timeout_list_set_functions(), _dbus_watch_list_set_functions(), _dbus_watch_list_toggle_all_watches(), dbus_address_entry_get_value(), dbus_connection_dispatch(), and dbus_parse_address().

## _dbus_list_get_prev_link

#define _dbus_list_get_prev_link | ( |  | list,
|  |  | link )

Value:
((link) == *(list) ? NULL : (link)->prev)

Gets the previous link in the list, or NULL if there are no more links.

Used for iteration.

DBusList *link;
link = _dbus_list_get_last_link (&list);
while (link != NULL)
{
printf ("value is %p\n", link->data);
link = _dbus_list_get_prev_link (&link);
}
_dbus_list_get_last_link
DBusList * _dbus_list_get_last_link(DBusList **list)
Gets the last link in the list.
Definition dbus-list.c:610
_dbus_list_get_prev_link
#define _dbus_list_get_prev_link(list, link)
Gets the previous link in the list, or NULL if there are no more links.
Definition dbus-list.h:122

Parameters

  list | address of the list head.
  link | current link.

Returns
  the previous link, or NULL if none.

Definition at line 122 of file dbus-list.h.

Referenced by _dbus_list_find_last(), and dbus_connection_remove_filter().

## Function Documentation

## _dbus_list_alloc_link()

DBusList * _dbus_list_alloc_link | ( | void * | data | ) |

Allocates a linked list node.

Useful for preallocating nodes and using _dbus_list_append_link() to avoid allocations.

Parameters

  data | the value to store in the link.

Returns
  a newly allocated link.

Definition at line 245 of file dbus-list.c.

Referenced by _dbus_connection_new_for_transport(), _dbus_message_add_counter(), _dbus_pending_call_set_timeout_error_unlocked(), and dbus_connection_dispatch().

## _dbus_list_append()

dbus_bool_t _dbus_list_append | ( | DBusList ** | list,
|  | void * | data )

Appends a value to the list.

May return FALSE if insufficient memory exists to add a list link. This is a constant-time operation.

Parameters

  list | address of the list head.
  data | the value to append.

Returns
  TRUE on success.

Definition at line 273 of file dbus-list.c.

References _dbus_list_prepend(), FALSE, DBusList::next, and TRUE.

Referenced by _dbus_list_copy(), _dbus_listen_tcp_socket(), _dbus_object_tree_dispatch_and_unlock(), _dbus_set_up_transient_session_servicedirs(), _dbus_split_paths_and_append(), _dbus_timeout_list_add_timeout(), _dbus_validate_signature_with_reason(), _dbus_watch_list_add_watch(), dbus_connection_add_filter(), and dbus_parse_address().

## _dbus_list_append_link()

void _dbus_list_append_link | ( | DBusList ** | list,
|  | DBusList * | link )

Appends a link to the list.

Cannot fail due to out of memory. This is a constant-time operation.

Parameters

  list | address of the list head.
  link | the link to append.

Definition at line 318 of file dbus-list.c.

References _dbus_list_prepend_link(), and DBusList::next.

Referenced by _dbus_connection_queue_received_message_link(), _dbus_connection_queue_synthesized_message_link(), _dbus_list_insert_before_link(), and _dbus_message_add_counter_link().

## _dbus_list_clear()

void _dbus_list_clear | ( | DBusList ** | list | ) |

Frees all links in the list and sets the list head to NULL.

Does not free the data in each link, for obvious reasons. This is a linear-time operation.

Parameters

  list | address of the list head.

Definition at line 545 of file dbus-list.c.

References _dbus_list_get_next_link, and NULL.

Referenced by _dbus_auth_unref(), _dbus_list_copy(), _dbus_pending_call_set_reply_unlocked(), _dbus_validate_signature_with_reason(), and dbus_parse_address().

## _dbus_list_clear_full()

void _dbus_list_clear_full | ( | DBusList ** | list,
|  | DBusFreeFunction | function )

Free every link and every element in the list.

Parameters

  list | address of the head of the list.
  function | free-function to call for each element.

Definition at line 570 of file dbus-list.c.

References _dbus_list_get_next_link, DBusList::data, and NULL.

Referenced by _dbus_message_loader_unref(), _dbus_split_paths_and_append(), _dbus_timeout_list_free(), _dbus_watch_list_free(), and dbus_connection_dispatch().

## _dbus_list_copy()

dbus_bool_t _dbus_list_copy | ( | DBusList ** | list,
|  | DBusList ** | dest )

Copies a list.

This is a linear-time operation. If there isn't enough memory to copy the entire list, the destination list will be set to NULL.

Parameters

  list | address of the head of the list to copy.
  dest | address where the copied list should be placed.

Returns
  TRUE on success, FALSE if not enough memory.

Definition at line 727 of file dbus-list.c.

References _dbus_assert, _dbus_list_append(), _dbus_list_clear(), _dbus_list_get_next_link, DBusList::data, FALSE, NULL, and TRUE.

Referenced by dbus_connection_dispatch().

## _dbus_list_find_last()

DBusList * _dbus_list_find_last | ( | DBusList ** | list,
|  | void * | data )

Finds a value in the list.

Returns the last link with value equal to the given data pointer. This is a linear-time operation. Returns NULL if no value found that matches.

Parameters

  list | address of the list head.
  data | the value to find.

Returns
  the link if found

Definition at line 475 of file dbus-list.c.

References _dbus_list_get_last_link(), _dbus_list_get_prev_link, DBusList::data, and NULL.

Referenced by _dbus_list_remove_last(), _dbus_message_loader_queue_messages(), and _dbus_message_remove_counter().

## _dbus_list_foreach()

void _dbus_list_foreach | ( | DBusList ** | list,
|  | DBusForeachFunction | function,
|  | void * | data )

Calls the given function for each element in the list.

The function is passed the list element as its first argument, and the given data as its second argument.

Parameters

  list | address of the head of the list.
  function | function to call for each element.
  data | extra data for the function.

Definition at line 789 of file dbus-list.c.

References _dbus_list_get_next_link, DBusList::data, and NULL.

Referenced by _dbus_timeout_list_set_functions(), and _dbus_watch_list_set_functions().

## _dbus_list_free_link()

void _dbus_list_free_link | ( | DBusList * | link | ) |

Frees a linked list node allocated with _dbus_list_alloc_link.

Does not free the data in the node.

Parameters

  link | the list node

Definition at line 257 of file dbus-list.c.

Referenced by _dbus_connection_new_for_transport(), _dbus_connection_unlock(), dbus_connection_dispatch(), and dbus_connection_free_preallocated_send().

## _dbus_list_get_first()

void * _dbus_list_get_first | ( | DBusList ** | list | ) |

Gets the first data in the list.

This is a constant-time operation.

Parameters

  list | address of the list head.

Returns
  the first data in the list, or NULL for an empty list.

Definition at line 642 of file dbus-list.c.

References NULL.

Referenced by dbus_connection_borrow_message().

## _dbus_list_get_first_link()

DBusList * _dbus_list_get_first_link | ( | DBusList ** | list | ) |

Gets the first link in the list.

This is a constant-time operation.

Parameters

  list | address of the list head.

Returns
  the first link, or NULL for an empty list.

Definition at line 597 of file dbus-list.c.

Referenced by _dbus_list_pop_first(), _dbus_list_pop_first_link(), _dbus_object_tree_dispatch_and_unlock(), _dbus_timeout_list_set_functions(), _dbus_watch_list_set_functions(), _dbus_watch_list_toggle_all_watches(), dbus_address_entry_get_value(), dbus_connection_dispatch(), and dbus_parse_address().

## _dbus_list_get_last()

void * _dbus_list_get_last | ( | DBusList ** | list | ) |

Gets the last data in the list.

This is a constant-time operation.

Parameters

  list | address of the list head.

Returns
  the last data in the list, or NULL for an empty list.

Definition at line 626 of file dbus-list.c.

References NULL.

Referenced by _dbus_connection_get_message_to_send().

## _dbus_list_get_last_link()

DBusList * _dbus_list_get_last_link | ( | DBusList ** | list | ) |

Gets the last link in the list.

This is a constant-time operation.

Parameters

  list | address of the list head.

Returns
  the last link, or NULL for an empty list.

Definition at line 610 of file dbus-list.c.

References NULL.

Referenced by _dbus_connection_message_sent_unlocked(), _dbus_list_find_last(), _dbus_list_pop_last(), and dbus_connection_remove_filter().

## _dbus_list_get_length()

int _dbus_list_get_length | ( | DBusList ** | list | ) |

Gets the length of a list.

This is a linear-time operation.

Parameters

  list | address of the head of the list

Returns
  number of elements in the list.

Definition at line 760 of file dbus-list.c.

References _dbus_list_get_next_link, and NULL.

Referenced by _dbus_object_tree_dispatch_and_unlock(), and dbus_parse_address().

## _dbus_list_insert_after()

dbus_bool_t _dbus_list_insert_after | ( | DBusList ** | list,
|  | DBusList * | after_this_link,
|  | void * | data )

Inserts data into the list after the given existing link.

Parameters

  list | the list to modify
  after_this_link | existing link to insert after, or NULL to prepend
  data | the value to insert

Returns
  TRUE on success, FALSE if memory allocation fails

Definition at line 351 of file dbus-list.c.

References _dbus_list_prepend(), FALSE, NULL, and TRUE.

## _dbus_list_insert_after_link()

void _dbus_list_insert_after_link | ( | DBusList ** | list,
|  | DBusList * | after_this_link,
|  | DBusList * | link )

Inserts a link into the list after the given existing link.

Parameters

  list | the list to modify
  after_this_link | existing link to insert after, or NULL to prepend
  link | the link to insert

Definition at line 397 of file dbus-list.c.

References _dbus_list_prepend_link(), and NULL.

## _dbus_list_insert_before_link()

void _dbus_list_insert_before_link | ( | DBusList ** | list,
|  | DBusList * | before_this_link,
|  | DBusList * | link )

Inserts a link into the list before the given existing link.

Parameters

  list | the list to modify
  before_this_link | existing link to insert before, or NULL to append
  link | the link to insert

Definition at line 379 of file dbus-list.c.

References _dbus_list_append_link(), and NULL.

## _dbus_list_length_is_one()

dbus_bool_t _dbus_list_length_is_one | ( | DBusList ** | list | ) |

Check whether length is exactly one.

Parameters

  list | the list

Returns
  TRUE if length is exactly one

Definition at line 813 of file dbus-list.c.

References NULL.

## _dbus_list_pop_first()

void * _dbus_list_pop_first | ( | DBusList ** | list | ) |

Removes the first value in the list and returns it.

This is a constant-time operation.

Parameters

  list | address of the list head.

Returns
  the first data in the list, or NULL for an empty list.

Definition at line 679 of file dbus-list.c.

References _dbus_list_get_first_link(), _dbus_list_remove_link(), DBusList::data, and NULL.

Referenced by _dbus_listen_tcp_socket(), _dbus_message_loader_pop_message(), and dbus_connection_steal_borrowed_message().

## _dbus_list_pop_first_link()

DBusList * _dbus_list_pop_first_link | ( | DBusList ** | list | ) |

Removes the first link in the list and returns it.

This is a constant-time operation.

Parameters

  list | address of the list head.

Returns
  the first link in the list, or NULL for an empty list.

Definition at line 658 of file dbus-list.c.

References _dbus_list_get_first_link(), _dbus_list_unlink(), and NULL.

Referenced by _dbus_connection_unlock(), and _dbus_message_loader_pop_message_link().

## _dbus_list_pop_last()

void * _dbus_list_pop_last | ( | DBusList ** | list | ) |

Removes the last value in the list and returns it.

This is a constant-time operation.

Parameters

  list | address of the list head.

Returns
  the last data in the list, or NULL for an empty list.

Definition at line 702 of file dbus-list.c.

References _dbus_list_get_last_link(), _dbus_list_remove_link(), DBusList::data, and NULL.

Referenced by _dbus_validate_signature_with_reason().

## _dbus_list_prepend()

dbus_bool_t _dbus_list_prepend | ( | DBusList ** | list,
|  | void * | data )

Prepends a value to the list.

May return FALSE if insufficient memory exists to add a list link. This is a constant-time operation.

Parameters

  list | address of the list head.
  data | the value to prepend.

Returns
  TRUE on success.

Definition at line 295 of file dbus-list.c.

References FALSE, NULL, and TRUE.

Referenced by _dbus_list_append(), and _dbus_list_insert_after().

## _dbus_list_prepend_link()

void _dbus_list_prepend_link | ( | DBusList ** | list,
|  | DBusList * | link )

Prepends a link to the list.

Cannot fail due to out of memory. This is a constant-time operation.

Parameters

  list | address of the list head.
  link | the link to prepend.

Definition at line 336 of file dbus-list.c.

Referenced by _dbus_connection_message_sent_unlocked(), _dbus_list_append_link(), _dbus_list_insert_after_link(), _dbus_message_loader_putback_message_link(), and dbus_connection_dispatch().

## _dbus_list_remove()

dbus_bool_t _dbus_list_remove | ( | DBusList ** | list,
|  | void * | data )

Removes a value from the list.

Only removes the first value equal to the given data pointer, even if multiple values exist which match. This is a linear-time operation.

Parameters

  list | address of the list head.
  data | the value to remove.

Returns
  TRUE if a value was found to remove.

Definition at line 418 of file dbus-list.c.

References _dbus_list_get_next_link, _dbus_list_remove_link(), DBusList::data, FALSE, NULL, and TRUE.

Referenced by _dbus_timeout_list_remove_timeout(), and _dbus_watch_list_remove_watch().

## _dbus_list_remove_last()

dbus_bool_t _dbus_list_remove_last | ( | DBusList ** | list,
|  | void * | data )

Removes a value from the list.

Only removes the last value equal to the given data pointer, even if multiple values exist which match. This is a linear-time operation.

Parameters

  list | address of the list head.
  data | the value to remove.

Returns
  TRUE if a value was found to remove.

Definition at line 449 of file dbus-list.c.

References _dbus_list_find_last(), _dbus_list_remove_link(), FALSE, and TRUE.

Referenced by _dbus_timeout_list_add_timeout(), and _dbus_watch_list_add_watch().

## _dbus_list_remove_link()

void _dbus_list_remove_link | ( | DBusList ** | list,
|  | DBusList * | link )

Removes a link from the list.

This is a constant-time operation.

Parameters

  list | address of the list head.
  link | the list link to remove.

Definition at line 530 of file dbus-list.c.

References _dbus_list_unlink().

Referenced by _dbus_list_pop_first(), _dbus_list_pop_last(), _dbus_list_remove(), _dbus_list_remove_last(), _dbus_message_remove_counter(), _dbus_object_tree_dispatch_and_unlock(), and dbus_connection_remove_filter().

## _dbus_list_unlink()

void _dbus_list_unlink | ( | DBusList ** | list,
|  | DBusList * | link )

Removes the given link from the list, but doesn't free it.

_dbus_list_remove_link() both removes the link and also frees it.

Parameters

  list | the list
  link | the link in the list

Definition at line 502 of file dbus-list.c.

References DBusList::next, NULL, and DBusList::prev.

Referenced by _dbus_connection_message_sent_unlocked(), _dbus_list_pop_first_link(), and _dbus_list_remove_link().