list.h 5.56 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
/*
 * Copyright (C) 2002 Free Software Foundation, Inc.
 * (originally part of the GNU C Library and Userspace RCU)
 * Contributed by Ulrich Drepper <drepper@redhat.com>, 2002.
 *
 * Copyright (C) 2009 Pierre-Marc Fournier
 * Conversion to RCU list.
 * Copyright (C) 2010 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, see
 * <http://www.gnu.org/licenses/>.
 */

#ifndef LIST_H
#define LIST_H	1

/*
 * The definitions of this file are adopted from those which can be
 * found in the Linux kernel headers to enable people familiar with the
 * latter find their way in these sources as well.
 */

/* Basic type for the double-link list. */
struct list_head {
	struct list_head *next, *prev;
};

39 40
/* avoid conflicts with BSD-only sys/queue.h */
#undef LIST_HEAD
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
/* Define a variable with the head and tail of the list. */
#define LIST_HEAD(name) \
	struct list_head name = { &(name), &(name) }

/* Initialize a new list head. */
#define INIT_LIST_HEAD(ptr) \
	(ptr)->next = (ptr)->prev = (ptr)

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

/* Add new element at the head of the list. */
static inline void list_add(struct list_head *newp, struct list_head *head)
{
	head->next->prev = newp;
	newp->next = head->next;
	newp->prev = head;
	head->next = newp;
}

/* Add new element at the tail of the list. */
static inline void list_add_tail(struct list_head *newp, struct list_head *head)
{
	head->prev->next = newp;
	newp->next = head;
	newp->prev = head->prev;
	head->prev = newp;
}

/* Remove element from list. */
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}

/* Remove element from list. */
static inline void list_del(struct list_head *elem)
{
	__list_del(elem->prev, elem->next);
}

/* Remove element from list, initializing the element's list pointers. */
static inline void list_del_init(struct list_head *elem)
{
	list_del(elem);
	INIT_LIST_HEAD(elem);
}

/* Delete from list, add to another list as head. */
static inline void list_move(struct list_head *elem, struct list_head *head)
{
	__list_del(elem->prev, elem->next);
	list_add(elem, head);
}

/* Replace an old entry. */
static inline void list_replace(struct list_head *old, struct list_head *newp)
{
	newp->next = old->next;
	newp->prev = old->prev;
	newp->prev->next = newp;
	newp->next->prev = newp;
}

/* Join two lists. */
static inline void list_splice(struct list_head *add, struct list_head *head)
{
	/* Do nothing if the list which gets added is empty. */
	if (add != add->next) {
		add->next->prev = head;
		add->prev->next = head->next;
		head->next->prev = add->prev;
		head->next = add->next;
	}
}

/* Get typed element from list at a given position. */
#define list_entry(ptr, type, member) \
	((type *) ((char *) (ptr) - offsetof(type, member)))

/* Get first entry from a list. */
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

/* Iterate forward over the elements of the list. */
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

/*
 * Iterate forward over the elements list. The list elements can be
 * removed from the list while doing this.
 */
#define list_for_each_safe(pos, p, head) \
	for (pos = (head)->next, p = pos->next; \
		pos != (head); \
		pos = p, p = pos->next)

/* Iterate backward over the elements of the list. */
#define list_for_each_prev(pos, head) \
	for (pos = (head)->prev; pos != (head); pos = pos->prev)

/*
 * Iterate backwards over the elements list. The list elements can be
 * removed from the list while doing this.
 */
#define list_for_each_prev_safe(pos, p, head) \
	for (pos = (head)->prev, p = pos->prev; \
		pos != (head); \
		pos = p, p = pos->prev)

static inline int list_empty(struct list_head *head)
{
	return head == head->next;
}

static inline void list_replace_init(struct list_head *old,
				     struct list_head *newp)
{
	struct list_head *head = old->next;

	list_del(old);
	list_add_tail(newp, head);
	INIT_LIST_HEAD(old);
}

166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203
/*
 * This is exactly the same as a normal list_head, except that it can be
 * declared volatile (e.g., if you have a list that may be accessed from signal
 * handlers).
 */
struct volatile_list_head {
	volatile struct volatile_list_head *next, *prev;
};

#define VOLATILE_LIST_HEAD(name) \
	volatile struct volatile_list_head name = { &(name), &(name) }

static inline void __volatile_list_del(volatile struct volatile_list_head *prev,
				       volatile struct volatile_list_head *next)
{
	next->prev = prev;
	prev->next = next;
}

static inline void volatile_list_del(volatile struct volatile_list_head *elem)
{
	__volatile_list_del(elem->prev, elem->next);
}

static inline int volatile_list_empty(volatile struct volatile_list_head *head)
{
	return head == head->next;
}

static inline void volatile_list_add(volatile struct volatile_list_head *newp,
				     volatile struct volatile_list_head *head)
{
	head->next->prev = newp;
	newp->next = head->next;
	newp->prev = head;
	head->next = newp;
}

204
#endif /* LIST_H */