repo_tree.c

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