git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/tree.h

   1 /*
   2    Bacula(R) - The Network Backup Solution
   3
   4    Copyright (C) 2000-2017 Kern Sibbald
   5
   6    The original author of Bacula is Kern Sibbald, with contributions
   7    from many others, a complete list can be found in the file AUTHORS.
   8
   9    You may use this file and others of this release according to the
  10    license defined in the LICENSE file, which includes the Affero General
  11    Public License, v3.0 ("AGPLv3") and some additional permissions and
  12    terms pursuant to its AGPLv3 Section 7.
  13
  14    This notice must be preserved when any source code is
  15    conveyed and/or propagated.
  16
  17    Bacula(R) is a registered trademark of Kern Sibbald.
  18 */
  19 /*
  20  * Directory tree build/traverse routines
  21  *
  22  *    Kern Sibbald, June MMII
  23  *
  24 */
  25
  26 #include "htable.h"
  27
  28 struct s_mem {
  29    struct s_mem *next;                /* next buffer */
  30    int rem;                           /* remaining bytes */
  31    char *mem;                         /* memory pointer */
  32    char first[1];                     /* first byte */
  33 };
  34
  35 #define USE_DLIST
  36
  37 #define foreach_child(var, list) \
  38     for((var)=NULL; (*((TREE_NODE **)&(var))=(TREE_NODE*)(list->child.next(var))); )
  39
  40 #define tree_node_has_child(node) \
  41         ((node)->child.size() > 0)
  42
  43 #define first_child(node) \
  44         ((TREE_NODE *)(node->child.first())
  45
  46 struct delta_list {
  47    struct delta_list *next;
  48    JobId_t JobId;
  49    int32_t FileIndex;
  50 };
  51
  52 /*
  53  * Keep this node as small as possible because
  54  *   there is one for each file.
  55  */
  56 struct s_tree_node {
  57    /* KEEP sibling as the first member to avoid having to
  58     *  do initialization of child */
  59    rblink sibling;
  60    rblist child;
  61    char *fname;                       /* file name */
  62    int32_t FileIndex;                 /* file index */
  63    uint32_t JobId;                    /* JobId */
  64    int32_t delta_seq;                 /* current delta sequence */
  65    uint16_t fname_len;                /* filename length */
  66    int type: 8;                       /* node type */
  67    unsigned int extract: 1;           /* extract item */
  68    unsigned int extract_dir: 1;       /* extract dir entry only */
  69    unsigned int hard_link: 1;         /* set if have hard link */
  70    unsigned int soft_link: 1;         /* set if is soft link */
  71    unsigned int inserted: 1;          /* set when node newly inserted */
  72    unsigned int loaded: 1;            /* set when the dir is in the tree */
  73    unsigned int can_access: 1;        /* Can access to this node */
  74    struct s_tree_node *parent;
  75    struct s_tree_node *next;          /* next hash of FileIndex */
  76    struct delta_list *delta_list;     /* delta parts for this node */
  77 };
  78 typedef struct s_tree_node TREE_NODE;
  79
  80 struct s_tree_root {
  81    /* KEEP sibling as the first member to avoid having to
  82     *  do initialization of child */
  83    rblink sibling;
  84    rblist child;
  85    const 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 newly inserted */
  96    unsigned int loaded: 1;            /* set when the dir is in the tree */
  97    unsigned int can_access: 1;        /* Can access to this node */
  98    struct s_tree_node *parent;
  99    struct s_tree_node *next;          /* next hash of FileIndex */
 100    struct delta_list *delta_list;     /* delta parts for this node */
 101
 102    /* The above ^^^ must be identical to a TREE_NODE structure */
 103    struct s_tree_node *first;         /* first entry in the tree */
 104    struct s_tree_node *last;          /* last entry in tree */
 105    struct s_mem *mem;                 /* tree memory */
 106    uint32_t total_size;               /* total bytes allocated */
 107    uint32_t blocks;                   /* total mallocs */
 108    int cached_path_len;               /* length of cached path */
 109    char *cached_path;                 /* cached current path */
 110    TREE_NODE *cached_parent;          /* cached parent for above path */
 111    htable hardlinks;                  /* references to first occurrence of hardlinks */
 112 };
 113 typedef struct s_tree_root TREE_ROOT;
 114
 115 /* hardlink hashtable entry */
 116 struct s_hl_entry {
 117    uint64_t key;
 118    hlink link;
 119    TREE_NODE *node;
 120 };
 121 typedef struct s_hl_entry HL_ENTRY;
 122
 123 /* type values */
 124 #define TN_ROOT    1                  /* root node */
 125 #define TN_NEWDIR  2                  /* created directory to fill path */
 126 #define TN_DIR     3                  /* directory entry */
 127 #define TN_DIR_NLS 4                  /* directory -- no leading slash -- win32 */
 128 #define TN_FILE    5                  /* file entry */
 129
 130 /* External interface */
 131 TREE_ROOT *new_tree(int count);
 132 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
 133                             TREE_ROOT *root, TREE_NODE *parent);
 134 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root);
 135 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node);
 136 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node);
 137 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
 138                          JobId_t JobId, int32_t FileIndex);
 139 void free_tree(TREE_ROOT *root);
 140 int tree_getpath(TREE_NODE *node, char *buf, int buf_size);
 141 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node);
 142
 143 /*
 144  * Use the following for traversing the whole tree. It will be
 145  *   traversed in the order the entries were inserted into the
 146  *   tree.
 147  */
 148 #define first_tree_node(r) (r)->first
 149 #define next_tree_node(n)  (n)->next