sys/fs/ext2fs/htree.h

   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
  46 struct 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
  53 struct ext2fs_htree_count {
  54         uint16_t h_entries_max;
  55         uint16_t h_entries_num;
  56 };
  57
  58 struct 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  */
  66 struct ext2fs_htree_tail {
  67         uint32_t ht_reserved;
  68         uint32_t ht_checksum;   /* crc32c(uuid+inum+dirblock) */
  69 };
  70
  71 struct 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
  79 struct 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
  88 struct ext2fs_htree_node {
  89         struct ext2fs_fake_direct h_fake_dirent;
  90         struct ext2fs_htree_entry h_entries[0];
  91 };
  92
  93 struct 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
  99 struct ext2fs_htree_lookup_info {
 100         struct ext2fs_htree_lookup_level h_levels[2];
 101         uint32_t h_levels_num;
 102 };
 103
 104 struct 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_ */