[GitHub/mt8127/android_kernel_alcatel_ttab.git] / include / linux / prio_tree.h

#ifndef _LINUX_PRIO_TREE_H
#define _LINUX_PRIO_TREE_H

/*
 * K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct
 * fields with identical types should end up at the same location. We'll use
 * this until we can scrap struct raw_prio_tree_node.
 *
 * Note: all this could be done more elegantly by using unnamed union/struct
 * fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this
 * language extension.
 */

struct raw_prio_tree_node {
	struct prio_tree_node	*left;
	struct prio_tree_node	*right;
	struct prio_tree_node	*parent;
};

struct prio_tree_node {
	struct prio_tree_node	*left;
	struct prio_tree_node	*right;
	struct prio_tree_node	*parent;
	unsigned long		start;
	unsigned long		last;	/* last location _in_ interval */
};

struct prio_tree_root {
	struct prio_tree_node	*prio_tree_node;
	unsigned short 		index_bits;
	unsigned short		raw;
		/*
		 * 0: nodes are of type struct prio_tree_node
		 * 1: nodes are of type raw_prio_tree_node
		 */
};

struct prio_tree_iter {
	struct prio_tree_node	*cur;
	unsigned long		mask;
	unsigned long		value;
	int			size_level;

	struct prio_tree_root	*root;
	pgoff_t			r_index;
	pgoff_t			h_index;
};

static inline void prio_tree_iter_init(struct prio_tree_iter *iter,
		struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index)
{
	iter->root = root;
	iter->r_index = r_index;
	iter->h_index = h_index;
	iter->cur = NULL;
}

#define __INIT_PRIO_TREE_ROOT(ptr, _raw)	\
do {					\
	(ptr)->prio_tree_node = NULL;	\
	(ptr)->index_bits = 1;		\
	(ptr)->raw = (_raw);		\
} while (0)

#define INIT_PRIO_TREE_ROOT(ptr)	__INIT_PRIO_TREE_ROOT(ptr, 0)
#define INIT_RAW_PRIO_TREE_ROOT(ptr)	__INIT_PRIO_TREE_ROOT(ptr, 1)

#define INIT_PRIO_TREE_NODE(ptr)				\
do {								\
	(ptr)->left = (ptr)->right = (ptr)->parent = (ptr);	\
} while (0)

#define INIT_PRIO_TREE_ITER(ptr)	\
do {					\
	(ptr)->cur = NULL;		\
	(ptr)->mask = 0UL;		\
	(ptr)->value = 0UL;		\
	(ptr)->size_level = 0;		\
} while (0)

#define prio_tree_entry(ptr, type, member) \
       ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

static inline int prio_tree_empty(const struct prio_tree_root *root)
{
	return root->prio_tree_node == NULL;
}

static inline int prio_tree_root(const struct prio_tree_node *node)
{
	return node->parent == node;
}

static inline int prio_tree_left_empty(const struct prio_tree_node *node)
{
	return node->left == node;
}

static inline int prio_tree_right_empty(const struct prio_tree_node *node)
{
	return node->right == node;
}


struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
                struct prio_tree_node *old, struct prio_tree_node *node);
struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
                struct prio_tree_node *node);
void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node);
struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter);

#define raw_prio_tree_replace(root, old, node) \
	prio_tree_replace(root, (struct prio_tree_node *) (old), \
	    (struct prio_tree_node *) (node))
#define raw_prio_tree_insert(root, node) \
	prio_tree_insert(root, (struct prio_tree_node *) (node))
#define raw_prio_tree_remove(root, node) \
	prio_tree_remove(root, (struct prio_tree_node *) (node))

#endif /* _LINUX_PRIO_TREE_H */
Commit	Line	Data
1da177e4 LT	1	#ifndef _LINUX_PRIO_TREE_H
	2	#define _LINUX_PRIO_TREE_H
	3
	4	/*
	5	* K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct
	6	* fields with identical types should end up at the same location. We'll use
	7	* this until we can scrap struct raw_prio_tree_node.
	8	*
	9	* Note: all this could be done more elegantly by using unnamed union/struct
	10	* fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this
	11	* language extension.
	12	*/
	13
	14	struct raw_prio_tree_node {
	15	struct prio_tree_node *left;
	16	struct prio_tree_node *right;
	17	struct prio_tree_node *parent;
	18	};
	19
	20	struct prio_tree_node {
	21	struct prio_tree_node *left;
	22	struct prio_tree_node *right;
	23	struct prio_tree_node *parent;
	24	unsigned long start;
	25	unsigned long last; /* last location _in_ interval */
	26	};
	27
	28	struct prio_tree_root {
	29	struct prio_tree_node *prio_tree_node;
	30	unsigned short index_bits;
	31	unsigned short raw;
	32	/*
	33	* 0: nodes are of type struct prio_tree_node
	34	* 1: nodes are of type raw_prio_tree_node
	35	*/
	36	};
	37
	38	struct prio_tree_iter {
	39	struct prio_tree_node *cur;
	40	unsigned long mask;
	41	unsigned long value;
	42	int size_level;
	43
	44	struct prio_tree_root *root;
	45	pgoff_t r_index;
	46	pgoff_t h_index;
	47	};
	48
	49	static inline void prio_tree_iter_init(struct prio_tree_iter *iter,
	50	struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index)
	51	{
	52	iter->root = root;
	53	iter->r_index = r_index;
	54	iter->h_index = h_index;
	55	iter->cur = NULL;
	56	}
	57
	58	#define __INIT_PRIO_TREE_ROOT(ptr, _raw) \
	59	do { \
	60	(ptr)->prio_tree_node = NULL; \
	61	(ptr)->index_bits = 1; \
	62	(ptr)->raw = (_raw); \
	63	} while (0)
	64
65	#define INIT_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 0)
66	#define INIT_RAW_PRIO_TREE_ROOT(ptr) __INIT_PRIO_TREE_ROOT(ptr, 1)
67
68	#define INIT_PRIO_TREE_NODE(ptr) \
69	do { \
70	(ptr)->left = (ptr)->right = (ptr)->parent = (ptr); \
71	} while (0)
72
73	#define INIT_PRIO_TREE_ITER(ptr) \
74	do { \
75	(ptr)->cur = NULL; \
76	(ptr)->mask = 0UL; \
77	(ptr)->value = 0UL; \
78	(ptr)->size_level = 0; \
79	} while (0)
80
81	#define prio_tree_entry(ptr, type, member) \
82	((type )((char )(ptr)-(unsigned long)(&((type *)0)->member)))
83
84	static inline int prio_tree_empty(const struct prio_tree_root *root)
85	{
86	return root->prio_tree_node == NULL;
87	}
88
89	static inline int prio_tree_root(const struct prio_tree_node *node)
90	{
91	return node->parent == node;
92	}
93
94	static inline int prio_tree_left_empty(const struct prio_tree_node *node)
95	{
96	return node->left == node;
97	}
98
99	static inline int prio_tree_right_empty(const struct prio_tree_node *node)
100	{
101	return node->right == node;
102	}
103
104
105	struct prio_tree_node prio_tree_replace(struct prio_tree_root root,
106	struct prio_tree_node old, struct prio_tree_node node);
107	struct prio_tree_node prio_tree_insert(struct prio_tree_root root,
108	struct prio_tree_node *node);
109	void prio_tree_remove(struct prio_tree_root root, struct prio_tree_node node);
110	struct prio_tree_node prio_tree_next(struct prio_tree_iter iter);
111
112	#define raw_prio_tree_replace(root, old, node) \
113	prio_tree_replace(root, (struct prio_tree_node *) (old), \
114	(struct prio_tree_node *) (node))
115	#define raw_prio_tree_insert(root, node) \
116	prio_tree_insert(root, (struct prio_tree_node *) (node))
117	#define raw_prio_tree_remove(root, node) \
118	prio_tree_remove(root, (struct prio_tree_node *) (node))
119
120	#endif /* _LINUX_PRIO_TREE_H */