Merge pull request #803 from schu/gsoc-pack-objects

[GSoC] RFC: pack objects

16 files changed, 2300 insertions, 21 deletions

diff --git a/include/git2.h b/include/git2.h
index 805044abb..d55543986 100644
--- a/include/git2.h
+++ b/include/git2.h
@@ -51,5 +51,6 @@
 #include "git2/notes.h"
 #include "git2/reset.h"
 #include "git2/message.h"
+#include "git2/pack.h"
 
 #endif
diff --git a/include/git2/errors.h b/include/git2/errors.h
index f6d9bf2e3..1c4e910a6 100644
--- a/include/git2/errors.h
+++ b/include/git2/errors.h
@@ -56,6 +56,7 @@ typedef enum {
 	GITERR_INDEXER,
 	GITERR_SSL,
 	GITERR_SUBMODULE,
+	GITERR_THREAD,
 } git_error_t;
 
 /**
diff --git a/include/git2/pack.h b/include/git2/pack.h
new file mode 100644
index 000000000..748ad2e11
--- /dev/null
+++ b/include/git2/pack.h
@@ -0,0 +1,89 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_git_pack_h__
+#define INCLUDE_git_pack_h__
+
+#include "common.h"
+#include "oid.h"
+
+/**
+ * @file git2/pack.h
+ * @brief Git pack management routines
+ * @defgroup git_pack Git pack management routines
+ * @ingroup Git
+ * @{
+ */
+GIT_BEGIN_DECL
+
+/**
+ * Initialize a new packbuilder
+ *
+ * @param out The new packbuilder object
+ * @param repo The repository
+ *
+ * @return 0 or an error code
+ */
+GIT_EXTERN(int) git_packbuilder_new(git_packbuilder **out, git_repository *repo);
+
+/**
+ * Set number of threads to spawn
+ *
+ * By default, libgit2 won't spawn any threads at all;
+ * when set to 0, libgit2 will autodetect the number of
+ * CPUs.
+ *
+ * @param pb The packbuilder
+ * @param n Number of threads to spawn
+ */
+GIT_EXTERN(void) git_packbuilder_set_threads(git_packbuilder *pb, unsigned int n);
+
+/**
+ * Insert a single object
+ *
+ * For an optimal pack it's mandatory to insert objects in recency order,
+ * commits followed by trees and blobs.
+ *
+ * @param pb The packbuilder
+ * @param oid The oid of the commit
+ * @param oid The name; might be NULL
+ *
+ * @return 0 or an error code
+ */
+GIT_EXTERN(int) git_packbuilder_insert(git_packbuilder *pb, const git_oid *oid,	const char *name);
+
+/**
+ * Insert a root tree object
+ *
+ * This will add the tree as well as all referenced trees and blobs.
+ *
+ * @param pb The packbuilder
+ * @param oid The oid of the root tree
+ *
+ * @return 0 or an error code
+ */
+GIT_EXTERN(int) git_packbuilder_insert_tree(git_packbuilder *pb, const git_oid *oid);
+
+/**
+ * Write the new pack and the corresponding index to path
+ *
+ * @param pb The packbuilder
+ * @param path Directory to store the new pack and index
+ *
+ * @return 0 or an error code
+ */
+GIT_EXTERN(int) git_packbuilder_write(git_packbuilder *pb, const char *file);
+
+/**
+ * Free the packbuilder and all associated data
+ *
+ * @param pb The packbuilder
+ */
+GIT_EXTERN(void) git_packbuilder_free(git_packbuilder *pb);
+
+/** @} */
+GIT_END_DECL
+#endif
diff --git a/include/git2/tag.h b/include/git2/tag.h
index aab4b77a8..08504aef4 100644
--- a/include/git2/tag.h
+++ b/include/git2/tag.h
@@ -277,6 +277,21 @@ GIT_EXTERN(int) git_tag_list_match(
 		const char *pattern,
 		git_repository *repo);
 
+
+typedef int (*git_tag_foreach_cb)(const char *name, git_oid *oid, void *data);
+/**
+ * Call callback `cb' for each tag in the repository
+ *
+ * @param repo Repository
+ * @param cb Callback function
+ * @param cb_data Pointer to callback data (optional)
+ */
+GIT_EXTERN(int) git_tag_foreach(
+		git_repository *repo,
+		git_tag_foreach_cb cb,
+		void *cb_data);
+
+
 /**
  * Recursively peel a tag until a non tag git_object
  * is met
diff --git a/include/git2/types.h b/include/git2/types.h
index 26e9c57e7..01ddbf3d6 100644
--- a/include/git2/types.h
+++ b/include/git2/types.h
@@ -137,6 +137,9 @@ typedef struct git_reflog git_reflog;
 /** Representation of a git note */
 typedef struct git_note git_note;
 
+/** Representation of a git packbuilder */
+typedef struct git_packbuilder git_packbuilder;
+
 /** Time in a signature */
 typedef struct git_time {
 	git_time_t time; /** time in seconds from epoch */
diff --git a/src/compress.c b/src/compress.c
new file mode 100644
index 000000000..9388df1f2
--- /dev/null
+++ b/src/compress.c
@@ -0,0 +1,53 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+
+#include "compress.h"
+
+#include <zlib.h>
+
+#define BUFFER_SIZE (1024 * 1024)
+
+int git__compress(git_buf *buf, const void *buff, size_t len)
+{
+	z_stream zs;
+	char *zb;
+	size_t have;
+
+	memset(&zs, 0, sizeof(zs));
+	if (deflateInit(&zs, Z_DEFAULT_COMPRESSION) != Z_OK)
+		return -1;
+
+	zb = git__malloc(BUFFER_SIZE);
+	GITERR_CHECK_ALLOC(zb);
+
+	zs.next_in = (void *)buff;
+	zs.avail_in = (uInt)len;
+
+	do {
+		zs.next_out = (unsigned char *)zb;
+		zs.avail_out = BUFFER_SIZE;
+
+		if (deflate(&zs, Z_FINISH) == Z_STREAM_ERROR) {
+			git__free(zb);
+			return -1;
+		}
+
+		have = BUFFER_SIZE - (size_t)zs.avail_out;
+
+		if (git_buf_put(buf, zb, have) < 0) {
+			git__free(zb);
+			return -1;
+		}
+
+	} while (zs.avail_out == 0);
+
+	assert(zs.avail_in == 0);
+
+	deflateEnd(&zs);
+	git__free(zb);
+	return 0;
+}
diff --git a/src/compress.h b/src/compress.h
new file mode 100644
index 000000000..4b7388564
--- /dev/null
+++ b/src/compress.h
@@ -0,0 +1,16 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_compress_h__
+#define INCLUDE_compress_h__
+
+#include "common.h"
+
+#include "buffer.h"
+
+int git__compress(git_buf *buf, const void *buff, size_t len);
+
+#endif /* INCLUDE_compress_h__ */
diff --git a/src/delta.c b/src/delta.c
new file mode 100644
index 000000000..49f7df017
--- /dev/null
+++ b/src/delta.c
@@ -0,0 +1,491 @@
+/*
+ * diff-delta.c: generate a delta between two buffers
+ *
+ * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
+ * http://www.xmailserver.org/xdiff-lib.html
+ *
+ * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
+ *
+ * Modified for libgit2 by Michael Schubert <schu@schu.io>, (C) 2012
+ *
+ * This code is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#include "delta.h"
+
+/* maximum hash entry list for the same hash bucket */
+#define HASH_LIMIT 64
+
+#define RABIN_SHIFT 23
+#define RABIN_WINDOW 16
+
+static const unsigned int T[256] = {
+	0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344,
+	0x508c0e37, 0xfbd5bae6, 0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259,
+	0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc, 0x18fd9e54, 0xb3a42a85,
+	0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2,
+	0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a,
+	0x440f5f49, 0xef56eb98, 0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db,
+	0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e, 0x3d85f382, 0x96dc4753,
+	0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964,
+	0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8,
+	0x798aaccb, 0xd2d3181a, 0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5,
+	0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730, 0x63f67950, 0xc8afcd81,
+	0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6,
+	0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e,
+	0x3f04b84d, 0x945d0c9c, 0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77,
+	0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2, 0x7775282e, 0xdc2c9cff,
+	0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8,
+	0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc,
+	0x02814bcf, 0xa9d8ff1e, 0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1,
+	0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034, 0x4af0dbac, 0xe1a96f7d,
+	0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a,
+	0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2,
+	0x16021ab1, 0xbd5bae60, 0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02,
+	0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97, 0x60cb895b, 0xcb923d8a,
+	0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd,
+	0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61,
+	0x24c4d612, 0x8f9d62c3, 0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c,
+	0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9, 0x5d4e7ad9, 0xf617ce08,
+	0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f,
+	0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7,
+	0x01bcbbc4, 0xaae50f15, 0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe,
+	0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b, 0x49cd2ba7, 0xe2949f76,
+	0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141,
+	0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65,
+	0x5fcf3116, 0xf49685c7, 0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78,
+	0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed, 0x17bea175, 0xbce715a4,
+	0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93,
+	0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b,
+	0x4b4c6068, 0xe015d4b9, 0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa,
+	0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f, 0x32c6cca3, 0x999f7872,
+	0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645,
+	0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99,
+	0x76c993ea, 0xdd90273b, 0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84,
+	0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811
+};
+
+static const unsigned int U[256] = {
+	0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a,
+	0x510da98c, 0x2fb88981, 0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48,
+	0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f, 0x1cf9751c, 0x624c5511,
+	0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d,
+	0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8,
+	0x4388661e, 0x3d3d4613, 0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe,
+	0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9, 0x378e50b6, 0x493b70bb,
+	0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937,
+	0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e,
+	0x740636a8, 0x0ab316a5, 0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c,
+	0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b, 0x73e5d470, 0x0d50f47d,
+	0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1,
+	0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4,
+	0x2c94c772, 0x5221e77f, 0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa,
+	0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed, 0x61601be2, 0x1fd53bef,
+	0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263,
+	0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302,
+	0x1b1a97c4, 0x65afb7c9, 0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000,
+	0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47, 0x56ee4b54, 0x285b6b59,
+	0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5,
+	0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90,
+	0x099f5856, 0x772a785b, 0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7,
+	0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0, 0x42eea6bf, 0x3c5b86b2,
+	0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e,
+	0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467,
+	0x0166c0a1, 0x7fd3e0ac, 0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765,
+	0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22, 0x7560f609, 0x0bd5d604,
+	0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88,
+	0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd,
+	0x2a11e50b, 0x54a4c506, 0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3,
+	0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94, 0x67e5399b, 0x19501996,
+	0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a,
+	0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b,
+	0x6e7a61cd, 0x10cf41c0, 0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609,
+	0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e, 0x238ebd5d, 0x5d3b9d50,
+	0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc,
+	0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99,
+	0x7cffae5f, 0x024a8e52, 0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf,
+	0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8, 0x08f998f7, 0x764cb8fa,
+	0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176,
+	0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f,
+	0x4b71fee9, 0x35c4dee4, 0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d,
+	0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a
+};
+
+struct index_entry {
+	const unsigned char *ptr;
+	unsigned int val;
+};
+
+struct unpacked_index_entry {
+	struct index_entry entry;
+	struct unpacked_index_entry *next;
+};
+
+struct git_delta_index {
+	unsigned long memsize;
+	const void *src_buf;
+	unsigned long src_size;
+	unsigned int hash_mask;
+	struct index_entry *hash[GIT_FLEX_ARRAY];
+};
+
+struct git_delta_index *
+git_delta_create_index(const void *buf, unsigned long bufsize)
+{
+	unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
+	const unsigned char *data, *buffer = buf;
+	struct git_delta_index *index;
+	struct unpacked_index_entry *entry, **hash;
+	struct index_entry *packed_entry, **packed_hash;
+	void *mem;
+	unsigned long memsize;
+
+	if (!buf || !bufsize)
+		return NULL;
+
+	/* Determine index hash size.  Note that indexing skips the
+	   first byte to allow for optimizing the Rabin's polynomial
+	   initialization in create_delta(). */
+	entries = (bufsize - 1) / RABIN_WINDOW;
+	if (bufsize >= 0xffffffffUL) {
+		/*
+		 * Current delta format can't encode offsets into
+		 * reference buffer with more than 32 bits.
+		 */
+		entries = 0xfffffffeU / RABIN_WINDOW;
+	}
+	hsize = entries / 4;
+	for (i = 4; (1u << i) < hsize && i < 31; i++);
+	hsize = 1 << i;
+	hmask = hsize - 1;
+
+	/* allocate lookup index */
+	memsize = sizeof(*hash) * hsize +
+		  sizeof(*entry) * entries;
+	mem = git__malloc(memsize);
+	if (!mem)
+		return NULL;
+	hash = mem;
+	mem = hash + hsize;
+	entry = mem;
+
+	memset(hash, 0, hsize * sizeof(*hash));
+
+	/* allocate an array to count hash entries */
+	hash_count = calloc(hsize, sizeof(*hash_count));
+	if (!hash_count) {
+		git__free(hash);
+		return NULL;
+	}
+
+	/* then populate the index */
+	prev_val = ~0;
+	for (data = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;
+	     data >= buffer;
+	     data -= RABIN_WINDOW) {
+		unsigned int val = 0;
+		for (i = 1; i <= RABIN_WINDOW; i++)
+			val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
+		if (val == prev_val) {
+			/* keep the lowest of consecutive identical blocks */
+			entry[-1].entry.ptr = data + RABIN_WINDOW;
+			--entries;
+		} else {
+			prev_val = val;
+			i = val & hmask;
+			entry->entry.ptr = data + RABIN_WINDOW;
+			entry->entry.val = val;
+			entry->next = hash[i];
+			hash[i] = entry++;
+			hash_count[i]++;
+		}
+	}
+
+	/*
+	 * Determine a limit on the number of entries in the same hash
+	 * bucket.  This guards us against pathological data sets causing
+	 * really bad hash distribution with most entries in the same hash
+	 * bucket that would bring us to O(m*n) computing costs (m and n
+	 * corresponding to reference and target buffer sizes).
+	 *
+	 * Make sure none of the hash buckets has more entries than
+	 * we're willing to test.  Otherwise we cull the entry list
+	 * uniformly to still preserve a good repartition across
+	 * the reference buffer.
+	 */
+	for (i = 0; i < hsize; i++) {
+		int acc;
+
+		if (hash_count[i] <= HASH_LIMIT)
+			continue;
+
+		/* We leave exactly HASH_LIMIT entries in the bucket */
+		entries -= hash_count[i] - HASH_LIMIT;
+
+		entry = hash[i];
+		acc = 0;
+
+		/*
+		 * Assume that this loop is gone through exactly
+		 * HASH_LIMIT times and is entered and left with
+		 * acc==0.  So the first statement in the loop
+		 * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
+		 * to the accumulator, and the inner loop consequently
+		 * is run (hash_count[i]-HASH_LIMIT) times, removing
+		 * one element from the list each time.  Since acc
+		 * balances out to 0 at the final run, the inner loop
+		 * body can't be left with entry==NULL.  So we indeed
+		 * encounter entry==NULL in the outer loop only.
+		 */
+		do {
+			acc += hash_count[i] - HASH_LIMIT;
+			if (acc > 0) {
+				struct unpacked_index_entry *keep = entry;
+				do {
+					entry = entry->next;
+					acc -= HASH_LIMIT;
+				} while (acc > 0);
+				keep->next = entry->next;
+			}
+			entry = entry->next;
+		} while (entry);
+	}
+	git__free(hash_count);
+
+	/*
+	 * Now create the packed index in array form
+	 * rather than linked lists.
+	 */
+	memsize = sizeof(*index)
+		+ sizeof(*packed_hash) * (hsize+1)
+		+ sizeof(*packed_entry) * entries;
+	mem = git__malloc(memsize);
+	if (!mem) {
+		git__free(hash);
+		return NULL;
+	}
+
+	index = mem;
+	index->memsize = memsize;
+	index->src_buf = buf;
+	index->src_size = bufsize;
+	index->hash_mask = hmask;
+
+	mem = index->hash;
+	packed_hash = mem;
+	mem = packed_hash + (hsize+1);
+	packed_entry = mem;
+
+	for (i = 0; i < hsize; i++) {
+		/*
+		 * Coalesce all entries belonging to one linked list
+		 * into consecutive array entries.
+		 */
+		packed_hash[i] = packed_entry;
+		for (entry = hash[i]; entry; entry = entry->next)
+			*packed_entry++ = entry->entry;
+	}
+
+	/* Sentinel value to indicate the length of the last hash bucket */
+	packed_hash[hsize] = packed_entry;
+
+	assert(packed_entry - (struct index_entry *)mem == entries);
+	git__free(hash);
+
+	return index;
+}
+
+void git_delta_free_index(struct git_delta_index *index)
+{
+	git__free(index);
+}
+
+unsigned long git_delta_sizeof_index(struct git_delta_index *index)
+{
+	if (index)
+		return index->memsize;
+	else
+		return 0;
+}
+
+/*
+ * The maximum size for any opcode sequence, including the initial header
+ * plus Rabin window plus biggest copy.
+ */
+#define MAX_OP_SIZE	(5 + 5 + 1 + RABIN_WINDOW + 7)
+
+void *
+git_delta_create(const struct git_delta_index *index,
+		 const void *trg_buf, unsigned long trg_size,
+		 unsigned long *delta_size, unsigned long max_size)
+{
+	unsigned int i, outpos, outsize, moff, msize, val;
+	int inscnt;
+	const unsigned char *ref_data, *ref_top, *data, *top;
+	unsigned char *out;
+
+	if (!trg_buf || !trg_size)
+		return NULL;
+
+	outpos = 0;
+	outsize = 8192;
+	if (max_size && outsize >= max_size)
+		outsize = max_size + MAX_OP_SIZE + 1;
+	out = git__malloc(outsize);
+	if (!out)
+		return NULL;
+
+	/* store reference buffer size */
+	i = index->src_size;
+	while (i >= 0x80) {
+		out[outpos++] = i | 0x80;
+		i >>= 7;
+	}
+	out[outpos++] = i;
+
+	/* store target buffer size */
+	i = trg_size;
+	while (i >= 0x80) {
+		out[outpos++] = i | 0x80;
+		i >>= 7;
+	}
+	out[outpos++] = i;
+
+	ref_data = index->src_buf;
+	ref_top = ref_data + index->src_size;
+	data = trg_buf;
+	top = (const unsigned char *) trg_buf + trg_size;
+
+	outpos++;
+	val = 0;
+	for (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {
+		out[outpos++] = *data;
+		val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
+	}
+	inscnt = i;
+
+	moff = 0;
+	msize = 0;
+	while (data < top) {
+		if (msize < 4096) {
+			struct index_entry *entry;
+			val ^= U[data[-RABIN_WINDOW]];
+			val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
+			i = val & index->hash_mask;
+			for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {
+				const unsigned char *ref = entry->ptr;
+				const unsigned char *src = data;
+				unsigned int ref_size = ref_top - ref;
+				if (entry->val != val)
+					continue;
+				if (ref_size > (unsigned int)(top - src))
+					ref_size = top - src;
+				if (ref_size <= msize)
+					break;
+				while (ref_size-- && *src++ == *ref)
+					ref++;
+				if (msize < (unsigned int)(ref - entry->ptr)) {
+					/* this is our best match so far */
+					msize = ref - entry->ptr;
+					moff = entry->ptr - ref_data;
+					if (msize >= 4096) /* good enough */
+						break;
+				}
+			}
+		}
+
+		if (msize < 4) {
+			if (!inscnt)
+				outpos++;
+			out[outpos++] = *data++;
+			inscnt++;
+			if (inscnt == 0x7f) {
+				out[outpos - inscnt - 1] = inscnt;
+				inscnt = 0;
+			}
+			msize = 0;
+		} else {
+			unsigned int left;
+			unsigned char *op;
+
+			if (inscnt) {
+				while (moff && ref_data[moff-1] == data[-1]) {
+					/* we can match one byte back */
+					msize++;
+					moff--;
+					data--;
+					outpos--;
+					if (--inscnt)
+						continue;
+					outpos--;  /* remove count slot */
+					inscnt--;  /* make it -1 */
+					break;
+				}
+				out[outpos - inscnt - 1] = inscnt;
+				inscnt = 0;
+			}
+
+			/* A copy op is currently limited to 64KB (pack v2) */
+			left = (msize < 0x10000) ? 0 : (msize - 0x10000);
+			msize -= left;
+
+			op = out + outpos++;
+			i = 0x80;
+
+			if (moff & 0x000000ff)
+				out[outpos++] = moff >> 0,  i |= 0x01;
+			if (moff & 0x0000ff00)
+				out[outpos++] = moff >> 8,  i |= 0x02;
+			if (moff & 0x00ff0000)
+				out[outpos++] = moff >> 16, i |= 0x04;
+			if (moff & 0xff000000)
+				out[outpos++] = moff >> 24, i |= 0x08;
+
+			if (msize & 0x00ff)
+				out[outpos++] = msize >> 0, i |= 0x10;
+			if (msize & 0xff00)
+				out[outpos++] = msize >> 8, i |= 0x20;
+
+			*op = i;
+
+			data += msize;
+			moff += msize;
+			msize = left;
+
+			if (msize < 4096) {
+				int j;
+				val = 0;
+				for (j = -RABIN_WINDOW; j < 0; j++)
+					val = ((val << 8) | data[j])
+					      ^ T[val >> RABIN_SHIFT];
+			}
+		}
+
+		if (outpos >= outsize - MAX_OP_SIZE) {
+			void *tmp = out;
+			outsize = outsize * 3 / 2;
+			if (max_size && outsize >= max_size)
+				outsize = max_size + MAX_OP_SIZE + 1;
+			if (max_size && outpos > max_size)
+				break;
+			out = git__realloc(out, outsize);
+			if (!out) {
+				git__free(tmp);
+				return NULL;
+			}
+		}
+	}
+
+	if (inscnt)
+		out[outpos - inscnt - 1] = inscnt;
+
+	if (max_size && outpos > max_size) {
+		git__free(out);
+		return NULL;
+	}
+
+	*delta_size = outpos;
+	return out;
+}
diff --git a/src/delta.h b/src/delta.h
new file mode 100644
index 000000000..b0b8e4183
--- /dev/null
+++ b/src/delta.h
@@ -0,0 +1,112 @@
+/*
+ * diff-delta code taken from git.git. See diff-delta.c for details.
+ *
+ */
+#ifndef INCLUDE_git_delta_h__
+#define INCLUDE_git_delta_h__
+
+#include "common.h"
+
+/* opaque object for delta index */
+struct git_delta_index;
+
+/*
+ * create_delta_index: compute index data from given buffer
+ *
+ * This returns a pointer to a struct delta_index that should be passed to
+ * subsequent create_delta() calls, or to free_delta_index().  A NULL pointer
+ * is returned on failure.  The given buffer must not be freed nor altered
+ * before free_delta_index() is called.  The returned pointer must be freed
+ * using free_delta_index().
+ */
+extern struct git_delta_index *
+git_delta_create_index(const void *buf, unsigned long bufsize);
+
+/*
+ * free_delta_index: free the index created by create_delta_index()
+ *
+ * Given pointer must be what create_delta_index() returned, or NULL.
+ */
+extern void git_delta_free_index(struct git_delta_index *index);
+
+/*
+ * sizeof_delta_index: returns memory usage of delta index
+ *
+ * Given pointer must be what create_delta_index() returned, or NULL.
+ */
+extern unsigned long git_delta_sizeof_index(struct git_delta_index *index);
+
+/*
+ * create_delta: create a delta from given index for the given buffer
+ *
+ * This function may be called multiple times with different buffers using
+ * the same delta_index pointer.  If max_delta_size is non-zero and the
+ * resulting delta is to be larger than max_delta_size then NULL is returned.
+ * On success, a non-NULL pointer to the buffer with the delta data is
+ * returned and *delta_size is updated with its size.  The returned buffer
+ * must be freed by the caller.
+ */
+extern void *
+git_delta_create(const struct git_delta_index *index,
+		 const void *buf, unsigned long bufsize,
+		 unsigned long *delta_size,
+		 unsigned long max_delta_size);
+
+/*
+ * diff_delta: create a delta from source buffer to target buffer
+ *
+ * If max_delta_size is non-zero and the resulting delta is to be larger
+ * than max_delta_size then NULL is returned.  On success, a non-NULL
+ * pointer to the buffer with the delta data is returned and *delta_size is
+ * updated with its size.  The returned buffer must be freed by the caller.
+ */
+GIT_INLINE(void *)
+git_delta(const void *src_buf, unsigned long src_bufsize,
+	  const void *trg_buf, unsigned long trg_bufsize,
+	  unsigned long *delta_size, unsigned long max_delta_size)
+{
+	struct git_delta_index *index = git_delta_create_index(src_buf, src_bufsize);
+	if (index) {
+		void *delta = git_delta_create(index, trg_buf, trg_bufsize,
+					       delta_size, max_delta_size);
+		git_delta_free_index(index);
+		return delta;
+	}
+	return NULL;
+}
+
+/*
+ * patch_delta: recreate target buffer given source buffer and delta data
+ *
+ * On success, a non-NULL pointer to the target buffer is returned and
+ * *trg_bufsize is updated with its size.  On failure a NULL pointer is
+ * returned.  The returned buffer must be freed by the caller.
+ */
+extern void *git_delta_patch(const void *src_buf, unsigned long src_size,
+			     const void *delta_buf, unsigned long delta_size,
+			     unsigned long *dst_size);
+
+/* the smallest possible delta size is 4 bytes */
+#define GIT_DELTA_SIZE_MIN	4
+
+/*
+ * This must be called twice on the delta data buffer, first to get the
+ * expected source buffer size, and again to get the target buffer size.
+ */
+GIT_INLINE(unsigned long)
+git_delta_get_hdr_size(const unsigned char **datap,
+		       const unsigned char *top)
+{
+	const unsigned char *data = *datap;
+	unsigned long cmd, size = 0;
+	int i = 0;
+	do {
+		cmd = *data++;
+		size |= (cmd & 0x7f) << i;
+		i += 7;
+	} while (cmd & 0x80 && data < top);
+	*datap = data;
+	return size;
+}
+
+#endif
diff --git a/src/indexer.c b/src/indexer.c
index 85ffb161f..7d4e18d7a 100644
--- a/src/indexer.c
+++ b/src/indexer.c
@@ -599,11 +599,6 @@ int git_indexer_new(git_indexer **out, const char *packname)
 
 	assert(out && packname);
 
-	if (git_path_root(packname) < 0) {
-		giterr_set(GITERR_INDEXER, "Path is not absolute");
-		return -1;
-	}
-
 	idx = git__calloc(1, sizeof(git_indexer));
 	GITERR_CHECK_ALLOC(idx);
 
diff --git a/src/odb.c b/src/odb.c
index d951bc51b..7c21598f0 100644
--- a/src/odb.c
+++ b/src/odb.c
@@ -107,6 +107,9 @@ git_otype git_odb_object_type(git_odb_object *object)
 
 void git_odb_object_free(git_odb_object *object)
 {
+	if (object == NULL)
+		return;
+
 	git_cached_obj_decref((git_cached_obj *)object, &free_odb_object);
 }
 
diff --git a/src/pack-objects.c b/src/pack-objects.c
new file mode 100644
index 000000000..bb9b0eb88
--- /dev/null
+++ b/src/pack-objects.c
@@ -0,0 +1,1318 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+
+#include "pack-objects.h"
+
+#include "compress.h"
+#include "delta.h"
+#include "iterator.h"
+#include "netops.h"
+#include "pack.h"
+#include "thread-utils.h"
+#include "tree.h"
+
+#include "git2/pack.h"
+#include "git2/commit.h"
+#include "git2/tag.h"
+#include "git2/indexer.h"
+#include "git2/config.h"
+
+GIT__USE_OIDMAP;
+
+struct unpacked {
+	git_pobject *object;
+	void *data;
+	struct git_delta_index *index;
+	unsigned int depth;
+};
+
+static unsigned name_hash(const char *name)
+{
+	unsigned c, hash = 0;
+
+	if (!name)
+		return 0;
+
+	/*
+	 * This effectively just creates a sortable number from the
+	 * last sixteen non-whitespace characters. Last characters
+	 * count "most", so things that end in ".c" sort together.
+	 */
+	while ((c = *name++) != 0) {
+		if (git__isspace(c))
+			continue;
+		hash = (hash >> 2) + (c << 24);
+	}
+	return hash;
+}
+
+static int packbuilder_config(git_packbuilder *pb)
+{
+	git_config *config;
+	int ret;
+
+	if (git_repository_config__weakptr(&config, pb->repo) < 0)
+		return -1;
+
+#define config_get(key, dst, default) \
+	ret = git_config_get_int64((int64_t *)&dst, config, key); \
+	if (ret == GIT_ENOTFOUND) \
+		dst = default; \
+	else if (ret < 0) \
+		return -1;
+
+	config_get("pack.deltaCacheSize", pb->max_delta_cache_size,
+		   GIT_PACK_DELTA_CACHE_SIZE);
+	config_get("pack.deltaCacheLimit", pb->cache_max_small_delta_size,
+		   GIT_PACK_DELTA_CACHE_LIMIT);
+	config_get("pack.deltaCacheSize", pb->big_file_threshold,
+		   GIT_PACK_BIG_FILE_THRESHOLD);
+	config_get("pack.windowMemory", pb->window_memory_limit, 0);
+
+#undef config_get
+
+	return 0;
+}
+
+int git_packbuilder_new(git_packbuilder **out, git_repository *repo)
+{
+	git_packbuilder *pb;
+
+	*out = NULL;
+
+	pb = git__malloc(sizeof(*pb));
+	GITERR_CHECK_ALLOC(pb);
+
+	memset(pb, 0x0, sizeof(*pb));
+
+	pb->object_ix = git_oidmap_alloc();
+	GITERR_CHECK_ALLOC(pb->object_ix);
+
+	pb->repo = repo;
+	pb->nr_threads = 1; /* do not spawn any thread by default */
+	pb->ctx = git_hash_new_ctx();
+
+	if (git_repository_odb(&pb->odb, repo) < 0)
+		goto on_error;
+
+	if (packbuilder_config(pb) < 0)
+		goto on_error;
+
+	*out = pb;
+	return 0;
+
+on_error:
+	git__free(pb);
+	return -1;
+}
+
+void git_packbuilder_set_threads(git_packbuilder *pb, unsigned int n)
+{
+	assert(pb);
+	pb->nr_threads = n;
+}
+
+static void rehash(git_packbuilder *pb)
+{
+	git_pobject *po;
+	khiter_t pos;
+	unsigned int i;
+	int ret;
+
+	kh_clear(oid, pb->object_ix);
+	for (i = 0, po = pb->object_list; i < pb->nr_objects; i++, po++) {
+		pos = kh_put(oid, pb->object_ix, &po->id, &ret);
+		kh_value(pb->object_ix, pos) = po;
+	}
+}
+
+int git_packbuilder_insert(git_packbuilder *pb, const git_oid *oid,
+			   const char *name)
+{
+	git_pobject *po;
+	git_odb_object *obj;
+	khiter_t pos;
+	int ret;
+
+	assert(pb && oid);
+
+	pos = kh_get(oid, pb->object_ix, oid);
+	if (pos != kh_end(pb->object_ix))
+		return 0;
+
+	if (pb->nr_objects >= pb->nr_alloc) {
+		pb->nr_alloc = (pb->nr_alloc + 1024) * 3 / 2;
+		pb->object_list = git__realloc(pb->object_list,
+					       pb->nr_alloc * sizeof(*po));
+		GITERR_CHECK_ALLOC(pb->object_list);
+		rehash(pb);
+	}
+
+	if (git_odb_read(&obj, pb->odb, oid) < 0)
+		return -1;
+
+	po = pb->object_list + pb->nr_objects++;
+	memset(po, 0x0, sizeof(*po));
+
+	git_oid_cpy(&po->id, oid);
+	po->type = git_odb_object_type(obj);
+	po->size = git_odb_object_size(obj);
+	git_odb_object_free(obj);
+	po->hash = name_hash(name);
+
+	pos = kh_put(oid, pb->object_ix, &po->id, &ret);
+	assert(ret != 0);
+	kh_value(pb->object_ix, pos) = po;
+
+	pb->done = false;
+	return 0;
+}
+
+/*
+ * The per-object header is a pretty dense thing, which is
+ *  - first byte: low four bits are "size",
+ *    then three bits of "type",
+ *    with the high bit being "size continues".
+ *  - each byte afterwards: low seven bits are size continuation,
+ *    with the high bit being "size continues"
+ */
+static int gen_pack_object_header(
+		unsigned char *hdr,
+		unsigned long size,
+		git_otype type)
+{
+	unsigned char *hdr_base;
+	unsigned char c;
+
+	assert(type >= GIT_OBJ_COMMIT && type <= GIT_OBJ_REF_DELTA);
+
+	/* TODO: add support for chunked objects; see git.git 6c0d19b1 */
+
+	c = (unsigned char)((type << 4) | (size & 15));
+	size >>= 4;
+	hdr_base = hdr;
+
+	while (size) {
+		*hdr++ = c | 0x80;
+		c = size & 0x7f;
+		size >>= 7;
+	}
+	*hdr++ = c;
+
+	return hdr - hdr_base;
+}
+
+static int get_delta(void **out, git_odb *odb, git_pobject *po)
+{
+	git_odb_object *src = NULL, *trg = NULL;
+	unsigned long delta_size;
+	void *delta_buf;
+
+	*out = NULL;
+
+	if (git_odb_read(&src, odb, &po->delta->id) < 0 ||
+	    git_odb_read(&trg, odb, &po->id) < 0)
+		goto on_error;
+
+	delta_buf = git_delta(git_odb_object_data(src), git_odb_object_size(src),
+			      git_odb_object_data(trg), git_odb_object_size(trg),
+			      &delta_size, 0);
+
+	if (!delta_buf || delta_size != po->delta_size) {
+		giterr_set(GITERR_INVALID, "Delta size changed");
+		goto on_error;
+	}
+
+	*out = delta_buf;
+
+	git_odb_object_free(src);
+	git_odb_object_free(trg);
+	return 0;
+
+on_error:
+	git_odb_object_free(src);
+	git_odb_object_free(trg);
+	return -1;
+}
+
+static int write_object(git_buf *buf, git_packbuilder *pb, git_pobject *po)
+{
+	git_odb_object *obj = NULL;
+	git_buf zbuf = GIT_BUF_INIT;
+	git_otype type;
+	unsigned char hdr[10];
+	unsigned int hdr_len;
+	unsigned long size;
+	void *data;
+
+	if (po->delta) {
+		if (po->delta_data)
+			data = po->delta_data;
+		else if (get_delta(&data, pb->odb, po) < 0)
+				goto on_error;
+		size = po->delta_size;
+		type = GIT_OBJ_REF_DELTA;
+	} else {
+		if (git_odb_read(&obj, pb->odb, &po->id))
+			goto on_error;
+
+		data = (void *)git_odb_object_data(obj);
+		size = git_odb_object_size(obj);
+		type = git_odb_object_type(obj);
+	}
+
+	/* Write header */
+	hdr_len = gen_pack_object_header(hdr, size, type);
+
+	if (git_buf_put(buf, (char *)hdr, hdr_len) < 0)
+		goto on_error;
+
+	git_hash_update(pb->ctx, hdr, hdr_len);
+
+	if (type == GIT_OBJ_REF_DELTA) {
+		if (git_buf_put(buf, (char *)po->delta->id.id,
+				GIT_OID_RAWSZ) < 0)
+			goto on_error;
+
+		git_hash_update(pb->ctx, po->delta->id.id, GIT_OID_RAWSZ);
+	}
+
+	/* Write data */
+	if (po->z_delta_size)
+		size = po->z_delta_size;
+	else if (git__compress(&zbuf, data, size) < 0)
+		goto on_error;
+	else {
+		if (po->delta)
+			git__free(data);
+		data = zbuf.ptr;
+		size = zbuf.size;
+	}
+
+	if (git_buf_put(buf, data, size) < 0)
+		goto on_error;
+
+	git_hash_update(pb->ctx, data, size);
+
+	if (po->delta_data)
+		git__free(po->delta_data);
+
+	git_odb_object_free(obj);
+	git_buf_free(&zbuf);
+
+	pb->nr_written++;
+	return 0;
+
+on_error:
+	git_odb_object_free(obj);
+	git_buf_free(&zbuf);
+	return -1;
+}
+
+enum write_one_status {
+	WRITE_ONE_SKIP = -1, /* already written */
+	WRITE_ONE_BREAK = 0, /* writing this will bust the limit; not written */
+	WRITE_ONE_WRITTEN = 1, /* normal */
+	WRITE_ONE_RECURSIVE = 2 /* already scheduled to be written */
+};
+
+static int write_one(git_buf *buf, git_packbuilder *pb, git_pobject *po,
+		     enum write_one_status *status)
+{
+	if (po->recursing) {
+		*status = WRITE_ONE_RECURSIVE;
+		return 0;
+	} else if (po->written) {
+		*status = WRITE_ONE_SKIP;
+		return 0;
+	}
+
+	if (po->delta) {
+		po->recursing = 1;
+		if (write_one(buf, pb, po->delta, status) < 0)
+			return -1;
+		switch (*status) {
+		case WRITE_ONE_RECURSIVE:
+			/* we cannot depend on this one */
+			po->delta = NULL;
+			break;
+		default:
+			break;
+		}
+	}
+
+	po->written = 1;
+	po->recursing = 0;
+	return write_object(buf, pb, po);
+}
+
+GIT_INLINE(void) add_to_write_order(git_pobject **wo, unsigned int *endp,
+				    git_pobject *po)
+{
+	if (po->filled)
+		return;
+	wo[(*endp)++] = po;
+	po->filled = 1;
+}
+
+static void add_descendants_to_write_order(git_pobject **wo, unsigned int *endp,
+					   git_pobject *po)
+{
+	int add_to_order = 1;
+	while (po) {
+		if (add_to_order) {
+			git_pobject *s;
+			/* add this node... */
+			add_to_write_order(wo, endp, po);
+			/* all its siblings... */
+			for (s = po->delta_sibling; s; s = s->delta_sibling) {
+				add_to_write_order(wo, endp, s);
+			}
+		}
+		/* drop down a level to add left subtree nodes if possible */
+		if (po->delta_child) {
+			add_to_order = 1;
+			po = po->delta_child;
+		} else {
+			add_to_order = 0;
+			/* our sibling might have some children, it is next */
+			if (po->delta_sibling) {
+				po = po->delta_sibling;
+				continue;
+			}
+			/* go back to our parent node */
+			po = po->delta;
+			while (po && !po->delta_sibling) {
+				/* we're on the right side of a subtree, keep
+				 * going up until we can go right again */
+				po = po->delta;
+			}
+			if (!po) {
+				/* done- we hit our original root node */
+				return;
+			}
+			/* pass it off to sibling at this level */
+			po = po->delta_sibling;
+		}
+	};
+}
+
+static void add_family_to_write_order(git_pobject **wo, unsigned int *endp,
+				      git_pobject *po)
+{
+	git_pobject *root;
+
+	for (root = po; root->delta; root = root->delta)
+		; /* nothing */
+	add_descendants_to_write_order(wo, endp, root);
+}
+
+static int cb_tag_foreach(const char *name, git_oid *oid, void *data)
+{
+	git_packbuilder *pb = data;
+	git_pobject *po;
+	khiter_t pos;
+
+	GIT_UNUSED(name);
+
+	pos = kh_get(oid, pb->object_ix, oid);
+	if (pos == kh_end(pb->object_ix))
+		return 0;
+
+	po = kh_value(pb->object_ix, pos);
+	po->tagged = 1;
+
+	/* TODO: peel objects */
+
+	return 0;
+}
+
+static git_pobject **compute_write_order(git_packbuilder *pb)
+{
+	unsigned int i, wo_end, last_untagged;
+
+	git_pobject **wo = git__malloc(sizeof(*wo) * pb->nr_objects);
+
+	for (i = 0; i < pb->nr_objects; i++) {
+		git_pobject *po = pb->object_list + i;
+		po->tagged = 0;
+		po->filled = 0;
+		po->delta_child = NULL;
+		po->delta_sibling = NULL;
+	}
+
+	/*
+	 * Fully connect delta_child/delta_sibling network.
+	 * Make sure delta_sibling is sorted in the original
+	 * recency order.
+	 */
+	for (i = pb->nr_objects; i > 0;) {
+		git_pobject *po = &pb->object_list[--i];
+		if (!po->delta)
+			continue;
+		/* Mark me as the first child */
+		po->delta_sibling = po->delta->delta_child;
+		po->delta->delta_child = po;
+	}
+
+	/*
+	 * Mark objects that are at the tip of tags.
+	 */
+	if (git_tag_foreach(pb->repo, &cb_tag_foreach, pb) < 0)
+		return NULL;
+
+	/*
+	 * Give the objects in the original recency order until
+	 * we see a tagged tip.
+	 */
+	for (i = wo_end = 0; i < pb->nr_objects; i++) {
+		git_pobject *po = pb->object_list + i;
+		if (po->tagged)
+			break;
+		add_to_write_order(wo, &wo_end, po);
+	}
+	last_untagged = i;
+
+	/*
+	 * Then fill all the tagged tips.
+	 */
+	for (; i < pb->nr_objects; i++) {
+		git_pobject *po = pb->object_list + i;
+		if (po->tagged)
+			add_to_write_order(wo, &wo_end, po);
+	}
+
+	/*
+	 * And then all remaining commits and tags.
+	 */
+	for (i = last_untagged; i < pb->nr_objects; i++) {
+		git_pobject *po = pb->object_list + i;
+		if (po->type != GIT_OBJ_COMMIT &&
+		    po->type != GIT_OBJ_TAG)
+			continue;
+		add_to_write_order(wo, &wo_end, po);
+	}
+
+	/*
+	 * And then all the trees.
+	 */
+	for (i = last_untagged; i < pb->nr_objects; i++) {
+		git_pobject *po = pb->object_list + i;
+		if (po->type != GIT_OBJ_TREE)
+			continue;
+		add_to_write_order(wo, &wo_end, po);
+	}
+
+	/*
+	 * Finally all the rest in really tight order
+	 */
+	for (i = last_untagged; i < pb->nr_objects; i++) {
+		git_pobject *po = pb->object_list + i;
+		if (!po->filled)
+			add_family_to_write_order(wo, &wo_end, po);
+	}
+
+	if (wo_end != pb->nr_objects) {
+		giterr_set(GITERR_INVALID, "invalid write order");
+		return NULL;
+	}
+
+	return wo;
+}
+
+static int write_pack(git_packbuilder *pb,
+		      int (*cb)(void *buf, size_t size, void *data),
+		      void *data)
+{
+	git_pobject **write_order;
+	git_pobject *po;
+	git_buf buf = GIT_BUF_INIT;
+	enum write_one_status status;
+	struct git_pack_header ph;
+	unsigned int i = 0;
+
+	write_order = compute_write_order(pb);
+	if (write_order == NULL)
+		goto on_error;
+
+	/* Write pack header */
+	ph.hdr_signature = htonl(PACK_SIGNATURE);
+	ph.hdr_version = htonl(PACK_VERSION);
+	ph.hdr_entries = htonl(pb->nr_objects);
+
+	if (cb(&ph, sizeof(ph), data) < 0)
+		goto on_error;
+
+	git_hash_update(pb->ctx, &ph, sizeof(ph));
+
+	pb->nr_remaining = pb->nr_objects;
+	do {
+		pb->nr_written = 0;
+		for ( ; i < pb->nr_objects; ++i) {
+			po = write_order[i];
+			if (write_one(&buf, pb, po, &status) < 0)
+				goto on_error;
+			if (cb(buf.ptr, buf.size, data) < 0)
+				goto on_error;
+			git_buf_clear(&buf);
+		}
+
+		pb->nr_remaining -= pb->nr_written;
+	} while (pb->nr_remaining && i < pb->nr_objects);
+
+	git__free(write_order);
+	git_buf_free(&buf);
+	git_hash_final(&pb->pack_oid, pb->ctx);
+
+	return cb(pb->pack_oid.id, GIT_OID_RAWSZ, data);
+
+on_error:
+	git__free(write_order);
+	git_buf_free(&buf);
+	return -1;
+}
+
+static int send_pack_file(void *buf, size_t size, void *data)
+{
+	git_transport *t = (git_transport *)data;
+	return gitno_send(t, buf, size, 0);
+}
+
+static int write_pack_buf(void *buf, size_t size, void *data)
+{
+	git_buf *b = (git_buf *)data;
+	return git_buf_put(b, buf, size);
+}
+
+static int write_pack_to_file(void *buf, size_t size, void *data)
+{
+	git_filebuf *file = (git_filebuf *)data;
+	return git_filebuf_write(file, buf, size);
+}
+
+static int write_pack_file(git_packbuilder *pb, const char *path)
+{
+	git_filebuf file = GIT_FILEBUF_INIT;
+
+	if (git_filebuf_open(&file, path, 0) < 0 ||
+	    write_pack(pb, &write_pack_to_file, &file) < 0 ||
+	    git_filebuf_commit(&file, GIT_PACK_FILE_MODE) < 0) {
+		git_filebuf_cleanup(&file);
+		return -1;
+	}
+
+	return 0;
+}
+
+static int type_size_sort(const void *_a, const void *_b)
+{
+	const git_pobject *a = (git_pobject *)_a;
+	const git_pobject *b = (git_pobject *)_b;
+
+	if (a->type > b->type)
+		return -1;
+	if (a->type < b->type)
+		return 1;
+	if (a->hash > b->hash)
+		return -1;
+	if (a->hash < b->hash)
+		return 1;
+	/*
+	 * TODO
+	 *
+	if (a->preferred_base > b->preferred_base)
+		return -1;
+	if (a->preferred_base < b->preferred_base)
+		return 1;
+	*/
+	if (a->size > b->size)
+		return -1;
+	if (a->size < b->size)
+		return 1;
+	return a < b ? -1 : (a > b); /* newest first */
+}
+
+static int delta_cacheable(git_packbuilder *pb, unsigned long src_size,
+			   unsigned long trg_size, unsigned long delta_size)
+{
+	if (pb->max_delta_cache_size &&
+		pb->delta_cache_size + delta_size > pb->max_delta_cache_size)
+		return 0;
+
+	if (delta_size < pb->cache_max_small_delta_size)
+		return 1;
+
+	/* cache delta, if objects are large enough compared to delta size */
+	if ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))
+		return 1;
+
+	return 0;
+}
+
+#ifdef GIT_THREADS
+static git_mutex cache_mutex;
+#define cache_lock()		git_mutex_lock(&cache_mutex);
+#define cache_unlock()		git_mutex_unlock(&cache_mutex);
+
+static git_mutex progress_mutex;
+#define progress_lock()		git_mutex_lock(&progress_mutex);
+#define progress_unlock()	git_mutex_unlock(&progress_mutex);
+
+static git_cond progress_cond;
+#else
+
+#define cache_lock()		(void)0;
+#define cache_unlock()		(void)0;
+#define progress_lock()		(void)0;
+#define progress_unlock()	(void)0;
+#endif
+
+static int try_delta(git_packbuilder *pb, struct unpacked *trg,
+		     struct unpacked *src, unsigned int max_depth,
+		     unsigned long *mem_usage, int *ret)
+{
+	git_pobject *trg_object = trg->object;
+	git_pobject *src_object = src->object;
+	git_odb_object *obj;
+	unsigned long trg_size, src_size, delta_size,
+		      sizediff, max_size, sz;
+	unsigned int ref_depth;
+	void *delta_buf;
+
+	/* Don't bother doing diffs between different types */
+	if (trg_object->type != src_object->type) {
+		*ret = -1;
+		return 0;
+	}
+
+	*ret = 0;
+
+	/* TODO: support reuse-delta */
+
+	/* Let's not bust the allowed depth. */
+	if (src->depth >= max_depth)
+		return 0;
+
+	/* Now some size filtering heuristics. */
+	trg_size = trg_object->size;
+	if (!trg_object->delta) {
+		max_size = trg_size/2 - 20;
+		ref_depth = 1;
+	} else {
+		max_size = trg_object->delta_size;
+		ref_depth = trg->depth;
+	}
+
+	max_size = (uint64_t)max_size * (max_depth - src->depth) /
+					(max_depth - ref_depth + 1);
+	if (max_size == 0)
+		return 0;
+
+	src_size = src_object->size;
+	sizediff = src_size < trg_size ? trg_size - src_size : 0;
+	if (sizediff >= max_size)
+		return 0;
+	if (trg_size < src_size / 32)
+		return 0;
+
+	/* Load data if not already done */
+	if (!trg->data) {
+		if (git_odb_read(&obj, pb->odb, &trg_object->id) < 0)
+			return -1;
+
+		sz = git_odb_object_size(obj);
+		trg->data = git__malloc(sz);
+		GITERR_CHECK_ALLOC(trg->data);
+		memcpy(trg->data, git_odb_object_data(obj), sz);
+
+		git_odb_object_free(obj);
+
+		if (sz != trg_size) {
+			giterr_set(GITERR_INVALID,
+				   "Inconsistent target object length");
+			return -1;
+		}
+
+		*mem_usage += sz;
+	}
+	if (!src->data) {
+		if (git_odb_read(&obj, pb->odb, &src_object->id) < 0)
+			return -1;
+
+		sz = git_odb_object_size(obj);
+		src->data = git__malloc(sz);
+		GITERR_CHECK_ALLOC(src->data);
+		memcpy(src->data, git_odb_object_data(obj), sz);
+
+		git_odb_object_free(obj);
+
+		if (sz != src_size) {
+			giterr_set(GITERR_INVALID,
+				   "Inconsistent source object length");
+			return -1;
+		}
+
+		*mem_usage += sz;
+	}
+	if (!src->index) {
+		src->index = git_delta_create_index(src->data, src_size);
+		if (!src->index)
+			return 0; /* suboptimal pack - out of memory */
+
+		*mem_usage += git_delta_sizeof_index(src->index);
+	}
+
+	delta_buf = git_delta_create(src->index, trg->data, trg_size,
+				     &delta_size, max_size);
+	if (!delta_buf)
+		return 0;
+
+	if (trg_object->delta) {
+		/* Prefer only shallower same-sized deltas. */
+		if (delta_size == trg_object->delta_size &&
+		    src->depth + 1 >= trg->depth) {
+			git__free(delta_buf);
+			return 0;
+		}
+	}
+
+	cache_lock();
+	if (trg_object->delta_data) {
+		git__free(trg_object->delta_data);
+		pb->delta_cache_size -= trg_object->delta_size;
+		trg_object->delta_data = NULL;
+	}
+	if (delta_cacheable(pb, src_size, trg_size, delta_size)) {
+		pb->delta_cache_size += delta_size;
+		cache_unlock();
+
+		trg_object->delta_data = git__realloc(delta_buf, delta_size);
+		GITERR_CHECK_ALLOC(trg_object->delta_data);
+	} else {
+		/* create delta when writing the pack */
+		cache_unlock();
+		git__free(delta_buf);
+	}
+
+	trg_object->delta = src_object;
+	trg_object->delta_size = delta_size;
+	trg->depth = src->depth + 1;
+
+	*ret = 1;
+	return 0;
+}
+
+static unsigned int check_delta_limit(git_pobject *me, unsigned int n)
+{
+	git_pobject *child = me->delta_child;
+	unsigned int m = n;
+
+	while (child) {
+		unsigned int c = check_delta_limit(child, n + 1);
+		if (m < c)
+			m = c;
+		child = child->delta_sibling;
+	}
+	return m;
+}
+
+static unsigned long free_unpacked(struct unpacked *n)
+{
+	unsigned long freed_mem = git_delta_sizeof_index(n->index);
+	git_delta_free_index(n->index);
+	n->index = NULL;
+	if (n->data) {
+		freed_mem += n->object->size;
+		git__free(n->data);
+		n->data = NULL;
+	}
+	n->object = NULL;
+	n->depth = 0;
+	return freed_mem;
+}
+
+static int find_deltas(git_packbuilder *pb, git_pobject **list,
+		       unsigned int *list_size, unsigned int window,
+		       unsigned int depth)
+{
+	git_pobject *po;
+	git_buf zbuf = GIT_BUF_INIT;
+	struct unpacked *array;
+	uint32_t idx = 0, count = 0;
+	unsigned long mem_usage = 0;
+	unsigned int i;
+	int error = -1;
+
+	array = git__calloc(window, sizeof(struct unpacked));
+	GITERR_CHECK_ALLOC(array);
+
+	for (;;) {
+		struct unpacked *n = array + idx;
+		unsigned int max_depth;
+		int j, best_base = -1;
+
+		progress_lock();
+		if (!*list_size) {
+			progress_unlock();
+			break;
+		}
+
+		po = *list++;
+		(*list_size)--;
+		progress_unlock();
+
+		mem_usage -= free_unpacked(n);
+		n->object = po;
+
+		while (pb->window_memory_limit &&
+		       mem_usage > pb->window_memory_limit &&
+		       count > 1) {
+			uint32_t tail = (idx + window - count) % window;
+			mem_usage -= free_unpacked(array + tail);
+			count--;
+		}
+
+		/*
+		 * If the current object is at pack edge, take the depth the
+		 * objects that depend on the current object into account
+		 * otherwise they would become too deep.
+		 */
+		max_depth = depth;
+		if (po->delta_child) {
+			max_depth -= check_delta_limit(po, 0);
+			if (max_depth <= 0)
+				goto next;
+		}
+
+		j = window;
+		while (--j > 0) {
+			int ret;
+			uint32_t other_idx = idx + j;
+			struct unpacked *m;
+
+			if (other_idx >= window)
+				other_idx -= window;
+
+			m = array + other_idx;
+			if (!m->object)
+				break;
+
+			if (try_delta(pb, n, m, max_depth, &mem_usage, &ret) < 0)
+				goto on_error;
+			if (ret < 0)
+				break;
+			else if (ret > 0)
+				best_base = other_idx;
+		}
+
+		/*
+		 * If we decided to cache the delta data, then it is best
+		 * to compress it right away.  First because we have to do
+		 * it anyway, and doing it here while we're threaded will
+		 * save a lot of time in the non threaded write phase,
+		 * as well as allow for caching more deltas within
+		 * the same cache size limit.
+		 * ...
+		 * But only if not writing to stdout, since in that case
+		 * the network is most likely throttling writes anyway,
+		 * and therefore it is best to go to the write phase ASAP
+		 * instead, as we can afford spending more time compressing
+		 * between writes at that moment.
+		 */
+		if (po->delta_data) {
+			if (git__compress(&zbuf, po->delta_data, po->delta_size) < 0)
+				goto on_error;
+
+			git__free(po->delta_data);
+			po->delta_data = git__malloc(zbuf.size);
+			GITERR_CHECK_ALLOC(po->delta_data);
+
+			memcpy(po->delta_data, zbuf.ptr, zbuf.size);
+			po->z_delta_size = zbuf.size;
+			git_buf_clear(&zbuf);
+
+			cache_lock();
+			pb->delta_cache_size -= po->delta_size;
+			pb->delta_cache_size += po->z_delta_size;
+			cache_unlock();
+		}
+
+		/*
+		 * If we made n a delta, and if n is already at max
+		 * depth, leaving it in the window is pointless.  we
+		 * should evict it first.
+		 */
+		if (po->delta && max_depth <= n->depth)
+			continue;
+
+		/*
+		 * Move the best delta base up in the window, after the
+		 * currently deltified object, to keep it longer.  It will
+		 * be the first base object to be attempted next.
+		 */
+		if (po->delta) {
+			struct unpacked swap = array[best_base];
+			int dist = (window + idx - best_base) % window;
+			int dst = best_base;
+			while (dist--) {
+				int src = (dst + 1) % window;
+				array[dst] = array[src];
+				dst = src;
+			}
+			array[dst] = swap;
+		}
+
+		next:
+		idx++;
+		if (count + 1 < window)
+			count++;
+		if (idx >= window)
+			idx = 0;
+	}
+	error = 0;
+
+on_error:
+	for (i = 0; i < window; ++i) {
+		git__free(array[i].index);
+		git__free(array[i].data);
+	}
+	git__free(array);
+	git_buf_free(&zbuf);
+
+	return error;
+}
+
+#ifdef GIT_THREADS
+
+struct thread_params {
+	git_thread thread;
+	git_packbuilder *pb;
+
+	git_pobject **list;
+
+	git_cond cond;
+	git_mutex mutex;
+
+	unsigned int list_size;
+	unsigned int remaining;
+
+	int window;
+	int depth;
+	int working;
+	int data_ready;
+};
+
+static void init_threaded_search(void)
+{
+	git_mutex_init(&cache_mutex);
+	git_mutex_init(&progress_mutex);
+
+	git_cond_init(&progress_cond);
+}
+
+static void cleanup_threaded_search(void)
+{
+	git_cond_free(&progress_cond);
+
+	git_mutex_free(&cache_mutex);
+	git_mutex_free(&progress_mutex);
+}
+
+static void *threaded_find_deltas(void *arg)
+{
+	struct thread_params *me = arg;
+
+	while (me->remaining) {
+		if (find_deltas(me->pb, me->list, &me->remaining,
+				me->window, me->depth) < 0) {
+			; /* TODO */
+		}
+
+		progress_lock();
+		me->working = 0;
+		git_cond_signal(&progress_cond);
+		progress_unlock();
+
+		/*
+		 * We must not set ->data_ready before we wait on the
+		 * condition because the main thread may have set it to 1
+		 * before we get here. In order to be sure that new
+		 * work is available if we see 1 in ->data_ready, it
+		 * was initialized to 0 before this thread was spawned
+		 * and we reset it to 0 right away.
+		 */
+		git_mutex_lock(&me->mutex);
+		while (!me->data_ready)
+			git_cond_wait(&me->cond, &me->mutex);
+		me->data_ready = 0;
+		git_mutex_unlock(&me->mutex);
+	}
+	/* leave ->working 1 so that this doesn't get more work assigned */
+	return NULL;
+}
+
+static int ll_find_deltas(git_packbuilder *pb, git_pobject **list,
+			  unsigned int list_size, unsigned int window,
+			  unsigned int depth)
+{
+	struct thread_params *p;
+	int i, ret, active_threads = 0;
+
+	init_threaded_search();
+
+	if (!pb->nr_threads)
+		pb->nr_threads = git_online_cpus();
+	if (pb->nr_threads <= 1) {
+		find_deltas(pb, list, &list_size, window, depth);
+		cleanup_threaded_search();
+		return 0;
+	}
+
+	p = git__malloc(pb->nr_threads * sizeof(*p));
+	GITERR_CHECK_ALLOC(p);
+
+	/* Partition the work among the threads */
+	for (i = 0; i < pb->nr_threads; ++i) {
+		unsigned sub_size = list_size / (pb->nr_threads - i);
+
+		/* don't use too small segments or no deltas will be found */
+		if (sub_size < 2*window && i+1 < pb->nr_threads)
+			sub_size = 0;
+
+		p[i].pb = pb;
+		p[i].window = window;
+		p[i].depth = depth;
+		p[i].working = 1;
+		p[i].data_ready = 0;
+
+		/* try to split chunks on "path" boundaries */
+		while (sub_size && sub_size < list_size &&
+		       list[sub_size]->hash &&
+		       list[sub_size]->hash == list[sub_size-1]->hash)
+			sub_size++;
+
+		p[i].list = list;
+		p[i].list_size = sub_size;
+		p[i].remaining = sub_size;
+
+		list += sub_size;
+		list_size -= sub_size;
+	}
+
+	/* Start work threads */
+	for (i = 0; i < pb->nr_threads; ++i) {
+		if (!p[i].list_size)
+			continue;
+
+		git_mutex_init(&p[i].mutex);
+		git_cond_init(&p[i].cond);
+
+		ret = git_thread_create(&p[i].thread, NULL,
+					threaded_find_deltas, &p[i]);
+		if (ret) {
+			giterr_set(GITERR_THREAD, "unable to create thread");
+			return -1;
+		}
+		active_threads++;
+	}
+
+	/*
+	 * Now let's wait for work completion.  Each time a thread is done
+	 * with its work, we steal half of the remaining work from the
+	 * thread with the largest number of unprocessed objects and give
+	 * it to that newly idle thread.  This ensure good load balancing
+	 * until the remaining object list segments are simply too short
+	 * to be worth splitting anymore.
+	 */
+	while (active_threads) {
+		struct thread_params *target = NULL;
+		struct thread_params *victim = NULL;
+		unsigned sub_size = 0;
+
+		progress_lock();
+		for (;;) {
+			for (i = 0; !target && i < pb->nr_threads; i++)
+				if (!p[i].working)
+					target = &p[i];
+			if (target)
+				break;
+			git_cond_wait(&progress_cond, &progress_mutex);
+		}
+
+		for (i = 0; i < pb->nr_threads; i++)
+			if (p[i].remaining > 2*window &&
+			    (!victim || victim->remaining < p[i].remaining))
+				victim = &p[i];
+		if (victim) {
+			sub_size = victim->remaining / 2;
+			list = victim->list + victim->list_size - sub_size;
+			while (sub_size && list[0]->hash &&
+			       list[0]->hash == list[-1]->hash) {
+				list++;
+				sub_size--;
+			}
+			if (!sub_size) {
+				/*
+				 * It is possible for some "paths" to have
+				 * so many objects that no hash boundary
+				 * might be found.  Let's just steal the
+				 * exact half in that case.
+				 */
+				sub_size = victim->remaining / 2;
+				list -= sub_size;
+			}
+			target->list = list;
+			victim->list_size -= sub_size;
+			victim->remaining -= sub_size;
+		}
+		target->list_size = sub_size;
+		target->remaining = sub_size;
+		target->working = 1;
+		progress_unlock();
+
+		git_mutex_lock(&target->mutex);
+		target->data_ready = 1;
+		git_cond_signal(&target->cond);
+		git_mutex_unlock(&target->mutex);
+
+		if (!sub_size) {
+			git_thread_join(target->thread, NULL);
+			git_cond_free(&target->cond);
+			git_mutex_free(&target->mutex);
+			active_threads--;
+		}
+	}
+
+	cleanup_threaded_search();
+	git__free(p);
+	return 0;
+}
+
+#else
+#define ll_find_deltas(pb, l, ls, w, d) find_deltas(pb, l, &ls, w, d)
+#endif
+
+static void get_object_details(git_packbuilder *pb)
+{
+	git_pobject *po;
+	unsigned int i;
+
+	for (i = 0; i < pb->nr_objects; ++i) {
+		po = &pb->object_list[i];
+		if (pb->big_file_threshold < po->size)
+			po->no_try_delta = 1;
+	}
+}
+
+static int prepare_pack(git_packbuilder *pb)
+{
+	git_pobject **delta_list;
+	unsigned int i, n = 0;
+
+	if (pb->nr_objects == 0 || pb->done)
+		return 0; /* nothing to do */
+
+	get_object_details(pb);
+
+	delta_list = git__malloc(pb->nr_objects * sizeof(*delta_list));
+	GITERR_CHECK_ALLOC(delta_list);
+
+	for (i = 0; i < pb->nr_objects; ++i) {
+		git_pobject *po = pb->object_list + i;
+
+		if (po->size < 50)
+			continue;
+
+		if (po->no_try_delta)
+			continue;
+
+		delta_list[n++] = po;
+	}
+
+	if (n > 1) {
+		git__tsort((void **)delta_list, n, type_size_sort);
+		if (ll_find_deltas(pb, delta_list, n,
+				   GIT_PACK_WINDOW + 1,
+				   GIT_PACK_DEPTH) < 0) {
+			git__free(delta_list);
+			return -1;
+		}
+	}
+
+	pb->done = true;
+	git__free(delta_list);
+	return 0;
+}
+
+#define PREPARE_PACK if (prepare_pack(pb) < 0) { return -1; }
+
+int git_packbuilder_send(git_packbuilder *pb, git_transport *t)
+{
+	PREPARE_PACK;
+	return write_pack(pb, &send_pack_file, t);
+}
+
+int git_packbuilder_write_buf(git_buf *buf, git_packbuilder *pb)
+{
+	PREPARE_PACK;
+	return write_pack(pb, &write_pack_buf, buf);
+}
+
+int git_packbuilder_write(git_packbuilder *pb, const char *path)
+{
+	PREPARE_PACK;
+	return write_pack_file(pb, path);
+}
+
+#undef PREPARE_PACK
+
+static int cb_tree_walk(const char *root, const git_tree_entry *entry, void *payload)
+{
+	git_packbuilder *pb = payload;
+	git_buf buf = GIT_BUF_INIT;
+
+	git_buf_puts(&buf, root);
+	git_buf_puts(&buf, git_tree_entry_name(entry));
+
+	if (git_packbuilder_insert(pb, git_tree_entry_id(entry),
+				   git_buf_cstr(&buf)) < 0) {
+		git_buf_free(&buf);
+		return -1;
+	}
+
+	git_buf_free(&buf);
+	return 0;
+}
+
+int git_packbuilder_insert_tree(git_packbuilder *pb, const git_oid *oid)
+{
+	git_tree *tree;
+
+	if (git_tree_lookup(&tree, pb->repo, oid) < 0 ||
+	    git_packbuilder_insert(pb, oid, NULL) < 0)
+		return -1;
+
+	if (git_tree_walk(tree, cb_tree_walk, GIT_TREEWALK_PRE, pb) < 0) {
+		git_tree_free(tree);
+		return -1;
+	}
+
+	git_tree_free(tree);
+	return 0;
+}
+
+void git_packbuilder_free(git_packbuilder *pb)
+{
+	if (pb == NULL)
+		return;
+
+	git_odb_free(pb->odb);
+	git_hash_free_ctx(pb->ctx);
+	git_oidmap_free(pb->object_ix);
+	git__free(pb->object_list);
+	git__free(pb);
+}
diff --git a/src/pack-objects.h b/src/pack-objects.h
new file mode 100644
index 000000000..8e8012689
--- /dev/null
+++ b/src/pack-objects.h
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2009-2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+
+#ifndef INCLUDE_pack_objects_h__
+#define INCLUDE_pack_objects_h__
+
+#include "common.h"
+
+#include "buffer.h"
+#include "hash.h"
+#include "oidmap.h"
+
+#include "git2/oid.h"
+
+#define GIT_PACK_WINDOW 10 /* number of objects to possibly delta against */
+#define GIT_PACK_DEPTH 50 /* max delta depth */
+#define GIT_PACK_DELTA_CACHE_SIZE (256 * 1024 * 1024)
+#define GIT_PACK_DELTA_CACHE_LIMIT 1000
+#define GIT_PACK_BIG_FILE_THRESHOLD (512 * 1024 * 1024)
+
+typedef struct git_pobject {
+	git_oid id;
+	git_otype type;
+	git_off_t offset;
+
+	size_t size;
+
+	unsigned int hash; /* name hint hash */
+
+	struct git_pobject *delta; /* delta base object */
+	struct git_pobject *delta_child; /* deltified objects who bases me */
+	struct git_pobject *delta_sibling; /* other deltified objects
+					    * who uses the same base as
+					    * me */
+
+	void *delta_data;
+	unsigned long delta_size;
+	unsigned long z_delta_size;
+
+	int written:1,
+	    recursing:1,
+	    no_try_delta:1,
+	    tagged:1,
+	    filled:1;
+} git_pobject;
+
+struct git_packbuilder {
+	git_repository *repo; /* associated repository */
+	git_odb *odb; /* associated object database */
+
+	git_hash_ctx *ctx;
+
+	uint32_t nr_objects,
+		 nr_alloc,
+		 nr_written,
+		 nr_remaining;
+
+	git_pobject *object_list;
+
+	git_oidmap *object_ix;
+
+	git_oid pack_oid; /* hash of written pack */
+
+	/* configs */
+	unsigned long delta_cache_size;
+	unsigned long max_delta_cache_size;
+	unsigned long cache_max_small_delta_size;
+	unsigned long big_file_threshold;
+	unsigned long window_memory_limit;
+
+	int nr_threads; /* nr of threads to use */
+
+	bool done;
+};
+
+
+int git_packbuilder_send(git_packbuilder *pb, git_transport *t);
+int git_packbuilder_write_buf(git_buf *buf, git_packbuilder *pb);
+
+#endif
diff --git a/src/tag.c b/src/tag.c
index ae9d0a895..56f84a85f 100644
--- a/src/tag.c
+++ b/src/tag.c
@@ -393,20 +393,51 @@ int git_tag__parse(git_tag *tag, git_odb_object *obj)
 }
 
 typedef struct {
- git_vector *taglist;
- const char *pattern;
+	git_repository *repo;
+	git_tag_foreach_cb cb;
+	void *cb_data;
+} tag_cb_data;
+
+static int tags_cb(const char *ref, void *data)
+{
+	git_oid oid;
+	tag_cb_data *d = (tag_cb_data *)data;
+
+	if (git__prefixcmp(ref, GIT_REFS_TAGS_DIR) != 0)
+		return 0; /* no tag */
+
+	if (git_reference_name_to_oid(&oid, d->repo, ref) < 0)
+		return -1;
+
+	return d->cb(ref, &oid, d->cb_data);
+}
+
+int git_tag_foreach(git_repository *repo, git_tag_foreach_cb cb, void *cb_data)
+{
+	tag_cb_data data;
+
+	assert(repo && cb);
+
+	data.cb = cb;
+	data.cb_data = cb_data;
+	data.repo = repo;
+
+	return git_reference_foreach(repo, GIT_REF_OID | GIT_REF_PACKED,
+				     &tags_cb, &data);
+}
+
+typedef struct {
+	git_vector *taglist;
+	const char *pattern;
 } tag_filter_data;
 
 #define GIT_REFS_TAGS_DIR_LEN strlen(GIT_REFS_TAGS_DIR)
 
-static int tag_list_cb(const char *tag_name, void *payload)
+static int tag_list_cb(const char *tag_name, git_oid *oid, void *data)
 {
-	tag_filter_data *filter;
-
-	if (git__prefixcmp(tag_name, GIT_REFS_TAGS_DIR) != 0)
-		return 0;
+	tag_filter_data *filter = (tag_filter_data *)data;
+	GIT_UNUSED(oid);
 
-	filter = (tag_filter_data *)payload;
 	if (!*filter->pattern || p_fnmatch(filter->pattern, tag_name + GIT_REFS_TAGS_DIR_LEN, 0) == 0)
 		return git_vector_insert(filter->taglist, git__strdup(tag_name + GIT_REFS_TAGS_DIR_LEN));
 
@@ -427,7 +458,7 @@ int git_tag_list_match(git_strarray *tag_names, const char *pattern, git_reposit
 	filter.taglist = &taglist;
 	filter.pattern = pattern;
 
-	error = git_reference_foreach(repo, GIT_REF_OID|GIT_REF_PACKED, &tag_list_cb, (void *)&filter);
+	error = git_tag_foreach(repo, &tag_list_cb, (void *)&filter);
 	if (error < 0) {
 		git_vector_free(&taglist);
 		return -1;
diff --git a/src/thread-utils.h b/src/thread-utils.h
index a309e93d1..f0a51f28c 100644
--- a/src/thread-utils.h
+++ b/src/thread-utils.h
@@ -38,13 +38,13 @@ GIT_INLINE(void) git_atomic_set(git_atomic *a, int val)
 #define git_mutex_unlock(a) pthread_mutex_unlock(a)
 #define git_mutex_free(a)	pthread_mutex_destroy(a)
 
-/* Pthreads condition vars -- disabled by now */
-#define git_cond unsigned int //pthread_cond_t
-#define git_cond_init(c, a)	(void)0		//pthread_cond_init(c, a)
-#define git_cond_free(c) (void)0		//pthread_cond_destroy(c)
-#define git_cond_wait(c, l)	(void)0		//pthread_cond_wait(c, l)
-#define git_cond_signal(c)	(void)0		//pthread_cond_signal(c)
-#define git_cond_broadcast(c) (void)0	//pthread_cond_broadcast(c)
+/* Pthreads condition vars */
+#define git_cond pthread_cond_t
+#define git_cond_init(c)	pthread_cond_init(c, NULL)
+#define git_cond_free(c) 	pthread_cond_destroy(c)
+#define git_cond_wait(c, l)	pthread_cond_wait(c, l)
+#define git_cond_signal(c)	pthread_cond_signal(c)
+#define git_cond_broadcast(c)	pthread_cond_broadcast(c)
 
 GIT_INLINE(int) git_atomic_inc(git_atomic *a)
 {
diff --git a/tests-clar/pack/packbuilder.c b/tests-clar/pack/packbuilder.c
new file mode 100644
index 000000000..fa7bec14e
--- /dev/null
+++ b/tests-clar/pack/packbuilder.c
@@ -0,0 +1,67 @@
+#include "clar_libgit2.h"
+#include "iterator.h"
+#include "vector.h"
+
+static git_repository *_repo;
+static git_revwalk *_revwalker;
+static git_packbuilder *_packbuilder;
+static git_indexer *_indexer;
+static git_vector _commits;
+
+void test_pack_packbuilder__initialize(void)
+{
+	cl_git_pass(git_repository_open(&_repo, cl_fixture("testrepo.git")));
+	cl_git_pass(git_revwalk_new(&_revwalker, _repo));
+	cl_git_pass(git_packbuilder_new(&_packbuilder, _repo));
+	cl_git_pass(git_vector_init(&_commits, 0, NULL));
+}
+
+void test_pack_packbuilder__cleanup(void)
+{
+	git_oid *o;
+	unsigned int i;
+
+	git_vector_foreach(&_commits, i, o) {
+		git__free(o);
+	}
+	git_vector_free(&_commits);
+	git_packbuilder_free(_packbuilder);
+	git_revwalk_free(_revwalker);
+	git_indexer_free(_indexer);
+	git_repository_free(_repo);
+}
+
+void test_pack_packbuilder__create_pack(void)
+{
+	git_indexer_stats stats;
+	git_oid oid, *o;
+	unsigned int i;
+
+	git_revwalk_sorting(_revwalker, GIT_SORT_TIME);
+	cl_git_pass(git_revwalk_push_ref(_revwalker, "HEAD"));
+
+	while (git_revwalk_next(&oid, _revwalker) == 0) {
+		o = git__malloc(GIT_OID_RAWSZ);
+		cl_assert(o != NULL);
+		git_oid_cpy(o, &oid);
+		cl_git_pass(git_vector_insert(&_commits, o));
+	}
+
+	git_vector_foreach(&_commits, i, o) {
+		cl_git_pass(git_packbuilder_insert(_packbuilder, o, NULL));
+	}
+
+	git_vector_foreach(&_commits, i, o) {
+		git_object *obj;
+		cl_git_pass(git_object_lookup(&obj, _repo, o, GIT_OBJ_COMMIT));
+		cl_git_pass(git_packbuilder_insert_tree(_packbuilder,
+					git_commit_tree_oid((git_commit *)obj)));
+		git_object_free(obj);
+	}
+
+	cl_git_pass(git_packbuilder_write(_packbuilder, "testpack.pack"));
+
+	cl_git_pass(git_indexer_new(&_indexer, "testpack.pack"));
+	cl_git_pass(git_indexer_run(_indexer, &stats));
+	cl_git_pass(git_indexer_write(_indexer));
+}