1 /* 2 This file is part of UFFS, the Ultra-low-cost Flash File System. 3 4 Copyright (C) 2005-2009 Ricky Zheng <[email protected]> 5 6 UFFS is free software; you can redistribute it and/or modify it under 7 the GNU Library General Public License as published by the Free Software 8 Foundation; either version 2 of the License, or (at your option) any 9 later version. 10 11 UFFS is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 or GNU Library General Public License, as applicable, for more details. 15 16 You should have received a copy of the GNU General Public License 17 and GNU Library General Public License along with UFFS; if not, write 18 to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 19 Boston, MA 02110-1301, USA. 20 21 As a special exception, if other files instantiate templates or use 22 macros or inline functions from this file, or you compile this file 23 and link it with other works to produce a work based on this file, 24 this file does not by itself cause the resulting work to be covered 25 by the GNU General Public License. However the source code for this 26 file must still be made available in accordance with section (3) of 27 the GNU General Public License v2. 28 29 This exception does not invalidate any other reasons why a work based 30 on this file might be covered by the GNU General Public License. 31 */ 32 33 #ifndef _UFFS_TREE_H_ 34 #define _UFFS_TREE_H_ 35 36 #include "uffs/uffs_types.h" 37 #include "uffs/uffs_pool.h" 38 #include "uffs/uffs_device.h" 39 #include "uffs/uffs_core.h" 40 41 #ifdef __cplusplus 42 extern "C"{ 43 #endif 44 45 #define UFFS_TYPE_DIR 0 46 #define UFFS_TYPE_FILE 1 47 #define UFFS_TYPE_DATA 2 48 #define UFFS_TYPE_RESV 3 49 #define UFFS_TYPE_INVALID 0xFF 50 51 struct uffs_NodeTypeNameMapSt { 52 int type; 53 const char *name; 54 }; 55 56 #define UFFS_TYPE_NAME_MAP { \ 57 {UFFS_TYPE_DIR, "DIR"}, \ 58 {UFFS_TYPE_FILE, "FILE"}, \ 59 {UFFS_TYPE_DATA, "DATA"}, \ 60 {UFFS_TYPE_RESV, "RESV"}, \ 61 {UFFS_TYPE_INVALID, "INVALID"} \ 62 } 63 64 struct BlockListSt { /* 12 bytes */ 65 struct uffs_TreeNodeSt * next; 66 struct uffs_TreeNodeSt * prev; 67 u16 block; 68 union { 69 u16 serial; /* for suspended block list */ 70 u8 need_check; /* for erased block list */ 71 } u; 72 }; 73 74 struct DirhSt { /* 8 bytes */ 75 u16 checksum; /* check sum of dir name */ 76 u16 block; 77 u16 parent; 78 u16 serial; 79 }; 80 81 82 struct FilehSt { /* 12 bytes */ 83 u16 block; 84 u16 checksum; /* check sum of file name */ 85 u16 parent; 86 u16 serial; 87 u32 len; /* file length total */ 88 }; 89 90 struct FdataSt { /* 10 bytes */ 91 u16 block; 92 u16 parent; 93 u32 len; /* file data length on this block */ 94 u16 serial; 95 }; 96 97 //UFFS TreeNode (14 or 16 bytes) 98 typedef struct uffs_TreeNodeSt { 99 union { 100 struct BlockListSt list; 101 struct DirhSt dir; 102 struct FilehSt file; 103 struct FdataSt data; 104 } u; 105 u16 hash_next; 106 u16 hash_prev; 107 } TreeNode; 108 109 110 //TODO: UFFS2 Tree structures 111 /* 112 struct FdataSt { 113 u32 len; 114 }; 115 116 struct filebSt { 117 u16 bls; //how many blocks this file contents ... 118 u8 offs; //the offset of this file header on FILE block 119 u8 sum; //short sum of file name 120 }; 121 122 //Extra data structure for storing file length information 123 struct FilehSt { 124 u32 len; 125 }; 126 127 //UFFS2 TreeNode (12 bytes) 128 typedef struct uffs_TreeNodeSt { 129 u16 nextIdx; 130 u16 block; 131 u16 parent; 132 u16 serial; 133 union { 134 struct FilehSt h; 135 struct filedSt file; 136 struct data; 137 } u; 138 } TreeNode; 139 140 */ 141 142 143 #define EMPTY_NODE 0xffff //!< special index num of empty node. 144 145 #define ROOT_DIR_SERIAL 0 //!< serial num of root dir 146 #define MAX_UFFS_FSN 0x3ff //!< maximum dir|file serial number (uffs_TagStore#parent: 10 bits) 147 #define MAX_UFFS_FDN 0x3fff //!< maximum file data block serial numbers (uffs_TagStore#serial: 14 bits) 148 #define PARENT_OF_ROOT 0xfffd //!< parent of ROOT ? kidding me ... 149 #define INVALID_UFFS_SERIAL 0xffff //!< invalid serial num 150 151 #define DIR_NODE_HASH_MASK 0x1f 152 #define DIR_NODE_ENTRY_LEN (DIR_NODE_HASH_MASK + 1) 153 154 #define FILE_NODE_HASH_MASK 0x3f 155 #define FILE_NODE_ENTRY_LEN (FILE_NODE_HASH_MASK + 1) 156 157 #define DATA_NODE_HASH_MASK 0x1ff 158 #define DATA_NODE_ENTRY_LEN (DATA_NODE_HASH_MASK + 1) 159 #define FROM_IDX(idx, pool) ((TreeNode *)uffs_PoolGetBufByIndex(pool, idx)) 160 #define TO_IDX(p, pool) ((u16)uffs_PoolGetIndex(pool, (void *) p)) 161 162 163 #define GET_FILE_HASH(serial) (serial & FILE_NODE_HASH_MASK) 164 #define GET_DIR_HASH(serial) (serial & DIR_NODE_HASH_MASK) 165 #define GET_DATA_HASH(parent, serial) ((parent + serial) & DATA_NODE_HASH_MASK) 166 167 168 struct uffs_TreeSt { 169 TreeNode *erased; //!< erased block list head 170 TreeNode *erased_tail; //!< erased block list tail 171 TreeNode *suspend; //!< suspended block list 172 int erased_count; //!< erased block counter 173 TreeNode *bad; //!< bad block list 174 int bad_count; //!< bad block count 175 u16 dir_entry[DIR_NODE_ENTRY_LEN]; 176 u16 file_entry[FILE_NODE_ENTRY_LEN]; 177 u16 data_entry[DATA_NODE_ENTRY_LEN]; 178 u16 max_serial; 179 }; 180 181 182 URET uffs_TreeInit(uffs_Device *dev); 183 URET uffs_TreeRelease(uffs_Device *dev); 184 URET uffs_BuildTree(uffs_Device *dev); 185 u16 uffs_FindFreeFsnSerial(uffs_Device *dev); 186 TreeNode * uffs_TreeFindFileNode(uffs_Device *dev, u16 serial); 187 TreeNode * uffs_TreeFindFileNodeWithParent(uffs_Device *dev, u16 parent); 188 TreeNode * uffs_TreeFindDirNode(uffs_Device *dev, u16 serial); 189 TreeNode * uffs_TreeFindDirNodeWithParent(uffs_Device *dev, u16 parent); 190 TreeNode * uffs_TreeFindFileNodeByName(uffs_Device *dev, const char *name, u32 len, u16 sum, u16 parent); 191 TreeNode * uffs_TreeFindDirNodeByName(uffs_Device *dev, const char *name, u32 len, u16 sum, u16 parent); 192 TreeNode * uffs_TreeFindDataNode(uffs_Device *dev, u16 parent, u16 serial); 193 194 195 TreeNode * uffs_TreeFindDirNodeByBlock(uffs_Device *dev, u16 block); 196 TreeNode * uffs_TreeFindFileNodeByBlock(uffs_Device *dev, u16 block); 197 TreeNode * uffs_TreeFindDataNodeByBlock(uffs_Device *dev, u16 block); 198 TreeNode * uffs_TreeFindErasedNodeByBlock(uffs_Device *dev, u16 block); 199 TreeNode * uffs_TreeFindBadNodeByBlock(uffs_Device *dev, u16 block); 200 201 void uffs_TreeSuspendAdd(uffs_Device *dev, TreeNode *node); 202 TreeNode * uffs_TreeFindSuspendNode(uffs_Device *dev, u16 serial); 203 void uffs_TreeRemoveSuspendNode(uffs_Device *dev, TreeNode *node); 204 205 #define SEARCH_REGION_DIR 1 206 #define SEARCH_REGION_FILE 2 207 #define SEARCH_REGION_DATA 4 208 #define SEARCH_REGION_BAD 8 209 #define SEARCH_REGION_ERASED 16 210 TreeNode * uffs_TreeFindNodeByBlock(uffs_Device *dev, u16 block, int *region); 211 212 213 214 UBOOL uffs_TreeCompareFileName(uffs_Device *dev, const char *name, u32 len, u16 sum, TreeNode *node, int type); 215 216 TreeNode * uffs_TreeGetErasedNode(uffs_Device *dev); 217 218 void uffs_InsertNodeToTree(uffs_Device *dev, u8 type, TreeNode *node); 219 void uffs_InsertToErasedListHead(uffs_Device *dev, TreeNode *node); 220 void uffs_TreeInsertToErasedListTail(uffs_Device *dev, TreeNode *node); 221 void uffs_TreeInsertToErasedListTailEx(uffs_Device *dev, TreeNode *node, int need_check); 222 void uffs_TreeInsertToBadBlockList(uffs_Device *dev, TreeNode *node); 223 224 void uffs_BreakFromEntry(uffs_Device *dev, u8 type, TreeNode *node); 225 226 void uffs_TreeSetNodeBlock(u8 type, TreeNode *node, u16 block); 227 228 229 #ifdef __cplusplus 230 } 231 #endif 232 233 234 235 #endif 236 237 238