linux-master/lib/xarray.c

25  * @mark is an xa_mark_t; a small number indicating one of the mark bits.
68 static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark)
70 	if (!(xa->xa_flags & XA_FLAGS_MARK(mark)))
71 		xa->xa_flags |= XA_FLAGS_MARK(mark);
74 static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark)
76 	if (xa->xa_flags & XA_FLAGS_MARK(mark))
77 		xa->xa_flags &= ~(XA_FLAGS_MARK(mark));
80 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark)
82 	return node->marks[(__force unsigned)mark];
86 		unsigned int offset, xa_mark_t mark)
88 	return test_bit(offset, node_marks(node, mark));
93 				xa_mark_t mark)
95 	return __test_and_set_bit(offset, node_marks(node, mark));
100 				xa_mark_t mark)
102 	return __test_and_clear_bit(offset, node_marks(node, mark));
105 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark)
107 	return !bitmap_empty(node_marks(node, mark), XA_CHUNK_SIZE);
110 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
112 	bitmap_fill(node_marks(node, mark), XA_CHUNK_SIZE);
115 #define mark_inc(mark) do { \
116 	mark = (__force xa_mark_t)((__force unsigned)(mark) + 1); \
123  * Set a mark on the first entry if any entry has it set.  Clear marks on
128 	unsigned int mark = 0;
135 		unsigned long *marks = xas->xa_node->marks[mark];
140 	} while (mark++ != (__force unsigned)XA_MARK_MAX);
579 		xa_mark_t mark = 0;
591 		/* Propagate the aggregated mark info to the new child */
593 			if (xa_track_free(xa) && mark == XA_FREE_MARK) {
599 			} else if (xa_marked(xa, mark)) {
600 				node_set_mark(node, 0, mark);
602 			if (mark == XA_MARK_MAX)
604 			mark_inc(mark);
816 		 * so the mark clearing will appear to happen before the
850  * xas_get_mark() - Returns the state of this mark.
852  * @mark: Mark number.
854  * Return: true if the mark is set, false if the mark is clear or @xas
857 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark)
862 		return xa_marked(xas->xa, mark);
863 	return node_get_mark(xas->xa_node, xas->xa_offset, mark);
868  * xas_set_mark() - Sets the mark on this entry and its parents.
870  * @mark: Mark number.
872  * Sets the specified mark on this entry, and walks up the tree setting it
876 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)
885 		if (node_set_mark(node, offset, mark))
891 	if (!xa_marked(xas->xa, mark))
892 		xa_mark_set(xas->xa, mark);
897  * xas_clear_mark() - Clears the mark on this entry and its parents.
899  * @mark: Mark number.
901  * Clears the specified mark on this entry, and walks back to the head
905 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)
914 		if (!node_clear_mark(node, offset, mark))
916 		if (node_any_mark(node, mark))
923 	if (xa_marked(xas->xa, mark))
924 		xa_mark_clear(xas->xa, mark);
933  * free entries with a mark, we need to set it on all entries.  All other
941 	xa_mark_t mark = 0;
944 		if (xa_track_free(xas->xa) && mark == XA_FREE_MARK)
945 			xas_set_mark(xas, mark);
947 			xas_clear_mark(xas, mark);
948 		if (mark == XA_MARK_MAX)
950 		mark_inc(mark);
959 	xa_mark_t mark = XA_MARK_0;
962 		if (node_get_mark(node, offset, mark))
963 			marks |= 1 << (__force unsigned int)mark;
964 		if (mark == XA_MARK_MAX)
966 		mark_inc(mark);
973 		xa_mark_t mark)
978 		node_mark_all(node, mark);
981 			node_set_mark(node, i, mark);
989 	xa_mark_t mark = XA_MARK_0;
992 		if (marks & (1 << (__force unsigned int)mark)) {
993 			node_set_mark(node, offset, mark);
995 				node_mark_slots(child, sibs, mark);
997 		if (mark == XA_MARK_MAX)
999 		mark_inc(mark);
1304  * @mark: Mark number to search for.
1321 void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
1342 			if (xa_marked(xas->xa, mark))
1369 		offset = xas_find_chunk(xas, advance, mark);
1382 		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))
1910  * __xa_set_mark() - Set this mark on this entry while locked.
1913  * @mark: Mark number.
1915  * Attempting to set a mark on a %NULL entry does not succeed.
1919 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1925 		xas_set_mark(&xas, mark);
1930  * __xa_clear_mark() - Clear this mark on this entry while locked.
1933  * @mark: Mark number.
1937 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1943 		xas_clear_mark(&xas, mark);
1948  * xa_get_mark() - Inquire whether this mark is set on this entry.
1951  * @mark: Mark number.
1957  * Return: True if the entry at @index has this mark set, false if it doesn't.
1959 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1966 	while (xas_get_mark(&xas, mark)) {
1980  * xa_set_mark() - Set this mark on this entry.
1983  * @mark: Mark number.
1985  * Attempting to set a mark on a %NULL entry does not succeed.
1989 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
1992 	__xa_set_mark(xa, index, mark);
1998  * xa_clear_mark() - Clear this mark on this entry.
2001  * @mark: Mark number.
2003  * Clearing a mark always succeeds.
2007 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark)
2010 	__xa_clear_mark(xa, index, mark);
2133 			unsigned long max, unsigned int n, xa_mark_t mark)
2139 	xas_for_each_marked(xas, entry, max, mark) {
2163  * The @filter may be an XArray mark value, in which case entries which are
2164  * marked with that mark will be copied.  It may also be %XA_PRESENT, in