ref: dee6a10ab37fef64f47ddfadeae02a9449fb9294
parent: b1a34c56f4556f256fc16096190e77b69a715197
author: gkostka <[email protected]>
date: Sat May 20 05:23:54 EDT 2017
ext4_dir_idx: make qsort as a default dir idx sort algorithm
--- a/include/ext4_config.h
+++ b/include/ext4_config.h
@@ -88,11 +88,6 @@
#define CONFIG_JOURNALING_ENABLE 1
#endif
-/**@brief Enable directory indexing comb sort*/
-#ifndef CONFIG_DIR_INDEX_COMB_SORT
-#define CONFIG_DIR_INDEX_COMB_SORT 1
-#endif
-
/**@brief Include error codes from ext4_errno or standard library.*/
#ifndef CONFIG_HAVE_OWN_ERRNO
#define CONFIG_HAVE_OWN_ERRNO 0
--- a/src/ext4_dir_idx.c
+++ b/src/ext4_dir_idx.c
@@ -830,42 +830,6 @@
return rc;
}
-#if CONFIG_DIR_INDEX_COMB_SORT
-#define SWAP_ENTRY(se1, se2) \
- do { \- struct ext4_dx_sort_entry tmp = se1; \
- se1 = se2; \
- se2 = tmp; \
- \
-} while (0)
-
-static void comb_sort(struct ext4_dx_sort_entry *se, uint32_t count)
-{- struct ext4_dx_sort_entry *p, *q, *top = se + count - 1;
- bool more;
- /* Combsort */
- while (count > 2) {- count = (count * 10) / 13;
- if (count - 9 < 2)
- count = 11;
- for (p = top, q = p - count; q >= se; p--, q--)
- if (p->hash < q->hash)
- SWAP_ENTRY(*p, *q);
- }
- /* Bubblesort */
- do {- more = 0;
- q = top;
- while (q-- > se) {- if (q[1].hash >= q[0].hash)
- continue;
- SWAP_ENTRY(*(q + 1), *q);
- more = 1;
- }
- } while (more);
-}
-#else
-
/**@brief Compare function used to pass in quicksort implementation.
* It can compare two entries by hash value.
* @param arg1 First entry
@@ -888,7 +852,6 @@
else
return 1;
}
-#endif
/**@brief Insert new index entry to block.
* Note that space for new entry must be checked by caller.
@@ -996,13 +959,9 @@
de = (void *)((uint8_t *)de + elen);
}
-/* Sort all entries */
-#if CONFIG_DIR_INDEX_COMB_SORT
- comb_sort(sort, idx);
-#else
qsort(sort, idx, sizeof(struct ext4_dx_sort_entry),
ext4_dir_dx_entry_comparator);
-#endif
+
/* Allocate new block for store the second part of entries */
ext4_fsblk_t new_fblock;
uint32_t new_iblock;