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