#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
\r
int rc = ext4_fs_get_inode_data_block_index(inode_ref,\r
block_idx, &block_addr);\r
- if (rc != EOK)\r
+ if(rc != EOK)\r
return rc;\r
\r
\r
p++;\r
\r
/* Don't forget to put old block (prevent memory leak) */\r
- ext4_block_set(inode_ref->fs->bdev, &p->block);\r
-\r
+ rc = ext4_block_set(inode_ref->fs->bdev, &p->block);\r
+ if(rc != EOK)\r
+ return rc;\r
\r
\r
memcpy(&p->block, &p->block, sizeof(block));\r
{\r
/* Load direct block 0 (index root) */\r
uint32_t root_block_addr;\r
+ int rc2;\r
int rc = ext4_fs_get_inode_data_block_index(inode_ref, 0,\r
&root_block_addr);\r
if (rc != EOK)\r
}\r
\r
/* Not found, leave untouched */\r
- ext4_block_set(fs->bdev, &leaf_block);\r
+ rc2 = ext4_block_set(fs->bdev, &leaf_block);\r
+ if(rc2 != EOK)\r
+ goto cleanup;\r
\r
if (rc != ENOENT)\r
goto cleanup;\r
/* Entry not found */\r
rc = ENOENT;\r
\r
- cleanup:\r
+cleanup:\r
/* The whole path must be released (preventing memory leak) */\r
tmp = dx_blocks;\r
\r
while (tmp <= dx_block) {\r
- ext4_block_set(fs->bdev, &tmp->block);\r
+ rc2 = ext4_block_set(fs->bdev, &tmp->block);\r
+ if (rc == EOK && rc2 != EOK)\r
+ rc = rc2;\r
++tmp;\r
}\r
\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
uint32_t count = ext4_dir_dx_countlimit_get_count(countlimit);\r
\r
struct ext4_directory_dx_entry *start_index = index_block->entries;\r
- size_t bytes = (void *) (start_index + count) - (void *) (new_index_entry);\r
+ size_t bytes = (uint8_t *) (start_index + count) - (uint8_t *) (new_index_entry);\r
\r
memmove(new_index_entry + 1, new_index_entry, bytes);\r
\r
uint32_t block_size =\r
ext4_sb_get_block_size(&inode_ref->fs->sb);\r
\r
- void *entry_buffer = malloc(block_size);\r
+ uint8_t *entry_buffer = malloc(block_size);\r
if (entry_buffer == NULL)\r
return ENOMEM;\r
\r
\r
/* Load all valid entries to the buffer */\r
struct ext4_directory_entry_ll *dentry = (void *)old_data_block->data;\r
- void *entry_buffer_ptr = entry_buffer;\r
+ uint8_t *entry_buffer_ptr = entry_buffer;\r
while ((void *)dentry < (void *)(old_data_block->data + block_size)) {\r
/* Read only valid entries */\r
if (ext4_dir_entry_ll_get_inode(dentry) && dentry->name_length) {\r
idx++;\r
}\r
\r
- dentry = (void *) dentry +\r
- ext4_dir_entry_ll_get_entry_length(dentry);\r
+ dentry = (void *)((uint8_t *)dentry +\r
+ ext4_dir_entry_ll_get_entry_length(dentry));\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