[linux.git] / include / linux / list_bl.h

#ifndef _LINUX_LIST_BL_H
#define _LINUX_LIST_BL_H

#include <linux/list.h>
#include <linux/bit_spinlock.h>

/*
 * Special version of lists, where head of the list has a lock in the lowest
 * bit. This is useful for scalable hash tables without increasing memory
 * footprint overhead.
 *
 * For modification operations, the 0 bit of hlist_bl_head->first
 * pointer must be set.
 *
 * With some small modifications, this can easily be adapted to store several
 * arbitrary bits (not just a single lock bit), if the need arises to store
 * some fast and compact auxiliary data.
 */

#if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK)
#define LIST_BL_LOCKMASK	1UL
#else
#define LIST_BL_LOCKMASK	0UL
#endif

#ifdef CONFIG_DEBUG_LIST
#define LIST_BL_BUG_ON(x) BUG_ON(x)
#else
#define LIST_BL_BUG_ON(x)
#endif


struct hlist_bl_head {
	struct hlist_bl_node *first;
};

struct hlist_bl_node {
	struct hlist_bl_node *next, **pprev;
};
#define INIT_HLIST_BL_HEAD(ptr) \
	((ptr)->first = NULL)

static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
{
	h->next = NULL;
	h->pprev = NULL;
}

#define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member)

static inline int hlist_bl_unhashed(const struct hlist_bl_node *h)
{
	return !h->pprev;
}

static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
{
	return (struct hlist_bl_node *)
		((unsigned long)h->first & ~LIST_BL_LOCKMASK);
}

static inline void hlist_bl_set_first(struct hlist_bl_head *h,
					struct hlist_bl_node *n)
{
	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
	LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
							LIST_BL_LOCKMASK);
	h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
}

static inline int hlist_bl_empty(const struct hlist_bl_head *h)
{
	return !((unsigned long)h->first & ~LIST_BL_LOCKMASK);
}

static inline void hlist_bl_add_head(struct hlist_bl_node *n,
					struct hlist_bl_head *h)
{
	struct hlist_bl_node *first = hlist_bl_first(h);

	n->next = first;
	if (first)
		first->pprev = &n->next;
	n->pprev = &h->first;
	hlist_bl_set_first(h, n);
}

static inline void __hlist_bl_del(struct hlist_bl_node *n)
{
	struct hlist_bl_node *next = n->next;
	struct hlist_bl_node **pprev = n->pprev;

	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);

	/* pprev may be `first`, so be careful not to lose the lock bit */
	*pprev = (struct hlist_bl_node *)
			((unsigned long)next |
			 ((unsigned long)*pprev & LIST_BL_LOCKMASK));
	if (next)
		next->pprev = pprev;
}

static inline void hlist_bl_del(struct hlist_bl_node *n)
{
	__hlist_bl_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}

static inline void hlist_bl_del_init(struct hlist_bl_node *n)
{
	if (!hlist_bl_unhashed(n)) {
		__hlist_bl_del(n);
		INIT_HLIST_BL_NODE(n);
	}
}

static inline void hlist_bl_lock(struct hlist_bl_head *b)
{
	bit_spin_lock(0, (unsigned long *)b);
}

static inline void hlist_bl_unlock(struct hlist_bl_head *b)
{
	__bit_spin_unlock(0, (unsigned long *)b);
}

/**
 * hlist_bl_for_each_entry	- iterate over list of given type
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 *
 */
#define hlist_bl_for_each_entry(tpos, pos, head, member)		\
	for (pos = hlist_bl_first(head);				\
	     pos &&							\
		({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

/**
 * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
 * @n:		another &struct hlist_node to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member)	 \
	for (pos = hlist_bl_first(head);				 \
	     pos && ({ n = pos->next; 1; }) && 				 \
		({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = n)

#endif
Commit	Line	Data
4e35e607 NP	1	#ifndef _LINUX_LIST_BL_H
	2	#define _LINUX_LIST_BL_H
	3
	4	#include <linux/list.h>
1879fd6a	5	#include <linux/bit_spinlock.h>
4e35e607 NP	6
	7	/*
	8	* Special version of lists, where head of the list has a lock in the lowest
	9	* bit. This is useful for scalable hash tables without increasing memory
	10	* footprint overhead.
	11	*
	12	* For modification operations, the 0 bit of hlist_bl_head->first
	13	* pointer must be set.
	14	*
	15	* With some small modifications, this can easily be adapted to store several
	16	* arbitrary bits (not just a single lock bit), if the need arises to store
	17	* some fast and compact auxiliary data.
	18	*/
	19
32385c7c	20	#if defined(CONFIG_SMP) \|\| defined(CONFIG_DEBUG_SPINLOCK)
4e35e607 NP	21	#define LIST_BL_LOCKMASK 1UL
	22	#else
	23	#define LIST_BL_LOCKMASK 0UL
	24	#endif
	25
	26	#ifdef CONFIG_DEBUG_LIST
	27	#define LIST_BL_BUG_ON(x) BUG_ON(x)
	28	#else
	29	#define LIST_BL_BUG_ON(x)
	30	#endif
	31
	32
	33	struct hlist_bl_head {
	34	struct hlist_bl_node *first;
	35	};
	36
	37	struct hlist_bl_node {
	38	struct hlist_bl_node next, *pprev;
	39	};
	40	#define INIT_HLIST_BL_HEAD(ptr) \
	41	((ptr)->first = NULL)
	42
	43	static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
	44	{
	45	h->next = NULL;
	46	h->pprev = NULL;
	47	}
	48
	49	#define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member)
	50
	51	static inline int hlist_bl_unhashed(const struct hlist_bl_node *h)
	52	{
	53	return !h->pprev;
	54	}
	55
	56	static inline struct hlist_bl_node hlist_bl_first(struct hlist_bl_head h)
	57	{
	58	return (struct hlist_bl_node *)
	59	((unsigned long)h->first & ~LIST_BL_LOCKMASK);
	60	}
	61
	62	static inline void hlist_bl_set_first(struct hlist_bl_head *h,
	63	struct hlist_bl_node *n)
	64	{
	65	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
2c675598 NP	66	LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
2c675598 NP	67	LIST_BL_LOCKMASK);
4e35e607 NP	68	h->first = (struct hlist_bl_node *)((unsigned long)n \| LIST_BL_LOCKMASK);
	69	}
	70
	71	static inline int hlist_bl_empty(const struct hlist_bl_head *h)
	72	{
	73	return !((unsigned long)h->first & ~LIST_BL_LOCKMASK);
	74	}
	75
	76	static inline void hlist_bl_add_head(struct hlist_bl_node *n,
	77	struct hlist_bl_head *h)
	78	{
	79	struct hlist_bl_node *first = hlist_bl_first(h);
	80
	81	n->next = first;
	82	if (first)
	83	first->pprev = &n->next;
	84	n->pprev = &h->first;
	85	hlist_bl_set_first(h, n);
	86	}
	87
	88	static inline void __hlist_bl_del(struct hlist_bl_node *n)
	89	{
	90	struct hlist_bl_node *next = n->next;
	91	struct hlist_bl_node **pprev = n->pprev;
	92
	93	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
	94
	95	/* pprev may be `first`, so be careful not to lose the lock bit */
	96	pprev = (struct hlist_bl_node )
	97	((unsigned long)next \|
	98	((unsigned long)*pprev & LIST_BL_LOCKMASK));
	99	if (next)
	100	next->pprev = pprev;
	101	}
	102
	103	static inline void hlist_bl_del(struct hlist_bl_node *n)
	104	{
	105	__hlist_bl_del(n);
	106	n->next = LIST_POISON1;
	107	n->pprev = LIST_POISON2;
	108	}
	109
	110	static inline void hlist_bl_del_init(struct hlist_bl_node *n)
	111	{
	112	if (!hlist_bl_unhashed(n)) {
	113	__hlist_bl_del(n);
	114	INIT_HLIST_BL_NODE(n);
	115	}
	116	}
	117
1879fd6a CH	118	static inline void hlist_bl_lock(struct hlist_bl_head *b)
	119	{
	120	bit_spin_lock(0, (unsigned long *)b);
	121	}
	122
	123	static inline void hlist_bl_unlock(struct hlist_bl_head *b)
	124	{
	125	__bit_spin_unlock(0, (unsigned long *)b);
	126	}
	127
4e35e607 NP	128	/**
	129	* hlist_bl_for_each_entry - iterate over list of given type
	130	* @tpos: the type * to use as a loop cursor.
	131	* @pos: the &struct hlist_node to use as a loop cursor.
	132	* @head: the head for your list.
	133	* @member: the name of the hlist_node within the struct.
	134	*
	135	*/
	136	#define hlist_bl_for_each_entry(tpos, pos, head, member) \
	137	for (pos = hlist_bl_first(head); \
	138	pos && \
	139	({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
	140	pos = pos->next)
	141
	142	/**
	143	* hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry
	144	* @tpos: the type * to use as a loop cursor.
	145	* @pos: the &struct hlist_node to use as a loop cursor.
	146	* @n: another &struct hlist_node to use as temporary storage
	147	* @head: the head for your list.
	148	* @member: the name of the hlist_node within the struct.
	149	*/
	150	#define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member) \
	151	for (pos = hlist_bl_first(head); \
	152	pos && ({ n = pos->next; 1; }) && \
	153	({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \
	154	pos = n)
	155
	156	#endif