1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org> 5 * Copyright (c) 2012, Vyacheslav Matyushin 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 #ifndef _FS_EXT2FS_HTREE_H_ 31 #define _FS_EXT2FS_HTREE_H_ 32 33 /* EXT3 HTree directory indexing */ 34 35 #define EXT2_HTREE_LEGACY 0 36 #define EXT2_HTREE_HALF_MD4 1 37 #define EXT2_HTREE_TEA 2 38 #define EXT2_HTREE_LEGACY_UNSIGNED 3 39 #define EXT2_HTREE_HALF_MD4_UNSIGNED 4 40 #define EXT2_HTREE_TEA_UNSIGNED 5 41 42 #define EXT2_HTREE_EOF 0x7FFFFFFF 43 44 struct ext2fs_fake_direct { 45 uint32_t e2d_ino; /* inode number of entry */ 46 uint16_t e2d_reclen; /* length of this record */ 47 uint8_t e2d_namlen; /* length of string in d_name */ 48 uint8_t e2d_type; /* file type */ 49 }; 50 51 struct ext2fs_htree_count { 52 uint16_t h_entries_max; 53 uint16_t h_entries_num; 54 }; 55 56 struct ext2fs_htree_entry { 57 uint32_t h_hash; 58 uint32_t h_blk; 59 }; 60 61 /* 62 * This goes at the end of each htree block. 63 */ 64 struct ext2fs_htree_tail { 65 uint32_t ht_reserved; 66 uint32_t ht_checksum; /* crc32c(uuid+inum+dirblock) */ 67 }; 68 69 struct ext2fs_htree_root_info { 70 uint32_t h_reserved1; 71 uint8_t h_hash_version; 72 uint8_t h_info_len; 73 uint8_t h_ind_levels; 74 uint8_t h_reserved2; 75 }; 76 77 struct ext2fs_htree_root { 78 struct ext2fs_fake_direct h_dot; 79 char h_dot_name[4]; 80 struct ext2fs_fake_direct h_dotdot; 81 char h_dotdot_name[4]; 82 struct ext2fs_htree_root_info h_info; 83 struct ext2fs_htree_entry h_entries[0]; 84 }; 85 86 struct ext2fs_htree_node { 87 struct ext2fs_fake_direct h_fake_dirent; 88 struct ext2fs_htree_entry h_entries[0]; 89 }; 90 91 struct ext2fs_htree_lookup_level { 92 struct buf *h_bp; 93 struct ext2fs_htree_entry *h_entries; 94 struct ext2fs_htree_entry *h_entry; 95 }; 96 97 struct ext2fs_htree_lookup_info { 98 struct ext2fs_htree_lookup_level h_levels[2]; 99 uint32_t h_levels_num; 100 }; 101 102 struct ext2fs_htree_sort_entry { 103 uint16_t h_offset; 104 uint16_t h_size; 105 uint32_t h_hash; 106 }; 107 108 #endif /* !_FS_EXT2FS_HTREE_H_ */ 109