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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2002-2009 Free Software Foundation Europe e.V.
   5
   6    The main author of Bacula is Kern Sibbald, with contributions from
   7    many others, a complete list can be found in the file AUTHORS.
   8    This program is Free Software; you can redistribute it and/or
   9    modify it under the terms of version three of the GNU Affero General Public
  10    License as published by the Free Software Foundation and included
  11    in the file LICENSE.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU Affero General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23    Bacula® is a registered trademark of Kern Sibbald.
  24    The licensor of Bacula is the Free Software Foundation Europe
  25    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  26    Switzerland, email:ftf@fsfeurope.org.
  27 */
  28 /*
  29  * Directory tree build/traverse routines
  30  *
  31  *    Kern Sibbald, June MMII
  32  *
  33 */
  34
  35 struct s_mem {
  36    struct s_mem *next;                /* next buffer */
  37    int rem;                           /* remaining bytes */
  38    char *mem;                         /* memory pointer */
  39    char first[1];                     /* first byte */
  40 };
  41
  42 #define USE_DLIST
  43
  44 #define foreach_child(var, list) \
  45     for((var)=NULL; (*((TREE_NODE **)&(var))=(TREE_NODE*)(list->child.next(var))); )
  46
  47 #define tree_node_has_child(node) \
  48         ((node)->child.size() > 0)
  49
  50 #define first_child(node) \
  51         ((TREE_NODE *)(node->child.first())
  52
  53 struct delta_list {
  54    struct delta_list *next;
  55    JobId_t JobId;
  56    int32_t FileIndex;
  57 };
  58
  59 /*
  60  * Keep this node as small as possible because
  61  *   there is one for each file.
  62  */
  63 struct s_tree_node {
  64    /* KEEP sibling as the first member to avoid having to
  65     *  do initialization of child */
  66    rblink sibling;
  67    rblist child;
  68    char *fname;                       /* file name */
  69    int32_t FileIndex;                 /* file index */
  70    uint32_t JobId;                    /* JobId */
  71    int32_t delta_seq;                 /* current delta sequence */
  72    uint16_t fname_len;                /* filename length */
  73    int type: 8;                       /* node type */
  74    unsigned int extract: 1;           /* extract item */
  75    unsigned int extract_dir: 1;       /* extract dir entry only */
  76    unsigned int hard_link: 1;         /* set if have hard link */
  77    unsigned int soft_link: 1;         /* set if is soft link */
  78    unsigned int inserted: 1;          /* set when node newly inserted */
  79    unsigned int loaded: 1;            /* set when the dir is in the tree */
  80    struct s_tree_node *parent;
  81    struct s_tree_node *next;          /* next hash of FileIndex */
  82    struct delta_list *delta_list;     /* delta parts for this node */
  83 };
  84 typedef struct s_tree_node TREE_NODE;
  85
  86 struct s_tree_root {
  87    /* KEEP sibling as the first member to avoid having to
  88     *  do initialization of child */
  89    rblink sibling;
  90    rblist child;
  91    const char *fname;                 /* file name */
  92    int32_t FileIndex;                 /* file index */
  93    uint32_t JobId;                    /* JobId */
  94    int32_t delta_seq;                 /* current delta sequence */
  95    uint16_t fname_len;                /* filename length */
  96    unsigned int type: 8;              /* node type */
  97    unsigned int extract: 1;           /* extract item */
  98    unsigned int extract_dir: 1;       /* extract dir entry only */
  99    unsigned int have_link: 1;         /* set if have hard link */
 100    unsigned int inserted: 1;          /* set when newly inserted */
 101    unsigned int loaded: 1;            /* set when the dir is in the tree */
 102    struct s_tree_node *parent;
 103    struct s_tree_node *next;          /* next hash of FileIndex */
 104    struct delta_list *delta_list;     /* delta parts for this node */
 105
 106    /* The above ^^^ must be identical to a TREE_NODE structure */
 107    struct s_tree_node *first;         /* first entry in the tree */
 108    struct s_tree_node *last;          /* last entry in tree */
 109    struct s_mem *mem;                 /* tree memory */
 110    uint32_t total_size;               /* total bytes allocated */
 111    uint32_t blocks;                   /* total mallocs */
 112    int cached_path_len;               /* length of cached path */
 113    char *cached_path;                 /* cached current path */
 114    TREE_NODE *cached_parent;          /* cached parent for above path */
 115 };
 116 typedef struct s_tree_root TREE_ROOT;
 117
 118
 119 /* type values */
 120 #define TN_ROOT    1                  /* root node */
 121 #define TN_NEWDIR  2                  /* created directory to fill path */
 122 #define TN_DIR     3                  /* directory entry */
 123 #define TN_DIR_NLS 4                  /* directory -- no leading slash -- win32 */
 124 #define TN_FILE    5                  /* file entry */
 125
 126 /* External interface */
 127 TREE_ROOT *new_tree(int count);
 128 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
 129                             TREE_ROOT *root, TREE_NODE *parent);
 130 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root);
 131 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node);
 132 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node);
 133 void tree_add_delta_part(TREE_ROOT *root, TREE_NODE *node,
 134                          JobId_t JobId, int32_t FileIndex);
 135 void free_tree(TREE_ROOT *root);
 136 int tree_getpath(TREE_NODE *node, char *buf, int buf_size);
 137 void tree_remove_node(TREE_ROOT *root, TREE_NODE *node);
 138
 139 /*
 140  * Use the following for traversing the whole tree. It will be
 141  *   traversed in the order the entries were inserted into the
 142  *   tree.
 143  */
 144 #define first_tree_node(r) (r)->first
 145 #define next_tree_node(n)  (n)->next