[PATCH 2/3] fs/ntfs3: Make binary search to search smaller chunks in beginning

[Kari Argillander]

We could try to optimize algorithm to first fill just small table and
after that use bigger table all the way up to ARRAY_SIZE(offs). This
way we can use bigger search array, but not lose benefits with entry
count smaller < ARRAY_SIZE(offs).

Signed-off-by: Kari Argillander <kari.argillander@xxxxxxxxx>
---
 fs/ntfs3/index.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c
index 8bac9d20e7e3..e336d5645628 100644
--- a/fs/ntfs3/index.c
+++ b/fs/ntfs3/index.c
@@ -8,6 +8,7 @@
 #include <linux/blkdev.h>
 #include <linux/buffer_head.h>
 #include <linux/fs.h>
+#include <linux/kernel.h>
 #include <linux/nls.h>
 
 #include "debug.h"
@@ -680,8 +681,9 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 #ifdef NTFS3_INDEX_BINARY_SEARCH
 	struct NTFS_DE *found = NULL;
 	int min_idx = 0, mid_idx, max_idx = 0;
+	int table_size = 8;
 	int diff2;
-	u16 offs[64];
+	u16 offs[128];
 
 	if (end > 0x10000)
 		goto next;
@@ -701,7 +703,7 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 		off += e_size;
 
 		max_idx++;
-		if (max_idx < ARRAY_SIZE(offs))
+		if (max_idx < table_size)
 			goto fill_table;
 
 		max_idx--;
@@ -719,6 +721,7 @@ static struct NTFS_DE *hdr_find_e(const struct ntfs_index *indx,
 				return NULL;
 
 			max_idx = 0;
+			table_size = min(table_size * 2, 128);
 			goto fill_table;
 		}
 	} else if (diff2 < 0) {
-- 
2.25.1