sys/fs/ext2fs/htree.h

   1 /*-
   2  * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org>
   3  * Copyright (c) 2012, Vyacheslav Matyushin
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  *
  27  * $FreeBSD$
  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 struct ext2fs_htree_root_info {
  62         uint32_t h_reserved1;
  63         uint8_t  h_hash_version;
  64         uint8_t  h_info_len;
  65         uint8_t  h_ind_levels;
  66         uint8_t  h_reserved2;
  67 };
  68
  69 struct ext2fs_htree_root {
  70         struct ext2fs_fake_direct h_dot;
  71         char h_dot_name[4];
  72         struct ext2fs_fake_direct h_dotdot;
  73         char h_dotdot_name[4];
  74         struct ext2fs_htree_root_info h_info;
  75         struct ext2fs_htree_entry h_entries[0];
  76 };
  77
  78 struct ext2fs_htree_node {
  79         struct ext2fs_fake_direct h_fake_dirent;
  80         struct ext2fs_htree_entry h_entries[0];
  81 };
  82
  83 struct ext2fs_htree_lookup_level {
  84         struct buf *h_bp;
  85         struct ext2fs_htree_entry *h_entries;
  86         struct ext2fs_htree_entry *h_entry;
  87 };
  88
  89 struct ext2fs_htree_lookup_info {
  90         struct ext2fs_htree_lookup_level h_levels[2];
  91         uint32_t h_levels_num;
  92 };
  93
  94 struct ext2fs_htree_sort_entry {
  95         uint16_t h_offset;
  96         uint16_t h_size;
  97         uint32_t h_hash;
  98 };
  99
 100 #endif /* !_FS_EXT2FS_HTREE_H_ */