60  * Return: -1 if not found.
78 			return -1;  in wnd_scan()
109 			return -1;  in wnd_scan()
112 		wpos = free_bits + 1;  in wnd_scan()
117 	return -1;  in wnd_scan()
167 static inline bool rb_insert_count(struct rb_root *root, struct e_node *e)  in rb_insert_count()  argument
171 	size_t e_ckey = e->count.key;  in rb_insert_count()
172 	size_t e_skey = e->start.key;  in rb_insert_count()
187 			WARN_ON(1);  in rb_insert_count()
192 	rb_link_node(&e->count.node, parent, p);  in rb_insert_count()
193 	rb_insert_color(&e->count.node, root);  in rb_insert_count()
200 static inline bool rb_insert_start(struct rb_root *root, struct e_node *e)  in rb_insert_start()  argument
204 	size_t e_skey = e->start.key;  in rb_insert_start()
217 			WARN_ON(1);  in rb_insert_start()
222 	rb_link_node(&e->start.node, parent, p);  in rb_insert_start()
223 	rb_insert_color(&e->start.node, root);  in rb_insert_start()
229  * @build:	1 when building tree.
234 	struct e_node *e, *e0 = NULL;  in wnd_add_free_ext()  local
242 			wnd->uptodated = -1;  in wnd_add_free_ext()
252 			e = rb_entry(n, struct e_node, start.node);  in wnd_add_free_ext()
254 			if (e->start.key + e->count.key == bit) {  in wnd_add_free_ext()
256 				bit = e->start.key;  in wnd_add_free_ext()
257 				len += e->count.key;  in wnd_add_free_ext()
258 				rb_erase(&e->start.node, &wnd->start_tree);  in wnd_add_free_ext()
259 				rb_erase(&e->count.node, &wnd->count_tree);  in wnd_add_free_ext()
260 				wnd->count -= 1;  in wnd_add_free_ext()
261 				e0 = e;  in wnd_add_free_ext()
268 			e = rb_entry(n, struct e_node, start.node);  in wnd_add_free_ext()
269 			next_end = e->start.key + e->count.key;  in wnd_add_free_ext()
270 			if (e->start.key > end_in)  in wnd_add_free_ext()
277 			rb_erase(&e->start.node, &wnd->start_tree);  in wnd_add_free_ext()
278 			rb_erase(&e->count.node, &wnd->count_tree);  in wnd_add_free_ext()
279 			wnd->count -= 1;  in wnd_add_free_ext()
282 				e0 = e;  in wnd_add_free_ext()
284 				kmem_cache_free(ntfs_enode_cachep, e);  in wnd_add_free_ext()
287 		if (wnd->uptodated != 1) {  in wnd_add_free_ext()
294 			while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) {  in wnd_add_free_ext()
295 				bit -= 1;  in wnd_add_free_ext()
296 				len += 1;  in wnd_add_free_ext()
305 			while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) {  in wnd_add_free_ext()
306 				end_in += 1;  in wnd_add_free_ext()
307 				len += 1;  in wnd_add_free_ext()
316 		wnd->uptodated = -1;  in wnd_add_free_ext()
320 		e = rb_entry(n, struct e_node, count.node);  in wnd_add_free_ext()
321 		if (len <= e->count.key)  in wnd_add_free_ext()
334 		rb_erase(&e->start.node, &wnd->start_tree);  in wnd_add_free_ext()
335 		rb_erase(&e->count.node, &wnd->count_tree);  in wnd_add_free_ext()
336 		wnd->count -= 1;  in wnd_add_free_ext()
338 		e = e0 ? e0 : kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC);  in wnd_add_free_ext()
339 		if (!e) {  in wnd_add_free_ext()
340 			wnd->uptodated = -1;  in wnd_add_free_ext()
347 	e->start.key = bit;  in wnd_add_free_ext()
348 	e->count.key = len;  in wnd_add_free_ext()
352 	rb_insert_start(&wnd->start_tree, e);  in wnd_add_free_ext()
353 	rb_insert_count(&wnd->count_tree, e);  in wnd_add_free_ext()
354 	wnd->count += 1;  in wnd_add_free_ext()
365 	struct e_node *e, *e3;  in wnd_remove_free_ext()  local
375 	e = rb_entry(n, struct e_node, start.node);  in wnd_remove_free_ext()
376 	end = e->start.key + e->count.key;  in wnd_remove_free_ext()
379 	len = e->count.key;  in wnd_remove_free_ext()
381 	/* Range [bit,end_in) must be inside 'e' or outside 'e' and 'n'. */  in wnd_remove_free_ext()
382 	if (e->start.key > bit)  in wnd_remove_free_ext()
385 		/* Range [bit,end_in) inside 'e'. */  in wnd_remove_free_ext()
388 		len = bit - e->start.key;  in wnd_remove_free_ext()
414 			wnd->count -= 1;  in wnd_remove_free_ext()
426 	if (e->count.key != wnd->extent_max) {  in wnd_remove_free_ext()
428 	} else if (rb_prev(&e->count.node)) {  in wnd_remove_free_ext()
431 		n3 = rb_next(&e->count.node);  in wnd_remove_free_ext()
443 			e->start.key = new_key;  in wnd_remove_free_ext()
444 			rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
445 			e->count.key = new_len;  in wnd_remove_free_ext()
446 			rb_insert_count(&wnd->count_tree, e);  in wnd_remove_free_ext()
448 			rb_erase(&e->start.node, &wnd->start_tree);  in wnd_remove_free_ext()
449 			rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
450 			wnd->count -= 1;  in wnd_remove_free_ext()
451 			kmem_cache_free(ntfs_enode_cachep, e);  in wnd_remove_free_ext()
455 	rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
456 	e->count.key = len;  in wnd_remove_free_ext()
457 	rb_insert_count(&wnd->count_tree, e);  in wnd_remove_free_ext()
463 		wnd->uptodated = -1;  in wnd_remove_free_ext()
466 		e = rb_entry(rb_last(&wnd->count_tree), struct e_node,  in wnd_remove_free_ext()
468 		if (e->count.key > new_len)  in wnd_remove_free_ext()
472 		rb_erase(&e->start.node, &wnd->start_tree);  in wnd_remove_free_ext()
473 		rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
474 		wnd->count -= 1;  in wnd_remove_free_ext()
476 		e = kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC);  in wnd_remove_free_ext()
477 		if (!e)  in wnd_remove_free_ext()
478 			wnd->uptodated = -1;  in wnd_remove_free_ext()
481 	if (e) {  in wnd_remove_free_ext()
482 		e->start.key = new_key;  in wnd_remove_free_ext()
483 		e->count.key = new_len;  in wnd_remove_free_ext()
484 		rb_insert_start(&wnd->start_tree, e);  in wnd_remove_free_ext()
485 		rb_insert_count(&wnd->count_tree, e);  in wnd_remove_free_ext()
486 		wnd->count += 1;  in wnd_remove_free_ext()
490 	if (!wnd->count && 1 != wnd->uptodated)  in wnd_remove_free_ext()
520 		if (iw + 1 == wnd->nwnd)  in wnd_rescan()
601 			/* Skip free block and first '1'. */  in wnd_rescan()
602 			wpos = frb + 1;  in wnd_rescan()
627 	 * wnd->uptodated will be -1.  in wnd_rescan()
631 		wnd->uptodated = 1;  in wnd_rescan()
658 	wnd->bits_last = nbits & (wbits - 1);  in wnd_init()
716 	u32 wbit = bit & (wbits - 1);  in wnd_set_free()
722 		if (iw + 1 == wnd->nwnd)  in wnd_set_free()
748 		iw += 1;  in wnd_set_free()
766 	u32 wbit = bit & (wbits - 1);  in wnd_set_used()
772 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_set_used()
797 		iw += 1;  in wnd_set_used()
823 		if (wnd_is_free(wnd, bit + i, 1)) {  in wnd_set_used_safe()
826 			len += 1;  in wnd_set_used_safe()
854 	u32 wbit = bit & (wbits - 1);  in wnd_is_free_hlp()
859 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_is_free_hlp()
881 		iw += 1;  in wnd_is_free_hlp()
897 	struct e_node *e;  in wnd_is_free()  local
906 	e = rb_entry(n, struct e_node, start.node);  in wnd_is_free()
908 	end = e->start.key + e->count.key;  in wnd_is_free()
930 	u32 wbit = bit & (wbits - 1);  in wnd_is_used()
933 	struct e_node *e;  in wnd_is_used()  local
939 	n = rb_lookup(&wnd->start_tree, end - 1);  in wnd_is_used()
943 	e = rb_entry(n, struct e_node, start.node);  in wnd_is_used()
944 	if (e->start.key + e->count.key > bit)  in wnd_is_used()
951 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_is_used()
972 		iw += 1;  in wnd_is_used()
995 	const struct e_node *e;  in wnd_find()  local
1026 		if (wnd->uptodated == 1) {  in wnd_find()
1033 	e = NULL;  in wnd_find()
1042 		e = rb_entry(cr, struct e_node, start.node);  in wnd_find()
1044 		if (e->start.key == hint)  in wnd_find()
1047 		if (e->start.key < hint) {  in wnd_find()
1057 			e = pr ? rb_entry(pr, struct e_node, start.node) : NULL;  in wnd_find()
1062 	if (!e)  in wnd_find()
1065 	if (e->start.key + e->count.key > hint) {  in wnd_find()
1067 		size_t len = e->start.key + e->count.key - hint;  in wnd_find()
1088 	e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node);  in wnd_find()
1089 	if (e->count.key != wnd->extent_max)  in wnd_find()
1090 		wnd->extent_max = e->count.key;  in wnd_find()
1092 	if (e->count.key < max_alloc) {  in wnd_find()
1093 		if (e->count.key >= to_alloc) {  in wnd_find()
1096 			if (e->count.key < to_alloc0) {  in wnd_find()
1100 			to_alloc = e->count.key;  in wnd_find()
1101 		} else if (-1 != wnd->uptodated) {  in wnd_find()
1102 			to_alloc = e->count.key;  in wnd_find()
1112 			max_check = e->start.key + to_alloc;  in wnd_find()
1115 			for (op = e->start.key + e->count.key; op < max_check;  in wnd_find()
1117 				if (!wnd_is_free(wnd, op, 1))  in wnd_find()
1122 			to_alloc = op - e->start.key;  in wnd_find()
1126 		fnd = e->start.key;  in wnd_find()
1127 		if (e->start.key + to_alloc > max_alloc)  in wnd_find()
1128 			to_alloc = max_alloc - e->start.key;  in wnd_find()
1132 	if (wnd->uptodated == 1) {  in wnd_find()
1137 	b_len = e->count.key;  in wnd_find()
1138 	b_pos = e->start.key;  in wnd_find()
1150 	wpos = hint & (wbits - 1);  in wnd_find()
1157 		size_t t = max_alloc + wbits - 1;  in wnd_find()
1178 		if (unlikely(iw + 1 == nwnd)) {  in wnd_find()
1182 				size_t t = max_alloc & (wbits - 1);  in wnd_find()
1316 		/* TODO: Optimize remove extent (pass 'e'?). */  in wnd_find()
1351 	new_last = new_bits & (wbits - 1);  in wnd_extend()
1369 	b0 = old_bits & (wbits - 1);  in wnd_extend()
1371 	for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) {  in wnd_extend()
1377 		if (iw + 1 == new_wnd)  in wnd_extend()
1440 	u32 wbit = lcn_from & (wbits - 1);  in ntfs_trim_fs()
1444 		minlen = 1;  in ntfs_trim_fs()
1446 	if (range->len == (u64)-1)  in ntfs_trim_fs()
1463 		if (iw + 1 == wnd->nwnd)  in ntfs_trim_fs()
1479 				len += 1;  in ntfs_trim_fs()