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
