Lines Matching +full:zero +full:- +full:based

1 /* SPDX-License-Identifier: GPL-2.0 */
15  * Traversal for trees in eytzinger layout - a full binary tree layed out in an
24  * Two variants are provided, for one based indexing and zero based indexing.
26  * Zero based indexing is more convenient, but one based indexing has better
56 	return rounddown_pow_of_two(size + 1) - 1;  in eytzinger1_last()
76 		i <<= __fls(size + 1) - __fls(i);  in eytzinger1_next()
92 		i <<= __fls(size + 1) - __fls(i);  in eytzinger1_prev()
93 		i -= 1;  in eytzinger1_prev()
105 		? (size + 1 - rounddown_pow_of_two(size)) << 1  in eytzinger1_extra()
113 	unsigned shift = __fls(size) - b;  in __eytzinger1_to_inorder()
127 	 *	i -= (i - extra) >> 1;  in __eytzinger1_to_inorder()
129 	s = extra - i;  in __eytzinger1_to_inorder()
147 	 *	i += i - extra;  in __inorder_to_eytzinger1()
149 	s = extra - i;  in __inorder_to_eytzinger1()
150 	i -= s & (s >> 31);  in __inorder_to_eytzinger1()
155 	i  |= 1U << (__fls(size) - shift);  in __inorder_to_eytzinger1()
175 /* Zero based indexing version: */
196 	return eytzinger1_first(size) - 1;  in eytzinger0_first()
201 	return eytzinger1_last(size) - 1;  in eytzinger0_last()
206 	return eytzinger1_next(i + 1, size) - 1;  in eytzinger0_next()
211 	return eytzinger1_prev(i + 1, size) - 1;  in eytzinger0_prev()
222 	return __eytzinger1_to_inorder(i + 1, size, extra) - 1;  in __eytzinger0_to_inorder()
228 	return __inorder_to_eytzinger1(i + 1, size, extra) - 1;  in __inorder_to_eytzinger0()
243 	     (_i) != -1;				\
246 /* return greatest node <= @search, or -1 if not found */
253 		return -1;  in eytzinger0_find_le()
265 		 * eytzinger0_prev(eytzinger0_first())) returns -1, as expected  in eytzinger0_find_le()
279 	 * if eytitzinger0_find_le() returned -1 - no element was <= search - we  in eytzinger0_find_gt()
283 	 * similarly if find_le() returns last element, we should return -1;  in eytzinger0_find_gt()