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 struct ext2fs_htree_root_info {
  64         uint32_t h_reserved1;
  65         uint8_t h_hash_version;
  66         uint8_t h_info_len;
  67         uint8_t h_ind_levels;
  68         uint8_t h_reserved2;
  69 };
  70
  71 struct ext2fs_htree_root {
  72         struct ext2fs_fake_direct h_dot;
  73         char    h_dot_name[4];
  74         struct ext2fs_fake_direct h_dotdot;
  75         char    h_dotdot_name[4];
  76         struct ext2fs_htree_root_info h_info;
  77         struct ext2fs_htree_entry h_entries[0];
  78 };
  79
  80 struct ext2fs_htree_node {
  81         struct ext2fs_fake_direct h_fake_dirent;
  82         struct ext2fs_htree_entry h_entries[0];
  83 };
  84
  85 struct ext2fs_htree_lookup_level {
  86         struct buf *h_bp;
  87         struct ext2fs_htree_entry *h_entries;
  88         struct ext2fs_htree_entry *h_entry;
  89 };
  90
  91 struct ext2fs_htree_lookup_info {
  92         struct ext2fs_htree_lookup_level h_levels[2];
  93         uint32_t h_levels_num;
  94 };
  95
  96 struct ext2fs_htree_sort_entry {
  97         uint16_t h_offset;
  98         uint16_t h_size;
  99         uint32_t h_hash;
 100 };
 101
 102 #endif  /* !_FS_EXT2FS_HTREE_H_ */