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(uint32_t *path, uint32_t mode,
 110                               uint32_t content_offset, uint32_t del)
 111 {
 112         uint32_t name, revision, dir_o = ~0, parent_dir_o = ~0;
 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_copy(uint32_t revision, uint32_t *src, uint32_t *dst)
 171 {
 172         uint32_t mode = 0, content_offset = 0;
 173         struct repo_dirent *src_dent;
 174         src_dent = repo_read_dirent(revision, src);
 175         if (src_dent != NULL) {
 176                 mode = src_dent->mode;
 177                 content_offset = src_dent->content_offset;
 178                 repo_write_dirent(dst, mode, content_offset, 0);
 179         }
 180         return mode;
 181 }
 182
 183 void repo_add(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 184 {
 185         repo_write_dirent(path, mode, blob_mark, 0);
 186 }
 187
 188 uint32_t repo_modify_path(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 189 {
 190         struct repo_dirent *src_dent;
 191         src_dent = repo_read_dirent(active_commit, path);
 192         if (!src_dent)
 193                 return 0;
 194         if (!blob_mark)
 195                 blob_mark = src_dent->content_offset;
 196         if (!mode)
 197                 mode = src_dent->mode;
 198         repo_write_dirent(path, mode, blob_mark, 0);
 199         return mode;
 200 }
 201
 202 void repo_delete(uint32_t *path)
 203 {
 204         repo_write_dirent(path, 0, 0, 1);
 205 }
 206
 207 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir);
 208
 209 static void repo_git_add(uint32_t depth, uint32_t *path, struct repo_dirent *dent)
 210 {
 211         if (repo_dirent_is_dir(dent))
 212                 repo_git_add_r(depth, path, repo_dir_from_dirent(dent));
 213         else
 214                 fast_export_modify(depth, path,
 215                                    dent->mode, dent->content_offset);
 216 }
 217
 218 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir)
 219 {
 220         struct repo_dirent *de = repo_first_dirent(dir);
 221         while (de) {
 222                 path[depth] = de->name_offset;
 223                 repo_git_add(depth + 1, path, de);
 224                 de = dent_next(&dir->entries, de);
 225         }
 226 }
 227
 228 static void repo_diff_r(uint32_t depth, uint32_t *path, struct repo_dir *dir1,
 229                         struct repo_dir *dir2)
 230 {
 231         struct repo_dirent *de1, *de2;
 232         de1 = repo_first_dirent(dir1);
 233         de2 = repo_first_dirent(dir2);
 234
 235         while (de1 && de2) {
 236                 if (de1->name_offset < de2->name_offset) {
 237                         path[depth] = de1->name_offset;
 238                         fast_export_delete(depth + 1, path);
 239                         de1 = dent_next(&dir1->entries, de1);
 240                         continue;
 241                 }
 242                 if (de1->name_offset > de2->name_offset) {
 243                         path[depth] = de2->name_offset;
 244                         repo_git_add(depth + 1, path, de2);
 245                         de2 = dent_next(&dir2->entries, de2);
 246                         continue;
 247                 }
 248                 path[depth] = de1->name_offset;
 249
 250                 if (de1->mode == de2->mode &&
 251                     de1->content_offset == de2->content_offset) {
 252                         ; /* No change. */
 253                 } else if (repo_dirent_is_dir(de1) && repo_dirent_is_dir(de2)) {
 254                         repo_diff_r(depth + 1, path,
 255                                     repo_dir_from_dirent(de1),
 256                                     repo_dir_from_dirent(de2));
 257                 } else if (!repo_dirent_is_dir(de1) && !repo_dirent_is_dir(de2)) {
 258                         repo_git_add(depth + 1, path, de2);
 259                 } else {
 260                         fast_export_delete(depth + 1, path);
 261                         repo_git_add(depth + 1, path, de2);
 262                 }
 263                 de1 = dent_next(&dir1->entries, de1);
 264                 de2 = dent_next(&dir2->entries, de2);
 265         }
 266         while (de1) {
 267                 path[depth] = de1->name_offset;
 268                 fast_export_delete(depth + 1, path);
 269                 de1 = dent_next(&dir1->entries, de1);
 270         }
 271         while (de2) {
 272                 path[depth] = de2->name_offset;
 273                 repo_git_add(depth + 1, path, de2);
 274                 de2 = dent_next(&dir2->entries, de2);
 275         }
 276 }
 277
 278 static uint32_t path_stack[REPO_MAX_PATH_DEPTH];
 279
 280 void repo_diff(uint32_t r1, uint32_t r2)
 281 {
 282         repo_diff_r(0,
 283                     path_stack,
 284                     repo_commit_root_dir(commit_pointer(r1)),
 285                     repo_commit_root_dir(commit_pointer(r2)));
 286 }
 287
 288 void repo_commit(uint32_t revision, uint32_t author, char *log, uint32_t uuid,
 289                  uint32_t url, unsigned long timestamp)
 290 {
 291         fast_export_commit(revision, author, log, uuid, url, timestamp);
 292         dent_commit();
 293         dir_commit();
 294         active_commit = commit_alloc(1);
 295         commit_pointer(active_commit)->root_dir_offset =
 296                 commit_pointer(active_commit - 1)->root_dir_offset;
 297 }
 298
 299 static void mark_init(void)
 300 {
 301         uint32_t i;
 302         mark = 0;
 303         for (i = 0; i < dent_pool.size; i++)
 304                 if (!repo_dirent_is_dir(dent_pointer(i)) &&
 305                     dent_pointer(i)->content_offset > mark)
 306                         mark = dent_pointer(i)->content_offset;
 307         mark++;
 308 }
 309
 310 void repo_init(void)
 311 {
 312         mark_init();
 313         if (commit_pool.size == 0) {
 314                 /* Create empty tree for commit 0. */
 315                 commit_alloc(1);
 316                 commit_pointer(0)->root_dir_offset = dir_alloc(1);
 317                 dir_pointer(0)->entries.trp_root = ~0;
 318                 dir_commit();
 319         }
 320         /* Preallocate next commit, ready for changes. */
 321         active_commit = commit_alloc(1);
 322         commit_pointer(active_commit)->root_dir_offset =
 323                 commit_pointer(active_commit - 1)->root_dir_offset;
 324 }
 325
 326 void repo_reset(void)
 327 {
 328         pool_reset();
 329         commit_reset();
 330         dir_reset();
 331         dent_reset();
 332 }