Linked list
[D-Bus secret internal implementation details]

DBusList data structure. More...

Data Structures

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

Defines

#define _dbus_list_get_next_link(list, link)   ((link)->next == *(list) ? NULL : (link)->next)
 Gets the next link in the list, or NULL if there are no more links.
#define _dbus_list_get_prev_link(list, link)   ((link) == *(list) ? NULL : (link)->prev)
 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.
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.

Define Documentation

#define _dbus_list_get_next_link ( list,
link   )     ((link)->next == *(list) ? NULL : (link)->next)

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);
   }

Parameters:
list address of the list head.
link current link.
Returns:
the next link, or NULL if none.

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

Referenced by _dbus_list_clear(), _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_address_entry_get_value(), dbus_connection_dispatch(), and dbus_parse_address().

#define _dbus_list_get_prev_link ( list,
link   )     ((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);
   }

Parameters:
list address of the list head.
link current link.
Returns:
the previous link, or NULL if none.

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

Referenced by _dbus_list_find_last(), and dbus_connection_remove_filter().

Function Documentation

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 218 of file dbus-list.c.

Referenced by _dbus_connection_new_for_transport(), _dbus_message_add_size_counter(), and _dbus_pending_call_set_timeout_error_unlocked().

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 246 of file dbus-list.c.

References _dbus_list_prepend(), FALSE, and TRUE.

Referenced by _dbus_condvar_new_at_location(), _dbus_list_copy(), _dbus_mutex_new_at_location(), _dbus_object_tree_dispatch_and_unlock(), _dbus_timeout_list_add_timeout(), _dbus_validate_signature_with_reason(), _dbus_watch_list_add_watch(), dbus_connection_add_filter(), and dbus_parse_address().

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 291 of file dbus-list.c.

References _dbus_list_prepend_link(), and next.

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

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 549 of file dbus-list.c.

References _dbus_list_get_next_link, and NULL.

Referenced by _dbus_auth_unref(), _dbus_list_copy(), _dbus_message_loader_unref(), _dbus_pending_call_set_reply_unlocked(), _dbus_timeout_list_free(), _dbus_validate_signature_with_reason(), _dbus_watch_list_free(), dbus_connection_dispatch(), and dbus_parse_address().

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, data, FALSE, NULL, and TRUE.

Referenced by dbus_connection_dispatch().

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 479 of file dbus-list.c.

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

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

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, data, and NULL.

Referenced by _dbus_message_loader_unref(), _dbus_timeout_list_free(), _dbus_timeout_list_set_functions(), _dbus_watch_list_free(), _dbus_watch_list_set_functions(), and dbus_connection_dispatch().

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 230 of file dbus-list.c.

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

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 619 of file dbus-list.c.

References NULL.

Referenced by dbus_connection_borrow_message().

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 574 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_address_entry_get_value(), dbus_connection_dispatch(), and dbus_parse_address().

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 603 of file dbus-list.c.

References NULL.

Referenced by _dbus_connection_get_message_to_send().

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 587 of file dbus-list.c.

References NULL.

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

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_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 355 of file dbus-list.c.

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

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 401 of file dbus-list.c.

References _dbus_list_prepend_link(), and NULL.

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 383 of file dbus-list.c.

References _dbus_list_append_link(), and NULL.

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.

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 656 of file dbus-list.c.

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

Referenced by _dbus_message_loader_pop_message(), and dbus_connection_steal_borrowed_message().

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 635 of file dbus-list.c.

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

Referenced by _dbus_message_loader_pop_message_link().

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 679 of file dbus-list.c.

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

Referenced by _dbus_validate_signature_with_reason().

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 268 of file dbus-list.c.

References FALSE, NULL, and TRUE.

Referenced by _dbus_list_append(), and _dbus_list_insert_after().

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 309 of file dbus-list.c.

Referenced by _dbus_connection_message_sent(), _dbus_list_append_link(), _dbus_list_insert_after_link(), and _dbus_message_loader_putback_message_link().

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 422 of file dbus-list.c.

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

Referenced by _dbus_condvar_free_at_location(), _dbus_mutex_free_at_location(), _dbus_timeout_list_remove_timeout(), and _dbus_watch_list_remove_watch().

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 453 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().

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 534 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_object_tree_dispatch_and_unlock(), and dbus_connection_remove_filter().

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 506 of file dbus-list.c.

References next, NULL, and prev.

Referenced by _dbus_connection_message_sent(), _dbus_list_pop_first_link(), _dbus_list_remove_link(), and _dbus_message_remove_size_counter().

Generated on Fri Sep 21 18:12:14 2007 for D-Bus by  doxygen 1.5.1