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