1/*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
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 * $FreeBSD$
30 */
31
32#ifndef _FS_EXT2FS_HTREE_H_
33#define	_FS_EXT2FS_HTREE_H_
34
35/* EXT3 HTree directory indexing */
36
37#define	EXT2_HTREE_LEGACY		0
38#define	EXT2_HTREE_HALF_MD4		1
39#define	EXT2_HTREE_TEA			2
40#define	EXT2_HTREE_LEGACY_UNSIGNED	3
41#define	EXT2_HTREE_HALF_MD4_UNSIGNED	4
42#define	EXT2_HTREE_TEA_UNSIGNED		5
43
44#define	EXT2_HTREE_EOF 0x7FFFFFFF
45
46struct ext2fs_fake_direct {
47	uint32_t e2d_ino;		/* inode number of entry */
48	uint16_t e2d_reclen;		/* length of this record */
49	uint8_t	e2d_namlen;		/* length of string in d_name */
50	uint8_t	e2d_type;		/* file type */
51};
52
53struct ext2fs_htree_count {
54	uint16_t h_entries_max;
55	uint16_t h_entries_num;
56};
57
58struct ext2fs_htree_entry {
59	uint32_t h_hash;
60	uint32_t h_blk;
61};
62
63/*
64 * This goes at the end of each htree block.
65 */
66struct ext2fs_htree_tail {
67	uint32_t ht_reserved;
68	uint32_t ht_checksum;	/* crc32c(uuid+inum+dirblock) */
69};
70
71struct ext2fs_htree_root_info {
72	uint32_t h_reserved1;
73	uint8_t	h_hash_version;
74	uint8_t	h_info_len;
75	uint8_t	h_ind_levels;
76	uint8_t	h_reserved2;
77};
78
79struct ext2fs_htree_root {
80	struct ext2fs_fake_direct h_dot;
81	char	h_dot_name[4];
82	struct ext2fs_fake_direct h_dotdot;
83	char	h_dotdot_name[4];
84	struct ext2fs_htree_root_info h_info;
85	struct ext2fs_htree_entry h_entries[0];
86};
87
88struct ext2fs_htree_node {
89	struct ext2fs_fake_direct h_fake_dirent;
90	struct ext2fs_htree_entry h_entries[0];
91};
92
93struct ext2fs_htree_lookup_level {
94	struct buf *h_bp;
95	struct ext2fs_htree_entry *h_entries;
96	struct ext2fs_htree_entry *h_entry;
97};
98
99struct ext2fs_htree_lookup_info {
100	struct ext2fs_htree_lookup_level h_levels[2];
101	uint32_t h_levels_num;
102};
103
104struct ext2fs_htree_sort_entry {
105	uint16_t h_offset;
106	uint16_t h_size;
107	uint32_t h_hash;
108};
109
110#endif	/* !_FS_EXT2FS_HTREE_H_ */
111