#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
- struct ext4_directory_dx_root_info *root_info, uint8_t v)\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
- struct ext4_directory_dx_root_info *root_info, uint8_t len)\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
- struct ext4_directory_dx_countlimit *climit)\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\r
+ext4_dir_dx_countlimit_get_limit(struct ext4_directory_dx_countlimit *climit)\r
{\r
return to_le16(climit->limit);\r
}\r
-void ext4_dir_dx_countlimit_set_limit(\r
- struct ext4_directory_dx_countlimit *climit, uint16_t 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\r
+ext4_dir_dx_countlimit_set_limit(struct ext4_directory_dx_countlimit *climit,\r
+ uint16_t limit)\r
{\r
climit->limit = to_le16(limit);\r
}\r
\r
-uint16_t ext4_dir_dx_countlimit_get_count(\r
- struct ext4_directory_dx_countlimit *climit)\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\r
+ext4_dir_dx_countlimit_get_count(struct ext4_directory_dx_countlimit *climit)\r
{\r
return to_le16(climit->count);\r
}\r
\r
-void ext4_dir_dx_countlimit_set_count(\r
- struct ext4_directory_dx_countlimit *climit, uint16_t 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\r
+ext4_dir_dx_countlimit_set_count(struct ext4_directory_dx_countlimit *climit,\r
+ uint16_t count)\r
{\r
climit->count = to_le16(count);\r
}\r
\r
-\r
-uint32_t ext4_dir_dx_entry_get_hash(\r
- struct ext4_directory_dx_entry *entry)\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\r
+ext4_dir_dx_entry_get_hash(struct ext4_directory_dx_entry *entry)\r
{\r
return to_le32(entry->hash);\r
}\r
-void ext4_dir_dx_entry_set_hash(\r
- struct ext4_directory_dx_entry *entry, uint32_t 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\r
+ext4_dir_dx_entry_set_hash(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
- struct ext4_directory_dx_entry *entry)\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\r
+ext4_dir_dx_entry_get_block(struct ext4_directory_dx_entry *entry)\r
{\r
return to_le32(entry->block);\r
}\r
-void ext4_dir_dx_entry_set_block(\r
- struct ext4_directory_dx_entry *entry, uint32_t 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\r
+ext4_dir_dx_entry_set_block(struct ext4_directory_dx_entry *entry,\r
+ 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
+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
int ext4_dir_dx_init(struct ext4_inode_ref *dir)\r
{\r
/* Load block 0, where will be index root located */\r
uint32_t fblock;\r
- int rc = ext4_fs_get_inode_data_block_index(dir, 0,\r
- &fblock);\r
+ int rc = ext4_fs_get_inode_data_block_index(dir, 0, &fblock);\r
if (rc != EOK)\r
return rc;\r
\r
\r
/* Set limit and current number of entries */\r
struct ext4_directory_dx_countlimit *countlimit =\r
- (struct ext4_directory_dx_countlimit *) &root->entries;\r
+ (struct ext4_directory_dx_countlimit *)&root->entries;\r
\r
ext4_dir_dx_countlimit_set_count(countlimit, 1);\r
\r
- uint32_t block_size =\r
- ext4_sb_get_block_size(&dir->fs->sb);\r
- uint32_t entry_space =\r
- block_size - 2 * sizeof(struct ext4_directory_dx_dot_entry) -\r
- sizeof(struct ext4_directory_dx_root_info);\r
+ uint32_t block_size = ext4_sb_get_block_size(&dir->fs->sb);\r
+ uint32_t entry_space = block_size -\r
+ 2 * sizeof(struct ext4_directory_dx_dot_entry) -\r
+ sizeof(struct ext4_directory_dx_root_info);\r
uint16_t root_limit = entry_space / sizeof(struct ext4_directory_dx_entry);\r
ext4_dir_dx_countlimit_set_limit(countlimit, root_limit);\r
\r
* @return Standard error code\r
*/\r
static int ext4_dir_hinfo_init(struct ext4_hash_info *hinfo,\r
- struct ext4_block *root_block, struct ext4_sblock *sb, size_t name_len,\r
- const char *name)\r
+ struct ext4_block *root_block,\r
+ struct ext4_sblock *sb, size_t name_len,\r
+ const char *name)\r
{\r
struct ext4_directory_dx_root *root =\r
- (struct ext4_directory_dx_root *) root_block->data;\r
+ (struct ext4_directory_dx_root *)root_block->data;\r
\r
if ((root->info.hash_version != EXT2_HTREE_LEGACY) &&\r
- (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&\r
- (root->info.hash_version != EXT2_HTREE_TEA))\r
+ (root->info.hash_version != EXT2_HTREE_HALF_MD4) &&\r
+ (root->info.hash_version != EXT2_HTREE_TEA))\r
return EXT4_ERR_BAD_DX_DIR;\r
\r
/* Check unused flags */\r
entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);\r
\r
uint16_t limit = ext4_dir_dx_countlimit_get_limit(\r
- (struct ext4_directory_dx_countlimit *) &root->entries);\r
+ (struct ext4_directory_dx_countlimit *)&root->entries);\r
if (limit != entry_space)\r
return EXT4_ERR_BAD_DX_DIR;\r
\r
/* Check hash version and modify if necessary */\r
- hinfo->hash_version =\r
- ext4_dir_dx_root_info_get_hash_version(&root->info);\r
+ hinfo->hash_version = ext4_dir_dx_root_info_get_hash_version(&root->info);\r
if ((hinfo->hash_version <= EXT2_HTREE_TEA) &&\r
- (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {\r
+ (ext4_sb_check_flag(sb, EXT4_SUPERBLOCK_FLAGS_UNSIGNED_HASH))) {\r
/* Use unsigned hash */\r
hinfo->hash_version += 3;\r
}\r
* @return Standard error code\r
*/\r
static int ext4_dir_dx_get_leaf(struct ext4_hash_info *hinfo,\r
- struct ext4_inode_ref *inode_ref, struct ext4_block *root_block,\r
- struct ext4_directory_dx_block **dx_block,\r
- struct ext4_directory_dx_block *dx_blocks)\r
+ struct ext4_inode_ref *inode_ref,\r
+ struct ext4_block *root_block,\r
+ struct ext4_directory_dx_block **dx_block,\r
+ struct ext4_directory_dx_block *dx_blocks)\r
{\r
struct ext4_directory_dx_block *tmp_dx_block = dx_blocks;\r
struct ext4_directory_dx_root *root =\r
- (struct ext4_directory_dx_root *) root_block->data;\r
+ (struct ext4_directory_dx_root *)root_block->data;\r
struct ext4_directory_dx_entry *entries =\r
- (struct ext4_directory_dx_entry *) &root->entries;\r
+ (struct ext4_directory_dx_entry *)&root->entries;\r
\r
uint16_t limit = ext4_dir_dx_countlimit_get_limit(\r
- (struct ext4_directory_dx_countlimit *) entries);\r
+ (struct ext4_directory_dx_countlimit *)entries);\r
uint8_t indirect_level =\r
- ext4_dir_dx_root_info_get_indirect_levels(&root->info);\r
+ ext4_dir_dx_root_info_get_indirect_levels(&root->info);\r
\r
struct ext4_block *tmp_block = root_block;\r
struct ext4_directory_dx_entry *p;\r
/* Walk through the index tree */\r
while (true) {\r
uint16_t count = ext4_dir_dx_countlimit_get_count(\r
- (struct ext4_directory_dx_countlimit *) entries);\r
+ (struct ext4_directory_dx_countlimit *)entries);\r
if ((count == 0) || (count > limit))\r
return EXT4_ERR_BAD_DX_DIR;\r
\r
indirect_level--;\r
\r
uint32_t fblock;\r
- int rc = ext4_fs_get_inode_data_block_index(inode_ref,\r
- next_block, &fblock);\r
+ int rc =\r
+ ext4_fs_get_inode_data_block_index(inode_ref, next_block, &fblock);\r
if (rc != EOK)\r
return rc;\r
\r
if (rc != EOK)\r
return rc;\r
\r
- entries = ((struct ext4_directory_dx_node *) tmp_block->data)->entries;\r
+ entries = ((struct ext4_directory_dx_node *)tmp_block->data)->entries;\r
limit = ext4_dir_dx_countlimit_get_limit(\r
- (struct ext4_directory_dx_countlimit *) entries);\r
+ (struct ext4_directory_dx_countlimit *)entries);\r
\r
- uint16_t entry_space =\r
- ext4_sb_get_block_size(&inode_ref->fs->sb) -\r
- sizeof(struct ext4_fake_directory_entry);\r
+ uint16_t entry_space = ext4_sb_get_block_size(&inode_ref->fs->sb) -\r
+ sizeof(struct ext4_fake_directory_entry);\r
\r
entry_space = entry_space / sizeof(struct ext4_directory_dx_entry);\r
\r
* @return Standard Error codee\r
*/\r
static int ext4_dir_dx_next_block(struct ext4_inode_ref *inode_ref,\r
- uint32_t hash, struct ext4_directory_dx_block *dx_block,\r
- struct ext4_directory_dx_block *dx_blocks)\r
+ uint32_t hash,\r
+ struct ext4_directory_dx_block *dx_block,\r
+ struct ext4_directory_dx_block *dx_blocks)\r
{\r
uint32_t num_handles = 0;\r
struct ext4_directory_dx_block *p = dx_block;\r
while (true) {\r
p->position++;\r
uint16_t count = ext4_dir_dx_countlimit_get_count(\r
- (struct ext4_directory_dx_countlimit *) p->entries);\r
+ (struct ext4_directory_dx_countlimit *)p->entries);\r
\r
if (p->position < p->entries + count)\r
break;\r
\r
/* Fill new path */\r
while (num_handles--) {\r
- uint32_t block_idx =\r
- ext4_dir_dx_entry_get_block(p->position);\r
+ uint32_t block_idx = ext4_dir_dx_entry_get_block(p->position);\r
uint32_t block_addr;\r
\r
- int rc = ext4_fs_get_inode_data_block_index(inode_ref,\r
- block_idx, &block_addr);\r
- if(rc != EOK)\r
+ int rc = ext4_fs_get_inode_data_block_index(inode_ref, block_idx,\r
+ &block_addr);\r
+ if (rc != EOK)\r
return rc;\r
\r
-\r
struct ext4_block block;\r
rc = ext4_block_get(inode_ref->fs->bdev, &block, block_addr);\r
if (rc != EOK)\r
\r
/* Don't forget to put old block (prevent memory leak) */\r
rc = ext4_block_set(inode_ref->fs->bdev, &p->block);\r
- if(rc != EOK)\r
+ if (rc != EOK)\r
return rc;\r
\r
-\r
memcpy(&p->block, &p->block, sizeof(block));\r
- p->entries = ((struct ext4_directory_dx_node *) block.data)->entries;\r
+ p->entries = ((struct ext4_directory_dx_node *)block.data)->entries;\r
p->position = p->entries;\r
}\r
\r
return ENOENT;\r
}\r
\r
-\r
-\r
-int ext4_dir_dx_find_entry(struct ext4_directory_search_result * result,\r
- struct ext4_inode_ref *inode_ref, size_t name_len, const char *name)\r
+int ext4_dir_dx_find_entry(struct ext4_directory_search_result *result,\r
+ struct ext4_inode_ref *inode_ref, size_t name_len,\r
+ const char *name)\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
+ int rc = ext4_fs_get_inode_data_block_index(inode_ref, 0, &root_block_addr);\r
if (rc != EOK)\r
return rc;\r
\r
\r
/* Initialize hash info (compute hash value) */\r
struct ext4_hash_info hinfo;\r
- rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb,\r
- name_len, name);\r
+ rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);\r
if (rc != EOK) {\r
ext4_block_set(fs->bdev, &root_block);\r
return EXT4_ERR_BAD_DX_DIR;\r
struct ext4_directory_dx_block *dx_block;\r
struct ext4_directory_dx_block *tmp;\r
\r
- rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block,\r
- &dx_block, dx_blocks);\r
+ rc = ext4_dir_dx_get_leaf(&hinfo, inode_ref, &root_block, &dx_block,\r
+ dx_blocks);\r
if (rc != EOK) {\r
ext4_block_set(fs->bdev, &root_block);\r
return EXT4_ERR_BAD_DX_DIR;\r
do {\r
/* Load leaf block */\r
uint32_t leaf_block_idx =\r
- ext4_dir_dx_entry_get_block(dx_block->position);\r
+ ext4_dir_dx_entry_get_block(dx_block->position);\r
uint32_t leaf_block_addr;\r
\r
- rc = ext4_fs_get_inode_data_block_index(inode_ref,\r
- leaf_block_idx, &leaf_block_addr);\r
+ rc = ext4_fs_get_inode_data_block_index(inode_ref, leaf_block_idx,\r
+ &leaf_block_addr);\r
if (rc != EOK)\r
goto cleanup;\r
\r
\r
/* Linear search inside block */\r
struct ext4_directory_entry_ll *res_dentry;\r
- rc = ext4_dir_find_in_block(&leaf_block, &fs->sb,\r
- name_len, name, &res_dentry);\r
+ rc = ext4_dir_find_in_block(&leaf_block, &fs->sb, name_len, name,\r
+ &res_dentry);\r
\r
/* Found => return it */\r
if (rc == EOK) {\r
\r
/* Not found, leave untouched */\r
rc2 = ext4_block_set(fs->bdev, &leaf_block);\r
- if(rc2 != EOK)\r
+ if (rc2 != EOK)\r
goto cleanup;\r
\r
if (rc != ENOENT)\r
goto cleanup;\r
\r
/* check if the next block could be checked */\r
- rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash,\r
- dx_block, &dx_blocks[0]);\r
+ rc = ext4_dir_dx_next_block(inode_ref, hinfo.hash, dx_block,\r
+ &dx_blocks[0]);\r
if (rc < 0)\r
goto cleanup;\r
} while (rc == ENOENT);\r
return rc;\r
}\r
\r
+#if CONFIG_DIR_INDEX_COMB_SORT\r
+#define SWAP_ENTRY(se1, se2) \\r
+ do { \\r
+ struct ext4_dx_sort_entry tmp = se1; \\r
+ se1 = se2; \\r
+ se2 = tmp; \\r
+ \\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
* @param iblock Logical number of child block\r
*\r
*/\r
-static void ext4_dir_dx_insert_entry(\r
- struct ext4_directory_dx_block *index_block, uint32_t hash,\r
- uint32_t iblock)\r
+static void\r
+ext4_dir_dx_insert_entry(struct ext4_directory_dx_block *index_block,\r
+ uint32_t hash, uint32_t iblock)\r
{\r
struct ext4_directory_dx_entry *old_index_entry = index_block->position;\r
struct ext4_directory_dx_entry *new_index_entry = old_index_entry + 1;\r
\r
struct ext4_directory_dx_countlimit *countlimit =\r
- (struct ext4_directory_dx_countlimit *) index_block->entries;\r
+ (struct ext4_directory_dx_countlimit *)index_block->entries;\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 = (uint8_t *) (start_index + count) - (uint8_t *) (new_index_entry);\r
+ size_t bytes =\r
+ (uint8_t *)(start_index + count) - (uint8_t *)(new_index_entry);\r
\r
memmove(new_index_entry + 1, new_index_entry, bytes);\r
\r
* @param new_data_block Output value for newly allocated data block\r
*/\r
static int ext4_dir_dx_split_data(struct ext4_inode_ref *inode_ref,\r
- struct ext4_hash_info *hinfo, struct ext4_block *old_data_block,\r
- struct ext4_directory_dx_block *index_block,\r
- struct ext4_block *new_data_block)\r
+ struct ext4_hash_info *hinfo,\r
+ struct ext4_block *old_data_block,\r
+ struct ext4_directory_dx_block *index_block,\r
+ struct ext4_block *new_data_block)\r
{\r
int rc = EOK;\r
\r
/* Allocate buffer for directory entries */\r
- uint32_t block_size =\r
- ext4_sb_get_block_size(&inode_ref->fs->sb);\r
+ uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);\r
\r
uint8_t *entry_buffer = malloc(block_size);\r
if (entry_buffer == NULL)\r
\r
/* dot entry has the smallest size available */\r
uint32_t max_entry_count =\r
- block_size / sizeof(struct ext4_directory_dx_dot_entry);\r
+ block_size / sizeof(struct ext4_directory_dx_dot_entry);\r
\r
/* Allocate sort entry */\r
struct ext4_dx_sort_entry *sort_array =\r
- malloc(max_entry_count * sizeof(struct ext4_dx_sort_entry));\r
+ malloc(max_entry_count * sizeof(struct ext4_dx_sort_entry));\r
\r
if (sort_array == NULL) {\r
free(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
- uint8_t len = ext4_dir_entry_ll_get_name_length(\r
- &inode_ref->fs->sb, dentry);\r
+ uint8_t len =\r
+ ext4_dir_entry_ll_get_name_length(&inode_ref->fs->sb, dentry);\r
\r
- rc = ext4_dir_dx_hash_string(&tmp_hinfo, len, (char*)dentry->name);\r
- if(rc != EOK) {\r
+ rc = ext4_dir_dx_hash_string(&tmp_hinfo, len, (char *)dentry->name);\r
+ if (rc != EOK) {\r
free(sort_array);\r
free(entry_buffer);\r
return rc;\r
}\r
\r
dentry = (void *)((uint8_t *)dentry +\r
- ext4_dir_entry_ll_get_entry_length(dentry));\r
+ ext4_dir_entry_ll_get_entry_length(dentry));\r
}\r
\r
- /* Sort all entries */\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
+ ext4_dir_dx_entry_comparator);\r
+#endif\r
/* Allocate new block for store the second part of entries */\r
uint32_t new_fblock;\r
uint32_t new_iblock;\r
- rc = ext4_fs_append_inode_block(inode_ref, &new_fblock,\r
- &new_iblock);\r
+ rc = ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);\r
if (rc != EOK) {\r
free(sort_array);\r
free(entry_buffer);\r
\r
/* Load new block */\r
struct ext4_block new_data_block_tmp;\r
- rc = ext4_block_get(inode_ref->fs->bdev, &new_data_block_tmp,\r
- new_fblock);\r
+ rc = ext4_block_get(inode_ref->fs->bdev, &new_data_block_tmp, new_fblock);\r
if (rc != EOK) {\r
free(sort_array);\r
free(entry_buffer);\r
uint32_t current_size = 0;\r
uint32_t mid = 0;\r
uint32_t i;\r
- for ( i = 0; i < idx; ++i) {\r
+ for (i = 0; i < idx; ++i) {\r
if ((current_size + sort_array[i].rec_len) > (block_size / 2)) {\r
new_hash = sort_array[i].hash;\r
mid = i;\r
\r
/* Check hash collision */\r
uint32_t continued = 0;\r
- if (new_hash == sort_array[mid-1].hash)\r
+ if (new_hash == sort_array[mid - 1].hash)\r
continued = 1;\r
\r
uint32_t offset = 0;\r
\r
struct ext4_directory_entry_ll *tmp = ptr;\r
if (i < (mid - 1))\r
- ext4_dir_entry_ll_set_entry_length(tmp,\r
- sort_array[i].rec_len);\r
+ ext4_dir_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);\r
else\r
- ext4_dir_entry_ll_set_entry_length(tmp,\r
- block_size - offset);\r
+ ext4_dir_entry_ll_set_entry_length(tmp, block_size - offset);\r
\r
offset += sort_array[i].rec_len;\r
}\r
\r
struct ext4_directory_entry_ll *tmp = ptr;\r
if (i < (idx - 1))\r
- ext4_dir_entry_ll_set_entry_length(tmp,\r
- sort_array[i].rec_len);\r
+ ext4_dir_entry_ll_set_entry_length(tmp, sort_array[i].rec_len);\r
else\r
- ext4_dir_entry_ll_set_entry_length(tmp,\r
- block_size - offset);\r
+ ext4_dir_entry_ll_set_entry_length(tmp, block_size - offset);\r
\r
offset += sort_array[i].rec_len;\r
}\r
free(sort_array);\r
free(entry_buffer);\r
\r
- ext4_dir_dx_insert_entry(index_block, new_hash + continued,\r
- new_iblock);\r
+ ext4_dir_dx_insert_entry(index_block, new_hash + continued, new_iblock);\r
\r
*new_data_block = new_data_block_tmp;\r
\r
* @param dx_block Leaf block to be split if needed\r
* @return Error code\r
*/\r
-static int ext4_dir_dx_split_index(struct ext4_inode_ref *inode_ref,\r
- struct ext4_directory_dx_block *dx_blocks,\r
- struct ext4_directory_dx_block *dx_block,\r
- struct ext4_directory_dx_block **new_dx_block)\r
+static int\r
+ext4_dir_dx_split_index(struct ext4_inode_ref *inode_ref,\r
+ struct ext4_directory_dx_block *dx_blocks,\r
+ struct ext4_directory_dx_block *dx_block,\r
+ struct ext4_directory_dx_block **new_dx_block)\r
{\r
struct ext4_directory_dx_entry *entries;\r
\r
if (dx_block == dx_blocks)\r
entries =\r
- ((struct ext4_directory_dx_root *) dx_block->block.data)->entries;\r
+ ((struct ext4_directory_dx_root *)dx_block->block.data)->entries;\r
else\r
entries =\r
- ((struct ext4_directory_dx_node *) dx_block->block.data)->entries;\r
+ ((struct ext4_directory_dx_node *)dx_block->block.data)->entries;\r
\r
struct ext4_directory_dx_countlimit *countlimit =\r
- (struct ext4_directory_dx_countlimit *) entries;\r
+ (struct ext4_directory_dx_countlimit *)entries;\r
\r
- uint16_t leaf_limit =\r
- ext4_dir_dx_countlimit_get_limit(countlimit);\r
- uint16_t leaf_count =\r
- ext4_dir_dx_countlimit_get_count(countlimit);\r
+ uint16_t leaf_limit = ext4_dir_dx_countlimit_get_limit(countlimit);\r
+ uint16_t leaf_count = ext4_dir_dx_countlimit_get_count(countlimit);\r
\r
/* Check if is necessary to split index block */\r
if (leaf_limit == leaf_count) {\r
size_t levels = dx_block - dx_blocks;\r
\r
struct ext4_directory_dx_entry *root_entries =\r
- ((struct ext4_directory_dx_root *) dx_blocks[0].block.data)->entries;\r
+ ((struct ext4_directory_dx_root *)dx_blocks[0].block.data)->entries;\r
\r
struct ext4_directory_dx_countlimit *root_countlimit =\r
- (struct ext4_directory_dx_countlimit *) root_entries;\r
- uint16_t root_limit =\r
- ext4_dir_dx_countlimit_get_limit(root_countlimit);\r
- uint16_t root_count =\r
- ext4_dir_dx_countlimit_get_count(root_countlimit);\r
+ (struct ext4_directory_dx_countlimit *)root_entries;\r
+ uint16_t root_limit = ext4_dir_dx_countlimit_get_limit(root_countlimit);\r
+ uint16_t root_count = ext4_dir_dx_countlimit_get_count(root_countlimit);\r
\r
/* Linux limitation */\r
if ((levels > 0) && (root_limit == root_count))\r
/* Add new block to directory */\r
uint32_t new_fblock;\r
uint32_t new_iblock;\r
- int rc = ext4_fs_append_inode_block(inode_ref,\r
- &new_fblock, &new_iblock);\r
+ int rc =\r
+ ext4_fs_append_inode_block(inode_ref, &new_fblock, &new_iblock);\r
if (rc != EOK)\r
return rc;\r
\r
/* load new block */\r
struct ext4_block new_block;\r
- rc = ext4_block_get(inode_ref->fs->bdev, &new_block,\r
- new_fblock);\r
+ rc = ext4_block_get(inode_ref->fs->bdev, &new_block, new_fblock);\r
if (rc != EOK)\r
return rc;\r
\r
- struct ext4_directory_dx_node *new_node = (void *)new_block.data;\r
+ struct ext4_directory_dx_node *new_node = (void *)new_block.data;\r
struct ext4_directory_dx_entry *new_entries = new_node->entries;\r
\r
memset(&new_node->fake, 0, sizeof(struct ext4_fake_directory_entry));\r
\r
- uint32_t block_size =\r
- ext4_sb_get_block_size(&inode_ref->fs->sb);\r
+ uint32_t block_size = ext4_sb_get_block_size(&inode_ref->fs->sb);\r
\r
new_node->fake.entry_length = block_size;\r
\r
uint32_t count_left = leaf_count / 2;\r
uint32_t count_right = leaf_count - count_left;\r
uint32_t hash_right =\r
- ext4_dir_dx_entry_get_hash(entries + count_left);\r
+ ext4_dir_dx_entry_get_hash(entries + count_left);\r
\r
/* Copy data to new node */\r
- memcpy((void *) new_entries, (void *) (entries + count_left),\r
- count_right * sizeof(struct ext4_directory_dx_entry));\r
+ memcpy((void *)new_entries, (void *)(entries + count_left),\r
+ count_right * sizeof(struct ext4_directory_dx_entry));\r
\r
/* Initialize new node */\r
struct ext4_directory_dx_countlimit *left_countlimit =\r
- (struct ext4_directory_dx_countlimit *) entries;\r
+ (struct ext4_directory_dx_countlimit *)entries;\r
struct ext4_directory_dx_countlimit *right_countlimit =\r
- (struct ext4_directory_dx_countlimit *) new_entries;\r
+ (struct ext4_directory_dx_countlimit *)new_entries;\r
\r
ext4_dir_dx_countlimit_set_count(left_countlimit, count_left);\r
ext4_dir_dx_countlimit_set_count(right_countlimit, count_right);\r
\r
uint32_t entry_space =\r
- block_size - sizeof(struct ext4_fake_directory_entry);\r
+ block_size - sizeof(struct ext4_fake_directory_entry);\r
uint32_t node_limit =\r
- entry_space / sizeof(struct ext4_directory_dx_entry);\r
+ entry_space / sizeof(struct ext4_directory_dx_entry);\r
ext4_dir_dx_countlimit_set_limit(right_countlimit, node_limit);\r
\r
/* Which index block is target for new entry */\r
\r
struct ext4_block block_tmp = dx_block->block;\r
\r
-\r
dx_block->block = new_block;\r
\r
- dx_block->position =\r
- new_entries + position_index - count_left;\r
+ dx_block->position = new_entries + position_index - count_left;\r
dx_block->entries = new_entries;\r
\r
new_block = block_tmp;\r
/* Create second level index */\r
\r
/* Copy data from root to child block */\r
- memcpy((void *) new_entries, (void *) entries,\r
- leaf_count * sizeof(struct ext4_directory_dx_entry));\r
+ memcpy((void *)new_entries, (void *)entries,\r
+ leaf_count * sizeof(struct ext4_directory_dx_entry));\r
\r
struct ext4_directory_dx_countlimit *new_countlimit =\r
- (struct ext4_directory_dx_countlimit *) new_entries;\r
+ (struct ext4_directory_dx_countlimit *)new_entries;\r
\r
uint32_t entry_space =\r
- block_size - sizeof(struct ext4_fake_directory_entry);\r
+ block_size - sizeof(struct ext4_fake_directory_entry);\r
uint32_t node_limit =\r
- entry_space / sizeof(struct ext4_directory_dx_entry);\r
+ entry_space / sizeof(struct ext4_directory_dx_entry);\r
ext4_dir_dx_countlimit_set_limit(new_countlimit, node_limit);\r
\r
/* Set values in root node */\r
struct ext4_directory_dx_countlimit *new_root_countlimit =\r
- (struct ext4_directory_dx_countlimit *) entries;\r
+ (struct ext4_directory_dx_countlimit *)entries;\r
\r
ext4_dir_dx_countlimit_set_count(new_root_countlimit, 1);\r
ext4_dir_dx_entry_set_block(entries, new_iblock);\r
\r
- ((struct ext4_directory_dx_root *)\r
- dx_blocks[0].block.data)->info.indirect_levels = 1;\r
+ ((struct ext4_directory_dx_root *)dx_blocks[0].block.data)\r
+ ->info.indirect_levels = 1;\r
\r
/* Add new entry to the path */\r
dx_block = dx_blocks + 1;\r
}\r
\r
int ext4_dir_dx_add_entry(struct ext4_inode_ref *parent,\r
- struct ext4_inode_ref *child, const char *name)\r
+ struct ext4_inode_ref *child, const char *name)\r
{\r
int rc2 = EOK;\r
\r
/* Get direct block 0 (index root) */\r
uint32_t root_block_addr;\r
- int rc = ext4_fs_get_inode_data_block_index(parent, 0,\r
- &root_block_addr);\r
+ int rc = ext4_fs_get_inode_data_block_index(parent, 0, &root_block_addr);\r
if (rc != EOK)\r
return rc;\r
\r
/* Initialize hinfo structure (mainly compute hash) */\r
uint32_t name_len = strlen(name);\r
struct ext4_hash_info hinfo;\r
- rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb,\r
- name_len, name);\r
+ rc = ext4_dir_hinfo_init(&hinfo, &root_block, &fs->sb, name_len, name);\r
if (rc != EOK) {\r
ext4_block_set(fs->bdev, &root_block);\r
return EXT4_ERR_BAD_DX_DIR;\r
struct ext4_directory_dx_block *dx_block;\r
struct ext4_directory_dx_block *dx_it;\r
\r
- rc = ext4_dir_dx_get_leaf(&hinfo, parent, &root_block,\r
- &dx_block, dx_blocks);\r
+ rc =\r
+ ext4_dir_dx_get_leaf(&hinfo, parent, &root_block, &dx_block, dx_blocks);\r
if (rc != EOK) {\r
rc = EXT4_ERR_BAD_DX_DIR;\r
goto release_index;\r
}\r
\r
/* Try to insert to existing data block */\r
- uint32_t leaf_block_idx =\r
- ext4_dir_dx_entry_get_block(dx_block->position);\r
+ uint32_t leaf_block_idx = ext4_dir_dx_entry_get_block(dx_block->position);\r
uint32_t leaf_block_addr;\r
rc = ext4_fs_get_inode_data_block_index(parent, leaf_block_idx,\r
- &leaf_block_addr);\r
+ &leaf_block_addr);\r
if (rc != EOK)\r
goto release_index;\r
\r
if (rc != EOK)\r
goto release_index;\r
\r
-\r
/* Check if insert operation passed */\r
- rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child,\r
- name, name_len);\r
+ rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child, name,\r
+ name_len);\r
if (rc == EOK)\r
goto release_target_index;\r
\r
-\r
/* Split entries to two blocks (includes sorting by hash value) */\r
struct ext4_block new_block;\r
- rc = ext4_dir_dx_split_data(parent, &hinfo, &target_block,\r
- dx_block, &new_block);\r
+ rc = ext4_dir_dx_split_data(parent, &hinfo, &target_block, dx_block,\r
+ &new_block);\r
if (rc != EOK) {\r
rc2 = rc;\r
goto release_target_index;\r
\r
/* Where to save new entry */\r
uint32_t new_block_hash =\r
- ext4_dir_dx_entry_get_hash(dx_block->position + 1);\r
+ ext4_dir_dx_entry_get_hash(dx_block->position + 1);\r
if (hinfo.hash >= new_block_hash)\r
- rc = ext4_dir_try_insert_entry(&fs->sb, &new_block,\r
- child, name, name_len);\r
+ rc = ext4_dir_try_insert_entry(&fs->sb, &new_block, child, name,\r
+ name_len);\r
else\r
- rc = ext4_dir_try_insert_entry(&fs->sb, &target_block,\r
- child, name, name_len);\r
+ rc = ext4_dir_try_insert_entry(&fs->sb, &target_block, child, name,\r
+ name_len);\r
\r
/* Cleanup */\r
rc = ext4_block_set(fs->bdev, &new_block);\r
if (rc != EOK)\r
return rc;\r
\r
- /* Cleanup operations */\r
+/* Cleanup operations */\r
\r
- release_target_index:\r
+release_target_index:\r
rc2 = rc;\r
\r
rc = ext4_block_set(fs->bdev, &target_block);\r
if (rc != EOK)\r
return rc;\r
\r
- release_index:\r
+release_index:\r
if (rc != EOK)\r
rc2 = rc;\r
\r
/**\r
* @}\r
*/\r
-\r
projects / lwext4.git / blobdiff