56 	return i + 1 == wnd->nwnd ? wnd->bits_last : wnd->sb->s_blocksize * 8;  in wnd_bits()
65  * Return: -1 if not found.
83 			return -1;  in wnd_scan()
114 			return -1;  in wnd_scan()
117 		wpos = free_bits + 1;  in wnd_scan()
122 	return -1;  in wnd_scan()
171 static inline bool rb_insert_count(struct rb_root *root, struct e_node *e)  in rb_insert_count()  argument
175 	size_t e_ckey = e->count.key;  in rb_insert_count()
176 	size_t e_skey = e->start.key;  in rb_insert_count()
191 			WARN_ON(1);  in rb_insert_count()
196 	rb_link_node(&e->count.node, parent, p);  in rb_insert_count()
197 	rb_insert_color(&e->count.node, root);  in rb_insert_count()
204 static inline bool rb_insert_start(struct rb_root *root, struct e_node *e)  in rb_insert_start()  argument
208 	size_t e_skey = e->start.key;  in rb_insert_start()
221 			WARN_ON(1);  in rb_insert_start()
226 	rb_link_node(&e->start.node, parent, p);  in rb_insert_start()
227 	rb_insert_color(&e->start.node, root);  in rb_insert_start()
233  * @build:	1 when building tree.
238 	struct e_node *e, *e0 = NULL;  in wnd_add_free_ext()  local
246 			wnd->uptodated = -1;  in wnd_add_free_ext()
256 			e = rb_entry(n, struct e_node, start.node);  in wnd_add_free_ext()
258 			if (e->start.key + e->count.key == bit) {  in wnd_add_free_ext()
260 				bit = e->start.key;  in wnd_add_free_ext()
261 				len += e->count.key;  in wnd_add_free_ext()
262 				rb_erase(&e->start.node, &wnd->start_tree);  in wnd_add_free_ext()
263 				rb_erase(&e->count.node, &wnd->count_tree);  in wnd_add_free_ext()
264 				wnd->count -= 1;  in wnd_add_free_ext()
265 				e0 = e;  in wnd_add_free_ext()
272 			e = rb_entry(n, struct e_node, start.node);  in wnd_add_free_ext()
273 			next_end = e->start.key + e->count.key;  in wnd_add_free_ext()
274 			if (e->start.key > end_in)  in wnd_add_free_ext()
281 			rb_erase(&e->start.node, &wnd->start_tree);  in wnd_add_free_ext()
282 			rb_erase(&e->count.node, &wnd->count_tree);  in wnd_add_free_ext()
283 			wnd->count -= 1;  in wnd_add_free_ext()
286 				e0 = e;  in wnd_add_free_ext()
288 				kmem_cache_free(ntfs_enode_cachep, e);  in wnd_add_free_ext()
291 		if (wnd->uptodated != 1) {  in wnd_add_free_ext()
298 			while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) {  in wnd_add_free_ext()
299 				bit -= 1;  in wnd_add_free_ext()
300 				len += 1;  in wnd_add_free_ext()
309 			while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) {  in wnd_add_free_ext()
310 				end_in += 1;  in wnd_add_free_ext()
311 				len += 1;  in wnd_add_free_ext()
320 		wnd->uptodated = -1;  in wnd_add_free_ext()
324 		e = rb_entry(n, struct e_node, count.node);  in wnd_add_free_ext()
325 		if (len <= e->count.key)  in wnd_add_free_ext()
338 		rb_erase(&e->start.node, &wnd->start_tree);  in wnd_add_free_ext()
339 		rb_erase(&e->count.node, &wnd->count_tree);  in wnd_add_free_ext()
340 		wnd->count -= 1;  in wnd_add_free_ext()
342 		e = e0 ? e0 : kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC);  in wnd_add_free_ext()
343 		if (!e) {  in wnd_add_free_ext()
344 			wnd->uptodated = -1;  in wnd_add_free_ext()
351 	e->start.key = bit;  in wnd_add_free_ext()
352 	e->count.key = len;  in wnd_add_free_ext()
356 	rb_insert_start(&wnd->start_tree, e);  in wnd_add_free_ext()
357 	rb_insert_count(&wnd->count_tree, e);  in wnd_add_free_ext()
358 	wnd->count += 1;  in wnd_add_free_ext()
369 	struct e_node *e, *e3;  in wnd_remove_free_ext()  local
379 	e = rb_entry(n, struct e_node, start.node);  in wnd_remove_free_ext()
380 	end = e->start.key + e->count.key;  in wnd_remove_free_ext()
383 	len = e->count.key;  in wnd_remove_free_ext()
385 	/* Range [bit,end_in) must be inside 'e' or outside 'e' and 'n'. */  in wnd_remove_free_ext()
386 	if (e->start.key > bit)  in wnd_remove_free_ext()
389 		/* Range [bit,end_in) inside 'e'. */  in wnd_remove_free_ext()
392 		len = bit - e->start.key;  in wnd_remove_free_ext()
418 			wnd->count -= 1;  in wnd_remove_free_ext()
430 	if (e->count.key != wnd->extent_max) {  in wnd_remove_free_ext()
432 	} else if (rb_prev(&e->count.node)) {  in wnd_remove_free_ext()
435 		n3 = rb_next(&e->count.node);  in wnd_remove_free_ext()
447 			e->start.key = new_key;  in wnd_remove_free_ext()
448 			rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
449 			e->count.key = new_len;  in wnd_remove_free_ext()
450 			rb_insert_count(&wnd->count_tree, e);  in wnd_remove_free_ext()
452 			rb_erase(&e->start.node, &wnd->start_tree);  in wnd_remove_free_ext()
453 			rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
454 			wnd->count -= 1;  in wnd_remove_free_ext()
455 			kmem_cache_free(ntfs_enode_cachep, e);  in wnd_remove_free_ext()
459 	rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
460 	e->count.key = len;  in wnd_remove_free_ext()
461 	rb_insert_count(&wnd->count_tree, e);  in wnd_remove_free_ext()
467 		wnd->uptodated = -1;  in wnd_remove_free_ext()
470 		e = rb_entry(rb_last(&wnd->count_tree), struct e_node,  in wnd_remove_free_ext()
472 		if (e->count.key > new_len)  in wnd_remove_free_ext()
476 		rb_erase(&e->start.node, &wnd->start_tree);  in wnd_remove_free_ext()
477 		rb_erase(&e->count.node, &wnd->count_tree);  in wnd_remove_free_ext()
478 		wnd->count -= 1;  in wnd_remove_free_ext()
480 		e = kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC);  in wnd_remove_free_ext()
481 		if (!e)  in wnd_remove_free_ext()
482 			wnd->uptodated = -1;  in wnd_remove_free_ext()
485 	if (e) {  in wnd_remove_free_ext()
486 		e->start.key = new_key;  in wnd_remove_free_ext()
487 		e->count.key = new_len;  in wnd_remove_free_ext()
488 		rb_insert_start(&wnd->start_tree, e);  in wnd_remove_free_ext()
489 		rb_insert_count(&wnd->count_tree, e);  in wnd_remove_free_ext()
490 		wnd->count += 1;  in wnd_remove_free_ext()
494 	if (!wnd->count && 1 != wnd->uptodated)  in wnd_remove_free_ext()
525 		if (iw + 1 == wnd->nwnd)  in wnd_rescan()
608 			/* Skip free block and first '1'. */  in wnd_rescan()
609 			wpos = frb + 1;  in wnd_rescan()
634 	 * wnd->uptodated will be -1.  in wnd_rescan()
638 		wnd->uptodated = 1;  in wnd_rescan()
665 	wnd->bits_last = nbits & (wbits - 1);  in wnd_init()
721 	u32 wbit = bit & (wbits - 1);  in wnd_set_free()
728 		if (iw + 1 == wnd->nwnd)  in wnd_set_free()
756 		iw += 1;  in wnd_set_free()
774 	u32 wbit = bit & (wbits - 1);  in wnd_set_used()
781 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_set_used()
807 		iw += 1;  in wnd_set_used()
826 	u32 wbit = bit & (wbits - 1);  in wnd_is_free_hlp()
831 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_is_free_hlp()
853 		iw += 1;  in wnd_is_free_hlp()
869 	struct e_node *e;  in wnd_is_free()  local
878 	e = rb_entry(n, struct e_node, start.node);  in wnd_is_free()
880 	end = e->start.key + e->count.key;  in wnd_is_free()
902 	u32 wbit = bit & (wbits - 1);  in wnd_is_used()
905 	struct e_node *e;  in wnd_is_used()  local
911 	n = rb_lookup(&wnd->start_tree, end - 1);  in wnd_is_used()
915 	e = rb_entry(n, struct e_node, start.node);  in wnd_is_used()
916 	if (e->start.key + e->count.key > bit)  in wnd_is_used()
923 		if (unlikely(iw + 1 == wnd->nwnd))  in wnd_is_used()
944 		iw += 1;  in wnd_is_used()
968 	const struct e_node *e;  in wnd_find()  local
999 		if (wnd->uptodated == 1) {  in wnd_find()
1006 	e = NULL;  in wnd_find()
1015 		e = rb_entry(cr, struct e_node, start.node);  in wnd_find()
1017 		if (e->start.key == hint)  in wnd_find()
1020 		if (e->start.key < hint) {  in wnd_find()
1030 			e = pr ? rb_entry(pr, struct e_node, start.node) : NULL;  in wnd_find()
1035 	if (!e)  in wnd_find()
1038 	if (e->start.key + e->count.key > hint) {  in wnd_find()
1040 		size_t len = e->start.key + e->count.key - hint;  in wnd_find()
1061 	e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node);  in wnd_find()
1062 	if (e->count.key != wnd->extent_max)  in wnd_find()
1063 		wnd->extent_max = e->count.key;  in wnd_find()
1065 	if (e->count.key < max_alloc) {  in wnd_find()
1066 		if (e->count.key >= to_alloc) {  in wnd_find()
1069 			if (e->count.key < to_alloc0) {  in wnd_find()
1073 			to_alloc = e->count.key;  in wnd_find()
1074 		} else if (-1 != wnd->uptodated) {  in wnd_find()
1075 			to_alloc = e->count.key;  in wnd_find()
1085 			max_check = e->start.key + to_alloc;  in wnd_find()
1088 			for (op = e->start.key + e->count.key; op < max_check;  in wnd_find()
1090 				if (!wnd_is_free(wnd, op, 1))  in wnd_find()
1095 			to_alloc = op - e->start.key;  in wnd_find()
1099 		fnd = e->start.key;  in wnd_find()
1100 		if (e->start.key + to_alloc > max_alloc)  in wnd_find()
1101 			to_alloc = max_alloc - e->start.key;  in wnd_find()
1105 	if (wnd->uptodated == 1) {  in wnd_find()
1110 	b_len = e->count.key;  in wnd_find()
1111 	b_pos = e->start.key;  in wnd_find()
1123 	wpos = hint & (wbits - 1);  in wnd_find()
1130 		size_t t = max_alloc + wbits - 1;  in wnd_find()
1151 		if (unlikely(iw + 1 == nwnd)) {  in wnd_find()
1155 				size_t t = max_alloc & (wbits - 1);  in wnd_find()
1292 		/* TODO: Optimize remove extent (pass 'e'?). */  in wnd_find()
1327 	new_last = new_bits & (wbits - 1);  in wnd_extend()
1347 	b0 = old_bits & (wbits - 1);  in wnd_extend()
1349 	for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) {  in wnd_extend()
1356 		if (iw + 1 == new_wnd)  in wnd_extend()
1421 	u32 wbit = lcn_from & (wbits - 1);  in ntfs_trim_fs()
1426 		minlen = 1;  in ntfs_trim_fs()
1428 	if (range->len == (u64)-1)  in ntfs_trim_fs()
1445 		if (iw + 1 == wnd->nwnd)  in ntfs_trim_fs()
1463 				len += 1;  in ntfs_trim_fs()