1 /*
2    BAREOS® - Backup Archiving REcovery Open Sourced
3 
4    Copyright (C) 2002-2009 Free Software Foundation Europe e.V.
5    Copyright (C) 2016-2016 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/hostconfig.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