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()
715 	u32 wbit = bit & (wbits - 1);  in wnd_set_free()
720 		if (iw + 1 == wnd->nwnd)  in wnd_set_free()
757 	u32 wbit = bit & (wbits - 1);  in wnd_set_used()
762 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_set_used()
807 		if (wnd_is_free(wnd, bit + i, 1)) {  in wnd_set_used_safe()
810 			len += 1;  in wnd_set_used_safe()
838 	u32 wbit = bit & (wbits - 1);  in wnd_is_free_hlp()
842 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_is_free_hlp()
875 	struct e_node *e;  in wnd_is_free()  local
884 	e = rb_entry(n, struct e_node, start.node);  in wnd_is_free()
886 	end = e->start.key + e->count.key;  in wnd_is_free()
908 	u32 wbit = bit & (wbits - 1);  in wnd_is_used()
912 	struct e_node *e;  in wnd_is_used()  local
918 	n = rb_lookup(&wnd->start_tree, end - 1);  in wnd_is_used()
922 	e = rb_entry(n, struct e_node, start.node);  in wnd_is_used()
923 	if (e->start.key + e->count.key > bit)  in wnd_is_used()
928 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_is_used()
967 	const struct e_node *e;  in wnd_find()  local
998 		if (wnd->uptodated == 1) {  in wnd_find()
1005 	e = NULL;  in wnd_find()
1014 		e = rb_entry(cr, struct e_node, start.node);  in wnd_find()
1016 		if (e->start.key == hint)  in wnd_find()
1019 		if (e->start.key < hint) {  in wnd_find()
1029 			e = pr ? rb_entry(pr, struct e_node, start.node) : NULL;  in wnd_find()
1034 	if (!e)  in wnd_find()
1037 	if (e->start.key + e->count.key > hint) {  in wnd_find()
1039 		size_t len = e->start.key + e->count.key - hint;  in wnd_find()
1060 	e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node);  in wnd_find()
1061 	if (e->count.key != wnd->extent_max)  in wnd_find()
1062 		wnd->extent_max = e->count.key;  in wnd_find()
1064 	if (e->count.key < max_alloc) {  in wnd_find()
1065 		if (e->count.key >= to_alloc) {  in wnd_find()
1068 			if (e->count.key < to_alloc0) {  in wnd_find()
1072 			to_alloc = e->count.key;  in wnd_find()
1073 		} else if (-1 != wnd->uptodated) {  in wnd_find()
1074 			to_alloc = e->count.key;  in wnd_find()
1084 			max_check = e->start.key + to_alloc;  in wnd_find()
1087 			for (op = e->start.key + e->count.key; op < max_check;  in wnd_find()
1089 				if (!wnd_is_free(wnd, op, 1))  in wnd_find()
1094 			to_alloc = op - e->start.key;  in wnd_find()
1098 		fnd = e->start.key;  in wnd_find()
1099 		if (e->start.key + to_alloc > max_alloc)  in wnd_find()
1100 			to_alloc = max_alloc - e->start.key;  in wnd_find()
1104 	if (wnd->uptodated == 1) {  in wnd_find()
1109 	b_len = e->count.key;  in wnd_find()
1110 	b_pos = e->start.key;  in wnd_find()
1122 	wpos = hint & (wbits - 1);  in wnd_find()
1129 		size_t t = max_alloc + wbits - 1;  in wnd_find()
1150 		if (unlikely(iw + 1 == nwnd)) {  in wnd_find()
1154 				size_t t = max_alloc & (wbits - 1);  in wnd_find()
1288 		/* TODO: Optimize remove extent (pass 'e'?). */  in wnd_find()
1323 	new_last = new_bits & (wbits - 1);  in wnd_extend()
1341 	b0 = old_bits & (wbits - 1);  in wnd_extend()
1343 	for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) {  in wnd_extend()
1349 		if (iw + 1 == new_wnd)  in wnd_extend()
1412 	u32 wbit = lcn_from & (wbits - 1);  in ntfs_trim_fs()
1416 		minlen = 1;  in ntfs_trim_fs()
1418 	if (range->len == (u64)-1)  in ntfs_trim_fs()
1435 		if (iw + 1 == wnd->nwnd)  in ntfs_trim_fs()
1451 				len += 1;  in ntfs_trim_fs()