vcs-svn/repo_tree.c

   1 /*
   2  * Licensed under a two-clause BSD-style license.
   3  * See LICENSE for details.
   4  */
   5
   6 #include "git-compat-util.h"
   7
   8 #include "string_pool.h"
   9 #include "repo_tree.h"
  10 #include "obj_pool.h"
  11 #include "fast_export.h"
  12
  13 #include "trp.h"
  14
  15 struct repo_dirent {
  16         uint32_t name_offset;
  17         struct trp_node children;
  18         uint32_t mode;
  19         uint32_t content_offset;
  20 };
  21
  22 struct repo_dir {
  23         struct trp_root entries;
  24 };
  25
  26 struct repo_commit {
  27         uint32_t root_dir_offset;
  28 };
  29
  30 /* Memory pools for commit, dir and dirent */
  31 obj_pool_gen(commit, struct repo_commit, 4096)
  32 obj_pool_gen(dir, struct repo_dir, 4096)
  33 obj_pool_gen(dent, struct repo_dirent, 4096)
  34
  35 static uint32_t active_commit;
  36 static uint32_t mark;
  37
  38 static int repo_dirent_name_cmp(const void *a, const void *b);
  39
  40 /* Treap for directory entries */
  41 trp_gen(static, dent_, struct repo_dirent, children, dent, repo_dirent_name_cmp)
  42
  43 uint32_t next_blob_mark(void)
  44 {
  45         return mark++;
  46 }
  47
  48 static struct repo_dir *repo_commit_root_dir(struct repo_commit *commit)
  49 {
  50         return dir_pointer(commit->root_dir_offset);
  51 }
  52
  53 static struct repo_dirent *repo_first_dirent(struct repo_dir *dir)
  54 {
  55         return dent_first(&dir->entries);
  56 }
  57
  58 static int repo_dirent_name_cmp(const void *a, const void *b)
  59 {
  60         const struct repo_dirent *dent1 = a, *dent2 = b;
  61         uint32_t a_offset = dent1->name_offset;
  62         uint32_t b_offset = dent2->name_offset;
  63         return (a_offset > b_offset) - (a_offset < b_offset);
  64 }
  65
  66 static int repo_dirent_is_dir(struct repo_dirent *dent)
  67 {
  68         return dent != NULL && dent->mode == REPO_MODE_DIR;
  69 }
  70
  71 static struct repo_dir *repo_dir_from_dirent(struct repo_dirent *dent)
  72 {
  73         if (!repo_dirent_is_dir(dent))
  74                 return NULL;
  75         return dir_pointer(dent->content_offset);
  76 }
  77
  78 static struct repo_dir *repo_clone_dir(struct repo_dir *orig_dir)
  79 {
  80         uint32_t orig_o, new_o;
  81         orig_o = dir_offset(orig_dir);
  82         if (orig_o >= dir_pool.committed)
  83                 return orig_dir;
  84         new_o = dir_alloc(1);
  85         orig_dir = dir_pointer(orig_o);
  86         *dir_pointer(new_o) = *orig_dir;
  87         return dir_pointer(new_o);
  88 }
  89
  90 static struct repo_dirent *repo_read_dirent(uint32_t revision,
  91                                             const uint32_t *path)
  92 {
  93         uint32_t name = 0;
  94         struct repo_dirent *key = dent_pointer(dent_alloc(1));
  95         struct repo_dir *dir = NULL;
  96         struct repo_dirent *dent = NULL;
  97         dir = repo_commit_root_dir(commit_pointer(revision));
  98         while (~(name = *path++)) {
  99                 key->name_offset = name;
 100                 dent = dent_search(&dir->entries, key);
 101                 if (dent == NULL || !repo_dirent_is_dir(dent))
 102                         break;
 103                 dir = repo_dir_from_dirent(dent);
 104         }
 105         dent_free(1);
 106         return dent;
 107 }
 108
 109 static void repo_write_dirent(const uint32_t *path, uint32_t mode,
 110                               uint32_t content_offset, uint32_t del)
 111 {
 112         uint32_t name, revision, dir_o = ~0U, parent_dir_o = ~0U;
 113         struct repo_dir *dir;
 114         struct repo_dirent *key;
 115         struct repo_dirent *dent = NULL;
 116         revision = active_commit;
 117         dir = repo_commit_root_dir(commit_pointer(revision));
 118         dir = repo_clone_dir(dir);
 119         commit_pointer(revision)->root_dir_offset = dir_offset(dir);
 120         while (~(name = *path++)) {
 121                 parent_dir_o = dir_offset(dir);
 122
 123                 key = dent_pointer(dent_alloc(1));
 124                 key->name_offset = name;
 125
 126                 dent = dent_search(&dir->entries, key);
 127                 if (dent == NULL)
 128                         dent = key;
 129                 else
 130                         dent_free(1);
 131
 132                 if (dent == key) {
 133                         dent->mode = REPO_MODE_DIR;
 134                         dent->content_offset = 0;
 135                         dent = dent_insert(&dir->entries, dent);
 136                 }
 137
 138                 if (dent_offset(dent) < dent_pool.committed) {
 139                         dir_o = repo_dirent_is_dir(dent) ?
 140                                         dent->content_offset : ~0;
 141                         dent_remove(&dir->entries, dent);
 142                         dent = dent_pointer(dent_alloc(1));
 143                         dent->name_offset = name;
 144                         dent->mode = REPO_MODE_DIR;
 145                         dent->content_offset = dir_o;
 146                         dent = dent_insert(&dir->entries, dent);
 147                 }
 148
 149                 dir = repo_dir_from_dirent(dent);
 150                 dir = repo_clone_dir(dir);
 151                 dent->content_offset = dir_offset(dir);
 152         }
 153         if (dent == NULL)
 154                 return;
 155         dent->mode = mode;
 156         dent->content_offset = content_offset;
 157         if (del && ~parent_dir_o)
 158                 dent_remove(&dir_pointer(parent_dir_o)->entries, dent);
 159 }
 160
 161 uint32_t repo_read_path(const uint32_t *path)
 162 {
 163         uint32_t content_offset = 0;
 164         struct repo_dirent *dent = repo_read_dirent(active_commit, path);
 165         if (dent != NULL)
 166                 content_offset = dent->content_offset;
 167         return content_offset;
 168 }
 169
 170 uint32_t repo_read_mode(const uint32_t *path)
 171 {
 172         struct repo_dirent *dent = repo_read_dirent(active_commit, path);
 173         if (dent == NULL)
 174                 die("invalid dump: path to be modified is missing");
 175         return dent->mode;
 176 }
 177
 178 void repo_copy(uint32_t revision, const uint32_t *src, const uint32_t *dst)
 179 {
 180         uint32_t mode = 0, content_offset = 0;
 181         struct repo_dirent *src_dent;
 182         src_dent = repo_read_dirent(revision, src);
 183         if (src_dent != NULL) {
 184                 mode = src_dent->mode;
 185                 content_offset = src_dent->content_offset;
 186                 repo_write_dirent(dst, mode, content_offset, 0);
 187         }
 188 }
 189
 190 void repo_add(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 191 {
 192         repo_write_dirent(path, mode, blob_mark, 0);
 193 }
 194
 195 void repo_delete(uint32_t *path)
 196 {
 197         repo_write_dirent(path, 0, 0, 1);
 198 }
 199
 200 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir);
 201
 202 static void repo_git_add(uint32_t depth, uint32_t *path, struct repo_dirent *dent)
 203 {
 204         if (repo_dirent_is_dir(dent))
 205                 repo_git_add_r(depth, path, repo_dir_from_dirent(dent));
 206         else
 207                 fast_export_modify(depth, path,
 208                                    dent->mode, dent->content_offset);
 209 }
 210
 211 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir)
 212 {
 213         struct repo_dirent *de = repo_first_dirent(dir);
 214         while (de) {
 215                 path[depth] = de->name_offset;
 216                 repo_git_add(depth + 1, path, de);
 217                 de = dent_next(&dir->entries, de);
 218         }
 219 }
 220
 221 static void repo_diff_r(uint32_t depth, uint32_t *path, struct repo_dir *dir1,
 222                         struct repo_dir *dir2)
 223 {
 224         struct repo_dirent *de1, *de2;
 225         de1 = repo_first_dirent(dir1);
 226         de2 = repo_first_dirent(dir2);
 227
 228         while (de1 && de2) {
 229                 if (de1->name_offset < de2->name_offset) {
 230                         path[depth] = de1->name_offset;
 231                         fast_export_delete(depth + 1, path);
 232                         de1 = dent_next(&dir1->entries, de1);
 233                         continue;
 234                 }
 235                 if (de1->name_offset > de2->name_offset) {
 236                         path[depth] = de2->name_offset;
 237                         repo_git_add(depth + 1, path, de2);
 238                         de2 = dent_next(&dir2->entries, de2);
 239                         continue;
 240                 }
 241                 path[depth] = de1->name_offset;
 242
 243                 if (de1->mode == de2->mode &&
 244                     de1->content_offset == de2->content_offset) {
 245                         ; /* No change. */
 246                 } else if (repo_dirent_is_dir(de1) && repo_dirent_is_dir(de2)) {
 247                         repo_diff_r(depth + 1, path,
 248                                     repo_dir_from_dirent(de1),
 249                                     repo_dir_from_dirent(de2));
 250                 } else if (!repo_dirent_is_dir(de1) && !repo_dirent_is_dir(de2)) {
 251                         repo_git_add(depth + 1, path, de2);
 252                 } else {
 253                         fast_export_delete(depth + 1, path);
 254                         repo_git_add(depth + 1, path, de2);
 255                 }
 256                 de1 = dent_next(&dir1->entries, de1);
 257                 de2 = dent_next(&dir2->entries, de2);
 258         }
 259         while (de1) {
 260                 path[depth] = de1->name_offset;
 261                 fast_export_delete(depth + 1, path);
 262                 de1 = dent_next(&dir1->entries, de1);
 263         }
 264         while (de2) {
 265                 path[depth] = de2->name_offset;
 266                 repo_git_add(depth + 1, path, de2);
 267                 de2 = dent_next(&dir2->entries, de2);
 268         }
 269 }
 270
 271 static uint32_t path_stack[REPO_MAX_PATH_DEPTH];
 272
 273 void repo_diff(uint32_t r1, uint32_t r2)
 274 {
 275         repo_diff_r(0,
 276                     path_stack,
 277                     repo_commit_root_dir(commit_pointer(r1)),
 278                     repo_commit_root_dir(commit_pointer(r2)));
 279 }
 280
 281 void repo_commit(uint32_t revision, const char *author,
 282                 const struct strbuf *log, const char *uuid, const char *url,
 283                 unsigned long timestamp)
 284 {
 285         fast_export_commit(revision, author, log, uuid, url, timestamp);
 286         dent_commit();
 287         dir_commit();
 288         active_commit = commit_alloc(1);
 289         commit_pointer(active_commit)->root_dir_offset =
 290                 commit_pointer(active_commit - 1)->root_dir_offset;
 291 }
 292
 293 static void mark_init(void)
 294 {
 295         uint32_t i;
 296         mark = 0;
 297         for (i = 0; i < dent_pool.size; i++)
 298                 if (!repo_dirent_is_dir(dent_pointer(i)) &&
 299                     dent_pointer(i)->content_offset > mark)
 300                         mark = dent_pointer(i)->content_offset;
 301         mark++;
 302 }
 303
 304 void repo_init(void)
 305 {
 306         mark_init();
 307         if (commit_pool.size == 0) {
 308                 /* Create empty tree for commit 0. */
 309                 commit_alloc(1);
 310                 commit_pointer(0)->root_dir_offset = dir_alloc(1);
 311                 dir_pointer(0)->entries.trp_root = ~0;
 312                 dir_commit();
 313         }
 314         /* Preallocate next commit, ready for changes. */
 315         active_commit = commit_alloc(1);
 316         commit_pointer(active_commit)->root_dir_offset =
 317                 commit_pointer(active_commit - 1)->root_dir_offset;
 318 }
 319
 320 void repo_reset(void)
 321 {
 322         pool_reset();
 323         commit_reset();
 324         dir_reset();
 325         dent_reset();
 326 }