vcs-svn/repo_tree.c - git - Git at Google

 /*
  * 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, 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(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_copy(uint32_t revision, uint32_t *src, 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);
 	}
 	return mode;
 }

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

 uint32_t repo_replace(uint32_t *path, uint32_t blob_mark)
 {
 	uint32_t mode = 0;
 	struct repo_dirent *src_dent;
 	src_dent = repo_read_dirent(active_commit, path);
 	if (src_dent != NULL) {
 		mode = src_dent->mode;
 		repo_write_dirent(path, mode, blob_mark, 0);
 	}
 	return mode;
 }

 void repo_modify(uint32_t *path, uint32_t mode, uint32_t blob_mark)
 {
 	struct repo_dirent *src_dent;
 	src_dent = repo_read_dirent(active_commit, path);
 	if (src_dent != NULL && blob_mark == 0)
 		blob_mark = src_dent->content_offset;
 	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, uint32_t author, char *log, uint32_t uuid,
 		 uint32_t 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();
 }
	/*
	* 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, 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(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_copy(uint32_t revision, uint32_t src, 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);
	}
	return mode;
	}

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

	uint32_t repo_replace(uint32_t *path, uint32_t blob_mark)
	{
	uint32_t mode = 0;
	struct repo_dirent *src_dent;
	src_dent = repo_read_dirent(active_commit, path);
	if (src_dent != NULL) {
	mode = src_dent->mode;
	repo_write_dirent(path, mode, blob_mark, 0);
	}
	return mode;
	}

	void repo_modify(uint32_t *path, uint32_t mode, uint32_t blob_mark)
	{
	struct repo_dirent *src_dent;
	src_dent = repo_read_dirent(active_commit, path);
	if (src_dent != NULL && blob_mark == 0)
	blob_mark = src_dent->content_offset;
	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, uint32_t author, char *log, uint32_t uuid,
	uint32_t 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();
	}