Double-linked list.

Data Structures
struct	m0_list_link
struct	m0_list

Macros
#define	m0_list_entry(link, type, member)   container_of(link, type, member)
#define	m0_list_for_each(head, pos)
#define	m0_list_for_each_entry(head, pos, type, member)
#define	m0_list_for_each_entry_safe(head, pos, next, type, member)
#define	m0_list_forall(var, head, ...)
#define	m0_list_entry_forall(var, head, type, member, ...)
#define	m0_list_teardown(head, pos, type, member)

Functions
struct m0_list_link	M0_XCA_DOMAIN (be)
M0_INTERNAL void	m0_list_link_init (struct m0_list_link *link)
M0_INTERNAL void	m0_list_link_fini (struct m0_list_link *link)
M0_INTERNAL bool	m0_list_link_invariant (const struct m0_list_link *link)
	M0_BASSERT (offsetof(struct m0_list, l_head)==offsetof(struct m0_list_link, ll_next))
	M0_BASSERT (offsetof(struct m0_list, l_tail)==offsetof(struct m0_list_link, ll_prev))
M0_INTERNAL void	m0_list_init (struct m0_list *head)
M0_INTERNAL void	m0_list_fini (struct m0_list *head)
M0_INTERNAL bool	m0_list_is_empty (const struct m0_list *head)
M0_INTERNAL bool	m0_list_contains (const struct m0_list *list, const struct m0_list_link *link)
M0_INTERNAL bool	m0_list_invariant (const struct m0_list *list)
M0_INTERNAL size_t	m0_list_length (const struct m0_list *list)
M0_INTERNAL void	m0_list_add (struct m0_list *head, struct m0_list_link *next)
M0_INTERNAL void	m0_list_add_tail (struct m0_list *head, struct m0_list_link *next)
M0_INTERNAL void	m0_list_add_after (struct m0_list_link *anchor, struct m0_list_link *next)
M0_INTERNAL void	m0_list_add_before (struct m0_list_link *anchor, struct m0_list_link *next)
M0_INTERNAL void	m0_list_del (struct m0_list_link *old)
M0_INTERNAL void	m0_list_move (struct m0_list *head, struct m0_list_link *next)
M0_INTERNAL void	m0_list_move_tail (struct m0_list *head, struct m0_list_link *next)
static struct m0_list_link *	m0_list_first (const struct m0_list *head)
M0_INTERNAL bool	m0_list_link_is_in (const struct m0_list_link *link)
M0_INTERNAL bool	m0_list_link_is_last (const struct m0_list_link *link, const struct m0_list *head)

Detailed Description

Macro Definition Documentation

m0_list_entry

#define m0_list_entry	(		link,
			type,
			member
	)		container_of(link, type, member)

get pointer to object from pointer to list link entry

Definition at line 217 of file list.h.

m0_list_entry_forall

#define m0_list_entry_forall	(		var,
			head,
			type,
			member,
			...
	)

Value:

({                                                                      \
        type *var;                                                      \
        type *next;                                                     \
									\
	m0_list_for_each_entry_safe(head, var, next, type, member) {   \
                if (!({ __VA_ARGS__ ; }))                               \
                    break;                                              \
        }                                                               \
        &var->member == (void *)head;                                   \
})

Returns a conjunction (logical AND) of an expression evaluated for each list element.

Declares a pointer variable named "var", in a new scope and evaluates user-supplied expression (the last argument) with "var" iterated over successive list elements, while this expression returns true. Returns true iff the whole list was iterated over.

The list can be modified by the user-supplied expression.

This function is useful for invariant checking.

bool foo_invariant(const struct foo *f)
{
        return m0_list_entry_forall(b, &f->f_bars, struct bar, b_linkage,
                                    b->b_count > 0 && b->b_parent == f);
}

See also

m0_tlist_forall(), m0_tl_forall(), m0_list_forall(), m0_forall().

Definition at line 313 of file list.h.

m0_list_for_each

#define m0_list_for_each	(		head,
			pos
	)

Value:

for (pos = (head)->l_head; pos != (void *)(head); \
             pos = (pos)->ll_next)

Iterates over a list

Parameters

head	the head of list.
pos	the pointer to list_link to use as a loop counter.

Definition at line 226 of file list.h.

m0_list_for_each_entry

#define m0_list_for_each_entry	(		head,
			pos,
			type,
			member
	)

Value:

for (pos = m0_list_entry((head)->l_head, type, member); \
             &(pos->member) != (void *)head; \
             pos = m0_list_entry((pos)->member.ll_next, type, member))

Read-only iterates over a "typed" list.

The loop body is not allowed to modify the list.

Definition at line 235 of file list.h.

m0_list_for_each_entry_safe

#define m0_list_for_each_entry_safe	(		head,
			pos,
			next,
			type,
			member
	)

Value:

for (pos = m0_list_entry((head)->l_head, type, member),         \
             next = m0_list_entry((pos)->member.ll_next, type, member); \
             &(pos)->member != (void *)head;                            \
             pos = next,                                                \
             next = m0_list_entry((next)->member.ll_next, type, member))

Iterates over a "typed" list safely: the loop body is allowed to remove the current element.

Parameters

head	the head of list.
pos	the pointer to list_link to use as a loop counter.

Definition at line 247 of file list.h.

m0_list_forall

#define m0_list_forall	(		var,
			head,
			...
	)

Value:

({                                              \
        struct m0_list_link *var;               \
						\
	m0_list_for_each(head, var) {          \
                if (!({ __VA_ARGS__ ; }))       \
                    break;                      \
        }                                       \
        var == (void *)head;                    \
})

Returns a conjunction (logical AND) of an expression evaluated for each list element.

Declares a struct m0_list_link pointer variable named "var" in a new scope and evaluates user-supplied expression (the last argument) with "var" iterated over successive list elements, while this expression returns true. Returns true iff the whole list was iterated over.

The list can not be modified by the user-supplied expression.

This function is useful for invariant checking.

bool foo_invariant(const struct foo *f)
{
        return m0_list_forall(bar, &f->f_bars,
                              bar_is_valid(container_of(bar, struct bar,
                                           b_linkage)));
}

See also

m0_tlist_forall(), m0_tl_forall(),

m0_forall(), m0_list_entry_forall().

Definition at line 279 of file list.h.

m0_list_teardown

#define m0_list_teardown	(		head,
			pos,
			type,
			member
	)

Value:

while (!m0_list_is_empty((head)) && \
         ((pos) = m0_list_entry((head)->l_head, type, member)) && \
         (m0_list_del(&(pos)->member), true))

Empties the list by taking its elements to and removing them one after another starting from head.

Parameters

head	of list.
pos	current list element.
type	containing m0_list_link .
member	field name at the .

Definition at line 334 of file list.h.

Function Documentation

M0_BASSERT() [1/2]

M0_BASSERT

(

offsetof(struct m0_list, l_head)

= =offsetof(struct m0_list_link, ll_next)

)

M0_BASSERT() [2/2]

M0_BASSERT

(

offsetof(struct m0_list, l_tail)

= =offsetof(struct m0_list_link, ll_prev)

)

m0_list_add()

M0_INTERNAL void m0_list_add	(	struct m0_list *	head,
		struct m0_list_link *	next
	)

add list to top on the list

This function can be called on an uninitialised link. All fields are overwritten.

Parameters

head	pointer to list head
next	pointer to list entry

Definition at line 113 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_add_after()

M0_INTERNAL void m0_list_add_after	(	struct m0_list_link *	anchor,
		struct m0_list_link *	next
	)

Adds an element to the list right after the specified element.

This function can be called on an uninitialised link. All fields are overwritten.

Definition at line 126 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_add_before()

M0_INTERNAL void m0_list_add_before	(	struct m0_list_link *	anchor,
		struct m0_list_link *	next
	)

Adds an element to the list right before the specified element.

This function can be called on an uninitialised link. All fields are overwritten.

Definition at line 133 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_add_tail()

M0_INTERNAL void m0_list_add_tail	(	struct m0_list *	head,
		struct m0_list_link *	next
	)

add list to tail on the list

This function can be called on an uninitialised link. All fields are overwritten.

Parameters

head	pointer to list head
next	pointer to list entry

Definition at line 119 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_contains()

M0_INTERNAL bool m0_list_contains	(	const struct m0_list *	list,
		const struct m0_list_link *	link
	)

Returns true iff in .

Definition at line 87 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_del()

M0_INTERNAL void m0_list_del

(

struct m0_list_link *

old

)

Deletes an entry from the list and re-initializes the entry.

Definition at line 147 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_fini()

M0_INTERNAL void m0_list_fini

(

struct m0_list *

head

)

Finalizes the list.

Definition at line 36 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_first()

static struct m0_list_link* m0_list_first ( const struct m0_list *  head )

inlinestatic

return first entry from the list

Parameters

head	pointer to list head

Returns

pointer to first list entry or NULL if list empty

Definition at line 191 of file list.h.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_init()

M0_INTERNAL void m0_list_init

(

struct m0_list *

head

)

Initializes list head.

Definition at line 29 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_invariant()

M0_INTERNAL bool m0_list_invariant

(

const struct m0_list *

list

)

This function iterate over the argument list checking that double-linked list invariant holds (x->ll_prev->ll_next == x && x->ll_next->ll_prev == x).

Returns

true iff isn't corrupted

Definition at line 70 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_is_empty()

M0_INTERNAL bool m0_list_is_empty

(

const struct m0_list *

head

)

check list is empty

Parameters

head	pointer to list head

Definition at line 42 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_length()

M0_INTERNAL size_t m0_list_length

(

const struct m0_list *

list

)

Definition at line 75 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_link_fini()

M0_INTERNAL void m0_list_link_fini

(

struct m0_list_link *

link

)

free resources associated with link entry

Parameters

link	- pointer to link enty

Definition at line 176 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_link_init()

M0_INTERNAL void m0_list_link_init

(

struct m0_list_link *

link

)

initialize list link entry

It is not necessary to call this function if the first operation on the link is any of m0_list_add*() functions.

Parameters

link	- pointer to link enty

Definition at line 169 of file list.c.

Here is the caller graph for this function:

m0_list_link_invariant()

M0_INTERNAL bool m0_list_link_invariant

(

const struct m0_list_link *

link

)

Definition at line 48 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_link_is_in()

M0_INTERNAL bool m0_list_link_is_in

(

const struct m0_list_link *

link

)

is link entry connected to the list

Parameters

link	- pointer to link entry

Return values

true	- entry connected to a list
false	- entry disconnected from a list

Definition at line 181 of file list.c.

Here is the caller graph for this function:

m0_list_link_is_last()

M0_INTERNAL bool m0_list_link_is_last	(	const struct m0_list_link *	link,
		const struct m0_list *	head
	)

Definition at line 186 of file list.c.

Here is the call graph for this function:

m0_list_move()

M0_INTERNAL void m0_list_move	(	struct m0_list *	head,
		struct m0_list_link *	next
	)

Moves an entry to head of the list.

Definition at line 154 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_list_move_tail()

M0_INTERNAL void m0_list_move_tail	(	struct m0_list *	head,
		struct m0_list_link *	next
	)

Moves an entry to tail of the list.

Definition at line 161 of file list.c.

Here is the call graph for this function:

Here is the caller graph for this function:

M0_XCA_DOMAIN()

struct m0_list_link M0_XCA_DOMAIN

(

be

)