repo_tree.c   [plain text]

/*
 * 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();
}