1 /* 2 BAREOS® - Backup Archiving REcovery Open Sourced 3 4 Copyright (C) 2002-2009 Free Software Foundation Europe e.V. 5 Copyright (C) 2016-2020 Bareos GmbH & Co. KG 6 7 This program is Free Software; you can redistribute it and/or 8 modify it under the terms of version three of the GNU Affero General Public 9 License as published by the Free Software Foundation and included 10 in the file LICENSE. 11 12 This program is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 Affero General Public License for more details. 16 17 You should have received a copy of the GNU Affero General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301, USA. 21 */ 22 /* 23 * Kern Sibbald, June MMII 24 */ 25 /** 26 * @file 27 * Directory tree build/traverse routines 28 */ 29 30 #include "lib/htable.h" 31 #include "lib/rblist.h" 32 33 #ifndef BAREOS_LIB_TREE_H_ 34 # define BAREOS_LIB_TREE_H_ 35 36 # include "include/config.h" 37 38 # ifdef HAVE_HPUX_OS 39 # pragma pack(push, 4) 40 # endif 41 42 struct s_mem { 43 struct s_mem* next; /* next buffer */ 44 int rem; /* remaining bytes */ 45 void* mem; /* memory pointer */ 46 char first[1]; /* first byte */ 47 }; 48 49 # define USE_DLIST 50 51 # define foreach_child(var, list) \ 52 for ((var) = NULL; \ 53 (*((TREE_NODE**)&(var)) = (TREE_NODE*)(list->child.next(var)));) 54 55 # define TreeNodeHasChild(node) ((node)->child.size() > 0) 56 57 # define first_child(node) \ 58 ((TREE_NODE *)(node->child.first()) 59 60 struct delta_list { 61 struct delta_list* next; 62 JobId_t JobId; 63 int32_t FileIndex; 64 }; 65 66 /** 67 * Keep this node as small as possible because 68 * there is one for each file. 69 */ 70 struct s_tree_node { s_tree_nodes_tree_node71 s_tree_node() 72 : type{false} 73 , extract{false} 74 , extract_dir{false} 75 , hard_link{false} 76 , soft_link{false} 77 , inserted{false} 78 , loaded{false} 79 { 80 } 81 /* KEEP sibling as the first member to avoid having to 82 * do initialization of child */ 83 rblink sibling; 84 rblist child; 85 char* fname{}; /* file name */ 86 int32_t FileIndex{}; /* file index */ 87 uint32_t JobId{}; /* JobId */ 88 int32_t delta_seq{}; /* current delta sequence */ 89 uint16_t fname_len{}; /* filename length */ 90 unsigned int type : 8; /* node type */ 91 unsigned int extract : 1; /* extract item */ 92 unsigned int extract_dir : 1; /* extract dir entry only */ 93 unsigned int hard_link : 1; /* set if have hard link */ 94 unsigned int soft_link : 1; /* set if is soft link */ 95 unsigned int inserted : 1; /* set when node newly inserted */ 96 unsigned int loaded : 1; /* set when the dir is in the tree */ 97 struct s_tree_node* parent{}; 98 struct s_tree_node* next{}; /* next hash of FileIndex */ 99 struct delta_list* delta_list{}; /* delta parts for this node */ 100 uint64_t fhinfo{}; /* NDMP Fh_info */ 101 uint64_t fhnode{}; /* NDMP Fh_node */ 102 }; 103 typedef struct s_tree_node TREE_NODE; 104 105 struct s_tree_root { s_tree_roots_tree_root106 s_tree_root() 107 : type{false} 108 , extract{false} 109 , extract_dir{false} 110 , have_link{false} 111 , inserted{false} 112 , loaded{false} 113 { 114 } 115 /* KEEP sibling as the first member to avoid having to 116 * do initialization of child */ 117 rblink sibling{}; 118 rblist child; 119 const char* fname{}; /* file name */ 120 int32_t FileIndex{}; /* file index */ 121 uint32_t JobId{}; /* JobId */ 122 int32_t delta_seq{}; /* current delta sequence */ 123 uint16_t fname_len{}; /* filename length */ 124 unsigned int type : 8; /* node type */ 125 unsigned int extract : 1; /* extract item */ 126 unsigned int extract_dir : 1; /* extract dir entry only */ 127 unsigned int have_link : 1; /* set if have hard link */ 128 unsigned int inserted : 1; /* set when newly inserted */ 129 unsigned int loaded : 1; /* set when the dir is in the tree */ 130 struct s_tree_node* parent{}; 131 struct s_tree_node* next{}; /* next hash of FileIndex */ 132 struct delta_list* delta_list{}; /* delta parts for this node */ 133 134 /* The above ^^^ must be identical to a TREE_NODE structure */ 135 struct s_tree_node* first{}; /* first entry in the tree */ 136 struct s_tree_node* last{}; /* last entry in tree */ 137 struct s_mem* mem{}; /* tree memory */ 138 uint32_t total_size{}; /* total bytes allocated */ 139 uint32_t blocks{}; /* total mallocs */ 140 int cached_path_len{}; /* length of cached path */ 141 char* cached_path{}; /* cached current path */ 142 TREE_NODE* cached_parent{}; /* cached parent for above path */ 143 htable hardlinks; /* references to first occurence of hardlinks */ 144 }; 145 typedef struct s_tree_root TREE_ROOT; 146 147 /* hardlink hashtable entry */ 148 struct s_hl_entry { 149 uint64_t key; 150 hlink link; 151 TREE_NODE* node; 152 }; 153 typedef struct s_hl_entry HL_ENTRY; 154 155 # ifdef HAVE_HPUX_OS 156 # pragma pack(pop) 157 # endif 158 159 /* type values */ 160 # define TN_ROOT 1 /* root node */ 161 # define TN_NEWDIR 2 /* created directory to fill path */ 162 # define TN_DIR 3 /* directory entry */ 163 # define TN_DIR_NLS 4 /* directory -- no leading slash -- win32 */ 164 # define TN_FILE 5 /* file entry */ 165 166 /* External interface */ 167 TREE_ROOT* new_tree(int count); 168 TREE_NODE* insert_tree_node(char* path, 169 char* fname, 170 int type, 171 TREE_ROOT* root, 172 TREE_NODE* parent); 173 TREE_NODE* make_tree_path(char* path, TREE_ROOT* root); 174 TREE_NODE* tree_cwd(char* path, TREE_ROOT* root, TREE_NODE* node); 175 TREE_NODE* tree_relcwd(char* path, TREE_ROOT* root, TREE_NODE* node); 176 void TreeAddDeltaPart(TREE_ROOT* root, 177 TREE_NODE* node, 178 JobId_t JobId, 179 int32_t FileIndex); 180 void FreeTree(TREE_ROOT* root); 181 POOLMEM* tree_getpath(TREE_NODE* node); 182 void TreeRemoveNode(TREE_ROOT* root, TREE_NODE* node); 183 184 /** 185 * Use the following for traversing the whole tree. It will be 186 * traversed in the order the entries were inserted into the 187 * tree. 188 */ 189 # define FirstTreeNode(r) (r)->first 190 # define NextTreeNode(n) (n)->next 191 192 #endif /* #ifndef BAREOS_LIB_TREE_H_ */ 193