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

   1 /*
   2  * Directory tree build/traverse routines
   3  *
   4  *    Kern Sibbald, June MMII
   5  *
   6 */
   7 /*
   8    Copyright (C) 2002-2004 Kern Sibbald and John Walker
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2 of
  13    the License, or (at your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public
  21    License along with this program; if not, write to the Free
  22    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  23    MA 02111-1307, USA.
  24
  25  */
  26
  27 struct s_mem {
  28    struct s_mem *next;                /* next buffer */
  29    int rem;                           /* remaining bytes */
  30    char *mem;                         /* memory pointer */
  31    char first[1];                     /* first byte */
  32 };
  33
  34 #define USE_DLIST
  35 #ifdef  USE_DLIST
  36 #define foreach_child(var, list) \
  37     for((var)=NULL; (*((TREE_NODE **)&(var))=(TREE_NODE*)(list->child.next(var))); )
  38
  39 #define tree_node_has_child(node) \
  40         ((node)->child.size() > 0)
  41
  42 #define first_child(node) \
  43         ((TREE_NODE *)(node->child.first())
  44
  45
  46 /*
  47  * Keep this node as small as possible because
  48  *   there is one for each file.
  49  */
  50 struct s_tree_node {
  51    /* KEEP sibling as the first member to avoid having to
  52     *  do initialization of child */
  53    dlink sibling;
  54    dlist child;
  55    char *fname;                       /* file name */
  56    int32_t FileIndex;                 /* file index */
  57    uint32_t JobId;                    /* JobId */
  58    uint16_t fname_len;                /* filename length */
  59    int type: 8;                       /* node type */
  60    unsigned int extract: 1;           /* extract item */
  61    unsigned int extract_dir: 1;       /* extract dir entry only */
  62    unsigned int hard_link: 1;         /* set if have hard link */
  63    unsigned int soft_link: 1;         /* set if is soft link */
  64    unsigned int inserted: 1;          /* set when newly inserted */
  65    struct s_tree_node *parent;
  66    struct s_tree_node *next;          /* next hash of FileIndex */
  67 };
  68 typedef struct s_tree_node TREE_NODE;
  69
  70 struct s_tree_root {
  71    /* KEEP sibling as the first member to avoid having to
  72     *  do initialization of child */
  73    dlink sibling;
  74    dlist child;
  75    const char *fname;                 /* file name */
  76    int32_t FileIndex;                 /* file index */
  77    uint32_t JobId;                    /* JobId */
  78    uint16_t fname_len;                /* filename length */
  79    unsigned int type: 8;              /* node type */
  80    unsigned int extract: 1;           /* extract item */
  81    unsigned int extract_dir: 1;       /* extract dir entry only */
  82    unsigned int have_link: 1;         /* set if have hard link */
  83    unsigned int inserted: 1;          /* set when newly inserted */
  84    struct s_tree_node *parent;
  85    struct s_tree_node *next;          /* next hash of FileIndex */
  86
  87    /* The above ^^^ must be identical to a TREE_NODE structure */
  88    struct s_tree_node *first;         /* first entry in the tree */
  89    struct s_tree_node *last;          /* last entry in tree */
  90    struct s_mem *mem;                 /* tree memory */
  91    uint32_t total_size;               /* total bytes allocated */
  92    uint32_t blocks;                   /* total mallocs */
  93    int cached_path_len;               /* length of cached path */
  94    char *cached_path;                 /* cached current path */
  95    TREE_NODE *cached_parent;          /* cached parent for above path */
  96 };
  97 typedef struct s_tree_root TREE_ROOT;
  98
  99 #else
 100 #define foreach_child(cld, node) \
 101         for(cld=(node)->child_; cld; cld=cld->sibling_)
 102
 103 #define tree_node_has_child(node) \
 104         ((node)->child_ != NULL)
 105
 106 #define first_child(node) \
 107         ((node)->child_)
 108
 109
 110 /*
 111  * Keep this node as small as possible because
 112  *   there is one for each file.
 113  */
 114 struct s_tree_node {
 115    char *fname;                       /* file name */
 116    int32_t FileIndex;                 /* file index */
 117    uint32_t JobId;                    /* JobId */
 118    uint16_t fname_len;                /* filename length */
 119    int type: 8;                       /* node type */
 120    unsigned int extract: 1;           /* extract item */
 121    unsigned int extract_dir: 1;       /* extract dir entry only */
 122    unsigned int hard_link: 1;         /* set if have hard link */
 123    unsigned int soft_link: 1;         /* set if is soft link */
 124    unsigned int inserted: 1;          /* set when newly inserted */
 125    struct s_tree_node *parent;
 126    struct s_tree_node *sibling_;
 127    struct s_tree_node *next;          /* next hash of FileIndex */
 128    struct s_tree_node *child_;
 129 };
 130 typedef struct s_tree_node TREE_NODE;
 131
 132 struct s_tree_root {
 133    char *fname;                       /* file name */
 134    int32_t FileIndex;                 /* file index */
 135    uint32_t JobId;                    /* JobId */
 136    uint16_t fname_len;                /* filename length */
 137    unsigned int type: 8;              /* node type */
 138    unsigned int extract: 1;           /* extract item */
 139    unsigned int extract_dir: 1;       /* extract dir entry only */
 140    unsigned int have_link: 1;         /* set if have hard link */
 141    unsigned int inserted: 1;          /* set when newly inserted */
 142    struct s_tree_node *parent;
 143    struct s_tree_node *sibling_;
 144    struct s_tree_node *next;          /* next hash of FileIndex */
 145    struct s_tree_node *child_;
 146
 147    /* The above ^^^ must be identical to a TREE_NODE structure */
 148    struct s_tree_node *first;         /* first entry in the tree */
 149    struct s_tree_node *last;          /* last entry in tree */
 150    struct s_mem *mem;                 /* tree memory */
 151    uint32_t total_size;               /* total bytes allocated */
 152    uint32_t blocks;                   /* total mallocs */
 153    int cached_path_len;               /* length of cached path */
 154    char *cached_path;                 /* cached current path */
 155    TREE_NODE *cached_parent;          /* cached parent for above path */
 156 };
 157 typedef struct s_tree_root TREE_ROOT;
 158 #endif
 159
 160 /* type values */
 161 #define TN_ROOT    1                  /* root node */
 162 #define TN_NEWDIR  2                  /* created directory to fill path */
 163 #define TN_DIR     3                  /* directory entry */
 164 #define TN_DIR_NLS 4                  /* directory -- no leading slash -- win32 */
 165 #define TN_FILE    5                  /* file entry */
 166
 167 /* External interface */
 168 TREE_ROOT *new_tree(int count);
 169 TREE_NODE *insert_tree_node(char *path, char *fname, int type,
 170                             TREE_ROOT *root, TREE_NODE *parent);
 171 TREE_NODE *make_tree_path(char *path, TREE_ROOT *root);
 172 TREE_NODE *tree_cwd(char *path, TREE_ROOT *root, TREE_NODE *node);
 173 TREE_NODE *tree_relcwd(char *path, TREE_ROOT *root, TREE_NODE *node);
 174 void free_tree(TREE_ROOT *root);
 175 int tree_getpath(TREE_NODE *node, char *buf, int buf_size);
 176
 177 /*
 178  * Use the following for traversing the whole tree. It will be
 179  *   traversed in the order the entries were inserted into the
 180  *   tree.
 181  */
 182 #ifdef SLOW_WAY
 183 TREE_NODE *first_tree_node(TREE_ROOT *root);
 184 TREE_NODE *next_tree_node(TREE_NODE *node);
 185 #else
 186   #define first_tree_node(r) (r)->first
 187   #define next_tree_node(n)  (n)->next
 188 #endif