htree.h revision 262723
1106184Smarcel/*- 2106184Smarcel * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org> 3106184Smarcel * Copyright (c) 2012, Vyacheslav Matyushin 4106184Smarcel * All rights reserved. 5106184Smarcel * 6106184Smarcel * Redistribution and use in source and binary forms, with or without 7106184Smarcel * modification, are permitted provided that the following conditions 8106184Smarcel * are met: 9106184Smarcel * 1. Redistributions of source code must retain the above copyright 10106184Smarcel * notice, this list of conditions and the following disclaimer. 11106184Smarcel * 2. Redistributions in binary form must reproduce the above copyright 12106184Smarcel * notice, this list of conditions and the following disclaimer in the 13106184Smarcel * documentation and/or other materials provided with the distribution. 14106184Smarcel * 15106184Smarcel * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 16106184Smarcel * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17106184Smarcel * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18106184Smarcel * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 19106184Smarcel * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20106184Smarcel * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21106184Smarcel * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22106184Smarcel * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23106184Smarcel * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24106184Smarcel * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25106184Smarcel * SUCH DAMAGE. 26106184Smarcel * 27106184Smarcel * $FreeBSD: stable/10/sys/fs/ext2fs/htree.h 262723 2014-03-04 03:10:31Z pfg $ 28106184Smarcel */ 29106184Smarcel 30106184Smarcel#ifndef _FS_EXT2FS_HTREE_H_ 31106184Smarcel#define _FS_EXT2FS_HTREE_H_ 32106184Smarcel 33106184Smarcel/* EXT3 HTree directory indexing */ 34106184Smarcel 35106184Smarcel#define EXT2_HTREE_LEGACY 0 36106184Smarcel#define EXT2_HTREE_HALF_MD4 1 37106184Smarcel#define EXT2_HTREE_TEA 2 38106184Smarcel#define EXT2_HTREE_LEGACY_UNSIGNED 3 39106184Smarcel#define EXT2_HTREE_HALF_MD4_UNSIGNED 4 40106184Smarcel#define EXT2_HTREE_TEA_UNSIGNED 5 41106184Smarcel 42106184Smarcel#define EXT2_HTREE_EOF 0x7FFFFFFF 43106184Smarcel 44106184Smarcelstruct ext2fs_fake_direct { 45106184Smarcel uint32_t e2d_ino; /* inode number of entry */ 46106184Smarcel uint16_t e2d_reclen; /* length of this record */ 47106184Smarcel uint8_t e2d_namlen; /* length of string in d_name */ 48106184Smarcel uint8_t e2d_type; /* file type */ 49106184Smarcel}; 50106184Smarcel 51106184Smarcelstruct ext2fs_htree_count { 52106184Smarcel uint16_t h_entries_max; 53106184Smarcel uint16_t h_entries_num; 54106184Smarcel}; 55106184Smarcel 56106184Smarcelstruct ext2fs_htree_entry { 57106184Smarcel uint32_t h_hash; 58106184Smarcel uint32_t h_blk; 59106184Smarcel}; 60106184Smarcel 61106184Smarcelstruct ext2fs_htree_root_info { 62106184Smarcel uint32_t h_reserved1; 63106184Smarcel uint8_t h_hash_version; 64106184Smarcel uint8_t h_info_len; 65106184Smarcel uint8_t h_ind_levels; 66106184Smarcel uint8_t h_reserved2; 67106184Smarcel}; 68106184Smarcel 69106184Smarcelstruct ext2fs_htree_root { 70106184Smarcel struct ext2fs_fake_direct h_dot; 71106184Smarcel char h_dot_name[4]; 72106184Smarcel struct ext2fs_fake_direct h_dotdot; 73106184Smarcel char h_dotdot_name[4]; 74106184Smarcel struct ext2fs_htree_root_info h_info; 75106184Smarcel struct ext2fs_htree_entry h_entries[0]; 76106184Smarcel}; 77106184Smarcel 78106184Smarcelstruct ext2fs_htree_node { 79106184Smarcel struct ext2fs_fake_direct h_fake_dirent; 80106184Smarcel struct ext2fs_htree_entry h_entries[0]; 81106184Smarcel}; 82106184Smarcel 83106184Smarcelstruct ext2fs_htree_lookup_level { 84106184Smarcel struct buf *h_bp; 85106184Smarcel struct ext2fs_htree_entry *h_entries; 86106184Smarcel struct ext2fs_htree_entry *h_entry; 87106184Smarcel}; 88106184Smarcel 89106184Smarcelstruct ext2fs_htree_lookup_info { 90106184Smarcel struct ext2fs_htree_lookup_level h_levels[2]; 91106184Smarcel uint32_t h_levels_num; 92106184Smarcel}; 93106184Smarcel 94struct ext2fs_htree_sort_entry { 95 uint16_t h_offset; 96 uint16_t h_size; 97 uint32_t h_hash; 98}; 99 100#endif /* !_FS_EXT2FS_HTREE_H_ */ 101