1、前言
前文已经讲述了如何根据索引号获取实际的文件内容。对于文件而言，到了这里已经结束了。
但是对于文件夹来说，我们还需要从数据块中解析出对应的数据。
而在文件系统的实现中，文件夹的实际存储方式有着两种不同的实现，经典的线性布局方式和全新的Hash树布局。
2、经典线性布局
线性布局，顾名思义，文件夹的所有子项目以线性方式存储在数据块中。项目的存储结构如下：
#define EXT2_NAME_LEN 255
typedef struct {ub32 inode; /* Inode number */ub16 rec_len; /* Directory entry length */union {struct {ub8 name_len; /* Name length */ub8 file_type;};ub16 name_len_v2; /* Name length */};b8 name[EXT2_NAME_LEN]; /* File name */
} app_ext4_dir_entry;
| 名称 | 含义 |
|---|---|
| inode | 索引号 |
| rec_len | 当前结构的长度 |
| name_len/name_len_v2 | 名称长度 |
| file_type | 开启file_type特性，用于存储文件类型。 |
| name | 文件或文件夹名称 |
在内联文件夹中，通常使用线性布局的方式管理。
3、Hash树布局
Hash树布局是为了提升经典线性布局的性能而诞生的一种解决方案。即在原有的线性布局基础上加上Hash树，从而提升文件系统遍历的性能。
因此Hash树布局在实现上与经典线性布局完全兼容，也就是说，同样可以使用线性布局的方式遍历Hash树管理的文件系统。
Hash树的根节点中，前24个字节用于存储当前目录和父目录的app_ext4_dir_entry结构，紧接其后的就是app_ext4_dx_header、app_ext4_dx_info、app_ext4_dx_entry结构。其中app_ext4_dir_entry.indirect_levels代表Hash树的深度。
在其余节点中，前8个字节用于存储空的的app_ext4_dir_entry结构，然后是app_ext4_dx_info、app_ext4_dx_entry结构。
而最后的叶子节点，就是原本的经典线性布局。
| 名称 | 含义 |
|---|---|
| app_ext4_dx_info.limit | 当前entry最大可以管理的app_ext4_dx_entry数，包含自身 |
| app_ext4_dx_info.count | 实际管理的app_ext4_dx_entry数，包含自身。 |
| app_ext4_dx_info.block | hash = 0 时指向的物理块号 |
| app_ext4_dx_entry.hash | hash值 |
| app_ext4_dx_entry.block | hash值对应的块号。 |
typedef struct {ub32 reserved_zero;ub8 hash_version; /* 0 now, 1 at release */ub8 info_length; /* 8 */ub8 indirect_levels;ub8 unused_flags;
} app_ext4_dx_header;typedef struct {ub16 limit; // maximum number of dx_entries that can follow this headerub16 count; // actual number of dx_entries that can follow this headerub32 block; // The block number that goes with the lowest hash value of// this block
} app_ext4_dx_info;typedef struct {ub32 hash;ub32 block;
} app_ext4_dx_entry;bool ReadIndex(const void *entry_data, b32 depth, b32 cur_depth,CIndexList *dirlist) {scope::ScopedPtr<b8> dir_entry_data;app_ext4_dx_info *dx_info = NULL;if (depth) {app_ext4_dir_entry *dir_entry = (app_ext4_dir_entry *)entry_data;if (dir_entry->inode || dir_entry->name_len) return false;dx_info = (app_ext4_dx_info *)((b8 *)dir_entry + 8);++cur_depth;} else {app_ext4_dx_header *dx_header = (app_ext4_dx_header *)entry_data;depth = dx_header->indirect_levels;dx_info = (app_ext4_dx_info *)((b8 *)dx_header + dx_header->info_length);cur_depth = 0;}dir_entry_data = new b8[ext_volume_->block_size_];app_ext4_dx_entry *dx_entry =(app_ext4_dx_entry *)((b8 *)dx_info + sizeof(app_ext4_dx_info));for (int i = 0; i < dx_info->count; i++) {if (i) {if (lseek64(ext_volume_->fd_,block_list_[dx_entry->block] * (b64)ext_volume_->block_size_,SEEK_SET) < 0)return false;} else {if (lseek64(ext_volume_->fd_,block_list_[dx_info->block] * (b64)ext_volume_->block_size_,SEEK_SET) < 0)return false;}if (ext_volume_->block_size_ !=read(ext_volume_->fd_, dir_entry_data, ext_volume_->block_size_))return false;if (depth == cur_depth) {if (!ReadLinear(dir_entry_data, dirlist)) return false;} else {if (!ReadIndex(dir_entry_data, depth, cur_depth, dirlist)) return false;}if (i)dx_entry =(app_ext4_dx_entry *)((b8 *)dx_entry + sizeof(app_ext4_dx_entry));}return true;
}if (inode_info_->i_flags & EXT4_INDEX_FL) {if (!ReadIndex((b8 *)dir_entry_data + 24, 0, 0, dirlist)) return false;break;
}
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
