Merge branch 'krh/master'

Conflicts:

	librazor/razor.h
	librazor/rpm.c
	razor.c
	src/main.c

13 files changed, 4658 insertions, 0 deletions

diff --git a/librazor/.gitignore b/librazor/.gitignore
new file mode 100644
index 0000000..7fe452b
--- /dev/null
+++ b/librazor/.gitignore
@@ -0,0 +1,5 @@
+.deps
+.libs
+*.lo
+*.la
+
diff --git a/librazor/Makefile.am b/librazor/Makefile.am
new file mode 100644
index 0000000..a858968
--- /dev/null
+++ b/librazor/Makefile.am
@@ -0,0 +1,37 @@
+## Process this file with automake to produce Makefile.in
+
+INCLUDES = \
+	-I$(top_builddir)/src -I$(top_srcdir)/src \
+	-DPACKAGE_LIBEXEC_DIR=\""$(libexecdir)"\" \
+	-DPACKAGE_SYSCONF_DIR=\""$(sysconfdir)"\" \
+	-DPACKAGE_DATA_DIR=\""$(datadir)"\" \
+	-DPACKAGE_BIN_DIR=\""$(bindir)"\" \
+	-DPACKAGE_LOCALSTATE_DIR=\""$(localstatedir)"\" \
+	-DPACKAGE_LOCALE_DIR=\""$(localedir)"\" \
+	-DPACKAGE_LIB_DIR=\""$(libdir)"\"
+
+lib_LTLIBRARIES = librazor.la
+
+librazorincludedir = $(includedir)/razor
+
+librazorinclude_HEADERS =              			\
+	razor.h
+
+librazor_la_SOURCES =                                	\
+	razor-internal.h				\
+	razor.h						\
+	razor.c						\
+	root.c						\
+	types.c						\
+	util.c						\
+	rpm.c						\
+	iterator.c					\
+	importer.c					\
+	merger.c					\
+	transaction.c
+
+librazor_la_LIBADD = $(ZLIB_LIBS)
+
+clean-local :
+	rm -f *~
+
diff --git a/librazor/importer.c b/librazor/importer.c
new file mode 100644
index 0000000..eca9ede
--- /dev/null
+++ b/librazor/importer.c
@@ -0,0 +1,505 @@
+/*
+ * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
+ * Copyright (C) 2008  Red Hat, Inc
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#define _GNU_SOURCE
+
+#include <string.h>
+#include "razor-internal.h"
+#include "razor.h"
+
+void
+razor_importer_begin_package(struct razor_importer *importer,
+			     const char *name,
+			     const char *version,
+			     const char *arch)
+{
+	struct razor_package *p;
+
+	p = array_add(&importer->set->packages, sizeof *p);
+	p->name = hashtable_tokenize(&importer->table, name);
+	p->flags = 0;
+	p->version = hashtable_tokenize(&importer->table, version);
+	p->arch = hashtable_tokenize(&importer->table, arch);
+
+	importer->package = p;
+	array_init(&importer->properties);
+}
+
+
+void
+razor_importer_finish_package(struct razor_importer *importer)
+{
+	list_set_array(&importer->package->properties,
+		       &importer->set->property_pool,
+		       &importer->properties,
+		       1);
+
+	array_release(&importer->properties);
+}
+
+void
+razor_importer_add_details(struct razor_importer *importer,
+			   const char *summary,
+			   const char *description,
+			   const char *url,
+			   const char *license)
+{
+	importer->package->summary = hashtable_tokenize(&importer->details_table, summary);
+	importer->package->description = hashtable_tokenize(&importer->details_table, description);
+	importer->package->url = hashtable_tokenize(&importer->details_table, url);
+	importer->package->license = hashtable_tokenize(&importer->details_table, license);
+}
+
+void
+razor_importer_add_property(struct razor_importer *importer,
+			    const char *name,
+			    uint32_t flags,
+			    const char *version)
+{
+	struct razor_property *p;
+	uint32_t *r;
+
+	p = array_add(&importer->set->properties, sizeof *p);
+	p->name = hashtable_tokenize(&importer->table, name);
+	p->flags = flags;
+	p->version = hashtable_tokenize(&importer->table, version);
+	list_set_ptr(&p->packages, importer->package -
+		     (struct razor_package *) importer->set->packages.data);
+
+	r = array_add(&importer->properties, sizeof *r);
+	*r = p - (struct razor_property *) importer->set->properties.data;
+
+	if (((flags & RAZOR_PROPERTY_TYPE_MASK) == RAZOR_PROPERTY_REQUIRES) &&
+	    *name == '/') {
+		r = array_add(&importer->file_requires, sizeof *r);
+		*r = p->name;
+	}
+}
+
+void
+razor_importer_add_file(struct razor_importer *importer, const char *name)
+{
+	struct import_entry *e;
+
+	e = array_add(&importer->files, sizeof *e);
+
+	e->package = importer->package -
+		(struct razor_package *) importer->set->packages.data;
+	e->name = strdup(name);
+}
+
+struct razor_importer *
+razor_importer_new(void)
+{
+	struct razor_importer *importer;
+
+	importer = zalloc(sizeof *importer);
+	importer->set = razor_set_create();
+	hashtable_init(&importer->table, &importer->set->string_pool);
+	hashtable_init(&importer->details_table,
+		       &importer->set->details_string_pool);
+	hashtable_init(&importer->file_table,
+		       &importer->set->file_string_pool);
+
+	return importer;
+}
+
+/* Destroy an importer without creating the set. */
+void
+razor_importer_destroy(struct razor_importer *importer)
+{
+	/* FIXME: write this */
+}
+
+static int
+compare_packages(const void *p1, const void *p2, void *data)
+{
+	const struct razor_package *pkg1 = p1, *pkg2 = p2;
+	struct razor_set *set = data;
+	char *pool = set->string_pool.data;
+
+	/* FIXME: what if the flags are different? */
+	if (pkg1->name == pkg2->name)
+		return razor_versioncmp(&pool[pkg1->version], &pool[pkg2->version]);
+	else
+		return strcmp(&pool[pkg1->name], &pool[pkg2->name]);
+}
+
+static int
+compare_properties(const void *p1, const void *p2, void *data)
+{
+	const struct razor_property *prop1 = p1, *prop2 = p2;
+	struct razor_set *set = data;
+	char *pool = set->string_pool.data;
+
+	if (prop1->name != prop2->name)
+		return strcmp(&pool[prop1->name], &pool[prop2->name]);
+	else if (prop1->flags != prop2->flags)
+		return prop1->flags - prop2->flags;
+	else
+		return razor_versioncmp(&pool[prop1->version], &pool[prop2->version]);
+}
+
+static uint32_t *
+uniqueify_properties(struct razor_set *set)
+{
+	struct razor_property *rp, *up, *rp_end;
+	struct array *pkgs, *p;
+	struct list_head *r;
+	uint32_t *map, *rmap;
+	int i, count, unique;
+
+	count = set->properties.size / sizeof(struct razor_property);
+	map = razor_qsort_with_data(set->properties.data,
+				    count,
+				    sizeof(struct razor_property),
+				    compare_properties,
+				    set);
+
+	rp_end = set->properties.data + set->properties.size;
+	rmap = malloc(count * sizeof *map);
+	pkgs = zalloc(count * sizeof *pkgs);
+	for (rp = set->properties.data, up = rp, i = 0; rp < rp_end; rp++, i++) {
+		if (rp->name != up->name ||
+		    rp->flags != up->flags ||
+		    rp->version != up->version) {
+			up++;
+			up->name = rp->name;
+			up->flags = rp->flags;
+			up->version = rp->version;
+		}
+
+		unique = up - (struct razor_property *) set->properties.data;
+		rmap[map[i]] = unique;
+		r = array_add(&pkgs[unique], sizeof *r);
+		*r = rp->packages;
+	}
+	free(map);
+
+	if (up != rp)
+		up++;
+	set->properties.size = (void *) up - set->properties.data;
+	rp_end = up;
+	for (rp = set->properties.data, p = pkgs; rp < rp_end; rp++, p++) {
+		list_set_array(&rp->packages, &set->package_pool, p, 0);
+		array_release(p);
+	}
+
+	free(pkgs);
+
+	return rmap;
+}
+
+static int
+compare_filenames(const void *p1, const void *p2, void *data)
+{
+	const struct import_entry *e1 = p1;
+	const struct import_entry *e2 = p2;
+	const char *n1 = e1->name;
+	const char *n2 = e2->name;
+
+	/* Need to make sure that the contents of a directory
+	 * are sorted immediately after it. So "foo/bar" has to
+	 * sort before "foo.conf"
+	 *
+	 * FIXME: this is about 60% slower than strcmp
+	 */
+	while (*n1 && *n2) {
+		if (*n1 < *n2)
+			return *n2 == '/' ? 1 : -1;
+		else if (*n1 > *n2)
+			return *n1 == '/' ? -1 : 1;
+		n1++;
+		n2++;
+	}
+	if (*n1)
+		return 1;
+	else if (*n2)
+		return -1;
+	else
+		return 0;
+}
+
+static void
+count_entries(struct import_directory *d)
+{
+	struct import_directory *p, *end;
+
+	p = d->files.data;
+	end = d->files.data + d->files.size;
+	d->count = 0;
+	while (p < end) {
+		count_entries(p);
+		d->count += p->count + 1;
+		p++;
+	}
+}
+
+static void
+serialize_files(struct razor_set *set,
+		struct import_directory *d, struct array *array)
+{
+	struct import_directory *p, *end;
+	struct razor_entry *e = NULL;
+	uint32_t s;
+
+	p = d->files.data;
+	end = d->files.data + d->files.size;
+	s = array->size / sizeof *e + d->files.size / sizeof *p;
+	while (p < end) {
+		e = array_add(array, sizeof *e);
+		e->name = p->name;
+		e->flags = 0;
+		e->start = p->count > 0 ? s : 0;
+		s += p->count;
+
+		list_set_array(&e->packages, &set->package_pool, &p->packages, 0);
+		array_release(&p->packages);
+		p++;
+	}
+	if (e != NULL)
+		e->flags |= RAZOR_ENTRY_LAST;
+
+	p = d->files.data;
+	end = d->files.data + d->files.size;
+	while (p < end) {
+		serialize_files(set, p, array);
+		p++;
+	}
+}
+
+static void
+remap_property_package_links(struct array *properties, uint32_t *rmap)
+{
+	struct razor_property *p, *end;
+
+	end = properties->data + properties->size;
+	for (p = properties->data; p < end; p++)
+		list_remap_head(&p->packages, rmap);
+}
+
+static void
+build_file_tree(struct razor_importer *importer)
+{
+	int count, i, length;
+	struct import_entry *filenames;
+	char *f, *end;
+	uint32_t name, *r;
+	char dirname[256];
+	struct import_directory *d, root;
+	struct razor_entry *e;
+
+	count = importer->files.size / sizeof (struct import_entry);
+	razor_qsort_with_data(importer->files.data,
+			      count,
+			      sizeof (struct import_entry),
+			      compare_filenames,
+			      NULL);
+
+	root.name = hashtable_tokenize(&importer->table, "");
+	array_init(&root.files);
+	array_init(&root.packages);
+	root.last = NULL;
+
+	filenames = importer->files.data;
+	for (i = 0; i < count; i++) {
+		f = filenames[i].name;
+		if (*f != '/')
+			continue;
+		f++;
+
+		d = &root;
+		while (*f) {
+			end = strchr(f, '/');
+			if (end == NULL)
+				end = f + strlen(f);
+			length = end - f;
+			memcpy(dirname, f, length);
+			dirname[length] ='\0';
+			name = hashtable_tokenize(&importer->table, dirname);
+			if (d->last == NULL || d->last->name != name) {
+				d->last = array_add(&d->files, sizeof *d);
+				d->last->name = name;
+				d->last->last = NULL;
+				array_init(&d->last->files);
+				array_init(&d->last->packages);
+			}
+			d = d->last;
+			f = end + 1;
+			if (*end == '\0')
+				break;
+		}
+
+		r = array_add(&d->packages, sizeof *r);
+		*r = filenames[i].package;
+		free(filenames[i].name);
+	}
+
+	count_entries(&root);
+	e = importer->set->files.data;
+	e->name = root.name;
+	e->flags = RAZOR_ENTRY_LAST;
+	e->start = importer->files.size ? 1 : 0;
+	list_set_empty(&e->packages);
+
+	serialize_files(importer->set, &root, &importer->set->files);
+
+	array_release(&importer->files);
+}
+
+static void
+list_to_array(struct list *list, struct array *array)
+{
+	uint32_t *item;
+
+	while (list) {
+		 item = array_add(array, sizeof *item);
+		 *item = list->data;
+		 list = list_next(list);
+	}
+}
+
+static int
+compare_file_requires(const void *p1, const void *p2, void *data)
+{
+	uint32_t *f1 = (void *)p1, *f2 = (void *)p2;
+	const char *pool = data;
+
+	return strcmp(&pool[*f1], &pool[*f2]);
+}
+
+static void
+find_file_provides(struct razor_importer *importer)
+{
+	struct razor_property *prop;
+	struct razor_entry *top, *entry;
+	struct razor_package *packages;
+	struct array pkgprops;
+	struct list *pkg;
+	uint32_t *req, *req_start, *req_end;
+	uint32_t *map, *newprop;
+	char *pool;
+
+	pool = importer->set->string_pool.data;
+	packages = importer->set->packages.data;
+	top = importer->set->files.data;
+
+	req = req_start = importer->file_requires.data;
+	req_end = importer->file_requires.data + importer->file_requires.size;
+	map = razor_qsort_with_data(req, req_end - req, sizeof *req,
+				    compare_file_requires, pool);
+	free(map);
+
+	for (req = req_start; req < req_end; req++) {
+		if (req > req_start && req[0] == req[-1])
+			continue;
+		entry = razor_set_find_entry(importer->set, top, &pool[*req]);
+		if (!entry)
+			continue;
+
+		for (pkg = list_first(&entry->packages, &importer->set->package_pool); pkg; pkg = list_next(pkg)) {
+			prop = array_add(&importer->set->properties, sizeof *prop);
+			prop->name = *req;
+			prop->flags =
+				RAZOR_PROPERTY_PROVIDES | RAZOR_PROPERTY_EQUAL;
+			prop->version = hashtable_tokenize(&importer->table, "");
+			list_set_ptr(&prop->packages, pkg->data);
+
+			/* Update property list of pkg */
+			array_init(&pkgprops);
+			list_to_array(list_first(&packages[pkg->data].properties, &importer->set->property_pool), &pkgprops);
+			newprop = array_add(&pkgprops, sizeof *newprop);
+			*newprop = prop - (struct razor_property *)importer->set->properties.data;
+			list_set_array(&packages[pkg->data].properties, &importer->set->property_pool, &pkgprops, 1);
+			array_release(&pkgprops);
+		}
+	}
+
+	array_release(&importer->file_requires);
+}
+
+static void
+build_package_file_lists(struct razor_set *set, uint32_t *rmap)
+{
+	struct razor_package *p, *packages;
+	struct array *pkgs;
+	struct razor_entry *e, *end;
+	struct list *r;
+	uint32_t *q;
+	int i, count;
+
+	count = set->packages.size / sizeof *p;
+	pkgs = zalloc(count * sizeof *pkgs);
+
+	end = set->files.data + set->files.size;
+	for (e = set->files.data; e < end; e++) {
+		list_remap_head(&e->packages, rmap);
+		r = list_first(&e->packages, &set->package_pool);
+		while (r) {
+			q = array_add(&pkgs[r->data], sizeof *q);
+			*q = e - (struct razor_entry *) set->files.data;
+			r = list_next(r);
+		}
+	}
+
+	packages = set->packages.data;
+	for (i = 0; i < count; i++) {
+		list_set_array(&packages[i].files, &set->file_pool, &pkgs[i], 0);
+		array_release(&pkgs[i]);
+	}
+	free(pkgs);
+}
+
+struct razor_set *
+razor_importer_finish(struct razor_importer *importer)
+{
+	struct razor_set *set;
+	uint32_t *map, *rmap;
+	int i, count;
+
+	build_file_tree(importer);
+	find_file_provides(importer);
+
+	map = uniqueify_properties(importer->set);
+	list_remap_pool(&importer->set->property_pool, map);
+	free(map);
+
+	count = importer->set->packages.size / sizeof(struct razor_package);
+	map = razor_qsort_with_data(importer->set->packages.data,
+				    count,
+				    sizeof(struct razor_package),
+				    compare_packages,
+				    importer->set);
+
+	rmap = malloc(count * sizeof *rmap);
+	for (i = 0; i < count; i++)
+		rmap[map[i]] = i;
+	free(map);
+
+	list_remap_pool(&importer->set->package_pool, rmap);
+	build_package_file_lists(importer->set, rmap);
+	remap_property_package_links(&importer->set->properties, rmap);
+	free(rmap);
+
+	set = importer->set;
+	hashtable_release(&importer->table);
+	free(importer);
+
+	return set;
+}
diff --git a/librazor/iterator.c b/librazor/iterator.c
new file mode 100644
index 0000000..909b954
--- /dev/null
+++ b/librazor/iterator.c
@@ -0,0 +1,265 @@
+/*
+ * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
+ * Copyright (C) 2008  Red Hat, Inc
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#define _GNU_SOURCE
+
+#include <string.h>
+#include "razor-internal.h"
+#include "razor.h"
+
+static struct razor_package_iterator *
+razor_package_iterator_create_with_index(struct razor_set *set,
+					 struct list *index)
+{
+	struct razor_package_iterator *pi;
+
+	pi = zalloc(sizeof *pi);
+	pi->set = set;
+	pi->index = index;
+
+	return pi;
+}
+
+struct razor_package_iterator *
+razor_package_iterator_create(struct razor_set *set)
+{
+	struct razor_package_iterator *pi;
+
+	pi = zalloc(sizeof *pi);
+	pi->set = set;
+	pi->end = set->packages.data + set->packages.size;
+	pi->package = set->packages.data;
+
+	return pi;
+}
+
+void
+razor_package_iterator_init_for_property(struct razor_package_iterator *pi,
+					 struct razor_set *set,
+					 struct razor_property *property)
+{
+	memset(pi, 0, sizeof *pi);
+	pi->set = set;
+	pi->index = list_first(&property->packages, &set->package_pool);
+}
+
+struct razor_package_iterator *
+razor_package_iterator_create_for_property(struct razor_set *set,
+					   struct razor_property *property)
+{
+	struct list *index;
+
+	index = list_first(&property->packages, &set->package_pool);
+	return razor_package_iterator_create_with_index(set, index);
+}
+
+struct razor_package_iterator *
+razor_package_iterator_create_for_file(struct razor_set *set,
+				       const char *filename)
+{
+	struct razor_entry *entry;
+	struct list *index;
+
+	entry = razor_set_find_entry(set, set->files.data, filename);
+	if (entry == NULL)
+		return NULL;
+
+	index = list_first(&entry->packages, &set->package_pool);
+	return razor_package_iterator_create_with_index(set, index);
+}
+
+int
+razor_package_iterator_next(struct razor_package_iterator *pi,
+			    struct razor_package **package,
+			    const char **name,
+			    const char **version,
+			    const char **arch)
+{
+	char *pool;
+	int valid;
+	struct razor_package *p, *packages;
+
+	if (pi->package) {
+		p = pi->package++;
+		valid = p < pi->end;
+	} else if (pi->index) {
+		packages = pi->set->packages.data;
+		p = &packages[pi->index->data];
+		pi->index = list_next(pi->index);
+		valid = 1;
+	} else
+		valid = 0;
+
+	if (valid) {
+		pool = pi->set->string_pool.data;
+		*package = p;
+		*name = &pool[p->name];
+		*version = &pool[p->version];
+		*arch = &pool[p->arch];
+	} else {
+		*package = NULL;
+	}
+
+	return valid;
+}
+
+void
+razor_package_iterator_destroy(struct razor_package_iterator *pi)
+{
+	if (pi->free_index)
+		free(pi->index);
+
+	free(pi);
+}
+
+struct razor_property_iterator *
+razor_property_iterator_create(struct razor_set *set,
+			       struct razor_package *package)
+{
+	struct razor_property_iterator *pi;
+
+	pi = zalloc(sizeof *pi);
+	pi->set = set;
+
+	if (package) {
+		pi->index = list_first(&package->properties,
+				       &set->property_pool);
+	} else {
+		pi->property = set->properties.data;
+		pi->end = set->properties.data + set->properties.size;
+	}
+
+	return pi;
+}
+
+int
+razor_property_iterator_next(struct razor_property_iterator *pi,
+			     struct razor_property **property,
+			     const char **name,
+			     uint32_t *flags,
+			     const char **version)
+{
+	char *pool;
+	int valid;
+	struct razor_property *p, *properties;
+
+	if (pi->property) {
+		p = pi->property++;
+		valid = p < pi->end;
+	} else if (pi->index) {
+		properties = pi->set->properties.data;
+		p = &properties[pi->index->data];
+		pi->index = list_next(pi->index);
+		valid = 1;
+	} else
+		valid = 0;
+
+	if (valid) {
+		pool = pi->set->string_pool.data;
+		*property = p;
+		*name = &pool[p->name];
+		*flags = p->flags;
+		*version = &pool[p->version];
+	} else {
+		*property = NULL;
+	}
+
+	return valid;
+}
+
+void
+razor_property_iterator_destroy(struct razor_property_iterator *pi)
+{
+	free(pi);
+}
+
+struct razor_package_query {
+	struct razor_set *set;
+	char *vector;
+	int count;
+};
+
+struct razor_package_query *
+razor_package_query_create(struct razor_set *set)
+{
+	struct razor_package_query *pq;
+	int count;
+
+	pq = zalloc(sizeof *pq);
+	pq->set = set;
+	count = set->packages.size / sizeof(struct razor_package);
+	pq->vector = zalloc(count * sizeof(char));
+
+	return pq;
+}
+
+void
+razor_package_query_add_package(struct razor_package_query *pq,
+				struct razor_package *p)
+{
+	struct razor_package *packages;
+
+	packages = pq->set->packages.data;
+	pq->count += pq->vector[p - packages] ^ 1;
+	pq->vector[p - packages] = 1;
+}
+
+void
+razor_package_query_add_iterator(struct razor_package_query *pq,
+				 struct razor_package_iterator *pi)
+{
+	struct razor_package *packages, *p;
+	const char *name, *version, *arch;
+
+	packages = pq->set->packages.data;
+	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
+		pq->count += pq->vector[p - packages] ^ 1;
+		pq->vector[p - packages] = 1;
+	}
+}
+
+struct razor_package_iterator *
+razor_package_query_finish(struct razor_package_query *pq)
+{
+	struct razor_package_iterator *pi;
+	struct razor_set *set;
+	struct list *index;
+	int i, j, count;
+
+	set = pq->set;
+	count = set->packages.size / sizeof(struct razor_package);
+	index = zalloc(pq->count * sizeof *index);
+
+	for (i = 0, j = 0; i < count; i++) {
+		if (!pq->vector[i])
+			continue;
+
+		index[j].data = i;
+		if (j == pq->count - 1)
+			index[j].flags = 0x80;
+		j++;
+	}
+
+	free(pq);
+
+	pi = razor_package_iterator_create_with_index(set, index);
+	pi->free_index = 1;
+
+	return pi;
+}
diff --git a/librazor/merger.c b/librazor/merger.c
new file mode 100644
index 0000000..636903a
--- /dev/null
+++ b/librazor/merger.c
@@ -0,0 +1,525 @@
+/*
+ * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
+ * Copyright (C) 2008  Red Hat, Inc
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <string.h>
+#include "razor-internal.h"
+#include "razor.h"
+
+#define UPSTREAM_SOURCE 0x80
+
+struct source {
+	struct razor_set *set;
+	uint32_t *property_map;
+	uint32_t *file_map;
+};
+
+struct razor_merger {
+	struct razor_set *set;
+	struct hashtable table;
+	struct source source1;
+	struct source source2;
+};
+
+struct razor_merger *
+razor_merger_create(struct razor_set *set1, struct razor_set *set2)
+{
+	struct razor_merger *merger;
+	int count;
+	size_t size;
+
+	merger = zalloc(sizeof *merger);
+	merger->set = razor_set_create();
+	hashtable_init(&merger->table, &merger->set->string_pool);
+
+	merger->source1.set = set1;
+	count = set1->properties.size / sizeof (struct razor_property);
+	size = count * sizeof merger->source1.property_map[0];
+	merger->source1.property_map = zalloc(size);
+	count = set1->files.size / sizeof (struct razor_entry);
+	size = count * sizeof merger->source1.file_map[0];
+	merger->source1.file_map = zalloc(size);
+
+	merger->source2.set = set2;
+	count = set2->properties.size / sizeof (struct razor_property);
+	size = count * sizeof merger->source2.property_map[0];
+	merger->source2.property_map = zalloc(size);
+	count = set2->files.size / sizeof (struct razor_entry);
+	size = count * sizeof merger->source2.file_map[0];
+	merger->source2.file_map = zalloc(size);
+
+	return merger;
+}
+
+void
+razor_merger_add_package(struct razor_merger *merger,
+			 struct razor_package *package)
+{
+	char *pool;
+	struct list *r;
+	struct razor_package *p;
+	struct razor_set *set1;
+	struct source *source;
+	uint32_t flags;
+
+	set1 = merger->source1.set;
+	if (set1->packages.data <= (void *) package &&
+	    (void *) package < set1->packages.data + set1->packages.size) {
+		source = &merger->source1;
+		flags = 0;
+	} else {
+		source = &merger->source2;
+		flags = UPSTREAM_SOURCE;
+	}
+
+	pool = source->set->string_pool.data;
+	p = array_add(&merger->set->packages, sizeof *p);
+	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
+	p->flags = flags;
+	p->version = hashtable_tokenize(&merger->table,
+					&pool[package->version]);
+	p->arch = hashtable_tokenize(&merger->table,
+				     &pool[package->arch]);
+
+	p->properties = package->properties;
+	r = list_first(&package->properties, &source->set->property_pool);
+	while (r) {
+		source->property_map[r->data] = 1;
+		r = list_next(r);
+	}
+
+	p->files = package->files;
+	r = list_first(&package->files, &source->set->file_pool);
+	while (r) {
+		source->file_map[r->data] = 1;
+		r = list_next(r);
+	}
+}
+
+static uint32_t
+add_property(struct razor_merger *merger,
+	     const char *name, uint32_t flags, const char *version)
+{
+	struct razor_property *p;
+
+	p = array_add(&merger->set->properties, sizeof *p);
+	p->name = hashtable_tokenize(&merger->table, name);
+	p->flags = flags;
+	p->version = hashtable_tokenize(&merger->table, version);
+
+	return p - (struct razor_property *) merger->set->properties.data;
+}
+
+static void
+merge_properties(struct razor_merger *merger)
+{
+	struct razor_property *p1, *p2;
+	struct razor_set *set1, *set2;
+	uint32_t *map1, *map2;
+	int i, j, cmp, count1, count2;
+	char *pool1, *pool2;
+
+	set1 = merger->source1.set;
+	set2 = merger->source2.set;
+	map1 = merger->source1.property_map;
+	map2 = merger->source2.property_map;
+
+	i = 0;
+	j = 0;
+	pool1 = set1->string_pool.data;
+	pool2 = set2->string_pool.data;
+
+	count1 = set1->properties.size / sizeof *p1;
+	count2 = set2->properties.size / sizeof *p2;
+	while (i < count1 || j < count2) {
+		if (i < count1 && map1[i] == 0) {
+			i++;
+			continue;
+		}
+		if (j < count2 && map2[j] == 0) {
+			j++;
+			continue;
+		}
+		p1 = (struct razor_property *) set1->properties.data + i;
+		p2 = (struct razor_property *) set2->properties.data + j;
+		if (i < count1 && j < count2)
+			cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
+		else if (i < count1)
+			cmp = -1;
+		else
+			cmp = 1;
+		if (cmp == 0)
+			cmp = p1->flags - p2->flags;
+		if (cmp == 0)
+			cmp = razor_versioncmp(&pool1[p1->version],
+					       &pool2[p2->version]);
+		if (cmp < 0) {
+			map1[i++] = add_property(merger,
+						 &pool1[p1->name],
+						 p1->flags,
+						 &pool1[p1->version]);
+		} else if (cmp > 0) {
+			map2[j++] = add_property(merger,
+						 &pool2[p2->name],
+						 p2->flags,
+						 &pool2[p2->version]);
+		} else  {
+			map1[i++] = map2[j++] =
+				add_property(merger,
+					     &pool1[p1->name],
+					     p1->flags,
+					     &pool1[p1->version]);
+		}
+	}
+}
+
+static void
+emit_properties(struct list_head *properties, struct array *source_pool,
+		uint32_t *map, struct array *pool)
+{
+	uint32_t r;
+	struct list *p, *q;
+
+	r = pool->size / sizeof *q;
+	p = list_first(properties, source_pool);
+	while (p) {
+		q = array_add(pool, sizeof *q);
+		q->data = map[p->data];
+		q->flags = p->flags;
+		p = list_next(p);
+	}
+
+	list_set_ptr(properties, r);
+}
+
+static uint32_t
+add_file(struct razor_merger *merger, const char *name)
+{
+	struct razor_entry *e;
+
+	e = array_add(&merger->set->files, sizeof *e);
+	e->name = hashtable_tokenize(&merger->table, name);
+	e->flags = 0;
+	e->start = 0;
+
+	return e - (struct razor_entry *)merger->set->files.data;
+}
+
+/* FIXME. Blah */
+static int
+fix_file_map(uint32_t *map,
+	     struct razor_entry *files,
+	     struct razor_entry *top)
+{
+	uint32_t e;
+	int found_file = 0;
+
+	e = top->start;
+	do {
+		if (files[e].start)
+			fix_file_map(map, files, &files[e]);
+		if (map[e])
+			found_file = 1;
+	} while (!(files[e++].flags & RAZOR_ENTRY_LAST));
+
+	if (found_file)
+		map[top - files] = 1;
+	return found_file;
+}
+
+struct merge_directory {
+	uint32_t merged, dir1, dir2;
+};
+
+static void
+merge_one_directory(struct razor_merger *merger, struct merge_directory *md)
+{
+	struct razor_entry *root1, *root2, *mroot, *e1, *e2;
+	struct razor_set *set1, *set2;
+	struct array merge_stack;
+	struct merge_directory *child_md, *end_md;
+	uint32_t *map1, *map2, start, last;
+	int cmp;
+	char *pool1, *pool2;
+
+	set1 = merger->source1.set;
+	set2 = merger->source2.set;
+	map1 = merger->source1.file_map;
+	map2 = merger->source2.file_map;
+	pool1 = set1->string_pool.data;
+	pool2 = set2->string_pool.data;
+	root1 = (struct razor_entry *) set1->files.data;
+	root2 = (struct razor_entry *) set2->files.data;
+
+	array_init(&merge_stack);
+
+	start = merger->set->files.size / sizeof (struct razor_entry);
+	last = 0;
+	e1 = md->dir1 ? root1 + md->dir1 : NULL;
+	e2 = md->dir2 ? root2 + md->dir2 : NULL;
+	while (e1 || e2) {
+		if (!e2 && !map1[e1 - root1]) {
+			if ((e1++)->flags & RAZOR_ENTRY_LAST)
+				e1 = NULL;
+			continue;
+		}
+		if (!e1 && !map2[e2 - root2]) {
+			if ((e2++)->flags & RAZOR_ENTRY_LAST)
+				e2 = NULL;
+			continue;
+		}
+		if (e1 && !map1[e1 - root1] &&
+		    e2 && !map1[e2 - root2]) {
+			if ((e1++)->flags & RAZOR_ENTRY_LAST)
+				e1 = NULL;
+			if ((e2++)->flags & RAZOR_ENTRY_LAST)
+				e2 = NULL;
+			continue;
+		}
+
+		if (!e1)
+			cmp = 1;
+		else if (!e2)
+			cmp = -1;
+		else {
+			cmp = strcmp (&pool1[e1->name],
+				      &pool2[e2->name]);
+		}
+
+		if (cmp < 0) {
+			if (map1[e1 - root1]) {
+				map1[e1 - root1] = last =
+					add_file(merger, &pool1[e1->name]);
+				if (e1->start) {
+					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
+					child_md->merged = last;
+					child_md->dir1 = e1->start;
+					child_md->dir2 = 0;
+				}
+			}
+			if ((e1++)->flags & RAZOR_ENTRY_LAST)
+				e1 = NULL;
+		} else if (cmp > 0) {
+			if (map2[e2 - root2]) {
+				map2[e2 - root2] = last =
+					add_file(merger, &pool2[e2->name]);
+				if (e2->start) {
+					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
+					child_md->merged = last;
+					child_md->dir1 = 0;
+					child_md->dir2 = e2->start;
+				}
+			}
+			if ((e2++)->flags & RAZOR_ENTRY_LAST)
+				e2 = NULL;
+		} else {
+			map1[e1 - root1] = map2[e2- root2] = last =
+				add_file(merger, &pool1[e1->name]);
+			if (e1->start || e2->start) {
+				child_md = array_add(&merge_stack, sizeof (struct merge_directory));
+				child_md->merged = last;
+				child_md->dir1 = e1->start;
+				child_md->dir2 = e2->start;
+			}
+			if ((e1++)->flags & RAZOR_ENTRY_LAST)
+				e1 = NULL;
+			if ((e2++)->flags & RAZOR_ENTRY_LAST)
+				e2 = NULL;
+		}
+	}
+
+	mroot = (struct razor_entry *)merger->set->files.data;
+	if (last) {
+		mroot[last].flags = RAZOR_ENTRY_LAST;
+		mroot[md->merged].start = start;
+	} else
+		mroot[md->merged].start = 0;
+
+	end_md = merge_stack.data + merge_stack.size;
+	for (child_md = merge_stack.data; child_md < end_md; child_md++)
+		merge_one_directory(merger, child_md);
+	array_release(&merge_stack);
+}
+
+static void
+merge_files(struct razor_merger *merger)
+{
+	struct razor_entry *root;
+	struct merge_directory md;
+	uint32_t *map1, *map2;
+
+	map1 = merger->source1.file_map;
+	map2 = merger->source2.file_map;
+
+	md.merged = 0;
+
+	if (merger->source1.set->files.size) {
+		root = (struct razor_entry *) merger->source1.set->files.data;
+		if (root->start)
+			fix_file_map(map1, root, root);
+		md.dir1 = root->start;
+	} else
+		md.dir1 = 0;
+
+	if (merger->source2.set->files.size) {
+		root = (struct razor_entry *) merger->source2.set->files.data;
+		if (root->start)
+			fix_file_map(map2, root, root);
+		md.dir2 = root->start;
+	} else
+		md.dir2 = 0;
+
+	merge_one_directory(merger, &md);
+}
+
+static void
+emit_files(struct list_head *files, struct array *source_pool,
+	   uint32_t *map, struct array *pool)
+{
+	uint32_t r;
+	struct list *p, *q;
+
+	r = pool->size / sizeof *q;
+	p = list_first(files, source_pool);
+	while (p) {
+		q = array_add(pool, sizeof *q);
+		q->data = map[p->data];
+		q->flags = p->flags;
+		p = list_next(p);
+	}
+
+	list_set_ptr(files, r);
+}
+
+/* Rebuild property->packages maps.  We can't just remap these, as a
+ * property may have lost or gained a number of packages.  Allocate an
+ * array per property and loop through the packages and add them to
+ * the arrays for their properties. */
+static void
+rebuild_property_package_lists(struct razor_set *set)
+{
+	struct array *pkgs, *a;
+	struct razor_package *pkg, *pkg_end;
+	struct razor_property *prop, *prop_end;
+	struct list *r;
+	uint32_t *q;
+	int count;
+
+	count = set->properties.size / sizeof (struct razor_property);
+	pkgs = zalloc(count * sizeof *pkgs);
+	pkg_end = set->packages.data + set->packages.size;
+
+	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
+		r = list_first(&pkg->properties, &set->property_pool);
+		while (r) {
+			q = array_add(&pkgs[r->data], sizeof *q);
+			*q = pkg - (struct razor_package *) set->packages.data;
+			r = list_next(r);
+		}
+	}
+
+	prop_end = set->properties.data + set->properties.size;
+	a = pkgs;
+	for (prop = set->properties.data; prop < prop_end; prop++, a++) {
+		list_set_array(&prop->packages, &set->package_pool, a, 0);
+		array_release(a);
+	}
+	free(pkgs);
+}
+
+static void
+rebuild_file_package_lists(struct razor_set *set)
+{
+	struct array *pkgs, *a;
+	struct razor_package *pkg, *pkg_end;
+	struct razor_entry *entry, *entry_end;
+	struct list *r;
+	uint32_t *q;
+	int count;
+
+	count = set->files.size / sizeof (struct razor_entry);
+	pkgs = zalloc(count * sizeof *pkgs);
+	pkg_end = set->packages.data + set->packages.size;
+
+	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
+		r = list_first(&pkg->files, &set->file_pool);
+		while (r) {
+			q = array_add(&pkgs[r->data], sizeof *q);
+			*q = pkg - (struct razor_package *) set->packages.data;
+			r = list_next(r);
+		}
+	}
+
+	entry_end = set->files.data + set->files.size;
+	a = pkgs;
+	for (entry = set->files.data; entry < entry_end; entry++, a++) {
+		list_set_array(&entry->packages, &set->package_pool, a, 0);
+		array_release(a);
+	}
+	free(pkgs);
+}
+
+struct razor_set *
+razor_merger_finish(struct razor_merger *merger)
+{
+	struct razor_set *result;
+	struct razor_package *p, *pend;
+
+	/* As we built the package list, we filled out a bitvector of
+	 * the properties that are referenced by the packages in the
+	 * new set.  Now we do a parallel loop through the properties
+	 * and emit those marked in the bit vector to the new set.  In
+	 * the process, we update the bit vector to actually map from
+	 * indices in the old property list to indices in the new
+	 * property list for both sets. */
+
+	merge_properties(merger);
+	merge_files(merger);
+
+	/* Now we loop through the packages again and emit the
+	 * property lists, remapped to point to the new properties. */
+
+	pend = merger->set->packages.data + merger->set->packages.size;
+	for (p = merger->set->packages.data; p < pend; p++) {
+		struct source *src;
+
+		if (p->flags & UPSTREAM_SOURCE)
+			src = &merger->source2;
+		else
+			src = &merger->source1;
+
+		emit_properties(&p->properties,
+				&src->set->property_pool,
+				src->property_map,
+				&merger->set->property_pool);
+		emit_files(&p->files,
+			   &src->set->file_pool,
+			   src->file_map,
+			   &merger->set->file_pool);
+		p->flags &= ~UPSTREAM_SOURCE;
+	}
+
+	rebuild_property_package_lists(merger->set);
+	rebuild_file_package_lists(merger->set);
+
+	result = merger->set;
+	hashtable_release(&merger->table);
+	free(merger);
+
+	return result;
+}
diff --git a/librazor/razor-internal.h b/librazor/razor-internal.h
new file mode 100644
index 0000000..94eac41
--- /dev/null
+++ b/librazor/razor-internal.h
@@ -0,0 +1,194 @@
+#ifndef _RAZOR_INTERNAL_H_
+#define _RAZOR_INTERNAL_H_
+
+#include <stdlib.h>
+#include <stdint.h>
+
+void *zalloc(size_t size);
+
+struct array {
+	void *data;
+	int size, alloc;
+};
+
+void array_init(struct array *array);
+void array_release(struct array *array);
+void *array_add(struct array *array, int size);
+
+
+struct list_head {
+	uint32_t list_ptr : 24;
+	uint32_t flags    : 8;
+};
+
+struct list {
+	uint32_t data  : 24;
+	uint32_t flags : 8;
+};
+
+void list_set_empty(struct list_head *head);
+void list_set_ptr(struct list_head *head, uint32_t ptr);
+void list_set_array(struct list_head *head, struct array *pool, struct array *items, int force_indirect);
+
+struct list *list_first(struct list_head *head, struct array *pool);
+struct list *list_next(struct list *list);
+
+void list_remap_pool(struct array *pool, uint32_t *map);
+void list_remap_head(struct list_head *list, uint32_t *map);
+
+
+struct hashtable {
+	struct array buckets;
+	struct array *pool;
+};
+
+void hashtable_init(struct hashtable *table, struct array *pool);
+void hashtable_release(struct hashtable *table);
+uint32_t hashtable_insert(struct hashtable *table, const char *key);
+uint32_t hashtable_lookup(struct hashtable *table, const char *key);
+uint32_t hashtable_tokenize(struct hashtable *table, const char *string);
+
+
+struct razor_set_section {
+	uint32_t type;
+	uint32_t offset;
+	uint32_t size;
+};
+
+struct razor_set_header {
+	uint32_t magic;
+	uint32_t version;
+	struct razor_set_section sections[0];
+};
+
+#define RAZOR_MAGIC 		0x7a7a7a7a
+#define RAZOR_DETAILS_MAGIC 	0x7a7a7a7b
+#define RAZOR_FILES_MAGIC 	0x7a7a7a7c
+#define RAZOR_VERSION 1
+
+#define RAZOR_STRING_POOL		0
+#define RAZOR_PACKAGES			1
+#define RAZOR_PROPERTIES		2
+#define RAZOR_PACKAGE_POOL		3
+#define RAZOR_PROPERTY_POOL		4
+
+#define RAZOR_DETAILS_STRING_POOL	0
+
+#define RAZOR_FILES			0
+#define RAZOR_FILE_POOL			1
+#define RAZOR_FILE_STRING_POOL		2
+
+struct razor_package {
+	uint name  : 24;
+	uint flags : 8;
+	uint32_t version;
+	uint32_t arch;
+	uint32_t summary;
+	uint32_t description;
+	uint32_t url;
+	uint32_t license;
+	struct list_head properties;
+	struct list_head files;
+};
+
+
+struct razor_property {
+	uint32_t name;
+	uint32_t flags;
+	uint32_t version;
+	struct list_head packages;
+};
+
+struct razor_entry {
+	uint32_t name  : 24;
+	uint32_t flags : 8;
+	uint32_t start;
+	struct list_head packages;
+};
+
+#define RAZOR_ENTRY_LAST	0x80
+
+struct razor_set {
+	struct array string_pool;
+ 	struct array packages;
+ 	struct array properties;
+ 	struct array files;
+	struct array package_pool;
+ 	struct array property_pool;
+ 	struct array file_pool;
+	struct array file_string_pool;
+	struct array details_string_pool;
+	struct razor_set_header *header;
+	struct razor_set_header *details_header;
+	struct razor_set_header *files_header;
+};
+
+struct import_entry {
+	uint32_t package;
+	char *name;
+};
+
+struct import_directory {
+	uint32_t name, count;
+	struct array files;
+	struct array packages;
+	struct import_directory *last;
+};
+
+struct razor_importer {
+	struct razor_set *set;
+	struct hashtable table;
+	struct hashtable file_table;
+	struct hashtable details_table;
+	struct razor_package *package;
+	struct array properties;
+	struct array files;
+	struct array file_requires;
+};
+
+struct razor_package_iterator {
+	struct razor_set *set;
+	struct razor_package *package, *end;
+	struct list *index;
+	int free_index;
+};
+
+void
+razor_package_iterator_init_for_property(struct razor_package_iterator *pi,
+					 struct razor_set *set,
+					 struct razor_property *property);
+
+struct razor_property_iterator {
+	struct razor_set *set;
+	struct razor_property *property, *end;
+	struct list *index;
+};
+
+#define ALIGN(value, base) (((value) + (base - 1)) & ~((base) - 1))
+
+struct razor_entry *
+razor_set_find_entry(struct razor_set *set,
+		     struct razor_entry *dir, const char *pattern);
+
+struct razor_merger *
+razor_merger_create(struct razor_set *set1, struct razor_set *set2);
+void
+razor_merger_add_package(struct razor_merger *merger,
+			 struct razor_package *package);
+struct razor_set *
+razor_merger_finish(struct razor_merger *merger);
+
+/* Utility functions */
+
+int razor_create_dir(const char *root, const char *path);
+int razor_write(int fd, const void *data, size_t size);
+
+
+typedef int (*razor_compare_with_data_func_t)(const void *p1,
+					      const void *p,
+					      void *data);
+uint32_t *
+razor_qsort_with_data(void *base, size_t nelem, size_t size,
+		      razor_compare_with_data_func_t compare, void *data);
+
+#endif /* _RAZOR_INTERNAL_H_ */
diff --git a/librazor/razor.c b/librazor/razor.c
new file mode 100644
index 0000000..cddcc1b
--- /dev/null
+++ b/librazor/razor.c
@@ -0,0 +1,588 @@
+/*
+ * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
+ * Copyright (C) 2008  Red Hat, Inc
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#define _GNU_SOURCE
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <errno.h>
+#include <ctype.h>
+#include <fnmatch.h>
+
+#include "razor.h"
+#include "razor-internal.h"
+
+void *
+zalloc(size_t size)
+{
+	void *p;
+
+	p = malloc(size);
+	memset(p, 0, size);
+
+	return p;
+}
+
+struct razor_set_section razor_sections[] = {
+	{ RAZOR_STRING_POOL,	offsetof(struct razor_set, string_pool) },
+	{ RAZOR_PACKAGES,	offsetof(struct razor_set, packages) },
+	{ RAZOR_PROPERTIES,	offsetof(struct razor_set, properties) },
+	{ RAZOR_PACKAGE_POOL,	offsetof(struct razor_set, package_pool) },
+	{ RAZOR_PROPERTY_POOL,	offsetof(struct razor_set, property_pool) },
+};
+
+struct razor_set_section razor_files_sections[] = {
+	{ RAZOR_FILES,			offsetof(struct razor_set, files) },
+	{ RAZOR_FILE_POOL,		offsetof(struct razor_set, file_pool) },
+	{ RAZOR_FILE_STRING_POOL,	offsetof(struct razor_set, file_string_pool) },
+};
+
+struct razor_set_section razor_details_sections[] = {
+	{ RAZOR_DETAILS_STRING_POOL,	offsetof(struct razor_set, details_string_pool) },
+};
+struct razor_set *
+razor_set_create(void)
+{
+	struct razor_set *set;
+	struct razor_entry *e;
+	char *empty;
+
+	set = zalloc(sizeof *set);
+
+	e = array_add(&set->files, sizeof *e);
+	empty = array_add(&set->string_pool, 1);
+	*empty = '\0';
+	e->name = 0;
+	e->flags = RAZOR_ENTRY_LAST;
+	e->start = 0;
+	list_set_empty(&e->packages);
+
+	return set;
+}
+
+struct razor_set *
+razor_set_open(const char *filename)
+{
+	struct razor_set *set;
+	struct razor_set_section *s;
+	struct stat stat;
+	struct array *array;
+	int fd;
+
+	set = zalloc(sizeof *set);
+	fd = open(filename, O_RDONLY);
+	if (fstat(fd, &stat) < 0)
+		return NULL;
+	set->header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	if (set->header == MAP_FAILED) {
+		free(set);
+		return NULL;
+	}
+
+	for (s = set->header->sections; ~s->type; s++) {
+		if (s->type >= ARRAY_SIZE(razor_sections))
+			continue;
+		if (s->type != razor_sections[s->type].type)
+			continue;
+		array = (void *) set + razor_sections[s->type].offset;
+		array->data = (void *) set->header + s->offset;
+		array->size = s->size;
+		array->alloc = s->size;
+	}
+	close(fd);
+
+	return set;
+}
+
+void
+razor_set_open_details(struct razor_set *set, const char *filename)
+{
+	struct razor_set_section *s;
+	struct stat stat;
+	struct array *array;
+	int fd;
+
+	fd = open(filename, O_RDONLY);
+	if (fstat(fd, &stat) < 0)
+		return;
+	set->details_header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	if (set->details_header == MAP_FAILED)
+		return;
+
+	for (s = set->details_header->sections; ~s->type; s++) {
+		if (s->type >= ARRAY_SIZE(razor_details_sections))
+			continue;
+		if (s->type != razor_details_sections[s->type].type)
+			continue;
+		array = (void *) set + razor_details_sections[s->type].offset;
+		array->data = (void *) set->details_header + s->offset;
+		array->size = s->size;
+		array->alloc = s->size;
+	}
+	close(fd);
+}
+
+void
+razor_set_open_files(struct razor_set *set, const char *filename)
+{
+	struct razor_set_section *s;
+	struct stat stat;
+	struct array *array;
+	int fd;
+
+	fd = open(filename, O_RDONLY);
+	if (fstat(fd, &stat) < 0)
+		return;
+	set->files_header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	if (set->files_header == MAP_FAILED)
+		return;
+
+	for (s = set->files_header->sections; ~s->type; s++) {
+		if (s->type >= ARRAY_SIZE(razor_files_sections))
+			continue;
+		if (s->type != razor_files_sections[s->type].type)
+			continue;
+		array = (void *) set + razor_files_sections[s->type].offset;
+		array->data = (void *) set->files_header + s->offset;
+		array->size = s->size;
+		array->alloc = s->size;
+	}
+	close(fd);
+}
+
+void
+razor_set_destroy(struct razor_set *set)
+{
+	unsigned int size;
+	struct array *a;
+	int i;
+
+	if (set->header) {
+		for (i = 0; set->header->sections[i].type; i++)
+			;
+		size = set->header->sections[i].type;
+		munmap(set->header, size);
+	} else {
+		for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
+			a = (void *) set + razor_sections[i].offset;
+			free(a->data);
+		}
+	}
+
+	if (set->details_header) {
+		for (i = 0; set->details_header->sections[i].type; i++)
+			;
+		size = set->details_header->sections[i].type;
+		munmap(set->details_header, size);
+	} else {
+		for (i = 0; i < ARRAY_SIZE(razor_details_sections); i++) {
+			a = (void *) set + razor_details_sections[i].offset;
+			free(a->data);
+		}
+	}
+
+	if (set->files_header) {
+		for (i = 0; set->files_header->sections[i].type; i++)
+			;
+		size = set->files_header->sections[i].type;
+		munmap(set->files_header, size);
+	} else {
+		for (i = 0; i < ARRAY_SIZE(razor_files_sections); i++) {
+			a = (void *) set + razor_files_sections[i].offset;
+			free(a->data);
+		}
+	}
+
+	free(set);
+}
+
+static int
+razor_set_write_sections_to_fd(struct razor_set *set, int fd, int magic,
+			       struct razor_set_section *sections,
+			       size_t array_size)
+{
+	char data[4096];
+	struct razor_set_header *header = (struct razor_set_header *) data;
+	struct array *a;
+	uint32_t offset;
+	int i;
+
+	memset(data, 0, sizeof data);
+	header->magic = magic;
+	header->version = RAZOR_VERSION;
+	offset = sizeof data;
+
+	for (i = 0; i < array_size; i++) {
+		if (sections[i].type != i)
+			continue;
+		a = (void *) set + sections[i].offset;
+		header->sections[i].type = i;
+		header->sections[i].offset = offset;
+		header->sections[i].size = a->size;
+		offset += ALIGN(a->size, 4096);
+	}
+
+	header->sections[i].type = ~0;
+	header->sections[i].offset = 0;
+	header->sections[i].size = 0;
+
+	razor_write(fd, data, sizeof data);
+	memset(data, 0, sizeof data);
+	for (i = 0; i < array_size; i++) {
+		if (sections[i].type != i)
+			continue;
+		a = (void *) set + sections[i].offset;
+		razor_write(fd, a->data, a->size);
+		razor_write(fd, data, ALIGN(a->size, 4096) - a->size);
+	}
+
+	return 0;
+}
+
+int
+razor_set_write_to_fd(struct razor_set *set, int fd,
+		      enum razor_repo_file_type type)
+{
+	switch (type) {
+	case RAZOR_REPO_FILE_MAIN:
+		return razor_set_write_sections_to_fd(set, fd, RAZOR_MAGIC,
+						      razor_sections,
+						      ARRAY_SIZE(razor_sections));
+
+	case RAZOR_REPO_FILE_DETAILS:
+		return razor_set_write_sections_to_fd(set, fd, RAZOR_DETAILS_MAGIC,
+						      razor_details_sections,
+						      ARRAY_SIZE(razor_details_sections));
+	case RAZOR_REPO_FILE_FILES:
+		return razor_set_write_sections_to_fd(set, fd, RAZOR_FILES_MAGIC,
+						      razor_files_sections,
+						      ARRAY_SIZE(razor_files_sections));
+	default:
+		return -1;
+	}
+}
+
+int
+razor_set_write(struct razor_set *set, const char *filename,
+		enum razor_repo_file_type type)
+{
+	int fd, status;
+
+	fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, 0666);
+	if (fd < 0)
+		return -1;
+
+	status = razor_set_write_to_fd(set, fd, type);
+	if (status) {
+	    close(fd);
+	    return status;
+	}
+
+	return close(fd);
+}
+void
+razor_build_evr(char *evr_buf, int size, const char *epoch,
+		const char *version, const char *release)
+{
+	int len;
+
+	if (!version || !*version) {
+		*evr_buf = '\0';
+		return;
+	}
+
+	if (epoch && *epoch && strcmp(epoch, "0") != 0) {
+		len = snprintf(evr_buf, size, "%s:", epoch);
+		evr_buf += len;
+		size -= len;
+	}
+	len = snprintf(evr_buf, size, "%s", version);
+	evr_buf += len;
+	size -= len;
+	if (release && *release)
+		snprintf(evr_buf, size, "-%s", release);
+}
+
+int
+razor_versioncmp(const char *s1, const char *s2)
+{
+	const char *p1, *p2;
+	long n1, n2;
+	int res;
+
+	n1 = strtol(s1, (char **) &p1, 10);
+	n2 = strtol(s2, (char **) &p2, 10);
+
+	/* Epoch; if one but not the other has an epoch set, default
+	 * the epoch-less version to 0. */
+	res = (*p1 == ':') - (*p2 == ':');
+	if (res < 0) {
+		n1 = 0;
+		p1 = s1;
+		p2++;
+	} else if (res > 0) {
+		p1++;
+		n2 = 0;
+		p2 = s2;
+	}
+
+	if (n1 != n2)
+		return n1 - n2;
+	while (*p1 && *p2) {
+		if (*p1 != *p2)
+			return *p1 - *p2;
+		p1++;
+		p2++;
+		if (isdigit(*p1) && isdigit(*p2))
+			return razor_versioncmp(p1, p2);
+	}
+
+	return *p1 - *p2;
+}
+
+struct razor_package *
+razor_set_get_package(struct razor_set *set, const char *package)
+{
+	struct razor_package_iterator *pi;
+	struct razor_package *p;
+	const char *name, *version, *arch;
+
+	pi = razor_package_iterator_create(set);
+	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
+		if (strcmp(package, name) == 0)
+			break;
+	}
+	razor_package_iterator_destroy(pi);
+
+	return p;
+}
+
+void
+razor_package_get_details(struct razor_set *set, struct razor_package *package,
+			  const char **summary, const char **description,
+			  const char **url, const char **license)
+{
+	const char *pool = set->details_string_pool.data;
+
+	*summary = &pool[package->summary];
+	*description = &pool[package->description];
+	*url = &pool[package->url];
+	*license = &pool[package->license];
+}
+
+struct razor_entry *
+razor_set_find_entry(struct razor_set *set,
+		     struct razor_entry *dir, const char *pattern)
+{
+	struct razor_entry *e;
+	const char *n, *pool = set->string_pool.data;
+	int len;
+
+	e = (struct razor_entry *) set->files.data + dir->start;
+	do {
+		n = pool + e->name;
+		if (strcmp(pattern + 1, n) == 0)
+			return e;
+		len = strlen(n);
+		if (e->start != 0 && strncmp(pattern + 1, n, len) == 0 &&
+		    pattern[len + 1] == '/') {
+			return razor_set_find_entry(set, e, pattern + len + 1);
+		}
+	} while (!((e++)->flags & RAZOR_ENTRY_LAST));
+
+	return NULL;
+}
+
+static void
+list_dir(struct razor_set *set, struct razor_entry *dir,
+	 char *prefix, const char *pattern)
+{
+	struct razor_entry *e;
+	const char *n, *pool = set->string_pool.data;
+
+	e = (struct razor_entry *) set->files.data + dir->start;
+	do {
+		n = pool + e->name;
+		if (pattern && pattern[0] && fnmatch(pattern, n, 0) != 0)
+			continue;
+		printf("%s/%s\n", prefix, n);
+		if (e->start) {
+			char *sub = prefix + strlen (prefix);
+			*sub = '/';
+			strcpy (sub + 1, n);
+			list_dir(set, e, prefix, pattern);
+			*sub = '\0';
+		}
+	} while (!((e++)->flags & RAZOR_ENTRY_LAST));
+}
+
+void
+razor_set_list_files(struct razor_set *set, const char *pattern)
+{
+	struct razor_entry *e;
+	char buffer[512], *p, *base;
+
+	if (pattern == NULL || !strcmp (pattern, "/")) {
+		buffer[0] = '\0';
+		list_dir(set, set->files.data, buffer, NULL);
+		return;
+	}
+
+	strcpy(buffer, pattern);
+	e = razor_set_find_entry(set, set->files.data, buffer);
+	if (e && e->start > 0) {
+		base = NULL;
+	} else {
+		p = strrchr(buffer, '/');
+		if (p) {
+			*p = '\0';
+			base = p + 1;
+		} else {
+			base = NULL;
+		}
+	}
+	e = razor_set_find_entry(set, set->files.data, buffer);
+	if (e->start != 0)
+		list_dir(set, e, buffer, base);
+}
+
+static struct list *
+list_package_files(struct razor_set *set, struct list *r,
+		   struct razor_entry *dir, uint32_t end,
+		   char *prefix)
+{
+	struct razor_entry *e, *f, *entries;
+	uint32_t next, file;
+	char *pool;
+	int len;
+
+	entries = (struct razor_entry *) set->files.data;
+	pool = set->string_pool.data;
+
+	e = entries + dir->start;
+	do {
+		if (entries + r->data == e) {
+			printf("%s/%s\n", prefix, pool + e->name);
+			r = list_next(r);
+			if (!r)
+				return NULL;
+			if (r->data >= end)
+				return r;
+		}
+	} while (!((e++)->flags & RAZOR_ENTRY_LAST));
+
+	e = entries + dir->start;
+	do {
+		if (e->start == 0)
+			continue;
+
+		if (e->flags & RAZOR_ENTRY_LAST)
+			next = end;
+		else {
+			f = e + 1;
+			while (f->start == 0 && !(f->flags & RAZOR_ENTRY_LAST))
+				f++;
+			if (f->start == 0)
+				next = end;
+			else
+				next = f->start;
+		}
+
+		file = r->data;
+		if (e->start <= file && file < next) {
+			len = strlen(prefix);
+			prefix[len] = '/';
+			strcpy(prefix + len + 1, pool + e->name);
+			r = list_package_files(set, r, e, next, prefix);
+			prefix[len] = '\0';
+		}
+	} while (!((e++)->flags & RAZOR_ENTRY_LAST) && r != NULL);
+
+	return r;
+}
+
+void
+razor_set_list_package_files(struct razor_set *set, const char *name)
+{
+	struct razor_package *package;
+	struct list *r;
+	uint32_t end;
+	char buffer[512];
+
+	package = razor_set_get_package(set, name);
+
+	r = list_first(&package->files, &set->file_pool);
+	end = set->files.size / sizeof (struct razor_entry);
+	buffer[0] = '\0';
+	list_package_files(set, r, set->files.data, end, buffer);
+}
+
+/* The diff order matters.  We should sort the packages so that a
+ * REMOVE of a package comes before the INSTALL, and so that all
+ * requires for a package have been installed before the package.
+ **/
+
+void
+razor_set_diff(struct razor_set *set, struct razor_set *upstream,
+	       razor_package_callback_t callback, void *data)
+{
+ 	struct razor_package_iterator *pi1, *pi2;
+ 	struct razor_package *p1, *p2;
+	const char *name1, *name2, *version1, *version2, *arch1, *arch2;
+	int res;
+
+	pi1 = razor_package_iterator_create(set);
+	pi2 = razor_package_iterator_create(upstream);
+
+	razor_package_iterator_next(pi1, &p1, &name1, &version1, &arch1);
+	razor_package_iterator_next(pi2, &p2, &name2, &version2, &arch2);
+
+	while (p1 || p2) {
+		if (p1 && p2) {
+			res = strcmp(name1, name2);
+			if (res == 0)
+				res = razor_versioncmp(version1, version2);
+		} else {
+			res = 0;
+		}
+
+		if (p2 == NULL || res < 0)
+			callback(name1, version1, NULL, arch1, data);
+		else if (p1 == NULL || res > 0)
+			callback(name2, NULL, version2, arch2, data);
+
+		if (p1 != NULL && res <= 0)
+			razor_package_iterator_next(pi1, &p1,
+						    &name1, &version1, &arch1);
+		if (p2 != NULL && res >= 0)
+			razor_package_iterator_next(pi2, &p2,
+						    &name2, &version2, &arch2);
+	}
+
+	razor_package_iterator_destroy(pi1);
+	razor_package_iterator_destroy(pi2);
+}
diff --git a/librazor/razor.h b/librazor/razor.h
new file mode 100644
index 0000000..8429912
--- /dev/null
+++ b/librazor/razor.h
@@ -0,0 +1,218 @@
+/*
+ * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
+ * Copyright (C) 2008  Red Hat, Inc
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#ifndef _RAZOR_H_
+#define _RAZOR_H_
+
+#define ARRAY_SIZE(a) (sizeof(a) / sizeof((a)[0]))
+
+struct razor_set;
+struct razor_package;
+struct razor_property;
+
+enum razor_repo_file_type {
+	RAZOR_REPO_FILE_MAIN,
+	RAZOR_REPO_FILE_DETAILS,
+	RAZOR_REPO_FILE_FILES
+};
+
+enum razor_property_flags {
+	RAZOR_PROPERTY_LESS		= 1 << 0,
+	RAZOR_PROPERTY_GREATER		= 1 << 1,
+	RAZOR_PROPERTY_EQUAL		= 1 << 2,
+	RAZOR_PROPERTY_RELATION_MASK	=
+		RAZOR_PROPERTY_LESS |
+		RAZOR_PROPERTY_GREATER |
+		RAZOR_PROPERTY_EQUAL,
+
+	RAZOR_PROPERTY_REQUIRES		= 0 << 3,
+	RAZOR_PROPERTY_PROVIDES		= 1 << 3,
+	RAZOR_PROPERTY_CONFLICTS	= 2 << 3,
+	RAZOR_PROPERTY_OBSOLETES	= 3 << 3,
+	RAZOR_PROPERTY_TYPE_MASK	= 3 << 3,
+		
+	RAZOR_PROPERTY_PRE		= 1 << 5,
+	RAZOR_PROPERTY_POST		= 1 << 6,
+	RAZOR_PROPERTY_PREUN		= 1 << 7,
+	RAZOR_PROPERTY_POSTUN		= 1 << 8
+};
+
+const char *
+razor_property_relation_to_string(struct razor_property *p);
+const char *
+razor_property_type_to_string(struct razor_property *p);
+
+struct razor_set *razor_set_create(void);
+struct razor_set *razor_set_open(const char *filename);
+void razor_set_destroy(struct razor_set *set);
+int razor_set_write_to_fd(struct razor_set *set, int fd,
+			  enum razor_repo_file_type type);
+int razor_set_write(struct razor_set *set, const char *filename,
+		    enum razor_repo_file_type type);
+
+void razor_set_open_details(struct razor_set *set, const char *filename);
+void razor_set_open_files(struct razor_set *set, const char *filename);
+
+struct razor_package *
+razor_set_get_package(struct razor_set *set, const char *package);
+
+void
+razor_package_get_details(struct razor_set *set, struct razor_package *package,
+			  const char **summary, const char **description,
+			  const char **url, const char **license);
+
+struct razor_package_iterator;
+struct razor_package_iterator *
+razor_package_iterator_create(struct razor_set *set);
+struct razor_package_iterator *
+razor_package_iterator_create_for_property(struct razor_set *set,
+					   struct razor_property *property);
+struct razor_package_iterator *
+razor_package_iterator_create_for_file(struct razor_set *set,
+				       const char *filename);
+
+int razor_package_iterator_next(struct razor_package_iterator *pi,
+				struct razor_package **package,
+				const char **name,
+				const char **version,
+				const char **arch);
+void razor_package_iterator_destroy(struct razor_package_iterator *pi);
+
+struct razor_package_query *
+razor_package_query_create(struct razor_set *set);
+void
+razor_package_query_add_package(struct razor_package_query *pq,
+				struct razor_package *p);
+void
+razor_package_query_add_iterator(struct razor_package_query *pq,
+				 struct razor_package_iterator *pi);
+struct razor_package_iterator *
+razor_package_query_finish(struct razor_package_query *pq);
+
+struct razor_property_iterator;
+struct razor_property_iterator *
+razor_property_iterator_create(struct razor_set *set,
+			       struct razor_package *package);
+int razor_property_iterator_next(struct razor_property_iterator *pi,
+				 struct razor_property **property,
+				 const char **name,
+				 uint32_t *flags,
+				 const char **version);
+void
+razor_property_iterator_destroy(struct razor_property_iterator *pi);
+
+void razor_set_list_files(struct razor_set *set, const char *prefix);
+void razor_set_list_package_files(struct razor_set *set, const char *name);
+
+void razor_set_list_unsatisfied(struct razor_set *set);
+
+typedef void (*razor_package_callback_t)(const char *name,
+					 const char *old_version,
+					 const char *new_version,
+					 const char *arch,
+					 void *data);
+void
+razor_set_diff(struct razor_set *set, struct razor_set *upstream,
+	       razor_package_callback_t callback, void *data);
+
+/* Package transactions */
+
+struct razor_transaction *
+razor_transaction_create(struct razor_set *system, struct razor_set *upstream);
+void razor_transaction_install_package(struct razor_transaction *transaction,
+				       struct razor_package *package);
+void razor_transaction_remove_package(struct razor_transaction *transaction,
+				      struct razor_package *package);
+void razor_transaction_update_package(struct razor_transaction *trans,
+				      struct razor_package *package);
+void razor_transaction_update_all(struct razor_transaction *transaction);
+int razor_transaction_resolve(struct razor_transaction *trans);
+int razor_transaction_describe(struct razor_transaction *trans);
+struct razor_set *razor_transaction_finish(struct razor_transaction *trans);
+void razor_transaction_destroy(struct razor_transaction *trans);
+
+/* Temporary helper for test suite. */
+int razor_transaction_unsatisfied_property(struct razor_transaction *trans,
+					   const char *name,
+					   uint32_t flags,
+					   const char *version);
+
+/* Importer interface; for building a razor set from external sources,
+ * like yum, rpmdb or razor package files. */
+
+struct razor_importer;
+struct razor_rpm;
+
+struct razor_importer *razor_importer_new(void);
+void razor_importer_destroy(struct razor_importer *importer);
+void razor_importer_begin_package(struct razor_importer *importer,
+				  const char *name,
+				  const char *version,
+				  const char *arch);
+void razor_importer_add_details(struct razor_importer *importer,
+				const char *summary,
+				const char *description,
+				const char *url,
+				const char *license);
+void razor_importer_add_property(struct razor_importer *importer,
+				 const char *name,
+				 uint32_t flags,
+				 const char *version);
+void razor_importer_add_file(struct razor_importer *importer,
+			     const char *name);
+void razor_importer_finish_package(struct razor_importer *importer);
+
+int razor_importer_add_rpm(struct razor_importer *importer,
+			   struct razor_rpm *rpm);
+
+struct razor_set *razor_importer_finish(struct razor_importer *importer);
+
+void razor_build_evr(char *evr_buf, int size, const char *epoch,
+		     const char *version, const char *release);
+int razor_versioncmp(const char *s1, const char *s2);
+
+struct razor_set *razor_set_create_from_yum(void);
+struct razor_set *razor_set_create_from_rpmdb(void);
+
+/* RPM functions */
+
+struct razor_rpm *razor_rpm_open(const char *filename);
+int razor_rpm_install(struct razor_rpm *rpm, const char *root);
+int razor_rpm_close(struct razor_rpm *rpm);
+
+
+/* Razor root functions. The root data struct encapsulates filesystem
+ * conventions and the locking protocol. */
+
+struct razor_root;
+#define RAZOR_ROOT_OPEN_WRITE 0x01
+
+int razor_root_create(const char *root);
+struct razor_root *razor_root_open(const char *root, int flags);
+struct razor_set *razor_root_open_read_only(const char *root);
+struct razor_transaction *
+razor_root_create_transaction(struct razor_root *image,
+			      struct razor_set *upstream);
+int razor_root_close(struct razor_root *image);
+void razor_root_update(struct razor_root *image, struct razor_set *next);
+int razor_root_commit(struct razor_root *image);
+void razor_root_diff(struct razor_root *root,
+		     razor_package_callback_t callback, void *data);
+
+#endif /* _RAZOR_H_ */
diff --git a/librazor/root.c b/librazor/root.c
new file mode 100644
index 0000000..dc3b230
--- /dev/null
+++ b/librazor/root.c
@@ -0,0 +1,168 @@
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <sys/stat.h>
+#include <dirent.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include "razor.h"
+#include "razor-internal.h"
+
+static const char system_repo_filename[] = "system.repo";
+static const char next_repo_filename[] = "system-next.repo";
+static const char razor_root_path[] = "/var/lib/razor";
+
+struct razor_root {
+	struct razor_set *system;
+	struct razor_set *next;
+	int fd;
+	char path[PATH_MAX];
+	char new_path[PATH_MAX];
+};
+
+int
+razor_root_create(const char *root)
+{
+	struct stat buf;
+	struct razor_set *set;
+	char path[PATH_MAX];
+
+	if (stat(root, &buf) < 0) {
+		if (mkdir(root, 0777) < 0) {
+			fprintf(stderr,
+				"could not create install root \"%s\"\n",
+				root);
+			return -1;
+		}
+		fprintf(stderr, "created install root \"%s\"\n", root);
+	} else if (!S_ISDIR(buf.st_mode)) {
+		fprintf(stderr,
+			"install root \"%s\" exists, but is not a directory\n",
+			root);
+		return -1;
+	}
+
+	snprintf(path, sizeof path, "%s/%s",
+		 razor_root_path, system_repo_filename);
+	if (razor_create_dir(root, path) < 0) {
+		fprintf(stderr, "could not create %s%s\n",
+			root, razor_root_path);
+		return -1;
+	}
+
+	set = razor_set_create();
+	snprintf(path, sizeof path, "%s%s/%s",
+		 root, razor_root_path, system_repo_filename);
+	if (stat(path, &buf) == 0) {
+		fprintf(stderr,
+			"a razor install root is already initialized\n");
+		return -1;
+	}
+	if (razor_set_write(set, path, RAZOR_REPO_FILE_MAIN) < 0) {
+		fprintf(stderr, "could not write initial package set\n");
+		return -1;
+	}
+	razor_set_destroy(set);
+
+	return 0;
+}
+
+struct razor_root *
+razor_root_open(const char *root, int flags)
+{
+	struct razor_root *image;
+
+	image = malloc(sizeof *image);
+	if (image == NULL)
+		return NULL;
+
+	/* Create the new next repo file up front to ensure exclusive
+	 * access. */
+	snprintf(image->new_path, sizeof image->new_path,
+		 "%s%s/%s", root, razor_root_path, next_repo_filename);
+	image->fd = open(image->new_path,
+			 O_CREAT | O_WRONLY | O_TRUNC | O_EXCL, 0666);
+	if (image->fd < 0) {
+		fprintf(stderr, "failed to get lock file, "
+			"maybe previous operation crashed?\n");
+
+		/* FIXME: Use fcntl advisory locking on the system
+		 * package set file to figure out whether previous
+		 * operation crashed or is still in progress. */
+
+		free(image);
+		return NULL;
+	}
+
+	snprintf(image->path, sizeof image->path,
+		 "%s%s/%s", root, razor_root_path, system_repo_filename);
+	image->system = razor_set_open(image->path);
+	if (image->system == NULL) {
+		unlink(image->new_path);
+		close(image->fd);
+		free(image);
+		return NULL;
+	}
+
+	return image;
+}
+
+struct razor_set *
+razor_root_open_read_only(const char *root)
+{
+	char path[PATH_MAX];
+
+	snprintf(path, sizeof path, "%s%s/%s",
+		 root, razor_root_path, system_repo_filename);
+
+	return razor_set_open(path);
+}
+
+struct razor_transaction *
+razor_root_create_transaction(struct razor_root *image,
+			      struct razor_set *upstream)
+{
+	/* FIXME: This should take a number of upstream repos. */
+	return razor_transaction_create(image->system, upstream);
+}
+
+int
+razor_root_close(struct razor_root *image)
+{
+	unlink(image->new_path);
+	close(image->fd);
+	free(image);
+
+	return 0;
+}
+
+void
+razor_root_update(struct razor_root *root, struct razor_set *next)
+{
+	razor_set_write_to_fd(next, root->fd, RAZOR_REPO_FILE_MAIN);
+	root->next = next;
+
+	/* Sync the new repo file so the new package set is on disk
+	 * before we start upgrading. */
+	fsync(root->fd);
+	printf("wrote %s\n", root->new_path);
+}
+
+int
+razor_root_commit(struct razor_root *image)
+{
+	/* Make it so. */
+	rename(image->new_path, image->path);
+	printf("renamed %s to %s\n", image->new_path, image->path);
+	close(image->fd);
+	free(image);
+
+	return 0;
+}
+
+void
+razor_root_diff(struct razor_root *root,
+		razor_package_callback_t callback, void *data)
+{
+	return razor_set_diff(root->system, root->next, callback, data);
+}
diff --git a/librazor/rpm.c b/librazor/rpm.c
new file mode 100644
index 0000000..3f572c4
--- /dev/null
+++ b/librazor/rpm.c
@@ -0,0 +1,828 @@
+/*
+ * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
+ * Copyright (C) 2008  Red Hat, Inc
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include <stdio.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <fcntl.h>
+#include <dirent.h>
+#include <unistd.h>
+#include <arpa/inet.h>
+#include <zlib.h>
+
+#include "razor.h"
+#include "razor-internal.h"
+
+#define	RPM_LEAD_SIZE 96
+
+enum {
+    PIPE	=  1,	/*!< pipe/fifo */
+    CDEV	=  2,	/*!< character device */
+    XDIR	=  4,	/*!< directory */
+    BDEV	=  6,	/*!< block device */
+    REG		=  8,	/*!< regular file */
+    LINK	= 10,	/*!< hard link */
+    SOCK	= 12	/*!< socket */
+};
+
+enum {
+    RPMSENSE_LESS		= 1 << 1,
+    RPMSENSE_GREATER		= 1 << 2,
+    RPMSENSE_EQUAL		= 1 << 3,
+    RPMSENSE_PREREQ		= 1 << 6,
+    RPMSENSE_SCRIPT_PRE		= 1 << 9,
+    RPMSENSE_SCRIPT_POST	= 1 << 10,
+    RPMSENSE_SCRIPT_PREUN	= 1 << 11,
+    RPMSENSE_SCRIPT_POSTUN	= 1 << 12,
+};
+
+enum {
+    RPMTAG_NAME  		= 1000,	/* s */
+    RPMTAG_VERSION		= 1001,	/* s */
+    RPMTAG_RELEASE		= 1002,	/* s */
+    RPMTAG_EPOCH   		= 1003,	/* i */
+    RPMTAG_SUMMARY		= 1004,	/* s{} */
+    RPMTAG_DESCRIPTION		= 1005,	/* s{} */
+    RPMTAG_BUILDTIME		= 1006,	/* i */
+    RPMTAG_BUILDHOST		= 1007,	/* s */
+    RPMTAG_INSTALLTIME		= 1008,	/* i */
+    RPMTAG_SIZE			= 1009,	/* i */
+    RPMTAG_DISTRIBUTION		= 1010,	/* s */
+    RPMTAG_VENDOR		= 1011,	/* s */
+    RPMTAG_GIF			= 1012,	/* x */
+    RPMTAG_XPM			= 1013,	/* x */
+    RPMTAG_LICENSE		= 1014,	/* s */
+    RPMTAG_PACKAGER		= 1015,	/* s */
+    RPMTAG_GROUP		= 1016,	/* s{} */
+    RPMTAG_CHANGELOG		= 1017, /*!< s[] internal */
+    RPMTAG_SOURCE		= 1018,	/* s[] */
+    RPMTAG_PATCH		= 1019,	/* s[] */
+    RPMTAG_URL			= 1020,	/* s */
+    RPMTAG_OS			= 1021,	/* s legacy used int */
+    RPMTAG_ARCH			= 1022,	/* s legacy used int */
+    RPMTAG_PREIN		= 1023,	/* s */
+    RPMTAG_POSTIN		= 1024,	/* s */
+    RPMTAG_PREUN		= 1025,	/* s */
+    RPMTAG_POSTUN		= 1026,	/* s */
+    RPMTAG_OLDFILENAMES		= 1027, /* s[] obsolete */
+    RPMTAG_FILESIZES		= 1028,	/* i */
+    RPMTAG_FILESTATES		= 1029, /* c */
+    RPMTAG_FILEMODES		= 1030,	/* h */
+    RPMTAG_FILEUIDS		= 1031, /*!< internal */
+    RPMTAG_FILEGIDS		= 1032, /*!< internal */
+    RPMTAG_FILERDEVS		= 1033,	/* h */
+    RPMTAG_FILEMTIMES		= 1034, /* i */
+    RPMTAG_FILEMD5S		= 1035,	/* s[] */
+    RPMTAG_FILELINKTOS		= 1036,	/* s[] */
+    RPMTAG_FILEFLAGS		= 1037,	/* i */
+    RPMTAG_ROOT			= 1038, /*!< internal - obsolete */
+    RPMTAG_FILEUSERNAME		= 1039,	/* s[] */
+    RPMTAG_FILEGROUPNAME	= 1040,	/* s[] */
+    RPMTAG_EXCLUDE		= 1041, /*!< internal - obsolete */
+    RPMTAG_EXCLUSIVE		= 1042, /*!< internal - obsolete */
+    RPMTAG_ICON			= 1043,
+    RPMTAG_SOURCERPM		= 1044,	/* s */
+    RPMTAG_FILEVERIFYFLAGS	= 1045,	/* i */
+    RPMTAG_ARCHIVESIZE		= 1046,	/* i */
+    RPMTAG_PROVIDENAME		= 1047,	/* s[] */
+    RPMTAG_REQUIREFLAGS		= 1048,	/* i */
+    RPMTAG_REQUIRENAME		= 1049,	/* s[] */
+    RPMTAG_REQUIREVERSION	= 1050,	/* s[] */
+    RPMTAG_NOSOURCE		= 1051, /*!< internal */
+    RPMTAG_NOPATCH		= 1052, /*!< internal */
+    RPMTAG_CONFLICTFLAGS	= 1053, /* i */
+    RPMTAG_CONFLICTNAME		= 1054,	/* s[] */
+    RPMTAG_CONFLICTVERSION	= 1055,	/* s[] */
+    RPMTAG_DEFAULTPREFIX	= 1056, /*!< internal - deprecated */
+    RPMTAG_BUILDROOT		= 1057, /*!< internal */
+    RPMTAG_INSTALLPREFIX	= 1058, /*!< internal - deprecated */
+    RPMTAG_EXCLUDEARCH		= 1059,
+    RPMTAG_EXCLUDEOS		= 1060,
+    RPMTAG_EXCLUSIVEARCH	= 1061,
+    RPMTAG_EXCLUSIVEOS		= 1062,
+    RPMTAG_AUTOREQPROV		= 1063, /*!< internal */
+    RPMTAG_RPMVERSION		= 1064,	/* s */
+    RPMTAG_TRIGGERSCRIPTS	= 1065,	/* s[] */
+    RPMTAG_TRIGGERNAME		= 1066,	/* s[] */
+    RPMTAG_TRIGGERVERSION	= 1067,	/* s[] */
+    RPMTAG_TRIGGERFLAGS		= 1068,	/* i */
+    RPMTAG_TRIGGERINDEX		= 1069,	/* i */
+    RPMTAG_VERIFYSCRIPT		= 1079,	/* s */
+    RPMTAG_CHANGELOGTIME	= 1080,	/* i */
+    RPMTAG_CHANGELOGNAME	= 1081,	/* s[] */
+    RPMTAG_CHANGELOGTEXT	= 1082,	/* s[] */
+    RPMTAG_BROKENMD5		= 1083, /*!< internal - obsolete */
+    RPMTAG_PREREQ		= 1084, /*!< internal */
+    RPMTAG_PREINPROG		= 1085,	/* s */
+    RPMTAG_POSTINPROG		= 1086,	/* s */
+    RPMTAG_PREUNPROG		= 1087,	/* s */
+    RPMTAG_POSTUNPROG		= 1088,	/* s */
+    RPMTAG_BUILDARCHS		= 1089,
+    RPMTAG_OBSOLETENAME		= 1090,	/* s[] */
+    RPMTAG_VERIFYSCRIPTPROG	= 1091,	/* s */
+    RPMTAG_TRIGGERSCRIPTPROG	= 1092,	/* s */
+    RPMTAG_DOCDIR		= 1093, /*!< internal */
+    RPMTAG_COOKIE		= 1094,	/* s */
+    RPMTAG_FILEDEVICES		= 1095,	/* i */
+    RPMTAG_FILEINODES		= 1096,	/* i */
+    RPMTAG_FILELANGS		= 1097,	/* s[] */
+    RPMTAG_PREFIXES		= 1098,	/* s[] */
+    RPMTAG_INSTPREFIXES		= 1099,	/* s[] */
+    RPMTAG_TRIGGERIN		= 1100, /*!< internal */
+    RPMTAG_TRIGGERUN		= 1101, /*!< internal */
+    RPMTAG_TRIGGERPOSTUN	= 1102, /*!< internal */
+    RPMTAG_AUTOREQ		= 1103, /*!< internal */
+    RPMTAG_AUTOPROV		= 1104, /*!< internal */
+    RPMTAG_CAPABILITY		= 1105, /*!< internal - obsolete */
+    RPMTAG_SOURCEPACKAGE	= 1106, /*!< i src.rpm header marker */
+    RPMTAG_OLDORIGFILENAMES	= 1107, /*!< internal - obsolete */
+    RPMTAG_BUILDPREREQ		= 1108, /*!< internal */
+    RPMTAG_BUILDREQUIRES	= 1109, /*!< internal */
+    RPMTAG_BUILDCONFLICTS	= 1110, /*!< internal */
+    RPMTAG_BUILDMACROS		= 1111, /*!< internal - unused */
+    RPMTAG_PROVIDEFLAGS		= 1112,	/* i */
+    RPMTAG_PROVIDEVERSION	= 1113,	/* s[] */
+    RPMTAG_OBSOLETEFLAGS	= 1114,	/* i */
+    RPMTAG_OBSOLETEVERSION	= 1115,	/* s[] */
+    RPMTAG_DIRINDEXES		= 1116,	/* i */
+    RPMTAG_BASENAMES		= 1117,	/* s[] */
+    RPMTAG_DIRNAMES		= 1118,	/* s[] */
+    RPMTAG_ORIGDIRINDEXES	= 1119, /*!< internal */
+    RPMTAG_ORIGBASENAMES	= 1120, /*!< internal */
+    RPMTAG_ORIGDIRNAMES		= 1121, /*!< internal */
+    RPMTAG_OPTFLAGS		= 1122,	/* s */
+    RPMTAG_DISTURL		= 1123,	/* s */
+    RPMTAG_PAYLOADFORMAT	= 1124,	/* s */
+    RPMTAG_PAYLOADCOMPRESSOR	= 1125,	/* s */
+    RPMTAG_PAYLOADFLAGS		= 1126,	/* s */
+    RPMTAG_INSTALLCOLOR		= 1127, /*!< i transaction color when installed */
+    RPMTAG_INSTALLTID		= 1128,	/* i */
+    RPMTAG_REMOVETID		= 1129,	/* i */
+    RPMTAG_SHA1RHN		= 1130, /*!< internal - obsolete */
+    RPMTAG_RHNPLATFORM		= 1131,	/* s */
+    RPMTAG_PLATFORM		= 1132,	/* s */
+    RPMTAG_PATCHESNAME		= 1133, /*!< placeholder (SuSE) */
+    RPMTAG_PATCHESFLAGS		= 1134, /*!< placeholder (SuSE) */
+    RPMTAG_PATCHESVERSION	= 1135, /*!< placeholder (SuSE) */
+    RPMTAG_CACHECTIME		= 1136,	/* i */
+    RPMTAG_CACHEPKGPATH		= 1137,	/* s */
+    RPMTAG_CACHEPKGSIZE		= 1138,	/* i */
+    RPMTAG_CACHEPKGMTIME	= 1139,	/* i */
+    RPMTAG_FILECOLORS		= 1140,	/* i */
+    RPMTAG_FILECLASS		= 1141,	/* i */
+    RPMTAG_CLASSDICT		= 1142,	/* s[] */
+    RPMTAG_FILEDEPENDSX		= 1143,	/* i */
+    RPMTAG_FILEDEPENDSN		= 1144,	/* i */
+    RPMTAG_DEPENDSDICT		= 1145,	/* i */
+    RPMTAG_SOURCEPKGID		= 1146,	/* x */
+    RPMTAG_FILECONTEXTS		= 1147,	/* s[] */
+    RPMTAG_FSCONTEXTS		= 1148,	/*!< s[] extension */
+    RPMTAG_RECONTEXTS		= 1149,	/*!< s[] extension */
+    RPMTAG_POLICIES		= 1150,	/*!< s[] selinux *.te policy file. */
+    RPMTAG_PRETRANS		= 1151,	/* s */
+    RPMTAG_POSTTRANS		= 1152,	/* s */
+    RPMTAG_PRETRANSPROG		= 1153,	/* s */
+    RPMTAG_POSTTRANSPROG	= 1154,	/* s */
+    RPMTAG_DISTTAG		= 1155,	/* s */
+    RPMTAG_SUGGESTSNAME		= 1156,	/* s[] extension placeholder */
+    RPMTAG_SUGGESTSVERSION	= 1157,	/* s[] extension placeholder */
+    RPMTAG_SUGGESTSFLAGS	= 1158,	/* i   extension placeholder */
+    RPMTAG_ENHANCESNAME		= 1159,	/* s[] extension placeholder */
+    RPMTAG_ENHANCESVERSION	= 1160,	/* s[] extension placeholder */
+    RPMTAG_ENHANCESFLAGS	= 1161,	/* i   extension placeholder */
+    RPMTAG_PRIORITY		= 1162, /* i   extension placeholder */
+    RPMTAG_CVSID		= 1163, /* s */
+    RPMTAG_TRIGGERPREIN		= 1171, /*!< internal */
+};
+
+struct rpm_header {
+	unsigned char magic[4];
+	unsigned char reserved[4];
+	int nindex;
+	int hsize;
+};
+
+struct rpm_header_index {
+	int tag;
+	int type;
+	int offset;
+	int count;
+};
+
+struct razor_rpm {
+	struct rpm_header *signature;
+	struct rpm_header *header;
+	const char **dirs;
+	const char *pool;
+	void *map;
+	size_t size;
+	void *payload;
+};
+
+static struct rpm_header_index *
+razor_rpm_get_header(struct razor_rpm *rpm, unsigned int tag)
+{
+	struct rpm_header_index *index, *end;
+
+	index = (struct rpm_header_index *) (rpm->header + 1);
+	end = index + ntohl(rpm->header->nindex);
+	while (index < end) {
+		if (ntohl(index->tag) == tag)
+			return index;
+		index++;
+	}
+
+	return NULL;
+}
+
+static const void *
+razor_rpm_get_indirect(struct razor_rpm *rpm,
+		       unsigned int tag, unsigned int *count)
+{
+	struct rpm_header_index *index;
+
+	index = razor_rpm_get_header(rpm, tag);
+	if (index != NULL) {
+		if (count)
+			*count = ntohl(index->count);
+
+		return rpm->pool + ntohl(index->offset);
+	}
+
+	return NULL;
+}
+
+static uint32_t
+rpm_to_razor_flags(uint32_t flags)
+{
+	uint32_t razor_flags;
+
+	razor_flags = 0;
+	if (flags & RPMSENSE_LESS)
+		razor_flags |= RAZOR_PROPERTY_LESS;
+	if (flags & RPMSENSE_EQUAL)
+		razor_flags |= RAZOR_PROPERTY_EQUAL;
+	if (flags & RPMSENSE_GREATER)
+		razor_flags |= RAZOR_PROPERTY_GREATER;
+
+	if (flags & RPMSENSE_SCRIPT_PRE)
+		razor_flags |= RAZOR_PROPERTY_PRE;
+	if (flags & RPMSENSE_SCRIPT_POST)
+		razor_flags |= RAZOR_PROPERTY_POST;
+	if (flags & RPMSENSE_SCRIPT_PREUN)
+		razor_flags |= RAZOR_PROPERTY_PREUN;
+	if (flags & RPMSENSE_SCRIPT_POSTUN)
+		razor_flags |= RAZOR_PROPERTY_POSTUN;
+	
+	return razor_flags;
+}
+
+static void
+import_properties(struct razor_importer *importer, uint32_t type,
+		  struct razor_rpm *rpm,
+		  int name_tag, int version_tag, int flags_tag)
+{
+	const char *name, *version;
+	const uint32_t *flags;
+	uint32_t f;
+	unsigned int i, count;
+
+	name = razor_rpm_get_indirect(rpm, name_tag, &count);
+	if (name == NULL)
+		return;
+
+	flags = razor_rpm_get_indirect(rpm, flags_tag, &count);
+
+	version = razor_rpm_get_indirect(rpm, version_tag, &count);
+	for (i = 0; i < count; i++) {
+		f = rpm_to_razor_flags(ntohl(flags[i]));
+		razor_importer_add_property(importer, name, f | type, version);
+		name += strlen(name) + 1;
+		version += strlen(version) + 1;
+	}
+}
+
+static void
+import_files(struct razor_importer *importer, struct razor_rpm *rpm)
+{
+	const char *name;
+	const uint32_t *index;
+	unsigned int i, count;
+	char buffer[256];
+
+	if (rpm->dirs == NULL)
+		return;
+
+	/* assert: count is the same for all arrays */
+	index = razor_rpm_get_indirect(rpm, RPMTAG_DIRINDEXES, &count);
+	name = razor_rpm_get_indirect(rpm, RPMTAG_BASENAMES, &count);
+	for (i = 0; i < count; i++) {
+		snprintf(buffer, sizeof buffer,
+			 "%s%s", rpm->dirs[ntohl(*index)], name);
+		razor_importer_add_file(importer, buffer);
+		name += strlen(name) + 1;
+		index++;
+	}
+}
+
+struct razor_rpm *
+razor_rpm_open(const char *filename)
+{
+	struct razor_rpm *rpm;
+	struct rpm_header_index *base, *index;
+	struct stat buf;
+	unsigned int count, i, nindex, hsize;
+	const char *name;
+	int fd;
+
+	rpm = malloc(sizeof *rpm);
+	if (rpm == NULL)
+		return NULL;
+	memset(rpm, 0, sizeof *rpm);
+
+	fd = open(filename, O_RDONLY);
+	if (fd < 0) {
+		fprintf(stderr, "couldn't open %s\n", filename);
+		return NULL;
+	}
+
+	if (fstat(fd, &buf) < 0) {
+		fprintf(stderr, "failed to stat %s (%m)\n", filename);
+		return NULL;
+	}
+
+	rpm->size = buf.st_size;
+	rpm->map = mmap(NULL, rpm->size, PROT_READ, MAP_PRIVATE, fd, 0);
+	if (rpm->map == MAP_FAILED) {
+		fprintf(stderr, "couldn't mmap %s\n", filename);
+		return NULL;
+	}
+	close(fd);
+
+	rpm->signature = rpm->map + RPM_LEAD_SIZE;
+	nindex = ntohl(rpm->signature->nindex);
+	hsize = ntohl(rpm->signature->hsize);
+	rpm->header = (void *) (rpm->signature + 1) +
+		ALIGN(nindex * sizeof *index + hsize, 8);
+	nindex = ntohl(rpm->header->nindex);
+	hsize = ntohl(rpm->header->hsize);
+	rpm->payload = (void *) (rpm->header + 1) +
+		nindex * sizeof *index + hsize;
+
+	base = (struct rpm_header_index *) (rpm->header + 1);
+	rpm->pool = (void *) base + nindex * sizeof *index;
+
+	/* Look up dir names now so we can index them directly. */
+	name = razor_rpm_get_indirect(rpm, RPMTAG_DIRNAMES, &count);
+	if (name) {
+		rpm->dirs = calloc(count, sizeof *rpm->dirs);
+		for (i = 0; i < count; i++) {
+			rpm->dirs[i] = name;
+			name += strlen(name) + 1;
+		}
+	} else {
+		name = razor_rpm_get_indirect(rpm, RPMTAG_OLDFILENAMES,
+					      &count);
+		if (name) {
+			fprintf(stderr, "old filenames not supported\n");
+			return NULL;
+		}
+	}
+
+	return rpm;
+}
+
+struct cpio_file_header {
+	char magic[6];
+	char inode[8];
+	char mode[8];
+	char uid[8];
+	char gid[8];
+	char nlink[8];
+	char mtime[8];
+	char filesize[8];
+	char devmajor[8];
+	char devminor[8];
+	char rdevmajor[8];
+	char rdevminor[8];
+	char namesize[8];
+	char checksum[8];
+	char filename[0];
+};
+
+/* gzip flags */
+#define ASCII_FLAG   0x01 /* bit 0 set: file probably ascii text */
+#define HEAD_CRC     0x02 /* bit 1 set: header CRC present */
+#define EXTRA_FIELD  0x04 /* bit 2 set: extra field present */
+#define ORIG_NAME    0x08 /* bit 3 set: original file name present */
+#define COMMENT      0x10 /* bit 4 set: file comment present */
+#define RESERVED     0xE0 /* bits 5..7: reserved */
+
+struct installer {
+	const char *root;
+	struct razor_rpm *rpm;
+	z_stream stream;
+	unsigned char buffer[32768];
+	size_t rest, length;
+};
+
+static int
+installer_inflate(struct installer *installer)
+{
+	size_t length;
+	int err;
+
+	if (installer->rest > sizeof installer->buffer)
+		length = sizeof installer->buffer;
+	else
+		length = installer->rest;
+
+	installer->stream.next_out = installer->buffer;
+	installer->stream.avail_out = length;
+	err = inflate(&installer->stream, Z_SYNC_FLUSH);
+	if (err != Z_OK && err != Z_STREAM_END) {
+		fprintf(stderr, "inflate error: %d (%m)\n", err);
+		return -1;
+	}
+
+	installer->rest -= length;
+	installer->length = length;
+
+	return 0;
+}
+
+static int
+installer_align(struct installer *installer, size_t size)
+{
+	unsigned char buffer[4];
+	int err;
+
+	installer->stream.next_out = buffer;
+	installer->stream.avail_out =
+		(size - installer->stream.total_out) & (size - 1);
+
+	if (installer->stream.avail_out == 0)
+		return 0;
+
+	err = inflate(&installer->stream, Z_SYNC_FLUSH);
+	if (err != Z_OK && err != Z_STREAM_END) {
+		fprintf(stderr, "inflate error: %d (%m)\n", err);
+		return -1;
+	}
+
+	return 0;
+}
+
+static int
+create_path(struct installer *installer, const char *path, unsigned int mode)
+{
+	char buffer[PATH_MAX];
+	struct stat buf;
+	int fd, ret;
+
+	if (razor_create_dir(installer->root, path) < 0)
+		return -1;
+
+	snprintf(buffer, sizeof buffer, "%s%s", installer->root, path);
+
+	switch (mode >> 12) {
+	case REG:
+		/* FIXME: handle the case where a file is already there. */
+		fd = open(buffer, O_WRONLY | O_CREAT | O_TRUNC, mode & 0x1ff);
+		if (fd < 0){
+			fprintf(stderr, "failed to create file %s\n", buffer);
+			return -1;
+		}
+		while (installer->rest > 0) {
+			if (installer_inflate(installer)) {
+				fprintf(stderr, "failed to inflate\n");
+				return -1;
+			}
+			if (razor_write(fd, installer->buffer,
+					installer->length)) {
+				fprintf(stderr, "failed to write payload\n");
+				return -1;
+			}
+		}
+		if (close(fd) < 0) {
+			fprintf(stderr, "failed to close %s: %m\n", buffer);
+			return -1;
+		}
+		return 0;
+	case XDIR:
+		ret = mkdir(buffer, mode & 0x1ff);
+		if (ret == 0 || errno != EEXIST)
+			return ret;
+		if (stat(buffer, &buf) || !S_ISDIR(buf.st_mode)) {
+			/* FIXME: also check that mode match. */
+			fprintf(stderr,
+				"%s exists but is not a directory\n", buffer);
+			return -1;
+		}
+		return 0;
+	case PIPE:
+	case CDEV:
+	case BDEV:
+	case SOCK:
+		printf("%s: unhandled file type %d\n", buffer, mode >> 12);
+		return 0;
+	case LINK:
+		if (installer_inflate(installer)) {
+			fprintf(stderr, "failed to inflate\n");
+			return -1;
+		}
+		if (installer->length >= sizeof installer->buffer) {
+			fprintf(stderr, "link name too long\n");
+			return -1;
+		}
+		installer->buffer[installer->length] = '\0';
+		if (symlink((const char *) installer->buffer, buffer)) {
+			fprintf(stderr, "failed to create symlink, %m\n");
+			return -1;
+		}
+		return 0;
+	default:
+		printf("%s: unknown file type %d\n", buffer, mode >> 12);
+		return 0;
+	}
+}
+
+static int
+run_script(struct installer *installer,
+	   unsigned int program_tag, unsigned int script_tag)
+{
+	int pid, status, fd[2];
+	const char *script = NULL, *program = NULL;
+
+	program = razor_rpm_get_indirect(installer->rpm, program_tag, NULL);
+	script = razor_rpm_get_indirect(installer->rpm, script_tag, NULL);
+	if (program == NULL && script == NULL) {
+		return 0;
+	} else if (program == NULL) {
+		program = "/bin/sh";
+	}
+
+	if (pipe(fd) < 0) {
+		fprintf(stderr, "failed to create pipe\n");
+		return -1;
+	}
+	pid = fork();
+	if (pid < 0) {
+		fprintf(stderr, "failed to fork, %m\n");
+	} else if (pid == 0) {
+		if (dup2(fd[0], STDIN_FILENO) < 0) {
+			fprintf(stderr, "failed redirect stdin, %m\n");
+			return -1;
+		}
+		if (close(fd[0]) < 0 || close(fd[1]) < 0) {
+			fprintf(stderr, "failed to close pipe, %m\n");
+			return -1;
+		}
+		if (chroot(installer->root) < 0) {
+			fprintf(stderr, "failed to chroot to %s, %m\n",
+				installer->root);
+			return -1;
+		}
+		printf("executing program %s in chroot %s\n",
+		       program, installer->root);
+		if (execl(program, program, NULL)) {
+			fprintf(stderr, "failed to exec %s, %m\n", program);
+			exit(-1);
+		}
+	} else {
+		if (script && razor_write(fd[1], script, strlen(script)) < 0) {
+			fprintf(stderr, "failed to pipe script, %m\n");
+			return -1;
+		}
+		if (close(fd[0]) || close(fd[1])) {
+			fprintf(stderr, "failed to close pipe, %m\n");
+			return -1;
+		}
+		if (wait(&status) < 0) {
+			fprintf(stderr, "wait for child failed, %m");
+			return -1;
+		}
+		if (status)
+			printf("script exited with status %d\n", status);
+	}
+
+	return 0;
+}
+
+static int
+installer_init(struct installer *installer)
+{
+	unsigned char *gz_header;
+	int method, flags, err;
+
+	gz_header = installer->rpm->payload;
+	if (gz_header[0] != 0x1f || gz_header[1] != 0x8b) {
+		fprintf(stderr, "payload section doesn't have gz header\n");
+		return -1;
+	}
+
+	method = gz_header[2];
+	flags = gz_header[3];
+
+	if (method != Z_DEFLATED || flags != 0) {
+		fprintf(stderr,
+			"unknown payload compression method or flags set\n");
+		return -1;
+	}
+
+	installer->stream.zalloc = NULL;
+	installer->stream.zfree = NULL;
+	installer->stream.opaque = NULL;
+
+	installer->stream.next_in  = gz_header + 10;
+	installer->stream.avail_in =
+		(installer->rpm->map + installer->rpm->size) -
+		(void *) installer->stream.next_in;
+	installer->stream.next_out = NULL;
+	installer->stream.avail_out = 0;
+
+	err = inflateInit2(&installer->stream, -MAX_WBITS);
+	if (err != Z_OK) {
+		fprintf(stderr, "inflateInit error: %d\n", err);
+		return -1;
+	}
+
+	return 0;
+}
+
+static int
+installer_finish(struct installer *installer)
+{
+	int err;
+
+	err = inflateEnd(&installer->stream);
+
+	if (err != Z_OK) {
+		fprintf(stderr, "inflateEnd error: %d\n", err);
+		return -1;
+	}
+
+	return 0;
+}
+
+static unsigned long
+fixed_hex_to_ulong(const char *hex, int length)
+{
+	long l;
+	int i;
+
+	for (i = 0, l = 0; i < length; i++) {
+		if (hex[i] < 'a')
+			l = l * 16 + hex[i] - '0';
+		else
+			l = l * 16 + hex[i] - 'a' + 10;
+	}
+
+	return l;
+}
+
+int
+razor_rpm_install(struct razor_rpm *rpm, const char *root)
+{
+	struct installer installer;
+	struct cpio_file_header *header;
+	struct stat buf;
+	unsigned int mode;
+	char *path;
+	size_t filesize;
+
+	installer.rpm = rpm;
+	installer.root = root;
+
+	/* FIXME: Only do this before a transaction, not per rpm. */
+	if (stat(root, &buf) < 0 || !S_ISDIR(buf.st_mode)) {
+		fprintf(stderr,
+			"root installation directory \"%s\" does not exist\n",
+			root);
+		return -1;
+	}
+
+	if (installer_init(&installer))
+		return -1;
+
+	run_script(&installer, RPMTAG_PREINPROG, RPMTAG_PREIN);
+
+	while (installer.stream.avail_in > 0) {
+		installer.rest = sizeof *header;
+		if (installer_inflate(&installer))
+			return -1;
+
+		header = (struct cpio_file_header *) installer.buffer;
+		mode = fixed_hex_to_ulong(header->mode, sizeof header->mode);
+		filesize = fixed_hex_to_ulong(header->filesize,
+					      sizeof header->filesize);
+
+		installer.rest = fixed_hex_to_ulong(header->namesize,
+						    sizeof header->namesize);
+
+		if (installer_inflate(&installer) ||
+		    installer_align(&installer, 4))
+			return -1;
+
+		path = (char *) installer.buffer;
+		/* This convention is so lame... */
+		if (strcmp(path, "TRAILER!!!") == 0)
+			break;
+
+		installer.rest = filesize;
+		if (create_path(&installer, path + 1, mode) < 0)
+			return -1;
+		if (installer_align(&installer, 4))
+			return -1;
+	}
+
+	if (installer_finish(&installer))
+		return -1;
+
+	run_script(&installer, RPMTAG_POSTINPROG, RPMTAG_POSTIN);
+
+	return 0;
+}
+
+int
+razor_rpm_close(struct razor_rpm *rpm)
+{
+	int err;
+
+	free(rpm->dirs);
+	err = munmap(rpm->map, rpm->size);
+	free(rpm);
+
+	return err;
+}
+
+int
+razor_importer_add_rpm(struct razor_importer *importer, struct razor_rpm *rpm)
+{
+	const char *name, *version, *release, *arch, *summary;
+	const uint32_t *epoch;
+	char evr[128], buf[16];
+
+	name = razor_rpm_get_indirect(rpm, RPMTAG_NAME, NULL);
+	epoch = razor_rpm_get_indirect(rpm, RPMTAG_EPOCH, NULL);
+	version = razor_rpm_get_indirect(rpm, RPMTAG_VERSION, NULL);
+	release = razor_rpm_get_indirect(rpm, RPMTAG_RELEASE, NULL);
+	arch = razor_rpm_get_indirect(rpm, RPMTAG_ARCH, NULL);
+	summary = razor_rpm_get_indirect(rpm, RPMTAG_SUMMARY, NULL);
+
+	if (epoch) {
+		snprintf(buf, sizeof buf, "%u", ntohl(*epoch));
+		razor_build_evr(evr, sizeof evr, buf, version, release);
+	} else {
+		razor_build_evr(evr, sizeof evr, NULL, version, release);
+	}
+	razor_importer_begin_package(importer, name, evr, arch);
+
+	import_properties(importer, RAZOR_PROPERTY_REQUIRES, rpm,
+			  RPMTAG_REQUIRENAME,
+			  RPMTAG_REQUIREVERSION,
+			  RPMTAG_REQUIREFLAGS);
+
+	import_properties(importer, RAZOR_PROPERTY_PROVIDES, rpm,
+			  RPMTAG_PROVIDENAME,
+			  RPMTAG_PROVIDEVERSION,
+			  RPMTAG_PROVIDEFLAGS);
+
+	import_properties(importer, RAZOR_PROPERTY_OBSOLETES, rpm,
+			  RPMTAG_OBSOLETENAME,
+			  RPMTAG_OBSOLETEVERSION,
+			  RPMTAG_OBSOLETEFLAGS);
+
+	import_properties(importer, RAZOR_PROPERTY_CONFLICTS, rpm,
+			  RPMTAG_CONFLICTNAME,
+			  RPMTAG_CONFLICTVERSION,
+			  RPMTAG_CONFLICTFLAGS);
+
+	import_files(importer, rpm);
+
+	razor_importer_finish_package(importer);
+
+	return 0;
+}
diff --git a/librazor/transaction.c b/librazor/transaction.c
new file mode 100644
index 0000000..93b1bf2
--- /dev/null
+++ b/librazor/transaction.c
@@ -0,0 +1,912 @@
+/*
+ * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
+ * Copyright (C) 2008  Red Hat, Inc
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#define _GNU_SOURCE
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <errno.h>
+#include <ctype.h>
+#include <fnmatch.h>
+
+#include "razor-internal.h"
+#include "razor.h"
+
+static int
+provider_satisfies_requirement(struct razor_property *provider,
+			       const char *provider_strings,
+			       uint32_t flags,
+			       const char *required)
+{
+	int cmp, len;
+	const char *provided = &provider_strings[provider->version];
+
+	if (!*required)
+		return 1;
+	if (!*provided) {
+		if (flags & RAZOR_PROPERTY_LESS)
+			return 0;
+		else
+			return 1;
+	}
+
+	cmp = razor_versioncmp(provided, required);
+
+	switch (flags & RAZOR_PROPERTY_RELATION_MASK) {
+	case RAZOR_PROPERTY_LESS:
+		return cmp < 0;
+
+	case RAZOR_PROPERTY_LESS | RAZOR_PROPERTY_EQUAL:
+		if (cmp <= 0)
+			return 1;
+		/* fall through: FIXME, make sure this is correct */
+
+	case RAZOR_PROPERTY_EQUAL:
+		if (cmp == 0)
+			return 1;
+
+		/* "foo == 1.1" is satisfied by "foo 1.1-2" */
+		len = strlen(required);
+		if (!strncmp(required, provided, len) && provided[len] == '-')
+			return 1;
+		return 0;
+
+	case RAZOR_PROPERTY_GREATER | RAZOR_PROPERTY_EQUAL:
+		return cmp >= 0;
+
+	case RAZOR_PROPERTY_GREATER:
+		return cmp > 0;
+	}
+
+	/* shouldn't happen */
+	return 0;
+}
+
+#define TRANS_PACKAGE_PRESENT		1
+#define TRANS_PACKAGE_UPDATE		2
+#define TRANS_PROPERTY_SATISFIED	0x80000000
+
+struct transaction_set {
+	struct razor_set *set;
+	uint32_t *packages;
+	uint32_t *properties;
+};
+
+struct razor_transaction {
+	int package_count, errors;
+	struct transaction_set system, upstream;
+	int changes;
+};
+
+static void
+transaction_set_init(struct transaction_set *ts, struct razor_set *set)
+{
+	int count;
+
+	ts->set = set;
+	count = set->packages.size / sizeof (struct razor_package);
+	ts->packages = zalloc(count * sizeof *ts->packages);
+	count = set->properties.size / sizeof (struct razor_property);
+	ts->properties = zalloc(count * sizeof *ts->properties);
+}
+
+static void
+transaction_set_release(struct transaction_set *ts)
+{
+	free(ts->packages);
+	free(ts->properties);
+}
+
+static void
+transaction_set_install_package(struct transaction_set *ts,
+				struct razor_package *package)
+{
+	struct razor_package *pkgs;
+	struct list *prop;
+	int i;
+
+	pkgs = ts->set->packages.data;
+	i = package - pkgs;
+	if (ts->packages[i] == TRANS_PACKAGE_PRESENT)
+		return;
+
+	ts->packages[i] = TRANS_PACKAGE_PRESENT;
+
+	prop = list_first(&package->properties, &ts->set->property_pool);
+	while (prop) {
+		ts->properties[prop->data]++;
+		prop = list_next(prop);
+	}
+}
+
+static void
+transaction_set_remove_package(struct transaction_set *ts,
+			       struct razor_package *package)
+{
+	struct razor_package *pkgs;
+	struct list *prop;
+	int i;
+
+	pkgs = ts->set->packages.data;
+	i = package - pkgs;
+	if (ts->packages[i] == 0)
+		return;
+
+	ts->packages[i] = 0;
+
+	prop = list_first(&package->properties, &ts->set->property_pool);
+	while (prop) {
+		ts->properties[prop->data]--;
+		prop = list_next(prop);
+	}
+}
+
+struct razor_transaction *
+razor_transaction_create(struct razor_set *system, struct razor_set *upstream)
+{
+	struct razor_transaction *trans;
+	struct razor_package *p, *spkgs, *pend;
+
+	trans = zalloc(sizeof *trans);
+	transaction_set_init(&trans->system, system);
+	transaction_set_init(&trans->upstream, upstream);
+
+	spkgs = trans->system.set->packages.data;
+	pend = trans->system.set->packages.data +
+		trans->system.set->packages.size;
+	for (p = spkgs; p < pend; p++)
+		transaction_set_install_package(&trans->system, p);
+
+	return trans;
+}
+
+void
+razor_transaction_install_package(struct razor_transaction *trans,
+				  struct razor_package *package)
+{
+	transaction_set_install_package(&trans->upstream, package);
+	trans->changes++;
+}
+
+void
+razor_transaction_remove_package(struct razor_transaction *trans,
+				 struct razor_package *package)
+{
+	transaction_set_remove_package(&trans->system, package);
+	trans->changes++;
+}
+
+void
+razor_transaction_update_package(struct razor_transaction *trans,
+				  struct razor_package *package)
+{
+	struct razor_package *spkgs, *upkgs, *end;
+
+	spkgs = trans->system.set->packages.data;
+	upkgs = trans->upstream.set->packages.data;
+	end = trans->system.set->packages.data +
+		trans->system.set->packages.size;
+	if (spkgs <= package && package < end)
+		trans->system.packages[package - spkgs] |= TRANS_PACKAGE_UPDATE;
+	else
+		trans->upstream.packages[package - upkgs] |= TRANS_PACKAGE_UPDATE;
+}
+
+struct prop_iter {
+	struct razor_property *p, *start, *end;
+	const char *pool;
+	uint32_t *present;
+};
+
+static void
+prop_iter_init(struct prop_iter *pi, struct transaction_set *ts)
+{
+	pi->p = ts->set->properties.data;
+	pi->start = ts->set->properties.data;
+	pi->end = ts->set->properties.data + ts->set->properties.size;
+	pi->pool = ts->set->string_pool.data;
+	pi->present = ts->properties;
+}
+
+static int
+prop_iter_next(struct prop_iter *pi, uint32_t flags, struct razor_property **p)
+{
+	while (pi->p < pi->end) {
+		if ((pi->present[pi->p - pi->start] & ~TRANS_PROPERTY_SATISFIED) &&
+		    (pi->p->flags & RAZOR_PROPERTY_TYPE_MASK) == flags) {
+			*p = pi->p++;
+			return 1;
+		}
+		pi->p++;
+	}
+
+	return 0;
+}
+
+static struct razor_property *
+prop_iter_seek_to(struct prop_iter *pi,
+		  uint32_t flags, const char *match)
+{
+	uint32_t name;
+
+	while (pi->p < pi->end && strcmp(&pi->pool[pi->p->name], match) < 0)
+		pi->p++;
+
+	if (pi->p == pi->end || strcmp(&pi->pool[pi->p->name], match) > 0)
+		return NULL;
+
+	name = pi->p->name;
+	while (pi->p < pi->end &&
+	       pi->p->name == name &&
+	       (pi->p->flags & RAZOR_PROPERTY_TYPE_MASK) != flags)
+		pi->p++;
+
+	if (pi->p == pi->end || pi->p->name != name)
+		return NULL;
+
+	return pi->p;
+}
+
+/* Remove packages from set that provide any of the matching (same
+ * name and type) providers from ppi onwards that match the
+ * requirement that rpi points to. */
+static void
+remove_matching_providers(struct razor_transaction *trans,
+			  struct prop_iter *ppi,
+			  uint32_t flags,
+			  const char *version)
+{
+	struct razor_property *p;
+	struct razor_package *pkg, *pkgs;
+	struct razor_package_iterator pkg_iter;
+	struct razor_set *set;
+	const char *n, *v, *a;
+	uint32_t type;
+
+	if (ppi->present == trans->system.properties)
+		set = trans->system.set;
+	else
+		set = trans->upstream.set;
+
+	pkgs = (struct razor_package *) set->packages.data;
+	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
+	for (p = ppi->p;
+	     p < ppi->end &&
+	     p->name == ppi->p->name &&
+	     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;
+	     p++) {
+		if (!ppi->present[p - ppi->start])
+			continue;
+		if (!provider_satisfies_requirement(p, ppi->pool,
+						    flags, version))
+			continue;
+
+		razor_package_iterator_init_for_property(&pkg_iter, set, p);
+		while (razor_package_iterator_next(&pkg_iter,
+						   &pkg, &n, &v, &a)) {
+			fprintf(stderr, "removing %s-%s\n", n, v);
+			razor_transaction_remove_package(trans, pkg);
+		}
+	}
+}
+
+static void
+flag_matching_providers(struct razor_transaction *trans,
+			struct prop_iter *ppi,
+			struct razor_property *r,
+			struct prop_iter *rpi,
+			unsigned int flag)
+{
+	struct razor_property *p;
+	struct razor_package *pkg, *pkgs;
+	struct razor_package_iterator pkg_iter;
+	struct razor_set *set;
+	const char *name, *version, *arch;
+	uint32_t *flags, type;
+
+	if (ppi->present == trans->system.properties) {
+		set = trans->system.set;
+		flags = trans->system.packages;
+	} else {
+		set = trans->upstream.set;
+		flags = trans->upstream.packages;
+	}
+
+	pkgs = (struct razor_package *) set->packages.data;
+	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
+	for (p = ppi->p;
+	     p < ppi->end &&
+		     p->name == ppi->p->name &&
+		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;
+	     p++) {
+		if (!ppi->present[p - ppi->start])
+			continue;
+		if (!provider_satisfies_requirement(p, ppi->pool,
+						    r->flags,
+						    &rpi->pool[r->version]))
+			continue;
+
+		razor_package_iterator_init_for_property(&pkg_iter, set, p);
+		while (razor_package_iterator_next(&pkg_iter, &pkg,
+						   &name, &version, &arch)) {
+
+			fprintf(stderr, "flagging %s-%s for providing %s matching %s %s\n",
+				name, version,
+				ppi->pool + p->name,
+				rpi->pool + r->name,
+				rpi->pool + r->version);
+			flags[pkg - pkgs] |= flag;
+		}
+	}
+}
+
+static struct razor_package *
+pick_matching_provider(struct razor_set *set,
+		       struct prop_iter *ppi,
+		       uint32_t flags,
+		       const char *version)
+{
+	struct razor_property *p;
+	struct razor_package *pkgs;
+	struct list *i;
+	uint32_t type;
+
+	/* This is where we decide which pkgs to pull in to satisfy a
+	 * requirement.  There may be several different providers
+	 * (different versions) and each version of a provider may
+	 * come from a number of packages.  We pick the first package
+	 * from the first provider that matches. */
+
+	pkgs = set->packages.data;
+	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
+	for (p = ppi->p;
+	     p < ppi->end &&
+		     p->name == ppi->p->name &&
+		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type &&
+		     ppi->present[p - ppi->start] == 0;
+	     p++) {
+		if (!provider_satisfies_requirement(p, ppi->pool,
+						    flags, version))
+			continue;
+
+		i = list_first(&p->packages, &set->package_pool);
+
+		return &pkgs[i->data];
+	}
+
+	return NULL;
+}
+
+static void
+remove_obsoleted_packages(struct razor_transaction *trans)
+{
+	struct razor_property *up;
+	struct razor_package *spkgs;
+	struct prop_iter spi, upi;
+
+	spkgs = trans->system.set->packages.data;
+	prop_iter_init(&spi, &trans->system);
+	prop_iter_init(&upi, &trans->upstream);
+
+	while (prop_iter_next(&upi, RAZOR_PROPERTY_OBSOLETES, &up)) {
+		if (!prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,
+				       &upi.pool[up->name]))
+			continue;
+		remove_matching_providers(trans, &spi, up->flags,
+					  &upi.pool[up->version]);
+	}
+}
+
+static int
+any_provider_satisfies_requirement(struct prop_iter *ppi,
+				   uint32_t flags,
+				   const char *version)
+{
+	struct razor_property *p;
+	uint32_t type;
+
+	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;
+	for (p = ppi->p;
+	     p < ppi->end &&
+		     p->name == ppi->p->name &&
+		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;
+	     p++) {
+		if (ppi->present[p - ppi->start] > 0 &&
+		    provider_satisfies_requirement(p, ppi->pool,
+						   flags, version))
+			return 1;
+	}
+
+	return 0;
+}
+
+static void
+clear_requires_flags(struct transaction_set *ts)
+{
+	struct razor_property *p;
+	const char *pool;
+	int i, count;
+
+	count = ts->set->properties.size / sizeof *p;
+	p = ts->set->properties.data;
+	pool = ts->set->string_pool.data;
+	for (i = 0; i < count; i++) {
+		ts->properties[i] &= ~TRANS_PROPERTY_SATISFIED;
+		if (strncmp(&pool[p[i].name], "rpmlib(", 7) == 0)
+			ts->properties[i] |= TRANS_PROPERTY_SATISFIED;
+	}
+}
+
+const char *
+razor_property_relation_to_string(struct razor_property *p)
+{
+	switch (p->flags & RAZOR_PROPERTY_RELATION_MASK) {
+	case RAZOR_PROPERTY_LESS:
+		return "<";
+
+	case RAZOR_PROPERTY_LESS | RAZOR_PROPERTY_EQUAL:
+		return "<=";
+
+	case RAZOR_PROPERTY_EQUAL:
+		return "=";
+
+	case RAZOR_PROPERTY_GREATER | RAZOR_PROPERTY_EQUAL:
+		return ">=";
+
+	case RAZOR_PROPERTY_GREATER:
+		return ">";
+
+	default:
+		return "?";
+	}
+}
+
+const char *
+razor_property_type_to_string(struct razor_property *p)
+{
+	switch (p->flags & RAZOR_PROPERTY_TYPE_MASK) {
+	case RAZOR_PROPERTY_REQUIRES:
+		return "requires";
+	case RAZOR_PROPERTY_PROVIDES:
+		return "provides";
+	case RAZOR_PROPERTY_CONFLICTS:
+		return "conflicts";
+	case RAZOR_PROPERTY_OBSOLETES:
+		return "obsoletes";
+	default:
+		return NULL;
+	}
+}
+
+static void
+mark_satisfied_requires(struct razor_transaction *trans,
+			struct transaction_set *rts,
+			struct transaction_set *pts)
+{
+	struct prop_iter rpi, ppi;
+	struct razor_property *rp;
+
+	prop_iter_init(&rpi, rts);
+	prop_iter_init(&ppi, pts);
+
+	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
+		if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES,
+				       &rpi.pool[rp->name]))
+			continue;
+
+		if (any_provider_satisfies_requirement(&ppi, rp->flags,
+						       &rpi.pool[rp->version]))
+			rpi.present[rp - rpi.start] |= TRANS_PROPERTY_SATISFIED;
+	}
+}
+
+static void
+mark_all_satisfied_requires(struct razor_transaction *trans)
+{
+	clear_requires_flags(&trans->system);
+	clear_requires_flags(&trans->upstream);
+	mark_satisfied_requires(trans, &trans->system, &trans->system);
+	mark_satisfied_requires(trans, &trans->system, &trans->upstream);
+	mark_satisfied_requires(trans, &trans->upstream, &trans->system);
+	mark_satisfied_requires(trans, &trans->upstream, &trans->upstream);
+}
+
+static void
+update_unsatisfied_packages(struct razor_transaction *trans)
+{
+	struct razor_package *spkgs, *pkg;
+	struct razor_property *sp;
+	struct prop_iter spi;
+	struct razor_package_iterator pkg_iter;
+	const char *name, *version, *arch;
+
+	spkgs = trans->system.set->packages.data;
+	prop_iter_init(&spi, &trans->system);
+
+	while (prop_iter_next(&spi, RAZOR_PROPERTY_REQUIRES, &sp)) {
+		if (spi.present[sp - spi.start] & TRANS_PROPERTY_SATISFIED)
+			continue;
+
+		razor_package_iterator_init_for_property(&pkg_iter,
+							 trans->system.set,
+							 sp);
+		while (razor_package_iterator_next(&pkg_iter, &pkg,
+						   &name, &version, &arch)) {
+			fprintf(stderr, "updating %s because %s %s %s "
+				"isn't satisfied\n",
+				name, spi.pool + sp->name,
+				razor_property_relation_to_string(sp),
+				spi.pool + sp->version);
+			trans->system.packages[pkg - spkgs] |=
+				TRANS_PACKAGE_UPDATE;
+		}
+	}
+}
+
+void
+razor_transaction_update_all(struct razor_transaction *trans)
+{
+	struct razor_package *p;
+	int i, count;
+
+	count = trans->system.set->packages.size / sizeof *p;
+	for (i = 0; i < count; i++)
+		trans->system.packages[i] |= TRANS_PACKAGE_UPDATE;
+}
+
+static void
+update_conflicted_packages(struct razor_transaction *trans)
+{
+	struct razor_package *pkg, *spkgs;
+	struct razor_property *up, *sp;
+	struct prop_iter spi, upi;
+	struct razor_package_iterator pkg_iter;
+	const char *name, *version, *arch;
+
+	spkgs = trans->system.set->packages.data;
+	prop_iter_init(&spi, &trans->system);
+	prop_iter_init(&upi, &trans->upstream);
+
+	while (prop_iter_next(&spi, RAZOR_PROPERTY_CONFLICTS, &sp)) {
+		if (!prop_iter_seek_to(&upi, RAZOR_PROPERTY_PROVIDES,
+				       &spi.pool[sp->name]))
+			continue;
+
+		if (!any_provider_satisfies_requirement(&upi, sp->flags,
+							&spi.pool[sp->version]))
+			continue;
+
+		razor_package_iterator_init_for_property(&pkg_iter,
+							 trans->system.set,
+							 sp);
+		while (razor_package_iterator_next(&pkg_iter, &pkg,
+						   &name, &version, &arch)) {
+			fprintf(stderr, "updating %s %s because it conflicts with %s",
+				name, version, spi.pool + sp->name);
+			trans->system.packages[pkg - spkgs] |=
+				TRANS_PACKAGE_UPDATE;
+		}
+	}
+
+	prop_iter_init(&spi, &trans->system);
+	prop_iter_init(&upi, &trans->upstream);
+
+	while (prop_iter_next(&upi, RAZOR_PROPERTY_CONFLICTS, &up)) {
+		sp = prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,
+				       &upi.pool[upi.p->name]);
+
+		if (sp)
+			flag_matching_providers(trans, &spi, up, &upi,
+						TRANS_PACKAGE_UPDATE);
+	}
+}
+
+static void
+pull_in_requirements(struct razor_transaction *trans,
+		     struct prop_iter *rpi, struct prop_iter *ppi)
+{
+	struct razor_property *rp, *pp;
+	struct razor_package *pkg, *upkgs;
+
+	upkgs = trans->upstream.set->packages.data;
+	while (prop_iter_next(rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
+		if (rpi->present[rp - rpi->start] & TRANS_PROPERTY_SATISFIED)
+			continue;
+
+		pp = prop_iter_seek_to(ppi, RAZOR_PROPERTY_PROVIDES,
+				       &rpi->pool[rp->name]);
+		if (pp == NULL)
+			continue;
+		pkg = pick_matching_provider(trans->upstream.set,
+					     ppi, rp->flags,
+					     &rpi->pool[rp->version]);
+		if (pkg == NULL)
+			continue;
+
+		rpi->present[rp - rpi->start] |= TRANS_PROPERTY_SATISFIED;
+
+		fprintf(stderr, "pulling in %s which provides %s %s %s "
+			"to satisfy %s %s %s\n",
+			ppi->pool + pkg->name,
+			ppi->pool + pp->name,
+			razor_property_relation_to_string(pp),
+			ppi->pool + pp->version,
+			&rpi->pool[rp->name],
+			razor_property_relation_to_string(rp),
+			&rpi->pool[rp->version]);
+
+		trans->upstream.packages[pkg - upkgs] |= TRANS_PACKAGE_UPDATE;
+	}
+}
+
+static void
+pull_in_all_requirements(struct razor_transaction *trans)
+{
+	struct prop_iter rpi, ppi;
+
+	prop_iter_init(&rpi, &trans->system);
+	prop_iter_init(&ppi, &trans->upstream);
+	pull_in_requirements(trans, &rpi, &ppi);
+
+	prop_iter_init(&rpi, &trans->upstream);
+	prop_iter_init(&ppi, &trans->upstream);
+	pull_in_requirements(trans, &rpi, &ppi);
+}
+
+static void
+flush_scheduled_system_updates(struct razor_transaction *trans)
+{
+ 	struct razor_package_iterator *pi;
+ 	struct razor_package *p, *pkg, *spkgs;
+	struct prop_iter ppi;
+	const char *name, *version, *arch;
+
+	spkgs = trans->system.set->packages.data;
+	pi = razor_package_iterator_create(trans->system.set);
+	prop_iter_init(&ppi, &trans->upstream);
+
+	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
+		if (!(trans->system.packages[p - spkgs] & TRANS_PACKAGE_UPDATE))
+			continue;
+
+		if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES, name))
+			continue;
+
+		pkg = pick_matching_provider(trans->upstream.set, &ppi,
+					     RAZOR_PROPERTY_GREATER, version);
+		if (pkg == NULL)
+			continue;
+
+		fprintf(stderr, "updating %s-%s to %s-%s\n",
+			name, version,
+			&ppi.pool[pkg->name], &ppi.pool[pkg->version]);
+
+		razor_transaction_remove_package(trans, p);
+		razor_transaction_install_package(trans, pkg);
+	}
+
+	razor_package_iterator_destroy(pi);
+}
+
+static void
+flush_scheduled_upstream_updates(struct razor_transaction *trans)
+{
+ 	struct razor_package_iterator *pi;
+ 	struct razor_package *p, *upkgs;
+	struct prop_iter spi;
+	const char *name, *version, *arch;
+
+	upkgs = trans->upstream.set->packages.data;
+	pi = razor_package_iterator_create(trans->upstream.set);
+	prop_iter_init(&spi, &trans->system);
+
+	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {
+		if (!(trans->upstream.packages[p - upkgs] & TRANS_PACKAGE_UPDATE))
+			continue;
+
+		if (prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES, name))
+			remove_matching_providers(trans,
+						  &spi,
+						  RAZOR_PROPERTY_LESS,
+						  version);
+		razor_transaction_install_package(trans, p);
+		fprintf(stderr, "installing %s-%s\n", name, version);
+	}
+}
+
+int
+razor_transaction_resolve(struct razor_transaction *trans)
+{
+	int last = 0;
+
+	flush_scheduled_system_updates(trans);
+	flush_scheduled_upstream_updates(trans);
+
+	while (last < trans->changes) {
+		last = trans->changes;
+		remove_obsoleted_packages(trans);
+		mark_all_satisfied_requires(trans);
+		update_unsatisfied_packages(trans);
+		update_conflicted_packages(trans);
+		pull_in_all_requirements(trans);
+		flush_scheduled_system_updates(trans);
+		flush_scheduled_upstream_updates(trans);
+	}
+
+	return trans->changes;
+}
+
+static void
+describe_unsatisfied(struct razor_set *set, struct razor_property *rp)
+{
+	struct razor_package_iterator pi;
+	struct razor_package *pkg;
+	const char *name, *version, *arch, *pool;
+
+	pool = set->string_pool.data;
+	if (pool[rp->version] == '\0') {
+		razor_package_iterator_init_for_property(&pi, set, rp);
+		while (razor_package_iterator_next(&pi, &pkg,
+						   &name, &version, &arch))
+			fprintf(stderr, "%s is needed by %s-%s.%s\n",
+				&pool[rp->name],
+				name, version, arch);
+	} else {
+		razor_package_iterator_init_for_property(&pi, set, rp);
+		while (razor_package_iterator_next(&pi, &pkg,
+						   &name, &version, &arch))
+			fprintf(stderr, "%s %s %s is needed by %s-%s.%s\n",
+				&pool[rp->name],
+				razor_property_relation_to_string(rp),
+				&pool[rp->version],
+				name, version, arch);
+	}
+}
+
+int
+razor_transaction_describe(struct razor_transaction *trans)
+{
+	struct prop_iter rpi;
+	struct razor_property *rp;
+	int unsatisfied;
+
+	flush_scheduled_system_updates(trans);
+	flush_scheduled_upstream_updates(trans);
+	mark_all_satisfied_requires(trans);
+
+	unsatisfied = 0;
+	prop_iter_init(&rpi, &trans->system);
+	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
+		if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED)) {
+			describe_unsatisfied(trans->system.set, rp);
+		        unsatisfied++;
+		}
+	}
+
+	prop_iter_init(&rpi, &trans->upstream);
+	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {
+		if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED)) {
+			describe_unsatisfied(trans->upstream.set, rp);
+			unsatisfied++;
+		}
+	}
+
+	return unsatisfied;
+}
+
+int
+razor_transaction_unsatisfied_property(struct razor_transaction *trans,
+				       const char *name,
+				       uint32_t flags,
+				       const char *version)
+{
+	struct prop_iter pi;
+	struct razor_property *p;
+
+	prop_iter_init(&pi, &trans->system);
+	while (prop_iter_next(&pi, flags, &p)) {
+		if (!(trans->system.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&
+		    p->flags == flags &&
+		    strcmp(&pi.pool[p->name], name) == 0 &&
+		    strcmp(&pi.pool[p->version], version) == 0)
+
+			return 1;
+	}
+
+	prop_iter_init(&pi, &trans->upstream);
+	while (prop_iter_next(&pi, flags, &p)) {
+		if (!(trans->upstream.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&
+		    p->flags == flags &&
+		    strcmp(&pi.pool[p->name], name) == 0 &&
+		    strcmp(&pi.pool[p->version], version) == 0)
+
+			return 1;
+	}
+
+	return 0;
+}
+
+struct razor_set *
+razor_transaction_finish(struct razor_transaction *trans)
+{
+	struct razor_merger *merger;
+	struct razor_package *u, *uend, *upkgs, *s, *send, *spkgs;
+	char *upool, *spool;
+	int cmp;
+
+	s = trans->system.set->packages.data;
+	spkgs = trans->system.set->packages.data;
+	send = trans->system.set->packages.data +
+		trans->system.set->packages.size;
+	spool = trans->system.set->string_pool.data;
+
+	u = trans->upstream.set->packages.data;
+	upkgs = trans->upstream.set->packages.data;
+	uend = trans->upstream.set->packages.data +
+		trans->upstream.set->packages.size;
+	upool = trans->upstream.set->string_pool.data;
+
+	merger = razor_merger_create(trans->system.set, trans->upstream.set);
+	while (s < send || u < uend) {
+		if (s < send && u < uend)
+			cmp = strcmp(&spool[s->name], &upool[u->name]);
+		else if (s < send)
+			cmp = -1;
+		else
+			cmp = 1;
+
+		if (cmp < 0) {
+			if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)
+				razor_merger_add_package(merger, s);
+			s++;
+		} else if (cmp == 0) {
+			if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)
+				razor_merger_add_package(merger, s);
+			if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)
+				razor_merger_add_package(merger, u);
+
+			s++;
+			u++;
+		} else {
+			if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)
+				razor_merger_add_package(merger, u);
+			u++;
+		}
+	}
+
+	razor_transaction_destroy(trans);
+
+	return razor_merger_finish(merger);
+}
+
+void
+razor_transaction_destroy(struct razor_transaction *trans)
+{
+	transaction_set_release(&trans->system);
+	transaction_set_release(&trans->upstream);
+	free(trans);
+}
diff --git a/librazor/types.c b/librazor/types.c
new file mode 100644
index 0000000..1dc9aef
--- /dev/null
+++ b/librazor/types.c
@@ -0,0 +1,246 @@
+#include <stdlib.h>
+#include <string.h>
+
+#include "razor-internal.h"
+
+void
+array_init(struct array *array)
+{
+	memset(array, 0, sizeof *array);
+}
+
+void
+array_release(struct array *array)
+{
+	free(array->data);
+}
+
+void *
+array_add(struct array *array, int size)
+{
+	int alloc;
+	void *data, *p;
+
+	if (array->alloc > 0)
+		alloc = array->alloc;
+	else
+		alloc = 16;
+
+	while (alloc < array->size + size)
+		alloc *= 2;
+
+	if (array->alloc < alloc) {
+		data = realloc(array->data, alloc);
+		if (data == NULL)
+			return 0;
+		array->data = data;
+		array->alloc = alloc;
+	}
+
+	p = array->data + array->size;
+	array->size += size;
+
+	return p;
+}
+
+/* RAZOR_IMMEDIATE and RAZOR_ENTRY_LAST must have the same value */
+#define RAZOR_ENTRY_LAST 0x80
+#define RAZOR_IMMEDIATE  0x80
+#define RAZOR_EMPTY_LIST 0xff
+
+void
+list_set_empty(struct list_head *head)
+{
+	head->list_ptr = ~0;
+	head->flags = RAZOR_EMPTY_LIST;
+}
+
+void
+list_set_ptr(struct list_head *head, uint32_t ptr)
+{
+	head->list_ptr = ptr;
+	head->flags = 0;
+}
+
+void
+list_set_array(struct list_head *head, struct array *pool,
+	       struct array *items, int force_indirect)
+{
+	struct list *p;
+
+	if (!force_indirect) {
+		if (items->size == 0) {
+			list_set_empty(head);
+			return;
+		} else if (items->size == sizeof (uint32_t)) {
+			head->list_ptr = *(uint32_t *) items->data;
+			head->flags = RAZOR_IMMEDIATE;
+			return;
+		}
+	}
+
+	p = array_add(pool, items->size);
+	memcpy(p, items->data, items->size);
+	p[items->size / sizeof *p - 1].flags = RAZOR_ENTRY_LAST;
+	list_set_ptr(head, p - (struct list *) pool->data);
+}
+
+struct list *
+list_first(struct list_head *head, struct array *pool)
+{
+	if (head->flags == RAZOR_EMPTY_LIST)
+		return NULL;
+	else if (head->flags == RAZOR_IMMEDIATE)
+		return (struct list *) head;
+	else
+		return (struct list *) pool->data + head->list_ptr;
+}
+
+struct list *
+list_next(struct list *list)
+{
+	if (list->flags)
+		return NULL;
+	return ++list;
+}
+
+void
+list_remap_pool(struct array *pool, uint32_t *map)
+{
+	struct list *p, *end;
+
+	end = pool->data + pool->size;
+	for (p = pool->data; p < end; p++)
+		p->data = map[p->data];
+}
+
+void
+list_remap_head(struct list_head *head, uint32_t *map)
+{
+	if (head->flags == RAZOR_IMMEDIATE)
+		head->list_ptr = map[head->list_ptr];
+}
+
+
+void
+hashtable_init(struct hashtable *table, struct array *pool)
+{
+	array_init(&table->buckets);
+	table->pool = pool;
+}
+
+void
+hashtable_release(struct hashtable *table)
+{
+	array_release(&table->buckets);
+}
+
+static unsigned int
+hash_string(const char *key)
+{
+	const char *p;
+	unsigned int hash = 0;
+
+	for (p = key; *p; p++)
+		hash = (hash * 617) ^ *p;
+
+	return hash;
+}
+
+uint32_t
+hashtable_lookup(struct hashtable *table, const char *key)
+{
+	unsigned int mask, start, i;
+	uint32_t *b;
+	char *pool;
+
+	pool = table->pool->data;
+	mask = table->buckets.alloc - 1;
+	start = hash_string(key) * sizeof(uint32_t);
+
+	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
+		b = table->buckets.data + ((start + i) & mask);
+
+		if (*b == 0)
+			return 0;
+
+		if (strcmp(key, &pool[*b]) == 0)
+			return *b;
+	}
+
+	return 0;
+}
+
+static void
+do_insert(struct hashtable *table, uint32_t value)
+{
+	unsigned int mask, start, i;
+	uint32_t *b;
+	const char *key;
+
+	key = (char *) table->pool->data + value;
+	mask = table->buckets.alloc - 1;
+	start = hash_string(key) * sizeof(uint32_t);
+
+	for (i = 0; i < table->buckets.alloc; i += sizeof *b) {
+		b = table->buckets.data + ((start + i) & mask);
+		if (*b == 0) {
+			*b = value;
+			break;
+		}
+	}
+}
+
+static uint32_t
+add_to_string_pool(struct hashtable *table, const char *key)
+{
+	int len;
+	char *p;
+
+	len = strlen(key) + 1;
+	p = array_add(table->pool, len);
+	memcpy(p, key, len);
+
+	return p - (char *) table->pool->data;
+}
+
+uint32_t
+hashtable_insert(struct hashtable *table, const char *key)
+{
+	uint32_t value, *buckets, *b, *end;
+	int alloc;
+
+	alloc = table->buckets.alloc;
+	array_add(&table->buckets, 4 * sizeof *buckets);
+	if (alloc != table->buckets.alloc) {
+		end = table->buckets.data + alloc;
+		memset(end, 0, table->buckets.alloc - alloc);
+		for (b = table->buckets.data; b < end; b++) {
+			value = *b;
+			if (value != 0) {
+				*b = 0;
+				do_insert(table, value);
+			}
+		}
+	}
+
+	value = add_to_string_pool(table, key);
+	do_insert (table, value);
+
+	return value;
+}
+
+uint32_t
+hashtable_tokenize(struct hashtable *table, const char *string)
+{
+	uint32_t token;
+
+	if (string == NULL)
+		string = "";
+
+	token = hashtable_lookup(table, string);
+	if (token != 0)
+		return token;
+
+	return hashtable_insert(table, string);
+}
diff --git a/librazor/util.c b/librazor/util.c
new file mode 100644
index 0000000..29a7716
--- /dev/null
+++ b/librazor/util.c
@@ -0,0 +1,167 @@
+#include <limits.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <unistd.h>
+
+#include "razor-internal.h"
+
+int
+razor_create_dir(const char *root, const char *path)
+{
+	char buffer[PATH_MAX], *p;
+	const char *slash, *next;
+	struct stat buf;
+
+	/* Create all sub-directories in dir. We know root exists and
+	 * is a dir, root does not end in a '/', and path has a
+	 * leading '/'. */
+
+	strcpy(buffer, root);
+	p = buffer + strlen(buffer);
+	slash = path;
+	for (slash = path; *slash != '\0'; slash = next) {
+		next = strchr(slash + 1, '/');
+		if (next == NULL)
+			break;
+
+		memcpy(p, slash, next - slash);
+		p += next - slash;
+		*p = '\0';
+
+		if (stat(buffer, &buf) == 0) {
+			if (!S_ISDIR(buf.st_mode)) {
+				fprintf(stderr,
+					"%s exists but is not a directory\n",
+					buffer);
+				return -1;
+			}
+		} else if (mkdir(buffer, 0777) < 0) {
+			fprintf(stderr, "failed to make directory %s: %m\n",
+				buffer);
+			return -1;
+		}
+
+		/* FIXME: What to do about permissions for dirs we
+		 * have to create but are not in the cpio archive? */
+	}
+
+	return 0;
+}
+
+int
+razor_write(int fd, const void *data, size_t size)
+{
+	size_t rest;
+	ssize_t written;
+	const unsigned char *p;
+
+	rest = size;
+	p = data;
+	while (rest > 0) {
+		written = write(fd, p, rest);
+		if (written < 0) {
+			fprintf(stderr, "write error: %m\n");
+			return -1;
+		}
+		rest -= written;
+		p += written;
+	}
+
+	return 0;
+}
+
+struct qsort_context {
+	size_t size;
+	razor_compare_with_data_func_t compare;
+	void *data;
+};
+
+static void
+qsort_swap(void *p1, void *p2, size_t size)
+{
+	char buffer[size];
+
+	memcpy(buffer, p1, size);
+	memcpy(p1, p2, size);
+	memcpy(p2, buffer, size);
+}
+
+static void
+__qsort_with_data(void *base, size_t nelem, uint32_t *map,
+		  struct qsort_context *ctx)
+{
+	void *p, *start, *end, *pivot;
+	uint32_t *mp, *mstart, *mend, tmp;
+	int left, right, result;
+	size_t size = ctx->size;
+
+	p = base;
+	start = base;
+	end = base + nelem * size;
+	mp = map;
+	mstart = map;
+	mend = map + nelem;
+	pivot = base + (random() % nelem) * size;
+
+	while (p < end) {
+		result = ctx->compare(p, pivot, ctx->data);
+		if (result < 0) {
+			qsort_swap(p, start, size);
+			tmp = *mp;
+			*mp = *mstart;
+			*mstart = tmp;
+			if (start == pivot)
+				pivot = p;
+			start += size;
+			mstart++;
+			p += size;
+			mp++;
+		} else if (result == 0) {
+			p += size;
+			mp++;
+		} else {
+ 			end -= size;
+			mend--;
+			qsort_swap(p, end, size);
+			tmp = *mp;
+			*mp = *mend;
+			*mend = tmp;
+			if (end == pivot)
+				pivot = p;
+		}
+	}
+
+	left = (start - base) / size;
+	right = (base + nelem * size - end) / size;
+	if (left > 1)
+		__qsort_with_data(base, left, map, ctx);
+	if (right > 1)
+		__qsort_with_data(end, right, mend, ctx);
+}
+
+uint32_t *
+razor_qsort_with_data(void *base, size_t nelem, size_t size,
+		      razor_compare_with_data_func_t compare, void *data)
+{
+	struct qsort_context ctx;
+	uint32_t *map;
+	int i;
+
+	if (nelem == 0)
+		return NULL;
+
+	ctx.size = size;
+	ctx.compare = compare;
+	ctx.data = data;
+
+	map = malloc(nelem * sizeof (uint32_t));
+	for (i = 0; i < nelem; i++)
+		map[i] = i;
+
+	__qsort_with_data(base, nelem, map, &ctx);
+
+	return map;
+}