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 typedef struct repo_dirent_s repo_dirent_t;
   9
  10 struct repo_dirent_s {
  11     uint32_t name_offset;
  12     uint32_t mode;
  13     uint32_t content_offset;
  14 };
  15
  16 typedef struct repo_dir_s repo_dir_t;
  17
  18 struct repo_dir_s {
  19     uint32_t size;
  20     uint32_t first_offset;
  21 };
  22
  23 typedef struct repo_commit_s repo_commit_t;
  24
  25 struct repo_commit_s {
  26     uint32_t mark;
  27     uint32_t root_dir_offset;
  28 };
  29
  30 /* Generate memory pools for commit, dir and dirent */
  31 obj_pool_gen(commit, repo_commit_t, 4096);
  32 obj_pool_gen(dir, repo_dir_t, 4096);
  33 obj_pool_gen(dirent, repo_dirent_t, 4096);
  34
  35 static uint32_t num_dirs_saved = 0;
  36 static uint32_t num_dirents_saved = 0;
  37 static uint32_t active_commit = -1;
  38
  39 static repo_dir_t *repo_commit_root_dir(repo_commit_t *commit)
  40 {
  41     return dir_pointer(commit->root_dir_offset);
  42 }
  43
  44 static repo_dirent_t *repo_first_dirent(repo_dir_t *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     return (((repo_dirent_t *) a)->name_offset
  52             > ((repo_dirent_t *) b)->name_offset) -
  53         (((repo_dirent_t *) a)->name_offset
  54          < ((repo_dirent_t *) b)->name_offset);
  55 }
  56
  57 static repo_dirent_t *repo_dirent_by_name(repo_dir_t *dir,
  58                                           uint32_t name_offset)
  59 {
  60     repo_dirent_t 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(repo_dirent_t), repo_dirent_name_cmp);
  66 }
  67
  68 static int repo_dirent_is_dir(repo_dirent_t *dirent)
  69 {
  70     return dirent != NULL && dirent->mode == REPO_MODE_DIR;
  71 }
  72
  73 static repo_dir_t *repo_dir_from_dirent(repo_dirent_t *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 repo_dir_t *repo_clone_dir(repo_dir_t *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(repo_dirent_t));
 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 repo_dirent_t *repo_read_dirent(uint32_t revision, uint32_t *path)
 110 {
 111     uint32_t name = 0;
 112     repo_dir_t *dir = NULL;
 113     repo_dirent_t *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     repo_dir_t *dir;
 134     repo_dirent_t *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(repo_dirent_t), 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(repo_dirent_t), 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     repo_dirent_t *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     repo_dirent_t *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     repo_write_dirent(path, mode, blob_mark, 0);
 213 }
 214
 215 void repo_delete(uint32_t *path)
 216 {
 217     repo_write_dirent(path, 0, 0, 1);
 218 }
 219
 220 static void
 221 repo_git_add_r(uint32_t depth, uint32_t *path, repo_dir_t *dir);
 222
 223 static void
 224 repo_git_add(uint32_t depth, uint32_t *path, repo_dirent_t *dirent)
 225 {
 226     if (repo_dirent_is_dir(dirent)) {
 227         repo_git_add_r(depth, path, repo_dir_from_dirent(dirent));
 228     } else {
 229         fast_export_modify(depth, path, dirent->mode, dirent->content_offset);
 230     }
 231 }
 232
 233 static void
 234 repo_git_add_r(uint32_t depth, uint32_t *path, repo_dir_t *dir)
 235 {
 236     uint32_t o;
 237     repo_dirent_t *de;
 238     de = repo_first_dirent(dir);
 239     for (o = 0; o < dir->size; o++) {
 240         path[depth] = de[o].name_offset;
 241         repo_git_add(depth + 1, path, &de[o]);
 242     }
 243 }
 244
 245 static void
 246 repo_diff_r(uint32_t depth, uint32_t *path, repo_dir_t *dir1,
 247             repo_dir_t *dir2)
 248 {
 249     repo_dirent_t *de1, *de2, *max_de1, *max_de2;
 250     de1 = repo_first_dirent(dir1);
 251     de2 = repo_first_dirent(dir2);
 252     max_de1 = &de1[dir1->size];
 253     max_de2 = &de2[dir2->size];
 254
 255     while (de1 < max_de1 && de2 < max_de2) {
 256         if (de1->name_offset < de2->name_offset) {
 257             path[depth] = (de1++)->name_offset;
 258             fast_export_delete(depth + 1, path);
 259         } else if (de1->name_offset == de2->name_offset) {
 260             path[depth] = de1->name_offset;
 261             if (de1->content_offset != de2->content_offset) {
 262                 if (repo_dirent_is_dir(de1) && repo_dirent_is_dir(de2)) {
 263                     repo_diff_r(depth + 1, path,
 264                                 repo_dir_from_dirent(de1),
 265                                 repo_dir_from_dirent(de2));
 266                 } else {
 267                     if (repo_dirent_is_dir(de1) != repo_dirent_is_dir(de2)) {
 268                         fast_export_delete(depth + 1, path);
 269                     }
 270                     repo_git_add(depth + 1, path, de2);
 271                 }
 272             }
 273             de1++;
 274             de2++;
 275         } else {
 276             path[depth] = de2->name_offset;
 277             repo_git_add(depth + 1, path, de2++);
 278         }
 279     }
 280     while (de1 < max_de1) {
 281         path[depth] = (de1++)->name_offset;
 282         fast_export_delete(depth + 1, path);
 283     }
 284     while (de2 < max_de2) {
 285         path[depth] = de2->name_offset;
 286         repo_git_add(depth + 1, path, de2++);
 287     }
 288 }
 289
 290 static uint32_t path_stack[REPO_MAX_PATH_DEPTH];
 291 void repo_diff(uint32_t r1, uint32_t r2)
 292 {
 293     repo_diff_r(0,
 294                 path_stack,
 295                 repo_commit_root_dir(commit_pointer(r1)),
 296                 repo_commit_root_dir(commit_pointer(r2)));
 297 }
 298
 299 void repo_commit(uint32_t revision, char *author, char *log, char *uuid,
 300                  char *url, time_t timestamp)
 301 {
 302     if (revision == 0) {
 303         active_commit = commit_alloc(1);
 304         commit_pointer(active_commit)->root_dir_offset =
 305             dir_with_dirents_alloc(0);
 306     } else {
 307         fast_export_commit(revision, author, log, uuid, url, timestamp);
 308     }
 309     num_dirs_saved = dir_pool.size;
 310     num_dirents_saved = 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 void repo_reset(void)
 317 {
 318     pool_reset();
 319     commit_reset();
 320     dir_reset();
 321     dirent_reset();
 322 }