/*

 * list.h

 *

 * Adapted from http://www.mcs.anl.gov/~kazutomo/list/list.h which is a

 * userspace port of the Linux kernel implementation in include/linux/list.h

 *

 * Thus licensed as GPLv2.

 *

 * Copyright (C) 2014 Seth Jennings <sjenning@redhat.com>

 *

 * 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.

 */

#ifndef _LIST_H

#define _LIST_H

/**

 * Get offset of a member

 */

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

/**

 * Casts a member of a structure out to the containing structure

 * @param ptr        the pointer to the member.

 * @param type       the type of the container struct this is embedded in.

 * @param member     the name of the member within the struct.

 *

 */

#define container_of(ptr, type, member) ({                      \

        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \

        (type *)( (char *)__mptr - offsetof(type,member) );})

/*

 * These are non-NULL pointers that will result in page faults

 * under normal circumstances, used to verify that nobody uses

 * non-initialized list entries.

 */

#define LIST_POISON1  ((void *) 0x00100100)

#define LIST_POISON2  ((void *) 0x00200200)

/**

 * Simple doubly linked list implementation.

 *

 * Some of the internal functions ("__xxx") are useful when

 * manipulating whole lists rather than single entries, as

 * sometimes we already know the next/prev entries and we can

 * generate better code by using them directly rather than

 * using the generic single-entry routines.

 */

struct list_head {

	struct list_head *next, *prev;

};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \

	struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \

	(ptr)->next = (ptr); (ptr)->prev = (ptr); \

} while (0)

/*

 * Insert a new entry between two known consecutive entries.

 *

 * This is only for internal list manipulation where we know

 * the prev/next entries already!

 */

static inline void __list_add(struct list_head *new,

			      struct list_head *prev,

			      struct list_head *next)

{

	next->prev = new;

	new->next = next;

	new->prev = prev;

	prev->next = new;

}

/**

 * list_add - add a new entry

 * @new: new entry to be added

 * @head: list head to add it after

 *

 * Insert a new entry after the specified head.

 * This is good for implementing stacks.

 */

static inline void list_add(struct list_head *new, struct list_head *head)

{

	__list_add(new, head, head->next);

}

/**

 * list_add_tail - add a new entry

 * @new: new entry to be added

 * @head: list head to add it before

 *

 * Insert a new entry before the specified head.

 * This is useful for implementing queues.

 */

static inline void list_add_tail(struct list_head *new, struct list_head *head)

{

	__list_add(new, head->prev, head);

}

/*

 * Delete a list entry by making the prev/next entries

 * point to each other.

 *

 * This is only for internal list manipulation where we know

 * the prev/next entries already!

 */

static inline void __list_del(struct list_head * prev, struct list_head * next)

{

	next->prev = prev;

	prev->next = next;

}

/**

 * list_del - deletes entry from list.

 * @entry: the element to delete from the list.

 * Note: list_empty on entry does not return true after this, the entry is

 * in an undefined state.

 */

static inline void list_del(struct list_head *entry)

{

	__list_del(entry->prev, entry->next);

	entry->next = LIST_POISON1;

	entry->prev = LIST_POISON2;

}

/**

 * list_replace - replace old entry by new one

 * @old : the element to be replaced

 * @new : the new element to insert

 *

 * If @old was empty, it will be overwritten.

 */

static inline void list_replace(struct list_head *old,

				struct list_head *new)

{

	new->next = old->next;

	new->next->prev = new;

	new->prev = old->prev;

	new->prev->next = new;

}

#define list_entry(ptr, type, member) \

	container_of(ptr, type, member)

/**

 * list_first_entry - get the first element from a list

 * @ptr:	the list head to take the element from.

 * @type:	the type of the struct this is embedded in.

 * @member:	the name of the list_struct within the struct.

 *

 * Note, that list is expected to be not empty.

 */

#define list_first_entry(ptr, type, member) \

	list_entry((ptr)->next, type, member)

/**

 * list_next_entry - get the next element in list

 * @pos:	the type * to cursor

 * @member:	the name of the list_struct within the struct.

 */

#define list_next_entry(pos, member) \

	list_entry((pos)->member.next, typeof(*(pos)), member)

/**

 * list_for_each_entry	-	iterate over list of given type

 * @pos:	the type * to use as a loop counter.

 * @head:	the head for your list.

 * @member:	the name of the list_struct within the struct.

 */

#define list_for_each_entry(pos, head, member)				\

	for (pos = list_entry((head)->next, typeof(*pos), member);	\

	     &pos->member != (head);					\

	     pos = list_entry(pos->member.next, typeof(*pos), member))

/**

 * list_for_each_entry_continue - continue iteration over list of given type

 * @pos:	the type * to use as a loop cursor.

 * @head:	the head for your list.

 * @member:	the name of the list_struct within the struct.

 *

 * Continue to iterate over list of given type, continuing after

 * the current position.

 */

#define list_for_each_entry_continue(pos, head, member) 		\

	for (pos = list_next_entry(pos, member);			\

	     &pos->member != (head);					\

	     pos = list_next_entry(pos, member))

/**

 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry

 * @pos:	the type * to use as a loop counter.

 * @n:		another type * to use as temporary storage

 * @head:	the head for your list.

 * @member:	the name of the list_struct within the struct.

 */

#define list_for_each_entry_safe(pos, n, head, member)			\

	for (pos = list_entry((head)->next, typeof(*pos), member),	\

		n = list_entry(pos->member.next, typeof(*pos), member);	\

	     &pos->member != (head); 					\

	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

#endif /* _LIST_H_ */