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, uint32_t *path)
  91 {
  92         uint32_t name = 0;
  93         struct repo_dirent *key = dent_pointer(dent_alloc(1));
  94         struct repo_dir *dir = NULL;
  95         struct repo_dirent *dent = NULL;
  96         dir = repo_commit_root_dir(commit_pointer(revision));
  97         while (~(name = *path++)) {
  98                 key->name_offset = name;
  99                 dent = dent_search(&dir->entries, key);
 100                 if (dent == NULL || !repo_dirent_is_dir(dent))
 101                         break;
 102                 dir = repo_dir_from_dirent(dent);
 103         }
 104         dent_free(1);
 105         return dent;
 106 }
 107
 108 static void repo_write_dirent(uint32_t *path, uint32_t mode,
 109                               uint32_t content_offset, uint32_t del)
 110 {
 111         uint32_t name, revision, dir_o = ~0, parent_dir_o = ~0;
 112         struct repo_dir *dir;
 113         struct repo_dirent *key;
 114         struct repo_dirent *dent = NULL;
 115         revision = active_commit;
 116         dir = repo_commit_root_dir(commit_pointer(revision));
 117         dir = repo_clone_dir(dir);
 118         commit_pointer(revision)->root_dir_offset = dir_offset(dir);
 119         while (~(name = *path++)) {
 120                 parent_dir_o = dir_offset(dir);
 121
 122                 key = dent_pointer(dent_alloc(1));
 123                 key->name_offset = name;
 124
 125                 dent = dent_search(&dir->entries, key);
 126                 if (dent == NULL)
 127                         dent = key;
 128                 else
 129                         dent_free(1);
 130
 131                 if (dent == key) {
 132                         dent->mode = REPO_MODE_DIR;
 133                         dent->content_offset = 0;
 134                         dent = dent_insert(&dir->entries, dent);
 135                 }
 136
 137                 if (dent_offset(dent) < dent_pool.committed) {
 138                         dir_o = repo_dirent_is_dir(dent) ?
 139                                         dent->content_offset : ~0;
 140                         dent_remove(&dir->entries, dent);
 141                         dent = dent_pointer(dent_alloc(1));
 142                         dent->name_offset = name;
 143                         dent->mode = REPO_MODE_DIR;
 144                         dent->content_offset = dir_o;
 145                         dent = dent_insert(&dir->entries, dent);
 146                 }
 147
 148                 dir = repo_dir_from_dirent(dent);
 149                 dir = repo_clone_dir(dir);
 150                 dent->content_offset = dir_offset(dir);
 151         }
 152         if (dent == NULL)
 153                 return;
 154         dent->mode = mode;
 155         dent->content_offset = content_offset;
 156         if (del && ~parent_dir_o)
 157                 dent_remove(&dir_pointer(parent_dir_o)->entries, dent);
 158 }
 159
 160 uint32_t repo_copy(uint32_t revision, uint32_t *src, uint32_t *dst)
 161 {
 162         uint32_t mode = 0, content_offset = 0;
 163         struct repo_dirent *src_dent;
 164         src_dent = repo_read_dirent(revision, src);
 165         if (src_dent != NULL) {
 166                 mode = src_dent->mode;
 167                 content_offset = src_dent->content_offset;
 168                 repo_write_dirent(dst, mode, content_offset, 0);
 169         }
 170         return mode;
 171 }
 172
 173 void repo_add(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 174 {
 175         repo_write_dirent(path, mode, blob_mark, 0);
 176 }
 177
 178 uint32_t repo_replace(uint32_t *path, uint32_t blob_mark)
 179 {
 180         uint32_t mode = 0;
 181         struct repo_dirent *src_dent;
 182         src_dent = repo_read_dirent(active_commit, path);
 183         if (src_dent != NULL) {
 184                 mode = src_dent->mode;
 185                 repo_write_dirent(path, mode, blob_mark, 0);
 186         }
 187         return mode;
 188 }
 189
 190 void repo_modify(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 191 {
 192         struct repo_dirent *src_dent;
 193         src_dent = repo_read_dirent(active_commit, path);
 194         if (src_dent != NULL && blob_mark == 0)
 195                 blob_mark = src_dent->content_offset;
 196         repo_write_dirent(path, mode, blob_mark, 0);
 197 }
 198
 199 void repo_delete(uint32_t *path)
 200 {
 201         repo_write_dirent(path, 0, 0, 1);
 202 }
 203
 204 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir);
 205
 206 static void repo_git_add(uint32_t depth, uint32_t *path, struct repo_dirent *dent)
 207 {
 208         if (repo_dirent_is_dir(dent))
 209                 repo_git_add_r(depth, path, repo_dir_from_dirent(dent));
 210         else
 211                 fast_export_modify(depth, path,
 212                                    dent->mode, dent->content_offset);
 213 }
 214
 215 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir)
 216 {
 217         struct repo_dirent *de = repo_first_dirent(dir);
 218         while (de) {
 219                 path[depth] = de->name_offset;
 220                 repo_git_add(depth + 1, path, de);
 221                 de = dent_next(&dir->entries, de);
 222         }
 223 }
 224
 225 static void repo_diff_r(uint32_t depth, uint32_t *path, struct repo_dir *dir1,
 226                         struct repo_dir *dir2)
 227 {
 228         struct repo_dirent *de1, *de2;
 229         de1 = repo_first_dirent(dir1);
 230         de2 = repo_first_dirent(dir2);
 231
 232         while (de1 && de2) {
 233                 if (de1->name_offset < de2->name_offset) {
 234                         path[depth] = de1->name_offset;
 235                         fast_export_delete(depth + 1, path);
 236                         de1 = dent_next(&dir1->entries, de1);
 237                         continue;
 238                 }
 239                 if (de1->name_offset > de2->name_offset) {
 240                         path[depth] = de2->name_offset;
 241                         repo_git_add(depth + 1, path, de2);
 242                         de2 = dent_next(&dir2->entries, de2);
 243                         continue;
 244                 }
 245                 path[depth] = de1->name_offset;
 246
 247                 if (de1->mode == de2->mode &&
 248                     de1->content_offset == de2->content_offset) {
 249                         ; /* No change. */
 250                 } else if (repo_dirent_is_dir(de1) && repo_dirent_is_dir(de2)) {
 251                         repo_diff_r(depth + 1, path,
 252                                     repo_dir_from_dirent(de1),
 253                                     repo_dir_from_dirent(de2));
 254                 } else if (!repo_dirent_is_dir(de1) && !repo_dirent_is_dir(de2)) {
 255                         repo_git_add(depth + 1, path, de2);
 256                 } else {
 257                         fast_export_delete(depth + 1, path);
 258                         repo_git_add(depth + 1, path, de2);
 259                 }
 260                 de1 = dent_next(&dir1->entries, de1);
 261                 de2 = dent_next(&dir2->entries, de2);
 262         }
 263         while (de1) {
 264                 path[depth] = de1->name_offset;
 265                 fast_export_delete(depth + 1, path);
 266                 de1 = dent_next(&dir1->entries, de1);
 267         }
 268         while (de2) {
 269                 path[depth] = de2->name_offset;
 270                 repo_git_add(depth + 1, path, de2);
 271                 de2 = dent_next(&dir2->entries, de2);
 272         }
 273 }
 274
 275 static uint32_t path_stack[REPO_MAX_PATH_DEPTH];
 276
 277 void repo_diff(uint32_t r1, uint32_t r2)
 278 {
 279         repo_diff_r(0,
 280                     path_stack,
 281                     repo_commit_root_dir(commit_pointer(r1)),
 282                     repo_commit_root_dir(commit_pointer(r2)));
 283 }
 284
 285 void repo_commit(uint32_t revision, uint32_t author, char *log, uint32_t uuid,
 286                  uint32_t url, unsigned long timestamp)
 287 {
 288         fast_export_commit(revision, author, log, uuid, url, timestamp);
 289         dent_commit();
 290         dir_commit();
 291         active_commit = commit_alloc(1);
 292         commit_pointer(active_commit)->root_dir_offset =
 293                 commit_pointer(active_commit - 1)->root_dir_offset;
 294 }
 295
 296 static void mark_init(void)
 297 {
 298         uint32_t i;
 299         mark = 0;
 300         for (i = 0; i < dent_pool.size; i++)
 301                 if (!repo_dirent_is_dir(dent_pointer(i)) &&
 302                     dent_pointer(i)->content_offset > mark)
 303                         mark = dent_pointer(i)->content_offset;
 304         mark++;
 305 }
 306
 307 void repo_init(void)
 308 {
 309         mark_init();
 310         if (commit_pool.size == 0) {
 311                 /* Create empty tree for commit 0. */
 312                 commit_alloc(1);
 313                 commit_pointer(0)->root_dir_offset = dir_alloc(1);
 314                 dir_pointer(0)->entries.trp_root = ~0;
 315                 dir_commit();
 316         }
 317         /* Preallocate next commit, ready for changes. */
 318         active_commit = commit_alloc(1);
 319         commit_pointer(active_commit)->root_dir_offset =
 320                 commit_pointer(active_commit - 1)->root_dir_offset;
 321 }
 322
 323 void repo_reset(void)
 324 {
 325         pool_reset();
 326         commit_reset();
 327         dir_reset();
 328         dent_reset();
 329 }