[thirdparty/git.git] / vcs-svn / repo_tree.c

/*
 * Licensed under a two-clause BSD-style license.
 * See LICENSE for details.
 */

#include "git-compat-util.h"

#include "string_pool.h"
#include "repo_tree.h"
#include "obj_pool.h"
#include "fast_export.h"

#include "trp.h"

struct repo_dirent {
	uint32_t name_offset;
	struct trp_node children;
	uint32_t mode;
	uint32_t content_offset;
};

struct repo_dir {
	struct trp_root entries;
};

struct repo_commit {
	uint32_t root_dir_offset;
};

/* Memory pools for commit, dir and dirent */
obj_pool_gen(commit, struct repo_commit, 4096)
obj_pool_gen(dir, struct repo_dir, 4096)
obj_pool_gen(dent, struct repo_dirent, 4096)

static uint32_t active_commit;
static uint32_t mark;

static int repo_dirent_name_cmp(const void *a, const void *b);

/* Treap for directory entries */
trp_gen(static, dent_, struct repo_dirent, children, dent, repo_dirent_name_cmp)

uint32_t next_blob_mark(void)
{
	return mark++;
}

static struct repo_dir *repo_commit_root_dir(struct repo_commit *commit)
{
	return dir_pointer(commit->root_dir_offset);
}

static struct repo_dirent *repo_first_dirent(struct repo_dir *dir)
{
	return dent_first(&dir->entries);
}

static int repo_dirent_name_cmp(const void *a, const void *b)
{
	const struct repo_dirent *dent1 = a, *dent2 = b;
	uint32_t a_offset = dent1->name_offset;
	uint32_t b_offset = dent2->name_offset;
	return (a_offset > b_offset) - (a_offset < b_offset);
}

static int repo_dirent_is_dir(struct repo_dirent *dent)
{
	return dent != NULL && dent->mode == REPO_MODE_DIR;
}

static struct repo_dir *repo_dir_from_dirent(struct repo_dirent *dent)
{
	if (!repo_dirent_is_dir(dent))
		return NULL;
	return dir_pointer(dent->content_offset);
}

static struct repo_dir *repo_clone_dir(struct repo_dir *orig_dir)
{
	uint32_t orig_o, new_o;
	orig_o = dir_offset(orig_dir);
	if (orig_o >= dir_pool.committed)
		return orig_dir;
	new_o = dir_alloc(1);
	orig_dir = dir_pointer(orig_o);
	*dir_pointer(new_o) = *orig_dir;
	return dir_pointer(new_o);
}

static struct repo_dirent *repo_read_dirent(uint32_t revision,
					    const uint32_t *path)
{
	uint32_t name = 0;
	struct repo_dirent *key = dent_pointer(dent_alloc(1));
	struct repo_dir *dir = NULL;
	struct repo_dirent *dent = NULL;
	dir = repo_commit_root_dir(commit_pointer(revision));
	while (~(name = *path++)) {
		key->name_offset = name;
		dent = dent_search(&dir->entries, key);
		if (dent == NULL || !repo_dirent_is_dir(dent))
			break;
		dir = repo_dir_from_dirent(dent);
	}
	dent_free(1);
	return dent;
}

static void repo_write_dirent(const uint32_t *path, uint32_t mode,
			      uint32_t content_offset, uint32_t del)
{
	uint32_t name, revision, dir_o = ~0, parent_dir_o = ~0;
	struct repo_dir *dir;
	struct repo_dirent *key;
	struct repo_dirent *dent = NULL;
	revision = active_commit;
	dir = repo_commit_root_dir(commit_pointer(revision));
	dir = repo_clone_dir(dir);
	commit_pointer(revision)->root_dir_offset = dir_offset(dir);
	while (~(name = *path++)) {
		parent_dir_o = dir_offset(dir);

		key = dent_pointer(dent_alloc(1));
		key->name_offset = name;

		dent = dent_search(&dir->entries, key);
		if (dent == NULL)
			dent = key;
		else
			dent_free(1);

		if (dent == key) {
			dent->mode = REPO_MODE_DIR;
			dent->content_offset = 0;
			dent = dent_insert(&dir->entries, dent);
		}

		if (dent_offset(dent) < dent_pool.committed) {
			dir_o = repo_dirent_is_dir(dent) ?
					dent->content_offset : ~0;
			dent_remove(&dir->entries, dent);
			dent = dent_pointer(dent_alloc(1));
			dent->name_offset = name;
			dent->mode = REPO_MODE_DIR;
			dent->content_offset = dir_o;
			dent = dent_insert(&dir->entries, dent);
		}

		dir = repo_dir_from_dirent(dent);
		dir = repo_clone_dir(dir);
		dent->content_offset = dir_offset(dir);
	}
	if (dent == NULL)
		return;
	dent->mode = mode;
	dent->content_offset = content_offset;
	if (del && ~parent_dir_o)
		dent_remove(&dir_pointer(parent_dir_o)->entries, dent);
}

uint32_t repo_read_path(const uint32_t *path)
{
	uint32_t content_offset = 0;
	struct repo_dirent *dent = repo_read_dirent(active_commit, path);
	if (dent != NULL)
		content_offset = dent->content_offset;
	return content_offset;
}

uint32_t repo_read_mode(const uint32_t *path)
{
	struct repo_dirent *dent = repo_read_dirent(active_commit, path);
	if (dent == NULL)
		die("invalid dump: path to be modified is missing");
	return dent->mode;
}

void repo_copy(uint32_t revision, const uint32_t *src, const uint32_t *dst)
{
	uint32_t mode = 0, content_offset = 0;
	struct repo_dirent *src_dent;
	src_dent = repo_read_dirent(revision, src);
	if (src_dent != NULL) {
		mode = src_dent->mode;
		content_offset = src_dent->content_offset;
		repo_write_dirent(dst, mode, content_offset, 0);
	}
}

void repo_add(uint32_t *path, uint32_t mode, uint32_t blob_mark)
{
	repo_write_dirent(path, mode, blob_mark, 0);
}

void repo_delete(uint32_t *path)
{
	repo_write_dirent(path, 0, 0, 1);
}

static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir);

static void repo_git_add(uint32_t depth, uint32_t *path, struct repo_dirent *dent)
{
	if (repo_dirent_is_dir(dent))
		repo_git_add_r(depth, path, repo_dir_from_dirent(dent));
	else
		fast_export_modify(depth, path,
				   dent->mode, dent->content_offset);
}

static void repo_git_add_r(uint32_t depth, uint32_t *path, struct repo_dir *dir)
{
	struct repo_dirent *de = repo_first_dirent(dir);
	while (de) {
		path[depth] = de->name_offset;
		repo_git_add(depth + 1, path, de);
		de = dent_next(&dir->entries, de);
	}
}

static void repo_diff_r(uint32_t depth, uint32_t *path, struct repo_dir *dir1,
			struct repo_dir *dir2)
{
	struct repo_dirent *de1, *de2;
	de1 = repo_first_dirent(dir1);
	de2 = repo_first_dirent(dir2);

	while (de1 && de2) {
		if (de1->name_offset < de2->name_offset) {
			path[depth] = de1->name_offset;
			fast_export_delete(depth + 1, path);
			de1 = dent_next(&dir1->entries, de1);
			continue;
		}
		if (de1->name_offset > de2->name_offset) {
			path[depth] = de2->name_offset;
			repo_git_add(depth + 1, path, de2);
			de2 = dent_next(&dir2->entries, de2);
			continue;
		}
		path[depth] = de1->name_offset;

		if (de1->mode == de2->mode &&
		    de1->content_offset == de2->content_offset) {
			; /* No change. */
		} else if (repo_dirent_is_dir(de1) && repo_dirent_is_dir(de2)) {
			repo_diff_r(depth + 1, path,
				    repo_dir_from_dirent(de1),
				    repo_dir_from_dirent(de2));
		} else if (!repo_dirent_is_dir(de1) && !repo_dirent_is_dir(de2)) {
			repo_git_add(depth + 1, path, de2);
		} else {
			fast_export_delete(depth + 1, path);
			repo_git_add(depth + 1, path, de2);
		}
		de1 = dent_next(&dir1->entries, de1);
		de2 = dent_next(&dir2->entries, de2);
	}
	while (de1) {
		path[depth] = de1->name_offset;
		fast_export_delete(depth + 1, path);
		de1 = dent_next(&dir1->entries, de1);
	}
	while (de2) {
		path[depth] = de2->name_offset;
		repo_git_add(depth + 1, path, de2);
		de2 = dent_next(&dir2->entries, de2);
	}
}

static uint32_t path_stack[REPO_MAX_PATH_DEPTH];

void repo_diff(uint32_t r1, uint32_t r2)
{
	repo_diff_r(0,
		    path_stack,
		    repo_commit_root_dir(commit_pointer(r1)),
		    repo_commit_root_dir(commit_pointer(r2)));
}

void repo_commit(uint32_t revision, const char *author,
		const struct strbuf *log, const char *uuid, const char *url,
		unsigned long timestamp)
{
	fast_export_commit(revision, author, log, uuid, url, timestamp);
	dent_commit();
	dir_commit();
	active_commit = commit_alloc(1);
	commit_pointer(active_commit)->root_dir_offset =
		commit_pointer(active_commit - 1)->root_dir_offset;
}

static void mark_init(void)
{
	uint32_t i;
	mark = 0;
	for (i = 0; i < dent_pool.size; i++)
		if (!repo_dirent_is_dir(dent_pointer(i)) &&
		    dent_pointer(i)->content_offset > mark)
			mark = dent_pointer(i)->content_offset;
	mark++;
}

void repo_init(void)
{
	mark_init();
	if (commit_pool.size == 0) {
		/* Create empty tree for commit 0. */
		commit_alloc(1);
		commit_pointer(0)->root_dir_offset = dir_alloc(1);
		dir_pointer(0)->entries.trp_root = ~0;
		dir_commit();
	}
	/* Preallocate next commit, ready for changes. */
	active_commit = commit_alloc(1);
	commit_pointer(active_commit)->root_dir_offset =
		commit_pointer(active_commit - 1)->root_dir_offset;
}

void repo_reset(void)
{
	pool_reset();
	commit_reset();
	dir_reset();
	dent_reset();
}
Commit	Line	Data
c0e6c23d DB	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)
68b4cfbc	33	obj_pool_gen(dent, struct repo_dirent, 4096)
c0e6c23d DB	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 */
06316234	41	trp_gen(static, dent_, struct repo_dirent, children, dent, repo_dirent_name_cmp)
c0e6c23d DB	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	{
68b4cfbc	55	return dent_first(&dir->entries);
c0e6c23d DB	56	}
	57
	58	static int repo_dirent_name_cmp(const void a, const void b)
	59	{
68b4cfbc JN	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;
c0e6c23d DB	63	return (a_offset > b_offset) - (a_offset < b_offset);
	64	}
	65
68b4cfbc	66	static int repo_dirent_is_dir(struct repo_dirent *dent)
c0e6c23d	67	{
68b4cfbc	68	return dent != NULL && dent->mode == REPO_MODE_DIR;
c0e6c23d DB	69	}
c0e6c23d DB	70
68b4cfbc	71	static struct repo_dir repo_dir_from_dirent(struct repo_dirent dent)
c0e6c23d	72	{
68b4cfbc	73	if (!repo_dirent_is_dir(dent))
c0e6c23d	74	return NULL;
68b4cfbc	75	return dir_pointer(dent->content_offset);
c0e6c23d DB	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
4f5de755 JN	90	static struct repo_dirent *repo_read_dirent(uint32_t revision,
4f5de755 JN	91	const uint32_t *path)
c0e6c23d DB	92	{
c0e6c23d DB	93	uint32_t name = 0;
68b4cfbc	94	struct repo_dirent *key = dent_pointer(dent_alloc(1));
c0e6c23d	95	struct repo_dir *dir = NULL;
68b4cfbc	96	struct repo_dirent *dent = NULL;
c0e6c23d DB	97	dir = repo_commit_root_dir(commit_pointer(revision));
	98	while (~(name = *path++)) {
	99	key->name_offset = name;
68b4cfbc JN	100	dent = dent_search(&dir->entries, key);
68b4cfbc JN	101	if (dent == NULL \|\| !repo_dirent_is_dir(dent))
c0e6c23d	102	break;
68b4cfbc	103	dir = repo_dir_from_dirent(dent);
c0e6c23d	104	}
68b4cfbc JN	105	dent_free(1);
68b4cfbc JN	106	return dent;
c0e6c23d DB	107	}
c0e6c23d DB	108
e75316de	109	static void repo_write_dirent(const uint32_t *path, uint32_t mode,
c0e6c23d DB	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;
68b4cfbc	115	struct repo_dirent *dent = NULL;
c0e6c23d DB	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
68b4cfbc	123	key = dent_pointer(dent_alloc(1));
c0e6c23d DB	124	key->name_offset = name;
c0e6c23d DB	125
68b4cfbc JN	126	dent = dent_search(&dir->entries, key);
	127	if (dent == NULL)
	128	dent = key;
c0e6c23d	129	else
68b4cfbc	130	dent_free(1);
c0e6c23d	131
68b4cfbc JN	132	if (dent == key) {
	133	dent->mode = REPO_MODE_DIR;
	134	dent->content_offset = 0;
3c939838	135	dent = dent_insert(&dir->entries, dent);
c0e6c23d DB	136	}
c0e6c23d DB	137
68b4cfbc JN	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;
3c939838	146	dent = dent_insert(&dir->entries, dent);
c0e6c23d DB	147	}
c0e6c23d DB	148
68b4cfbc	149	dir = repo_dir_from_dirent(dent);
c0e6c23d	150	dir = repo_clone_dir(dir);
68b4cfbc	151	dent->content_offset = dir_offset(dir);
c0e6c23d	152	}
68b4cfbc	153	if (dent == NULL)
c0e6c23d	154	return;
68b4cfbc JN	155	dent->mode = mode;
68b4cfbc JN	156	dent->content_offset = content_offset;
c0e6c23d	157	if (del && ~parent_dir_o)
68b4cfbc	158	dent_remove(&dir_pointer(parent_dir_o)->entries, dent);
c0e6c23d DB	159	}
c0e6c23d DB	160
4f5de755 JN	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
e75316de JN	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)
c0e6c23d DB	179	{
c0e6c23d DB	180	uint32_t mode = 0, content_offset = 0;
68b4cfbc JN	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;
c0e6c23d DB	186	repo_write_dirent(dst, mode, content_offset, 0);
c0e6c23d DB	187	}
c0e6c23d DB	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
c0e6c23d DB	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
68b4cfbc	202	static void repo_git_add(uint32_t depth, uint32_t path, struct repo_dirent dent)
c0e6c23d	203	{
68b4cfbc JN	204	if (repo_dirent_is_dir(dent))
68b4cfbc JN	205	repo_git_add_r(depth, path, repo_dir_from_dirent(dent));
c0e6c23d DB	206	else
c0e6c23d DB	207	fast_export_modify(depth, path,
68b4cfbc	208	dent->mode, dent->content_offset);
c0e6c23d DB	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);
68b4cfbc	217	de = dent_next(&dir->entries, de);
c0e6c23d DB	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);
68b4cfbc	232	de1 = dent_next(&dir1->entries, de1);
c0e6c23d DB	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);
68b4cfbc	238	de2 = dent_next(&dir2->entries, de2);
c0e6c23d DB	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	}
68b4cfbc JN	256	de1 = dent_next(&dir1->entries, de1);
68b4cfbc JN	257	de2 = dent_next(&dir2->entries, de2);
c0e6c23d DB	258	}
	259	while (de1) {
	260	path[depth] = de1->name_offset;
	261	fast_export_delete(depth + 1, path);
68b4cfbc	262	de1 = dent_next(&dir1->entries, de1);
c0e6c23d DB	263	}
	264	while (de2) {
	265	path[depth] = de2->name_offset;
	266	repo_git_add(depth + 1, path, de2);
68b4cfbc	267	de2 = dent_next(&dir2->entries, de2);
c0e6c23d DB	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
195b7ca6 JN	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)
c0e6c23d DB	284	{
c0e6c23d DB	285	fast_export_commit(revision, author, log, uuid, url, timestamp);
68b4cfbc	286	dent_commit();
c0e6c23d DB	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;
68b4cfbc JN	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;
c0e6c23d DB	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();
68b4cfbc	325	dent_reset();
c0e6c23d	326	}