diff --git a/Makefile b/Makefile
index 7ffc383f2b..09cfd3ef1b 100644
--- a/Makefile
+++ b/Makefile
@@ -844,6 +844,7 @@ LIB_OBJS += branch.o
 LIB_OBJS += bulk-checkin.o
 LIB_OBJS += bundle.o
 LIB_OBJS += cache-tree.o
+LIB_OBJS += change-table.o
 LIB_OBJS += chdir-notify.o
 LIB_OBJS += checkout.o
 LIB_OBJS += color.o
diff --git a/change-table.c b/change-table.c
new file mode 100644
index 0000000000..6daff5f58c
--- /dev/null
+++ b/change-table.c
@@ -0,0 +1,207 @@
+#include "cache.h"
+#include "change-table.h"
+#include "commit.h"
+#include "ref-filter.h"
+#include "metacommit-parser.h"
+
+void change_table_init(struct change_table *to_initialize)
+{
+	memset(to_initialize, 0, sizeof(*to_initialize));
+	mem_pool_init(&(to_initialize->memory_pool), 0);
+	to_initialize->memory_pool->block_alloc = 4*1024 - sizeof(struct mp_block);
+	oidmap_init(&(to_initialize->oid_to_metadata_index), 0);
+	string_list_init(&(to_initialize->refname_to_change_head), 1);
+}
+
+static void change_list_clear(struct change_list *to_clear) {
+	string_list_clear(&to_clear->additional_refnames, 0);
+}
+
+static void commit_change_list_entry_clear(
+	struct commit_change_list_entry *to_clear) {
+	change_list_clear(&(to_clear->changes));
+}
+
+static void change_head_array_clear(struct change_head_array *to_clear)
+{
+	FREE_AND_NULL(to_clear->array);
+}
+
+void change_table_clear(struct change_table *to_clear)
+{
+	struct oidmap_iter iter;
+	struct commit_change_list_entry *next;
+	for (next = oidmap_iter_first(&to_clear->oid_to_metadata_index, &iter);
+		next;
+		next = oidmap_iter_next(&iter)) {
+
+		commit_change_list_entry_clear(next);
+	}
+
+	oidmap_free(&to_clear->oid_to_metadata_index, 0);
+	string_list_clear(&(to_clear->refname_to_change_head), 0);
+	change_head_array_clear(&to_clear->heads);
+	mem_pool_discard(to_clear->memory_pool, 0);
+}
+
+/*
+ * Appends a new, empty, change_head struct to the end of the given array.
+ * Returns the index of the newly-added struct.
+ */
+static int change_head_array_append(struct change_head_array *to_add)
+{
+	int index = to_add->nr++;
+	struct change_head *new_head;
+	ALLOC_GROW(to_add->array, to_add->nr, to_add->alloc);
+	new_head = &(to_add->array[index]);
+	memset(new_head, 0, sizeof(*new_head));
+	return index;
+}
+
+static void add_head_to_commit(struct change_table *to_modify,
+	const struct object_id *to_add, const char *refname)
+{
+	struct commit_change_list_entry *entry;
+
+	// Note: the indices in the map are 1-based. 0 is used to indicate a missing
+	// element.
+	entry = oidmap_get(&(to_modify->oid_to_metadata_index), to_add);
+	if (!entry) {
+		entry = mem_pool_calloc(to_modify->memory_pool, 1,
+			sizeof(*entry));
+		oidcpy(&entry->entry.oid, to_add);
+		oidmap_put(&(to_modify->oid_to_metadata_index), entry);
+		string_list_init(&(entry->changes.additional_refnames), 0);
+	}
+
+	if (entry->changes.first_refname == NULL) {
+		entry->changes.first_refname = refname;
+	} else {
+		string_list_insert(&entry->changes.additional_refnames, refname);
+	}
+}
+
+void change_table_add(struct change_table *to_modify, const char *refname,
+	struct commit *to_add)
+{
+	struct change_head *new_head;
+	struct string_list_item *new_item;
+	long index;
+	int metacommit_type;
+
+	index = change_head_array_append(&to_modify->heads);
+	new_head = &(to_modify->heads.array[index]);
+
+	oidcpy(&new_head->head, &(to_add->object.oid));
+
+	metacommit_type = get_metacommit_content(to_add, &new_head->content);
+	if (metacommit_type == METACOMMIT_TYPE_NONE) {
+		oidcpy(&new_head->content, &(to_add->object.oid));
+	}
+	new_head->abandoned = (metacommit_type == METACOMMIT_TYPE_ABANDONED);
+	new_head->remote = starts_with(refname, "refs/remote/");
+	new_head->hidden = starts_with(refname, "refs/hiddenmetas/");
+
+	new_item = string_list_insert(&to_modify->refname_to_change_head, refname);
+	new_item->util = (void*)index;
+	// Use pointers to the copy of the string we're retaining locally
+	refname = new_item->string;
+
+	if (!oideq(&new_head->content, &new_head->head)) {
+		add_head_to_commit(to_modify, &(new_head->content), refname);
+	}
+	add_head_to_commit(to_modify, &(new_head->head), refname);
+}
+
+void change_table_add_all_visible(struct change_table *to_modify,
+	struct repository* repo)
+{
+	struct ref_filter filter;
+	const char *name_patterns[] = {NULL};
+	memset(&filter, 0, sizeof(filter));
+	filter.kind = FILTER_REFS_CHANGES;
+	filter.name_patterns = name_patterns;
+
+	change_table_add_matching_filter(to_modify, repo, &filter);
+}
+
+void change_table_add_matching_filter(struct change_table *to_modify,
+	struct repository* repo, struct ref_filter *filter)
+{
+	struct ref_array matching_refs;
+	int i;
+
+	memset(&matching_refs, 0, sizeof(matching_refs));
+	filter_refs(&matching_refs, filter, filter->kind);
+
+	// Determine the object id for the latest content commit for each change.
+	// Fetch the commit at the head of each change ref. If it's a normal commit,
+	// that's the commit we want. If it's a metacommit, locate its content parent
+	// and use that.
+
+	for (i = 0; i < matching_refs.nr; i++) {
+		struct ref_array_item *item = matching_refs.items[i];
+		struct commit *commit = item->commit;
+
+		commit = lookup_commit_reference_gently(repo, &(item->objectname), 1);
+
+		if (commit != NULL) {
+			change_table_add(to_modify, item->refname, commit);
+		}
+	}
+
+	ref_array_clear(&matching_refs);
+}
+
+static int return_true_callback(const char *refname, void *cb_data)
+{
+	return 1;
+}
+
+int change_table_has_change_referencing(struct change_table *changes,
+	const struct object_id *referenced_commit_id)
+{
+	return for_each_change_referencing(changes, referenced_commit_id,
+		return_true_callback, NULL);
+}
+
+int for_each_change_referencing(struct change_table *table,
+	const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data)
+{
+	const struct change_list *changes;
+	int i;
+	int retvalue;
+	struct commit_change_list_entry *entry;
+
+	entry = oidmap_get(&table->oid_to_metadata_index,
+		referenced_commit_id);
+	// If this commit isn't referenced by any changes, it won't be in the map
+	if (!entry) {
+		return 0;
+	}
+	changes = &(entry->changes);
+	if (changes->first_refname == NULL) {
+		return 0;
+	}
+	retvalue = fn(changes->first_refname, cb_data);
+	for (i = 0; retvalue == 0 && i < changes->additional_refnames.nr; i++) {
+		retvalue = fn(changes->additional_refnames.items[i].string, cb_data);
+	}
+	return retvalue;
+}
+
+struct change_head* get_change_head(struct change_table *heads,
+	const char* refname)
+{
+	struct string_list_item *item = string_list_lookup(
+		&heads->refname_to_change_head, refname);
+	long index;
+
+	if (!item) {
+		return NULL;
+	}
+
+	index = (long)item->util;
+	return &(heads->heads.array[index]);
+}
+
diff --git a/change-table.h b/change-table.h
new file mode 100644
index 0000000000..85bb19c3bf
--- /dev/null
+++ b/change-table.h
@@ -0,0 +1,138 @@
+#ifndef CHANGE_TABLE_H
+#define CHANGE_TABLE_H
+
+#include "oidmap.h"
+
+struct commit;
+struct ref_filter;
+
+/*
+ * This struct holds a list of change refs. The first element is stored inline,
+ * to optimize for small lists.
+ */
+struct change_list {
+	/* Ref name for the first change in the list, or null if none.
+	 *
+	 * This field is private. Use for_each_change_in to read.
+	 */
+	const char* first_refname;
+	/* List of additional change refs. Note that this is empty if the list
+	 * contains 0 or 1 elements.
+	 *
+	 * This field is private. Use for_each_change_in to read.
+	 */
+	struct string_list additional_refnames;
+};
+
+/*
+ * Holds information about the head of a single change.
+ */
+struct change_head {
+	/*
+	 * The location pointed to by the head of the change. May be a commit or a
+	 * metacommit.
+	 */
+	struct object_id head;
+	/*
+	 * The content commit for the latest commit in the change. Always points to a
+	 * real commit, never a metacommit.
+	 */
+	struct object_id content;
+	/*
+	 * Abandoned: indicates that the content commit should be removed from the
+	 * history.
+	 *
+	 * Hidden: indicates that the change is an inactive change from the
+	 * hiddenmetas namespace. Such changes will be hidden from the user by
+	 * default.
+	 *
+	 * Deleted: indicates that the change has been removed from the repository.
+	 * That is the ref was deleted since the time this struct was created. Such
+	 * entries should be ignored.
+	 */
+	int abandoned:1,
+		hidden:1,
+		remote:1,
+		deleted:1;
+};
+
+/*
+ * An array of change_head.
+ */
+struct change_head_array {
+	struct change_head* array;
+	int nr;
+	int alloc;
+};
+
+/*
+ * Holds the list of change refs whose content points to a particular content
+ * commit.
+ */
+struct commit_change_list_entry {
+	struct oidmap_entry entry;
+	struct change_list changes;
+};
+
+/*
+ * Holds information about the heads of each change, and permits effecient
+ * lookup from a commit to the changes that reference it directly.
+ *
+ * All fields should be considered private. Use the change_table functions
+ * to interact with this struct.
+ */
+struct change_table {
+	/**
+	 * Memory pool for the objects allocated by the change table.
+	 */
+	struct mem_pool *memory_pool;
+	/* Map object_id to commit_change_list_entry structs. */
+	struct oidmap oid_to_metadata_index;
+	/* List of ref names. The util value is an int index into change_metadata
+	 * array.
+	 */
+	struct string_list refname_to_change_head;
+	/* change_head structures for each head */
+	struct change_head_array heads;
+};
+
+extern void change_table_init(struct change_table *to_initialize);
+extern void change_table_clear(struct change_table *to_clear);
+
+/* Adds the given change head to the change_table struct */
+extern void change_table_add(struct change_table *to_modify,
+	const char *refname, struct commit *target);
+
+/* Adds the non-hidden local changes to the given change_table struct.
+ */
+extern void change_table_add_all_visible(struct change_table *to_modify,
+	struct repository *repo);
+
+/*
+ * Adds all changes matching the given ref filter to the given change_table
+ * struct.
+ */
+extern void change_table_add_matching_filter(struct change_table *to_modify,
+	struct repository* repo, struct ref_filter *filter);
+
+typedef int each_change_fn(const char *refname, void *cb_data);
+
+extern int change_table_has_change_referencing(struct change_table *changes,
+	const struct object_id *referenced_commit_id);
+
+/* Iterates over all changes that reference the given commit. For metacommits,
+ * this is the list of changes that point directly to that metacommit.
+ * For normal commits, this is the list of changes that have this commit as
+ * their latest content.
+ */
+extern int for_each_change_referencing(struct change_table *heads,
+	const struct object_id *referenced_commit_id, each_change_fn fn, void *cb_data);
+
+/**
+ * Returns the change head for the given refname. Returns NULL if no such change
+ * exists.
+ */
+extern struct change_head* get_change_head(struct change_table *heads,
+	const char* refname);
+
+#endif
