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