#include <string.h>\r
#include <stdlib.h>\r
\r
-/**@brief Sort entry item.*/\r
-struct ext4_dx_sort_entry {\r
- uint32_t hash;\r
- uint32_t rec_len;\r
- void *dentry;\r
-};\r
-\r
-\r
-static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,\r
- const char *name)\r
-{\r
- return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,\r
- &hinfo->hash, &hinfo->minor_hash);\r
-}\r
-\r
-\r
-uint8_t ext4_dir_dx_root_info_get_hash_version(\r
+/**@brief Get hash version used in directory index.\r
+ * @param root_info Pointer to root info structure of index\r
+ * @return Hash algorithm version\r
+ */\r
+static inline uint8_t ext4_dir_dx_root_info_get_hash_version(\r
struct ext4_directory_dx_root_info *root_info)\r
{\r
return root_info->hash_version;\r
}\r
\r
-\r
-void ext4_dir_dx_root_info_set_hash_version(\r
+/**@brief Set hash version, that will be used in directory index.\r
+ * @param root_info Pointer to root info structure of index\r
+ * @param v Hash algorithm version\r
+ */\r
+static inline void ext4_dir_dx_root_info_set_hash_version(\r
struct ext4_directory_dx_root_info *root_info, uint8_t v)\r
{\r
root_info->hash_version = v;\r
}\r
\r
-uint8_t ext4_dir_dx_root_info_get_info_length(\r
+/**@brief Get length of root_info structure in bytes.\r
+ * @param root_info Pointer to root info structure of index\r
+ * @return Length of the structure\r
+ */\r
+static inline uint8_t ext4_dir_dx_root_info_get_info_length(\r
struct ext4_directory_dx_root_info *root_info)\r
{\r
return root_info->info_length;\r
}\r
-void ext4_dir_dx_root_info_set_info_length(\r
+\r
+/**@brief Set length of root_info structure in bytes.\r
+ * @param root_info Pointer to root info structure of index\r
+ * @param info_length Length of the structure\r
+ */\r
+static inline void ext4_dir_dx_root_info_set_info_length(\r
struct ext4_directory_dx_root_info *root_info, uint8_t len)\r
{\r
root_info->info_length = len;\r
}\r
\r
-uint8_t ext4_dir_dx_root_info_get_indirect_levels(\r
+/**@brief Get number of indirect levels of HTree.\r
+ * @param root_info Pointer to root info structure of index\r
+ * @return Height of HTree (actually only 0 or 1)\r
+ */\r
+static inline uint8_t ext4_dir_dx_root_info_get_indirect_levels(\r
struct ext4_directory_dx_root_info *root_info)\r
{\r
return root_info->indirect_levels;\r
}\r
\r
-void ext4_dir_dx_root_info_set_indirect_levels(\r
+/**@brief Set number of indirect levels of HTree.\r
+ * @param root_info Pointer to root info structure of index\r
+ * @param lvl Height of HTree (actually only 0 or 1)\r
+ */\r
+static inline void ext4_dir_dx_root_info_set_indirect_levels(\r
struct ext4_directory_dx_root_info *root_info, uint8_t lvl)\r
{\r
root_info->indirect_levels = lvl;\r
}\r
\r
-\r
-\r
-uint16_t ext4_dir_dx_countlimit_get_limit(\r
+/**@brief Get maximum number of index node entries.\r
+ * @param climit Pointer to counlimit structure\r
+ * @return Maximum of entries in node\r
+ */\r
+static inline uint16_t ext4_dir_dx_countlimit_get_limit(\r
struct ext4_directory_dx_countlimit *climit)\r
{\r
return to_le16(climit->limit);\r
}\r
-void ext4_dir_dx_countlimit_set_limit(\r
+\r
+/**@brief Set maximum number of index node entries.\r
+ * @param climit Pointer to counlimit structure\r
+ * @param limit Maximum of entries in node\r
+ */\r
+static inline void ext4_dir_dx_countlimit_set_limit(\r
struct ext4_directory_dx_countlimit *climit, uint16_t limit)\r
{\r
climit->limit = to_le16(limit);\r
}\r
\r
-uint16_t ext4_dir_dx_countlimit_get_count(\r
+\r
+/**@brief Get current number of index node entries.\r
+ * @param climit Pointer to counlimit structure\r
+ * @return Number of entries in node\r
+ */\r
+static inline uint16_t ext4_dir_dx_countlimit_get_count(\r
struct ext4_directory_dx_countlimit *climit)\r
{\r
return to_le16(climit->count);\r
}\r
\r
-void ext4_dir_dx_countlimit_set_count(\r
+/**@brief Set current number of index node entries.\r
+ * @param climit Pointer to counlimit structure\r
+ * @param count Number of entries in node\r
+ */\r
+static inline void ext4_dir_dx_countlimit_set_count(\r
struct ext4_directory_dx_countlimit *climit, uint16_t count)\r
{\r
climit->count = to_le16(count);\r
}\r
\r
-\r
-uint32_t ext4_dir_dx_entry_get_hash(\r
+/**@brief Get hash value of index entry.\r
+ * @param entry Pointer to index entry\r
+ * @return Hash value\r
+ */\r
+static inline uint32_t ext4_dir_dx_entry_get_hash(\r
struct ext4_directory_dx_entry *entry)\r
{\r
return to_le32(entry->hash);\r
}\r
-void ext4_dir_dx_entry_set_hash(\r
+\r
+/**@brief Set hash value of index entry.\r
+ * @param entry Pointer to index entry\r
+ * @param hash Hash value\r
+ */\r
+static inline void ext4_dir_dx_entry_set_hash(\r
struct ext4_directory_dx_entry *entry, uint32_t hash)\r
{\r
entry->hash = to_le32(hash);\r
}\r
\r
-uint32_t ext4_dir_dx_entry_get_block(\r
+/**@brief Get block address where child node is located.\r
+ * @param entry Pointer to index entry\r
+ * @return Block address of child node\r
+ */\r
+static inline uint32_t ext4_dir_dx_entry_get_block(\r
struct ext4_directory_dx_entry *entry)\r
{\r
return to_le32(entry->block);\r
}\r
-void ext4_dir_dx_entry_set_block(\r
+\r
+/**@brief Set block address where child node is located.\r
+ * @param entry Pointer to index entry\r
+ * @param block Block address of child node\r
+ */\r
+static inline void ext4_dir_dx_entry_set_block(\r
struct ext4_directory_dx_entry *entry, uint32_t block)\r
{\r
entry->block = to_le32(block);\r
}\r
+\r
+/**@brief Sort entry item.*/\r
+struct ext4_dx_sort_entry {\r
+ uint32_t hash;\r
+ uint32_t rec_len;\r
+ void *dentry;\r
+};\r
+\r
+\r
+static int ext4_dir_dx_hash_string(struct ext4_hash_info *hinfo, int len,\r
+ const char *name)\r
+{\r
+ return ext2_htree_hash(name, len, hinfo->seed, hinfo->hash_version,\r
+ &hinfo->hash, &hinfo->minor_hash);\r
+}\r
+\r
+\r
+\r
/****************************************************************************/\r
\r
int ext4_dir_dx_init(struct ext4_inode_ref *dir)\r
return rc;\r
}\r
\r
+#if CONFIG_DIR_INDEX_COMB_SORT\r
+#define SWAP_ENTRY(se1, se2) do { \\r
+ struct ext4_dx_sort_entry tmp = se1; \\r
+ se1 = se2; \\r
+ se2 = tmp; \\r
+}while(0)\r
+\r
+static void comb_sort(struct ext4_dx_sort_entry *se, uint32_t count)\r
+{\r
+ struct ext4_dx_sort_entry *p, *q, *top = se + count - 1;\r
+ bool more;\r
+ /* Combsort */\r
+ while (count > 2) {\r
+ count = (count * 10) / 13;\r
+ if (count - 9 < 2)\r
+ count = 11;\r
+ for (p = top, q = p - count; q >= se; p--, q--)\r
+ if (p->hash < q->hash)\r
+ SWAP_ENTRY(*p, *q);\r
+ }\r
+ /* Bubblesort */\r
+ do {\r
+ more = 0;\r
+ q = top;\r
+ while (q-- > se) {\r
+ if (q[1].hash >= q[0].hash)\r
+ continue;\r
+ SWAP_ENTRY(*(q+1), *q);\r
+ more = 1;\r
+ }\r
+ } while(more);\r
+}\r
+#else\r
\r
/**@brief Compare function used to pass in quicksort implementation.\r
* It can compare two entries by hash value.\r
else\r
return 1;\r
}\r
-\r
+#endif\r
\r
/**@brief Insert new index entry to block.\r
* Note that space for new entry must be checked by caller.\r
}\r
\r
/* Sort all entries */\r
+#if CONFIG_DIR_INDEX_COMB_SORT\r
+ comb_sort(sort_array, idx);\r
+#else\r
qsort(sort_array, idx, sizeof(struct ext4_dx_sort_entry),\r
ext4_dir_dx_entry_comparator);\r
-\r
+#endif\r
/* Allocate new block for store the second part of entries */\r
uint32_t new_fblock;\r
uint32_t new_iblock;\r
projects / lwext4.git / blobdiff