repo_tree.c

   1 #include <string.h>
   2
   3 #include "string_pool.h"
   4 #include "repo_tree.h"
   5 #include "obj_pool.h"
   6 #include "fast_export.h"
   7
   8 struct repo_dirent {
   9         uint32_t name_offset;
  10         uint32_t mode;
  11         uint32_t content_offset;
  12 };
  13
  14 struct repo_dir {
  15         uint32_t size;
  16         uint32_t first_offset;
  17 };
  18
  19 struct repo_commit {
  20         uint32_t mark;
  21         uint32_t root_dir_offset;
  22 };
  23
  24 /* Generate memory pools for commit, dir and dirent */
  25 obj_pool_gen(commit, struct repo_commit, 4096);
  26 obj_pool_gen(dir, struct repo_dir, 4096);
  27 obj_pool_gen(dirent, struct repo_dirent, 4096);
  28
  29 static uint32_t num_dirs_saved;
  30 static uint32_t num_dirents_saved;
  31 static uint32_t active_commit;
  32 static uint32_t _mark;
  33
  34 uint32_t next_blob_mark(void)
  35 {
  36         return _mark++;
  37 }
  38
  39 static struct repo_dir *repo_commit_root_dir(struct repo_commit *commit)
  40 {
  41         return dir_pointer(commit->root_dir_offset);
  42 }
  43
  44 static struct repo_dirent *repo_first_dirent(struct repo_dir *dir)
  45 {
  46         return dirent_pointer(dir->first_offset);
  47 }
  48
  49 static int repo_dirent_name_cmp(const void *a, const void *b)
  50 {
  51         const struct repo_dirent *dirent1 = a, *dirent2 = b;
  52         uint32_t a_offset = dirent1->name_offset;
  53         uint32_t b_offset = dirent2->name_offset;
  54         return (a_offset > b_offset) - (a_offset < b_offset);
  55 }
  56
  57 static struct repo_dirent *repo_dirent_by_name(struct repo_dir *dir,
  58                                           uint32_t name_offset)
  59 {
  60         struct repo_dirent key;
  61         if (dir == NULL || dir->size == 0)
  62                 return NULL;
  63         key.name_offset = name_offset;
  64         return bsearch(&key, repo_first_dirent(dir), dir->size,
  65                                    sizeof(struct repo_dirent), repo_dirent_name_cmp);
  66 }
  67
  68 static int repo_dirent_is_dir(struct repo_dirent *dirent)
  69 {
  70         return dirent != NULL && dirent->mode == REPO_MODE_DIR;
  71 }
  72
  73 static struct repo_dir *repo_dir_from_dirent(struct repo_dirent *dirent)
  74 {
  75         if (!repo_dirent_is_dir(dirent))
  76                 return NULL;
  77         return dir_pointer(dirent->content_offset);
  78 }
  79
  80 static uint32_t dir_with_dirents_alloc(uint32_t size)
  81 {
  82         uint32_t offset = dir_alloc(1);
  83         dir_pointer(offset)->size = size;
  84         dir_pointer(offset)->first_offset = dirent_alloc(size);
  85         return offset;
  86 }
  87
  88 static struct repo_dir *repo_clone_dir(struct repo_dir *orig_dir, uint32_t padding)
  89 {
  90         uint32_t orig_o, new_o, dirent_o;
  91         orig_o = dir_offset(orig_dir);
  92         if (orig_o < num_dirs_saved) {
  93                 new_o = dir_with_dirents_alloc(orig_dir->size + padding);
  94                 orig_dir = dir_pointer(orig_o);
  95                 dirent_o = dir_pointer(new_o)->first_offset;
  96         } else {
  97                 if (padding == 0)
  98                         return orig_dir;
  99                 new_o = orig_o;
 100                 dirent_o = dirent_alloc(orig_dir->size + padding);
 101         }
 102         memcpy(dirent_pointer(dirent_o), repo_first_dirent(orig_dir),
 103                    orig_dir->size * sizeof(struct repo_dirent));
 104         dir_pointer(new_o)->size = orig_dir->size + padding;
 105         dir_pointer(new_o)->first_offset = dirent_o;
 106         return dir_pointer(new_o);
 107 }
 108
 109 static struct repo_dirent *repo_read_dirent(uint32_t revision, uint32_t *path)
 110 {
 111         uint32_t name = 0;
 112         struct repo_dir *dir = NULL;
 113         struct repo_dirent *dirent = NULL;
 114         dir = repo_commit_root_dir(commit_pointer(revision));
 115         while (~(name = *path++)) {
 116                 dirent = repo_dirent_by_name(dir, name);
 117                 if (dirent == NULL) {
 118                         return NULL;
 119                 } else if (repo_dirent_is_dir(dirent)) {
 120                         dir = repo_dir_from_dirent(dirent);
 121                 } else {
 122                         break;
 123                 }
 124         }
 125         return dirent;
 126 }
 127
 128 static void
 129 repo_write_dirent(uint32_t *path, uint32_t mode, uint32_t content_offset,
 130                   uint32_t del)
 131 {
 132         uint32_t name, revision, dirent_o = ~0, dir_o = ~0, parent_dir_o = ~0;
 133         struct repo_dir *dir;
 134         struct repo_dirent *dirent = NULL;
 135         revision = active_commit;
 136         dir = repo_commit_root_dir(commit_pointer(revision));
 137         dir = repo_clone_dir(dir, 0);
 138         commit_pointer(revision)->root_dir_offset = dir_offset(dir);
 139         while (~(name = *path++)) {
 140                 parent_dir_o = dir_offset(dir);
 141                 dirent = repo_dirent_by_name(dir, name);
 142                 if (dirent == NULL) {
 143                         dir = repo_clone_dir(dir, 1);
 144                         dirent = &repo_first_dirent(dir)[dir->size - 1];
 145                         dirent->name_offset = name;
 146                         dirent->mode = REPO_MODE_DIR;
 147                         qsort(repo_first_dirent(dir), dir->size,
 148                                   sizeof(struct repo_dirent), repo_dirent_name_cmp);
 149                         dirent = repo_dirent_by_name(dir, name);
 150                         dir_o = dir_with_dirents_alloc(0);
 151                         dirent->content_offset = dir_o;
 152                         dir = dir_pointer(dir_o);
 153                 } else if ((dir = repo_dir_from_dirent(dirent))) {
 154                         dirent_o = dirent_offset(dirent);
 155                         dir = repo_clone_dir(dir, 0);
 156                         if (dirent_o != ~0)
 157                                 dirent_pointer(dirent_o)->content_offset = dir_offset(dir);
 158                 } else {
 159                         dirent->mode = REPO_MODE_DIR;
 160                         dirent_o = dirent_offset(dirent);
 161                         dir_o = dir_with_dirents_alloc(0);
 162                         dirent = dirent_pointer(dirent_o);
 163                         dir = dir_pointer(dir_o);
 164                         dirent->content_offset = dir_o;
 165                 }
 166         }
 167         if (dirent) {
 168                 dirent->mode = mode;
 169                 dirent->content_offset = content_offset;
 170                 if (del && ~parent_dir_o) {
 171                         dirent->name_offset = ~0;
 172                         dir = dir_pointer(parent_dir_o);
 173                         qsort(repo_first_dirent(dir), dir->size,
 174                                   sizeof(struct repo_dirent), repo_dirent_name_cmp);
 175                         dir->size--;
 176                 }
 177         }
 178 }
 179
 180 uint32_t repo_copy(uint32_t revision, uint32_t *src, uint32_t *dst)
 181 {
 182         uint32_t mode = 0, content_offset = 0;
 183         struct repo_dirent *src_dirent;
 184         src_dirent = repo_read_dirent(revision, src);
 185         if (src_dirent != NULL) {
 186                 mode = src_dirent->mode;
 187                 content_offset = src_dirent->content_offset;
 188                 repo_write_dirent(dst, mode, content_offset, 0);
 189         }
 190         return mode;
 191 }
 192
 193 void repo_add(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 194 {
 195         repo_write_dirent(path, mode, blob_mark, 0);
 196 }
 197
 198 uint32_t repo_replace(uint32_t *path, uint32_t blob_mark)
 199 {
 200         uint32_t mode = 0;
 201         struct repo_dirent *src_dirent;
 202         src_dirent = repo_read_dirent(active_commit, path);
 203         if (src_dirent != NULL) {
 204                 mode = src_dirent->mode;
 205                 repo_write_dirent(path, mode, blob_mark, 0);
 206         }
 207         return mode;
 208 }
 209
 210 void repo_modify(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 211 {
 212         struct repo_dirent *src_dirent;
 213         src_dirent = repo_read_dirent(active_commit, path);
 214         if (src_dirent != NULL && blob_mark == 0) {
 215                 blob_mark = src_dirent->content_offset;
 216         }
 217         repo_write_dirent(path, mode, blob_mark, 0);
 218 }
 219
 220 void repo_delete(uint32_t *path)
 221 {
 222         repo_write_dirent(path, 0, 0, 1);
 223 }
 224
 225 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir);
 226
 227 static void repo_git_add(uint32_t depth, uint32_t *path, struct repo_dirent *dirent)
 228 {
 229         if (repo_dirent_is_dir(dirent)) {
 230                 repo_git_add_r(depth, path, repo_dir_from_dirent(dirent));
 231         } else {
 232                 fast_export_modify(depth, path, dirent->mode, dirent->content_offset);
 233         }
 234 }
 235
 236 static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir)
 237 {
 238         uint32_t o;
 239         struct repo_dirent *de;
 240         de = repo_first_dirent(dir);
 241         for (o = 0; o < dir->size; o++) {
 242                 path[depth] = de[o].name_offset;
 243                 repo_git_add(depth + 1, path, &de[o]);
 244         }
 245 }
 246
 247 static void repo_diff_r(uint32_t depth, uint32_t *path, struct repo_dir *dir1,
 248                         struct repo_dir *dir2)
 249 {
 250         struct repo_dirent *de1, *de2, *max_de1, *max_de2;
 251         de1 = repo_first_dirent(dir1);
 252         de2 = repo_first_dirent(dir2);
 253         max_de1 = &de1[dir1->size];
 254         max_de2 = &de2[dir2->size];
 255
 256         while (de1 < max_de1 && de2 < max_de2) {
 257                 if (de1->name_offset < de2->name_offset) {
 258                         path[depth] = (de1++)->name_offset;
 259                         fast_export_delete(depth + 1, path);
 260                 } else if (de1->name_offset > de2->name_offset) {
 261                         path[depth] = de2->name_offset;
 262                         repo_git_add(depth + 1, path, de2++);
 263                 } else {
 264                         path[depth] = de1->name_offset;
 265                         if (de1->mode != de2->mode ||
 266                                 de1->content_offset != de2->content_offset) {
 267                                 if (repo_dirent_is_dir(de1) && repo_dirent_is_dir(de2)) {
 268                                         repo_diff_r(depth + 1, path,
 269                                                                 repo_dir_from_dirent(de1),
 270                                                                 repo_dir_from_dirent(de2));
 271                                 } else {
 272                                         if (repo_dirent_is_dir(de1) != repo_dirent_is_dir(de2)) {
 273                                                 fast_export_delete(depth + 1, path);
 274                                         }
 275                                         repo_git_add(depth + 1, path, de2);
 276                                 }
 277                         }
 278                         de1++;
 279                         de2++;
 280                 }
 281         }
 282         while (de1 < max_de1) {
 283                 path[depth] = (de1++)->name_offset;
 284                 fast_export_delete(depth + 1, path);
 285         }
 286         while (de2 < max_de2) {
 287                 path[depth] = de2->name_offset;
 288                 repo_git_add(depth + 1, path, de2++);
 289         }
 290 }
 291
 292 static uint32_t path_stack[REPO_MAX_PATH_DEPTH];
 293
 294 void repo_diff(uint32_t r1, uint32_t r2)
 295 {
 296         repo_diff_r(0,
 297                     path_stack,
 298                     repo_commit_root_dir(commit_pointer(r1)),
 299                     repo_commit_root_dir(commit_pointer(r2)));
 300 }
 301
 302 void repo_commit(uint32_t revision, uint32_t author, char *log, uint32_t uuid,
 303                  uint32_t url, time_t timestamp)
 304 {
 305         fast_export_commit(revision, author, log, uuid, url, timestamp);
 306         num_dirs_saved = dir_pool.size;
 307         num_dirents_saved = dirent_pool.size;
 308         active_commit = commit_alloc(1);
 309         commit_pointer(active_commit)->root_dir_offset =
 310                 commit_pointer(active_commit - 1)->root_dir_offset;
 311 }
 312
 313 static void mark_init(void)
 314 {
 315         uint32_t i;
 316         _mark = 0;
 317         for (i = 0; i < dirent_pool.size; i++)
 318                 if (!repo_dirent_is_dir(dirent_pointer(i)) &&
 319                         dirent_pointer(i)->content_offset > _mark)
 320                         _mark = dirent_pointer(i)->content_offset;
 321         _mark++;
 322 }
 323
 324 void repo_init() {
 325         pool_init();
 326         commit_init();
 327         dir_init();
 328         dirent_init();
 329         mark_init();
 330         num_dirs_saved = dir_pool.size;
 331         num_dirents_saved = dirent_pool.size;
 332         active_commit = commit_pool.size - 1;
 333         if (active_commit == -1) {
 334                 commit_alloc(2);
 335                 /* Create empty tree for commit 0. */
 336                 commit_pointer(0)->root_dir_offset =
 337                         dir_with_dirents_alloc(0);
 338                 /* Preallocate commit 1, ready for changes. */
 339                 commit_pointer(1)->root_dir_offset =
 340                         commit_pointer(0)->root_dir_offset;
 341                 active_commit = 1;
 342                 num_dirs_saved = dir_pool.size;
 343                 num_dirents_saved = dirent_pool.size;
 344         }
 345 }
 346
 347 void repo_reset(void)
 348 {
 349         pool_reset();
 350         commit_reset();
 351         dir_reset();
 352         dirent_reset();
 353 }