src/include/gsh_list.h

/*
 * Copyright IBM Corporation, 2010
 *  Contributor: Aneesh Kumar K.v  <aneesh.kumar@linux.vnet.ibm.com>
 *
 *
 * This software is a server that implements the NFS protocol.
 *
 * This program 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 3 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
 * 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, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301 USA
 *
 * ---------------------------------------
 *
 *
 */

#ifndef _GANESHA_LIST_H
#define _GANESHA_LIST_H

#include <stddef.h>

struct glist_head {
	struct glist_head *next;
	struct glist_head *prev;
};

/*
 * @brief Compare routine that is used by glist_insert_sorted
 *
 * This routine can be defined by the calling function
 * to enable a sorted insert
 *
 * @param struct glist_head *: The first element to compare
 * @param struct glist_head *: The second element to compare
 *
 * @return  negative if the 1st element should appear before the 2nd element
 *          0 if the 1st and 2nd element are equal
 *          positive if the 1st element should appear after the 2nd element
 */
typedef int (*glist_compare) (struct glist_head *, struct glist_head *);

/**
 * @brief List head initialization
 *
 * These macros and functions are only for list heads,
 * not nodes.  The head always points to something and
 * if the list is empty, it points to itself.
 */

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

#define GLIST_HEAD(name) \
	struct glist_head name = GLIST_HEAD_INIT(name)

static inline void glist_init(struct glist_head *head)
{				/* XXX glist_init? */
	head->next = head;
	head->prev = head;
}

/* Add the new element between left and right */
static inline void __glist_add(struct glist_head *left,
			       struct glist_head *right, struct glist_head *elt)
{
	elt->prev = left;
	elt->next = right;
	left->next = elt;
	right->prev = elt;
}

static inline void glist_add_tail(struct glist_head *head,
				  struct glist_head *elt)
{

	__glist_add(head->prev, head, elt);
}

/* add after the specified entry*/
static inline void glist_add(struct glist_head *head, struct glist_head *elt)
{
	__glist_add(head, head->next, elt);
}

static inline void glist_del(struct glist_head *node)
{
	struct glist_head *left = node->prev;
	struct glist_head *right = node->next;

	if (left != NULL)
		left->next = right;
	if (right != NULL)
		right->prev = left;
	node->next = NULL;
	node->prev = NULL;
}

/**
 * @brief Test if the list in this head is empty
 */
static inline int glist_empty(struct glist_head *head)
{
	return head->next == head;
}

/**
 * @brief Test if this node is not on a list.
 *
 * NOT to be confused with glist_empty which is just
 * for heads.  We poison with NULL for disconnected nodes.
 */

static inline int glist_null(struct glist_head *head)
{
	return (head->next == NULL) && (head->prev == NULL);
}

static inline void glist_add_list_tail(struct glist_head *list,
				       struct glist_head *elt)
{
	struct glist_head *first = elt->next;
	struct glist_head *last = elt->prev;

	if (glist_empty(elt)) {
		/* nothing to add */
		return;
	}

	first->prev = list->prev;
	list->prev->next = first;

	last->next = list;
	list->prev = last;
}

/* Move all of src onto the tail of tgt.  Clears src. */
static inline void glist_splice_tail(struct glist_head *tgt,
				     struct glist_head *src)
{
	if (glist_empty(src))
		return;

	src->next->prev = tgt->prev;
	tgt->prev->next = src->next;
	src->prev->next = tgt;
	tgt->prev = src->prev;

	glist_init(src);
}

static inline void glist_swap_lists(struct glist_head *l1,
				    struct glist_head *l2)
{
	struct glist_head temp;

	if (glist_empty(l1)) {
		/* l1 was empty, so splice tail will accomplish swap. */
		glist_splice_tail(l1, l2);
		return;
	}

	if (glist_empty(l2)) {
		/* l2 was empty, so reverse splice tail will accomplish swap. */
		glist_splice_tail(l2, l1);
		return;
	}

	/* Both lists are non-empty */

	/* First swap the list pointers. */
	temp = *l1;
	*l1 = *l2;
	*l2 = temp;

	/* Then fixup first entry in each list prev to point to it's new head */
	l1->next->prev = l1;
	l2->next->prev = l2;

	/* And fixup the last entry in each list next to point to it's new head
	 */
	l1->prev->next = l1;
	l2->prev->next = l2;
}

#define glist_for_each(node, head) \
	for (node = (head)->next; node != head; node = node->next)

#define glist_for_each_next(start, node, head)				\
	for (node = (start)->next; node != head; node = node->next)

static inline size_t glist_length(struct glist_head *head)
{
	size_t length = 0;
	struct glist_head *dummy = NULL;

	glist_for_each(dummy, head) {
		++length;
	}
	return length;
}

#define container_of(addr, type, member) ({			\
	const typeof(((type *) 0)->member) * __mptr = (addr);	\
	(type *)((char *) __mptr - offsetof(type, member)); })

#define glist_first_entry(head, type, member) \
	((head)->next != (head) ? \
	container_of((head)->next, type, member) : NULL)

#define glist_entry(node, type, member) \
	container_of(node, type, member)

#define glist_for_each_safe(node, noden, head)		\
	for (node = (head)->next, noden = node->next;	\
	     node != (head);				\
	     node = noden, noden = node->next)

#define glist_for_each_next_safe(start, node, noden, head)	\
	for (node = (start)->next, noden = node->next;	\
	     node != (head);				\
	     node = noden, noden = node->next)

static inline void glist_insert_sorted(struct glist_head *head,
				       struct glist_head *elt,
				       glist_compare compare)
{
	struct glist_head *next = NULL;

	if (glist_empty(head)) {
		glist_add_tail(head, elt);
		return;
	}
	glist_for_each(next, head) {
		if (compare(next, elt) >= 0)
			break;
	}

	__glist_add(next->prev, next, elt);
}

#endif				/* _GANESHA_LIST_H */