krh@248: /*
krh@248:  * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
krh@248:  * Copyright (C) 2008  Red Hat, Inc
krh@248:  *
krh@248:  * This program is free software; you can redistribute it and/or modify
krh@248:  * it under the terms of the GNU General Public License as published by
krh@248:  * the Free Software Foundation; either version 2 of the License, or
krh@248:  * (at your option) any later version.
krh@248:  *
krh@248:  * This program is distributed in the hope that it will be useful,
krh@248:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
krh@248:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
krh@248:  * GNU General Public License for more details.
krh@248:  *
krh@248:  * You should have received a copy of the GNU General Public License along
krh@248:  * with this program; if not, write to the Free Software Foundation, Inc.,
krh@248:  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
krh@248:  */
krh@248: 
krh@248: #include <string.h>
krh@248: #include "razor-internal.h"
krh@248: #include "razor.h"
krh@248: 
krh@248: #define UPSTREAM_SOURCE 0x80
krh@248: 
krh@248: struct source {
krh@248: 	struct razor_set *set;
krh@248: 	uint32_t *property_map;
krh@248: 	uint32_t *file_map;
krh@248: };
krh@248: 
krh@248: struct razor_merger {
krh@248: 	struct razor_set *set;
krh@248: 	struct hashtable table;
krh@248: 	struct source source1;
krh@248: 	struct source source2;
krh@248: };
krh@248: 
krh@248: struct razor_merger *
krh@248: razor_merger_create(struct razor_set *set1, struct razor_set *set2)
krh@248: {
krh@248: 	struct razor_merger *merger;
krh@248: 	int count;
krh@248: 	size_t size;
krh@248: 
krh@248: 	merger = zalloc(sizeof *merger);
krh@248: 	merger->set = razor_set_create();
krh@248: 	hashtable_init(&merger->table, &merger->set->string_pool);
krh@248: 
krh@248: 	merger->source1.set = set1;
krh@248: 	count = set1->properties.size / sizeof (struct razor_property);
krh@248: 	size = count * sizeof merger->source1.property_map[0];
krh@248: 	merger->source1.property_map = zalloc(size);
krh@248: 	count = set1->files.size / sizeof (struct razor_entry);
krh@248: 	size = count * sizeof merger->source1.file_map[0];
krh@248: 	merger->source1.file_map = zalloc(size);
krh@248: 
krh@248: 	merger->source2.set = set2;
krh@248: 	count = set2->properties.size / sizeof (struct razor_property);
krh@248: 	size = count * sizeof merger->source2.property_map[0];
krh@248: 	merger->source2.property_map = zalloc(size);
krh@248: 	count = set2->files.size / sizeof (struct razor_entry);
krh@248: 	size = count * sizeof merger->source2.file_map[0];
krh@248: 	merger->source2.file_map = zalloc(size);
krh@248: 
krh@248: 	return merger;
krh@248: }
krh@248: 
krh@248: void
krh@248: razor_merger_add_package(struct razor_merger *merger,
krh@248: 			 struct razor_package *package)
krh@248: {
krh@248: 	char *pool;
krh@248: 	struct list *r;
krh@248: 	struct razor_package *p;
krh@248: 	struct razor_set *set1;
krh@248: 	struct source *source;
krh@248: 	uint32_t flags;
krh@248: 
krh@248: 	set1 = merger->source1.set;
krh@248: 	if (set1->packages.data <= (void *) package &&
krh@248: 	    (void *) package < set1->packages.data + set1->packages.size) {
krh@248: 		source = &merger->source1;
krh@248: 		flags = 0;
krh@248: 	} else {
krh@248: 		source = &merger->source2;
krh@248: 		flags = UPSTREAM_SOURCE;
krh@248: 	}
krh@248: 
krh@248: 	pool = source->set->string_pool.data;
krh@248: 	p = array_add(&merger->set->packages, sizeof *p);
krh@248: 	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
krh@248: 	p->flags = flags;
krh@248: 	p->version = hashtable_tokenize(&merger->table,
krh@248: 					&pool[package->version]);
krh@248: 	p->arch = hashtable_tokenize(&merger->table,
krh@248: 				     &pool[package->arch]);
krh@248: 
krh@248: 	p->properties = package->properties;
krh@248: 	r = list_first(&package->properties, &source->set->property_pool);
krh@248: 	while (r) {
krh@248: 		source->property_map[r->data] = 1;
krh@248: 		r = list_next(r);
krh@248: 	}
krh@248: 
krh@248: 	p->files = package->files;
krh@248: 	r = list_first(&package->files, &source->set->file_pool);
krh@248: 	while (r) {
krh@248: 		source->file_map[r->data] = 1;
krh@248: 		r = list_next(r);
krh@248: 	}
krh@248: }
krh@248: 
krh@248: static uint32_t
krh@248: add_property(struct razor_merger *merger,
krh@248: 	     const char *name, uint32_t flags, const char *version)
krh@248: {
krh@248: 	struct razor_property *p;
krh@248: 
krh@248: 	p = array_add(&merger->set->properties, sizeof *p);
krh@248: 	p->name = hashtable_tokenize(&merger->table, name);
krh@248: 	p->flags = flags;
krh@248: 	p->version = hashtable_tokenize(&merger->table, version);
krh@248: 
krh@248: 	return p - (struct razor_property *) merger->set->properties.data;
krh@248: }
krh@248: 
krh@248: static void
krh@248: merge_properties(struct razor_merger *merger)
krh@248: {
krh@248: 	struct razor_property *p1, *p2;
krh@248: 	struct razor_set *set1, *set2;
krh@248: 	uint32_t *map1, *map2;
krh@248: 	int i, j, cmp, count1, count2;
krh@248: 	char *pool1, *pool2;
krh@248: 
krh@248: 	set1 = merger->source1.set;
krh@248: 	set2 = merger->source2.set;
krh@248: 	map1 = merger->source1.property_map;
krh@248: 	map2 = merger->source2.property_map;
krh@248: 
krh@248: 	i = 0;
krh@248: 	j = 0;
krh@248: 	pool1 = set1->string_pool.data;
krh@248: 	pool2 = set2->string_pool.data;
krh@248: 
krh@248: 	count1 = set1->properties.size / sizeof *p1;
krh@248: 	count2 = set2->properties.size / sizeof *p2;
krh@248: 	while (i < count1 || j < count2) {
krh@248: 		if (i < count1 && map1[i] == 0) {
krh@248: 			i++;
krh@248: 			continue;
krh@248: 		}
krh@248: 		if (j < count2 && map2[j] == 0) {
krh@248: 			j++;
krh@248: 			continue;
krh@248: 		}
krh@248: 		p1 = (struct razor_property *) set1->properties.data + i;
krh@248: 		p2 = (struct razor_property *) set2->properties.data + j;
krh@248: 		if (i < count1 && j < count2)
krh@248: 			cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
krh@248: 		else if (i < count1)
krh@248: 			cmp = -1;
krh@248: 		else
krh@248: 			cmp = 1;
krh@248: 		if (cmp == 0)
krh@248: 			cmp = p1->flags - p2->flags;
krh@248: 		if (cmp == 0)
krh@248: 			cmp = razor_versioncmp(&pool1[p1->version],
krh@248: 					       &pool2[p2->version]);
krh@248: 		if (cmp < 0) {
krh@248: 			map1[i++] = add_property(merger,
krh@248: 						 &pool1[p1->name],
krh@248: 						 p1->flags,
krh@248: 						 &pool1[p1->version]);
krh@248: 		} else if (cmp > 0) {
krh@248: 			map2[j++] = add_property(merger,
krh@248: 						 &pool2[p2->name],
krh@248: 						 p2->flags,
krh@248: 						 &pool2[p2->version]);
krh@248: 		} else  {
krh@248: 			map1[i++] = map2[j++] =
krh@248: 				add_property(merger,
krh@248: 					     &pool1[p1->name],
krh@248: 					     p1->flags,
krh@248: 					     &pool1[p1->version]);
krh@248: 		}
krh@248: 	}
krh@248: }
krh@248: 
krh@248: static void
krh@248: emit_properties(struct list_head *properties, struct array *source_pool,
krh@248: 		uint32_t *map, struct array *pool)
krh@248: {
krh@248: 	uint32_t r;
krh@248: 	struct list *p, *q;
krh@248: 
krh@248: 	r = pool->size / sizeof *q;
krh@248: 	p = list_first(properties, source_pool);
krh@248: 	while (p) {
krh@248: 		q = array_add(pool, sizeof *q);
krh@248: 		q->data = map[p->data];
krh@248: 		q->flags = p->flags;
krh@248: 		p = list_next(p);
krh@248: 	}
krh@248: 
krh@248: 	list_set_ptr(properties, r);
krh@248: }
krh@248: 
krh@248: static uint32_t
krh@248: add_file(struct razor_merger *merger, const char *name)
krh@248: {
krh@248: 	struct razor_entry *e;
krh@248: 
krh@248: 	e = array_add(&merger->set->files, sizeof *e);
krh@248: 	e->name = hashtable_tokenize(&merger->table, name);
krh@248: 	e->flags = 0;
krh@248: 	e->start = 0;
krh@248: 
krh@248: 	return e - (struct razor_entry *)merger->set->files.data;
krh@248: }
krh@248: 
krh@248: /* FIXME. Blah */
krh@248: static int
krh@248: fix_file_map(uint32_t *map,
krh@248: 	     struct razor_entry *files,
krh@248: 	     struct razor_entry *top)
krh@248: {
krh@248: 	uint32_t e;
krh@248: 	int found_file = 0;
krh@248: 
krh@248: 	e = top->start;
krh@248: 	do {
krh@248: 		if (files[e].start)
krh@248: 			fix_file_map(map, files, &files[e]);
krh@248: 		if (map[e])
krh@248: 			found_file = 1;
krh@248: 	} while (!(files[e++].flags & RAZOR_ENTRY_LAST));
krh@248: 
krh@248: 	if (found_file)
krh@248: 		map[top - files] = 1;
krh@248: 	return found_file;
krh@248: }
krh@248: 
krh@248: struct merge_directory {
krh@248: 	uint32_t merged, dir1, dir2;
krh@248: };
krh@248: 
krh@248: static void
krh@248: merge_one_directory(struct razor_merger *merger, struct merge_directory *md)
krh@248: {
krh@248: 	struct razor_entry *root1, *root2, *mroot, *e1, *e2;
krh@248: 	struct razor_set *set1, *set2;
krh@248: 	struct array merge_stack;
krh@248: 	struct merge_directory *child_md, *end_md;
krh@248: 	uint32_t *map1, *map2, start, last;
krh@248: 	int cmp;
krh@248: 	char *pool1, *pool2;
krh@248: 
krh@248: 	set1 = merger->source1.set;
krh@248: 	set2 = merger->source2.set;
krh@248: 	map1 = merger->source1.file_map;
krh@248: 	map2 = merger->source2.file_map;
krh@313: 	pool1 = set1->file_string_pool.data;
krh@313: 	pool2 = set2->file_string_pool.data;
krh@248: 	root1 = (struct razor_entry *) set1->files.data;
krh@248: 	root2 = (struct razor_entry *) set2->files.data;
krh@248: 
krh@248: 	array_init(&merge_stack);
krh@248: 
krh@248: 	start = merger->set->files.size / sizeof (struct razor_entry);
krh@248: 	last = 0;
krh@248: 	e1 = md->dir1 ? root1 + md->dir1 : NULL;
krh@248: 	e2 = md->dir2 ? root2 + md->dir2 : NULL;
krh@248: 	while (e1 || e2) {
krh@248: 		if (!e2 && !map1[e1 - root1]) {
krh@248: 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e1 = NULL;
krh@248: 			continue;
krh@248: 		}
krh@248: 		if (!e1 && !map2[e2 - root2]) {
krh@248: 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e2 = NULL;
krh@248: 			continue;
krh@248: 		}
krh@248: 		if (e1 && !map1[e1 - root1] &&
krh@314: 		    e2 && !map2[e2 - root2]) {
krh@248: 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e1 = NULL;
krh@248: 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e2 = NULL;
krh@248: 			continue;
krh@248: 		}
krh@248: 
krh@248: 		if (!e1)
krh@248: 			cmp = 1;
krh@248: 		else if (!e2)
krh@248: 			cmp = -1;
krh@248: 		else {
krh@248: 			cmp = strcmp (&pool1[e1->name],
krh@248: 				      &pool2[e2->name]);
krh@248: 		}
krh@248: 
krh@248: 		if (cmp < 0) {
krh@248: 			if (map1[e1 - root1]) {
krh@248: 				map1[e1 - root1] = last =
krh@248: 					add_file(merger, &pool1[e1->name]);
krh@248: 				if (e1->start) {
krh@248: 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
krh@248: 					child_md->merged = last;
krh@248: 					child_md->dir1 = e1->start;
krh@248: 					child_md->dir2 = 0;
krh@248: 				}
krh@248: 			}
krh@248: 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e1 = NULL;
krh@248: 		} else if (cmp > 0) {
krh@248: 			if (map2[e2 - root2]) {
krh@248: 				map2[e2 - root2] = last =
krh@248: 					add_file(merger, &pool2[e2->name]);
krh@248: 				if (e2->start) {
krh@248: 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
krh@248: 					child_md->merged = last;
krh@248: 					child_md->dir1 = 0;
krh@248: 					child_md->dir2 = e2->start;
krh@248: 				}
krh@248: 			}
krh@248: 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e2 = NULL;
krh@248: 		} else {
krh@248: 			map1[e1 - root1] = map2[e2- root2] = last =
krh@248: 				add_file(merger, &pool1[e1->name]);
krh@248: 			if (e1->start || e2->start) {
krh@248: 				child_md = array_add(&merge_stack, sizeof (struct merge_directory));
krh@248: 				child_md->merged = last;
krh@248: 				child_md->dir1 = e1->start;
krh@248: 				child_md->dir2 = e2->start;
krh@248: 			}
krh@248: 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e1 = NULL;
krh@248: 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248: 				e2 = NULL;
krh@248: 		}
krh@248: 	}
krh@248: 
krh@248: 	mroot = (struct razor_entry *)merger->set->files.data;
krh@248: 	if (last) {
krh@248: 		mroot[last].flags = RAZOR_ENTRY_LAST;
krh@248: 		mroot[md->merged].start = start;
krh@248: 	} else
krh@248: 		mroot[md->merged].start = 0;
krh@248: 
krh@248: 	end_md = merge_stack.data + merge_stack.size;
krh@248: 	for (child_md = merge_stack.data; child_md < end_md; child_md++)
krh@248: 		merge_one_directory(merger, child_md);
krh@248: 	array_release(&merge_stack);
krh@248: }
krh@248: 
krh@248: static void
krh@248: merge_files(struct razor_merger *merger)
krh@248: {
krh@248: 	struct razor_entry *root;
krh@248: 	struct merge_directory md;
krh@248: 	uint32_t *map1, *map2;
krh@248: 
krh@248: 	map1 = merger->source1.file_map;
krh@248: 	map2 = merger->source2.file_map;
krh@248: 
krh@248: 	md.merged = 0;
krh@248: 
krh@248: 	if (merger->source1.set->files.size) {
krh@248: 		root = (struct razor_entry *) merger->source1.set->files.data;
krh@248: 		if (root->start)
krh@248: 			fix_file_map(map1, root, root);
krh@248: 		md.dir1 = root->start;
krh@248: 	} else
krh@248: 		md.dir1 = 0;
krh@248: 
krh@248: 	if (merger->source2.set->files.size) {
krh@248: 		root = (struct razor_entry *) merger->source2.set->files.data;
krh@248: 		if (root->start)
krh@248: 			fix_file_map(map2, root, root);
krh@248: 		md.dir2 = root->start;
krh@248: 	} else
krh@248: 		md.dir2 = 0;
krh@248: 
krh@248: 	merge_one_directory(merger, &md);
krh@248: }
krh@248: 
krh@248: static void
krh@248: emit_files(struct list_head *files, struct array *source_pool,
krh@248: 	   uint32_t *map, struct array *pool)
krh@248: {
krh@248: 	uint32_t r;
krh@248: 	struct list *p, *q;
krh@248: 
krh@248: 	r = pool->size / sizeof *q;
krh@248: 	p = list_first(files, source_pool);
krh@248: 	while (p) {
krh@248: 		q = array_add(pool, sizeof *q);
krh@248: 		q->data = map[p->data];
krh@248: 		q->flags = p->flags;
krh@248: 		p = list_next(p);
krh@248: 	}
krh@248: 
krh@248: 	list_set_ptr(files, r);
krh@248: }
krh@248: 
krh@248: /* Rebuild property->packages maps.  We can't just remap these, as a
krh@248:  * property may have lost or gained a number of packages.  Allocate an
krh@248:  * array per property and loop through the packages and add them to
krh@248:  * the arrays for their properties. */
krh@248: static void
krh@248: rebuild_property_package_lists(struct razor_set *set)
krh@248: {
krh@248: 	struct array *pkgs, *a;
krh@248: 	struct razor_package *pkg, *pkg_end;
krh@248: 	struct razor_property *prop, *prop_end;
krh@248: 	struct list *r;
krh@248: 	uint32_t *q;
krh@248: 	int count;
krh@248: 
krh@248: 	count = set->properties.size / sizeof (struct razor_property);
krh@248: 	pkgs = zalloc(count * sizeof *pkgs);
krh@248: 	pkg_end = set->packages.data + set->packages.size;
krh@248: 
krh@248: 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
krh@248: 		r = list_first(&pkg->properties, &set->property_pool);
krh@248: 		while (r) {
krh@248: 			q = array_add(&pkgs[r->data], sizeof *q);
krh@248: 			*q = pkg - (struct razor_package *) set->packages.data;
krh@248: 			r = list_next(r);
krh@248: 		}
krh@248: 	}
krh@248: 
krh@248: 	prop_end = set->properties.data + set->properties.size;
krh@248: 	a = pkgs;
krh@248: 	for (prop = set->properties.data; prop < prop_end; prop++, a++) {
krh@248: 		list_set_array(&prop->packages, &set->package_pool, a, 0);
krh@248: 		array_release(a);
krh@248: 	}
krh@248: 	free(pkgs);
krh@248: }
krh@248: 
krh@248: static void
krh@248: rebuild_file_package_lists(struct razor_set *set)
krh@248: {
krh@248: 	struct array *pkgs, *a;
krh@248: 	struct razor_package *pkg, *pkg_end;
krh@248: 	struct razor_entry *entry, *entry_end;
krh@248: 	struct list *r;
krh@248: 	uint32_t *q;
krh@248: 	int count;
krh@248: 
krh@248: 	count = set->files.size / sizeof (struct razor_entry);
krh@248: 	pkgs = zalloc(count * sizeof *pkgs);
krh@248: 	pkg_end = set->packages.data + set->packages.size;
krh@248: 
krh@248: 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
krh@248: 		r = list_first(&pkg->files, &set->file_pool);
krh@248: 		while (r) {
krh@248: 			q = array_add(&pkgs[r->data], sizeof *q);
krh@248: 			*q = pkg - (struct razor_package *) set->packages.data;
krh@248: 			r = list_next(r);
krh@248: 		}
krh@248: 	}
krh@248: 
krh@248: 	entry_end = set->files.data + set->files.size;
krh@248: 	a = pkgs;
krh@248: 	for (entry = set->files.data; entry < entry_end; entry++, a++) {
krh@248: 		list_set_array(&entry->packages, &set->package_pool, a, 0);
krh@248: 		array_release(a);
krh@248: 	}
krh@248: 	free(pkgs);
krh@248: }
krh@248: 
krh@248: struct razor_set *
krh@248: razor_merger_finish(struct razor_merger *merger)
krh@248: {
krh@248: 	struct razor_set *result;
krh@248: 	struct razor_package *p, *pend;
krh@248: 
krh@248: 	/* As we built the package list, we filled out a bitvector of
krh@248: 	 * the properties that are referenced by the packages in the
krh@248: 	 * new set.  Now we do a parallel loop through the properties
krh@248: 	 * and emit those marked in the bit vector to the new set.  In
krh@248: 	 * the process, we update the bit vector to actually map from
krh@248: 	 * indices in the old property list to indices in the new
krh@248: 	 * property list for both sets. */
krh@248: 
krh@248: 	merge_properties(merger);
krh@248: 	merge_files(merger);
krh@248: 
krh@248: 	/* Now we loop through the packages again and emit the
krh@248: 	 * property lists, remapped to point to the new properties. */
krh@248: 
krh@248: 	pend = merger->set->packages.data + merger->set->packages.size;
krh@248: 	for (p = merger->set->packages.data; p < pend; p++) {
krh@248: 		struct source *src;
krh@248: 
krh@248: 		if (p->flags & UPSTREAM_SOURCE)
krh@248: 			src = &merger->source2;
krh@248: 		else
krh@248: 			src = &merger->source1;
krh@248: 
krh@248: 		emit_properties(&p->properties,
krh@248: 				&src->set->property_pool,
krh@248: 				src->property_map,
krh@248: 				&merger->set->property_pool);
krh@248: 		emit_files(&p->files,
krh@248: 			   &src->set->file_pool,
krh@248: 			   src->file_map,
krh@248: 			   &merger->set->file_pool);
krh@248: 		p->flags &= ~UPSTREAM_SOURCE;
krh@248: 	}
krh@248: 
krh@248: 	rebuild_property_package_lists(merger->set);
krh@248: 	rebuild_file_package_lists(merger->set);
krh@248: 
krh@248: 	result = merger->set;
krh@248: 	hashtable_release(&merger->table);
krh@248: 	free(merger);
krh@248: 
krh@248: 	return result;
krh@248: }