Home | History | Annotate | Line # | Download | only in ext2fs 
      1 /*	$NetBSD: ext2fs_htree.h,v 1.1 2016/06/24 17:21:30 christos Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2010, 2012 Zheng Liu <lz (at) 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  * $FreeBSD: head/sys/fs/ext2fs/htree.h 262623 2014-02-28 21:25:32Z pfg $
     30  */
     31 #ifndef _FS_EXT2FS_HTREE_H_
     32 #define	_FS_EXT2FS_HTREE_H_
     33 
     34 /* EXT3 HTree directory indexing */
     35 
     36 #define	EXT2_HTREE_LEGACY		0
     37 #define	EXT2_HTREE_HALF_MD4		1
     38 #define	EXT2_HTREE_TEA			2
     39 #define	EXT2_HTREE_LEGACY_UNSIGNED	3
     40 #define	EXT2_HTREE_HALF_MD4_UNSIGNED	4
     41 #define	EXT2_HTREE_TEA_UNSIGNED		5
     42 
     43 #define	EXT2_HTREE_EOF 0x7FFFFFFF
     44 
     45 struct ext2fs_fake_direct {
     46 	uint32_t e2d_ino;	/* inode number of entry */
     47 	uint16_t e2d_reclen;	/* length of this record */
     48 	uint8_t  e2d_namlen;	/* length of string in d_name */
     49 	uint8_t  e2d_type;	/* file type */
     50 };
     51 
     52 struct ext2fs_htree_count {
     53 	uint16_t h_entries_max;
     54 	uint16_t h_entries_num;
     55 };
     56 
     57 struct ext2fs_htree_entry {
     58 	uint32_t h_hash;
     59 	uint32_t h_blk;
     60 };
     61 
     62 struct ext2fs_htree_root_info {
     63 	uint32_t h_reserved1;
     64 	uint8_t  h_hash_version;
     65 	uint8_t  h_info_len;
     66 	uint8_t  h_ind_levels;
     67 	uint8_t  h_reserved2;
     68 };
     69 
     70 struct ext2fs_htree_root {
     71 	struct ext2fs_fake_direct h_dot;
     72 	char h_dot_name[4];
     73 	struct ext2fs_fake_direct h_dotdot;
     74 	char h_dotdot_name[4];
     75 	struct ext2fs_htree_root_info h_info;
     76 	struct ext2fs_htree_entry h_entries[0];
     77 };
     78 
     79 struct ext2fs_htree_node {
     80 	struct ext2fs_fake_direct h_fake_dirent;
     81 	struct ext2fs_htree_entry h_entries[0];
     82 };
     83 
     84 struct ext2fs_htree_lookup_level {
     85 	struct buf *h_bp;
     86 	struct ext2fs_htree_entry *h_entries;
     87 	struct ext2fs_htree_entry *h_entry;
     88 };
     89 
     90 struct ext2fs_htree_lookup_info {
     91 	struct ext2fs_htree_lookup_level h_levels[2];
     92 	uint32_t h_levels_num;
     93 };
     94 
     95 struct ext2fs_htree_sort_entry {
     96 	uint16_t h_offset;
     97 	uint16_t h_size;
     98 	uint32_t h_hash;
     99 };
    100 
    101 #endif /* !_FS_EXT2FS_HTREE_H_ */
    102