pfe/common/list.h

/*
 *  Copyright (c) 2011 Mindspeed Technologies, Inc.
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 2
 *  of the License, or (at your option) any later version.

 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.

 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 *
 */

/** @file
 *  Generic implementation for linked lists
 */

#ifndef _LIST_H_
#define _LIST_H_

/** @name Null terminated simple linked lists */
/**@{*/


/** Simple linked list entry.
* To keep a generic data structure in a simple linked list add a slist_entry member to the structure.
* If the generic data structure may be part of several lists at a time, then one slist_entry member is needed for each list.
*
*/
struct slist_entry
{
	struct slist_entry *next;
};


/** Simple linked list head.
* One slist_head structure exists for each list. Each list should contain a
* single type of data structures (so that the loop functions work correctly).
*
*/
struct slist_head
{
	struct slist_entry *next;
};


/** Returns the next element of a simple linked list.
*
* @param entry	pointer to a list entry
*
* @return	pointer to next list element, may be NULL
*
*/
static inline struct slist_entry *slist_next(struct slist_entry *entry)
{
	return entry->next;
}


/** Sets the next pointer on a list entry
*
* @param entry	pointer to a list entry
* @param next	next pointer value to set
*
*/
static inline void slist_set_next(struct slist_entry *entry, struct slist_entry *next)
{
	entry->next = next;
}


/** Returns the first element of a simple linked list.
*
* @param list	pointer to the list head
*
* @return	pointer to the first list element, may be NULL
*/
static inline struct slist_entry *slist_first(struct slist_head *list)
{
	return list->next;
}


/** Loops over all container data structures in a list.
*
* @param container	pointer to the container data structure type, this is the loop variable
* @param entry		pointer to a temporary list entry
* @param list		pointer to the list head
* @param member		name of the list entry member in the container data structure
*/
#define slist_for_each(container, entry, list, member)	\
	for ((entry) = slist_first(list); \
		((entry) != NULL) && ({(container) = container_of(entry, typeof(*container), member); 1;}); \
		(entry) = slist_next(&((container)->member)))


/** Loops over all container data structures in a list.
* The safe version should be used when the list entry may be removed inside the loop
*
* @param container	pointer to the container data structure type, this is the loop variable
* @param entry		pointer to a temporary list entry
* @param list		pointer to the list head
* @param member		name of the list entry member in the container data structure
*/
#define slist_for_each_safe(container, entry, list, member)	\
	for ((entry) = slist_first(list); \
		((entry) != NULL) && ({(container) = container_of(entry, typeof(*container), member); (entry) = slist_next(entry); 1;}); )


/** Loops over all entries in a list.
*
* @param entry	pointer to a list entry, this is the loop variable
* @param list	pointer to the list head
*
*/

#define slist_for_each_entry(entry, list)	\
	for ((entry) = slist_first(list); \
		(entry) != NULL; \
		(entry) = slist_next(entry))


/** Initializes the head of a simple linked list.
* Must be called once for all slist_head structures.
*
* @param list	pointer to the list head to be initialized
*
*/
static inline void slist_head_init(struct slist_head *list)
{
	list->next = NULL;
}


/** Adds one entry at the head of a simple linked list.
*
* @param list	pointer to the list head, where the entry is to be added
* @param entry	pointer to the list entry to be added to the list, must not be part of another list already
*
*/
static inline void slist_add(struct slist_head *list, struct slist_entry *entry)
{
	entry->next = list->next;
	list->next = entry;
}


/** Returns the previous entry in a simple linked list.
*
* @param list	pointer to the list head
* @param entry	pointer to the list entry
*
* @return	pointer to the previous list entry (may point to list head), if the entry is not in the list returns NULL
*/
static inline struct slist_entry *slist_prev(struct slist_head *list, struct slist_entry *entry)
{
	struct slist_entry *cur = slist_first(list);
	struct slist_entry *prev = (struct slist_entry *)list;

	while (1)
	{
		/* Entry not on the list */
		if (!cur)
			return NULL;
	
		if (cur == entry)
			break;

		prev = cur;
		cur = slist_next(cur);
	}

	return prev;
}


/** Removes the next entry in a simple linked list.
* If prev is not NULL the caller needs to make sure the next is not NULL either
*
* @param prev	pointer to the previous list entry
*
*/
static inline void slist_remove_after(struct slist_entry *prev)
{
	if (prev)
		prev->next = prev->next->next;
}

/** Removes one entry from a simple linked list.
* If the entry is not part of the list, nothing is done.
*
* @param list	pointer to the list head, from where the entry is to be removed
* @param entry	pointer to the list entry to be removed from the list
*
*/
static inline void slist_remove(struct slist_head *list, struct slist_entry *entry)
{
	struct slist_entry *prev = slist_prev(list, entry);

	slist_remove_after(prev);
}


/**@}*/


/** @name Circular double linked lists */
/**@{*/


/** Double linked list element.
* To keep a generic data structure in a double linked list add a dlist_head member to the structure.
* If the generic data structure may be part of several lists at a time, then one dlist_head member is needed for each list.
*
*/
struct dlist_head
{
	struct dlist_head *next;
	struct dlist_head *prev;
};


/** Returns the previous element of a double linked list.
*
* @param entry	pointer to a list element
*
* @return	pointer to previous list element, may be the head
*
*/
static inline struct dlist_head *dlist_prev(struct dlist_head *entry)
{
	return entry->prev;
}


/** Returns the next element of a double linked list.
*
* @param entry	pointer to a list element
*
* @return	pointer to next list element, may be the head
*
*/
static inline struct dlist_head *dlist_next(struct dlist_head *entry)
{
	return entry->next;
}


/** Returns the first element of a double linked list.
*
* @param list	pointer to the list head
*
* @return	pointer to the first list element, may be the head
*
*/
static inline struct dlist_head *dlist_first(struct dlist_head *list)
{
	return list->next;
}


/** Returns the last element of a double linked list.
*
* @param list	pointer to the list head
*
* @return	pointer to the last list element, may be the head
*
*/
static inline struct dlist_head *dlist_last(struct dlist_head *list)
{
	return list->prev;
}


/** Loops over all container data structures in a list.
*
* @param container	pointer to the container data structure type, this is the loop variable
* @param entry		pointer to a temporary list entry
* @param list		pointer to the list head
* @param member		name of the list entry member in the container data structure
*/
#define dlist_for_each(container, entry, list, member)	\
	for ((entry) = dlist_first(list); \
		((entry) != (list)) && ({(container) = container_of(entry, typeof(*container), member); 1;}); \
		(entry) = dlist_next(entry))


/** Loops over all container data structures in a list.
* The safe version should be used when the list entry may be removed inside the loop
*
* @param container	pointer to the container data structure type, this is the loop variable
* @param entry		pointer to a temporary list entry
* @param list		pointer to the list head
* @param member		name of the list entry member in the container data structure
*/
#define dlist_for_each_safe(container, entry, list, member)	\
	for ((entry) = dlist_first(list); \
		((entry) != (list)) && ({(container) = container_of(entry, typeof(*container), member); (entry) = dlist_next(entry); 1;}); )


/** Loops over all entries in a list.
*
* @param entry	pointer to a list entry, this is the loop variable
* @param list	pointer to the list head
*
*/

#define dlist_for_each_entry(entry, list)	\
	for ((entry) = dlist_first(list); \
		(entry) != (list); \
		(entry) = dlist_next(entry))

/** Initializes the head of a double linked list.
* Must be called once for all list head structures.
*
* @param list	pointer to the list head to be initialized
*
*/
static inline void dlist_head_init(struct dlist_head *list)
{
	list->next = list;
	list->prev = list;
}


/** Adds one entry at the head of a double linked list.
*
* @param list	pointer to the list head, where the entry is to be added
* @param entry	pointer to the list entry to be added to the list, must not be part of another list already
*
*/
static inline void dlist_add(struct dlist_head *list, struct dlist_head *entry)
{
	struct dlist_head *list_next = list->next;
	entry->next = list_next;
	entry->prev = list;
	list_next->prev = entry;
	list->next = entry;

}


/** Removes one entry from a double linked list.
*
* @param list	pointer to the list head, from where the entry is to be removed
* @param entry	pointer to the list entry to be removed from the list
*
*/
static inline void dlist_remove(struct dlist_head *entry)
{
	struct dlist_head *prev = entry->prev;
	struct dlist_head *next = entry->next;
	next->prev = prev;
	prev->next = next;
}

/** Checks if a double linked list is empty.
*
* @param list	pointer to the list head
*
* @return	1 if list is empty, 0 otherwise
*
*/
static inline int dlist_empty(struct dlist_head *list)
{
	return list->next == list;
}

/**@}*/
#endif /* _LIST_H_ */