sys/fs/ext2fs/htree.h

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