ref: 627b4180e0732f1274af6a97f8abeec7bb0911ad
parent: 002155166db0337127c1b346e2f58087bc7cc832
author: gkostka <kostka.grzegorz@gmail.com>
date: Sun Jun 22 12:02:41 EDT 2014
Comb sort for directory indexing (shold be faster).
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -7,11 +7,6 @@
include_directories(blockdev/filedev_win)
-#Library build
-add_subdirectory(lwext4)
-#Detect all possible warnings for lwext4 target
-set_target_properties(lwext4 PROPERTIES COMPILE_FLAGS "-Wall -Wextra -pedantic")
-
#Examples
if (CMAKE_SYSTEM_PROCESSOR STREQUAL cortex-m0)
#cortex-m0 demos
@@ -32,6 +27,11 @@
elseif(CMAKE_SYSTEM_PROCESSOR STREQUAL avrxmega7)
#avrxmega7 demos
#...
+elseif(CMAKE_SYSTEM_PROCESSOR STREQUAL msp430g2210)
+ add_definitions(-DCONFIG_DEBUG_PRINTF=0)
+ add_definitions(-DCONFIG_DEBUG_ASSERT=0)
+ #msp430f6459 demos
+ #...
else()
#Generic example target
add_subdirectory(blockdev)
@@ -38,6 +38,11 @@
add_subdirectory(fs_test)
add_subdirectory(demos/generic)
endif()
+
+#Library build
+add_subdirectory(lwext4)
+#Detect all possible warnings for lwext4 target
+set_target_properties(lwext4 PROPERTIES COMPILE_FLAGS "-Wall -Wextra -pedantic")
#DISTRIBUTION
--- a/Makefile
+++ b/Makefile
@@ -23,6 +23,12 @@
mkdir build_avrxmega7
cd build_avrxmega7 && cmake -G$(PROJECT_SETUP) -DCMAKE_BUILD_TYPE=$(BUILD_TYPE) -DCMAKE_TOOLCHAIN_FILE=../toolchain/avrxmega7.cmake ..
+msp430:
+ rm -R -f build_msp430
+ mkdir build_msp430
+ cd build_msp430 && cmake -G$(PROJECT_SETUP) -DCMAKE_BUILD_TYPE=$(BUILD_TYPE) -DCMAKE_TOOLCHAIN_FILE=../toolchain/msp430.cmake ..
+
+
cortex-m0:
rm -R -f build_cortex-m0
mkdir build_cortex-m0
--- a/lwext4/ext4_balloc.c
+++ b/lwext4/ext4_balloc.c
@@ -171,10 +171,9 @@
/* Compute indexes */
uint32_t block_group_first =
ext4_balloc_get_bgid_of_block(sb, first);
- uint32_t block_group_last =
- ext4_balloc_get_bgid_of_block(sb, first + count - 1);
- ext4_assert(block_group_first == block_group_last);
+ ext4_assert(block_group_first ==
+ ext4_balloc_get_bgid_of_block(sb, first + count - 1));
/* Load block group reference */
struct ext4_block_group_ref bg_ref;
--- a/lwext4/ext4_config.h
+++ b/lwext4/ext4_config.h
@@ -53,6 +53,12 @@
#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 sandard library.*/
#ifndef CONFIG_HAVE_OWN_ERRNO
--- a/lwext4/ext4_dir_idx.c
+++ b/lwext4/ext4_dir_idx.c
@@ -557,7 +557,40 @@
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
@@ -580,8 +613,8 @@
else
return 1;
}
+#endif
-
/**@brief Insert new index entry to block.
* Note that space for new entry must be checked by caller.
* @param index_block Block where to insert new entry
@@ -692,9 +725,12 @@
}
/* Sort all entries */
+#if CONFIG_DIR_INDEX_COMB_SORT
+ comb_sort(sort_array, idx);
+#else
qsort(sort_array, idx, sizeof(struct ext4_dx_sort_entry),
ext4_dir_dx_entry_comparator);
-
+#endif
/* Allocate new block for store the second part of entries */
uint32_t new_fblock;
uint32_t new_iblock;