razor: librazor/merger.c@ccb1c11968ab (annotated)

krh@248	1	/*
krh@248	2	* Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
krh@248	3	* Copyright (C) 2008 Red Hat, Inc
krh@248	4	*
krh@248	5	* This program is free software; you can redistribute it and/or modify
krh@248	6	* it under the terms of the GNU General Public License as published by
krh@248	7	* the Free Software Foundation; either version 2 of the License, or
krh@248	8	* (at your option) any later version.
krh@248	9	*
krh@248	10	* This program is distributed in the hope that it will be useful,
krh@248	11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
krh@248	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
krh@248	13	* GNU General Public License for more details.
krh@248	14	*
krh@248	15	* You should have received a copy of the GNU General Public License along
krh@248	16	* with this program; if not, write to the Free Software Foundation, Inc.,
krh@248	17	* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
krh@248	18	*/
krh@248	19
krh@248	20	#include <string.h>
krh@248	21	#include "razor-internal.h"
krh@248	22	#include "razor.h"
krh@248	23
krh@248	24	#define UPSTREAM_SOURCE 0x80
krh@248	25
krh@248	26	struct source {
krh@248	27	struct razor_set *set;
krh@248	28	uint32_t *property_map;
krh@248	29	uint32_t *file_map;
krh@248	30	};
krh@248	31
krh@248	32	struct razor_merger {
krh@248	33	struct razor_set *set;
krh@248	34	struct hashtable table;
krh@248	35	struct source source1;
krh@248	36	struct source source2;
krh@248	37	};
krh@248	38
krh@248	39	struct razor_merger *
krh@248	40	razor_merger_create(struct razor_set set1, struct razor_set set2)
krh@248	41	{
krh@248	42	struct razor_merger *merger;
krh@248	43	int count;
krh@248	44	size_t size;
krh@248	45
krh@248	46	merger = zalloc(sizeof *merger);
krh@248	47	merger->set = razor_set_create();
krh@248	48	hashtable_init(&merger->table, &merger->set->string_pool);
krh@248	49
krh@248	50	merger->source1.set = set1;
krh@248	51	count = set1->properties.size / sizeof (struct razor_property);
krh@248	52	size = count * sizeof merger->source1.property_map[0];
krh@248	53	merger->source1.property_map = zalloc(size);
krh@248	54	count = set1->files.size / sizeof (struct razor_entry);
krh@248	55	size = count * sizeof merger->source1.file_map[0];
krh@248	56	merger->source1.file_map = zalloc(size);
krh@248	57
krh@248	58	merger->source2.set = set2;
krh@248	59	count = set2->properties.size / sizeof (struct razor_property);
krh@248	60	size = count * sizeof merger->source2.property_map[0];
krh@248	61	merger->source2.property_map = zalloc(size);
krh@248	62	count = set2->files.size / sizeof (struct razor_entry);
krh@248	63	size = count * sizeof merger->source2.file_map[0];
krh@248	64	merger->source2.file_map = zalloc(size);
krh@248	65
krh@248	66	return merger;
krh@248	67	}
krh@248	68
krh@248	69	void
krh@248	70	razor_merger_add_package(struct razor_merger *merger,
krh@248	71	struct razor_package *package)
krh@248	72	{
krh@248	73	char *pool;
krh@248	74	struct list *r;
krh@248	75	struct razor_package *p;
krh@248	76	struct razor_set *set1;
krh@248	77	struct source *source;
krh@248	78	uint32_t flags;
krh@248	79
krh@248	80	set1 = merger->source1.set;
krh@248	81	if (set1->packages.data <= (void *) package &&
krh@248	82	(void *) package < set1->packages.data + set1->packages.size) {
krh@248	83	source = &merger->source1;
krh@248	84	flags = 0;
krh@248	85	} else {
krh@248	86	source = &merger->source2;
krh@248	87	flags = UPSTREAM_SOURCE;
krh@248	88	}
krh@248	89
krh@248	90	pool = source->set->string_pool.data;
krh@248	91	p = array_add(&merger->set->packages, sizeof *p);
krh@248	92	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
krh@248	93	p->flags = flags;
krh@248	94	p->version = hashtable_tokenize(&merger->table,
krh@248	95	&pool[package->version]);
krh@248	96	p->arch = hashtable_tokenize(&merger->table,
krh@248	97	&pool[package->arch]);
krh@248	98
krh@248	99	p->properties = package->properties;
krh@248	100	r = list_first(&package->properties, &source->set->property_pool);
krh@248	101	while (r) {
krh@248	102	source->property_map[r->data] = 1;
krh@248	103	r = list_next(r);
krh@248	104	}
krh@248	105
krh@248	106	p->files = package->files;
krh@248	107	r = list_first(&package->files, &source->set->file_pool);
krh@248	108	while (r) {
krh@248	109	source->file_map[r->data] = 1;
krh@248	110	r = list_next(r);
krh@248	111	}
krh@248	112	}
krh@248	113
krh@248	114	static uint32_t
krh@248	115	add_property(struct razor_merger *merger,
krh@248	116	const char name, uint32_t flags, const char version)
krh@248	117	{
krh@248	118	struct razor_property *p;
krh@248	119
krh@248	120	p = array_add(&merger->set->properties, sizeof *p);
krh@248	121	p->name = hashtable_tokenize(&merger->table, name);
krh@248	122	p->flags = flags;
krh@248	123	p->version = hashtable_tokenize(&merger->table, version);
krh@248	124
krh@248	125	return p - (struct razor_property *) merger->set->properties.data;
krh@248	126	}
krh@248	127
krh@248	128	static void
krh@248	129	merge_properties(struct razor_merger *merger)
krh@248	130	{
krh@248	131	struct razor_property p1, p2;
krh@248	132	struct razor_set set1, set2;
krh@248	133	uint32_t map1, map2;
krh@248	134	int i, j, cmp, count1, count2;
krh@248	135	char pool1, pool2;
krh@248	136
krh@248	137	set1 = merger->source1.set;
krh@248	138	set2 = merger->source2.set;
krh@248	139	map1 = merger->source1.property_map;
krh@248	140	map2 = merger->source2.property_map;
krh@248	141
krh@248	142	i = 0;
krh@248	143	j = 0;
krh@248	144	pool1 = set1->string_pool.data;
krh@248	145	pool2 = set2->string_pool.data;
krh@248	146
krh@248	147	count1 = set1->properties.size / sizeof *p1;
krh@248	148	count2 = set2->properties.size / sizeof *p2;
krh@248	149	while (i < count1 \|\| j < count2) {
krh@248	150	if (i < count1 && map1[i] == 0) {
krh@248	151	i++;
krh@248	152	continue;
krh@248	153	}
krh@248	154	if (j < count2 && map2[j] == 0) {
krh@248	155	j++;
krh@248	156	continue;
krh@248	157	}
krh@248	158	p1 = (struct razor_property *) set1->properties.data + i;
krh@248	159	p2 = (struct razor_property *) set2->properties.data + j;
krh@248	160	if (i < count1 && j < count2)
krh@248	161	cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
krh@248	162	else if (i < count1)
krh@248	163	cmp = -1;
krh@248	164	else
krh@248	165	cmp = 1;
krh@248	166	if (cmp == 0)
krh@248	167	cmp = p1->flags - p2->flags;
krh@248	168	if (cmp == 0)
krh@248	169	cmp = razor_versioncmp(&pool1[p1->version],
krh@248	170	&pool2[p2->version]);
krh@248	171	if (cmp < 0) {
krh@248	172	map1[i++] = add_property(merger,
krh@248	173	&pool1[p1->name],
krh@248	174	p1->flags,
krh@248	175	&pool1[p1->version]);
krh@248	176	} else if (cmp > 0) {
krh@248	177	map2[j++] = add_property(merger,
krh@248	178	&pool2[p2->name],
krh@248	179	p2->flags,
krh@248	180	&pool2[p2->version]);
krh@248	181	} else {
krh@248	182	map1[i++] = map2[j++] =
krh@248	183	add_property(merger,
krh@248	184	&pool1[p1->name],
krh@248	185	p1->flags,
krh@248	186	&pool1[p1->version]);
krh@248	187	}
krh@248	188	}
krh@248	189	}
krh@248	190
krh@248	191	static void
krh@248	192	emit_properties(struct list_head properties, struct array source_pool,
krh@248	193	uint32_t map, struct array pool)
krh@248	194	{
krh@248	195	uint32_t r;
krh@248	196	struct list p, q;
krh@248	197
krh@248	198	r = pool->size / sizeof *q;
krh@248	199	p = list_first(properties, source_pool);
krh@248	200	while (p) {
krh@248	201	q = array_add(pool, sizeof *q);
krh@248	202	q->data = map[p->data];
krh@248	203	q->flags = p->flags;
krh@248	204	p = list_next(p);
krh@248	205	}
krh@248	206
krh@248	207	list_set_ptr(properties, r);
krh@248	208	}
krh@248	209
krh@248	210	static uint32_t
krh@248	211	add_file(struct razor_merger merger, const char name)
krh@248	212	{
krh@248	213	struct razor_entry *e;
krh@248	214
krh@248	215	e = array_add(&merger->set->files, sizeof *e);
krh@248	216	e->name = hashtable_tokenize(&merger->table, name);
krh@248	217	e->flags = 0;
krh@248	218	e->start = 0;
krh@248	219
krh@248	220	return e - (struct razor_entry *)merger->set->files.data;
krh@248	221	}
krh@248	222
krh@248	223	/* FIXME. Blah */
krh@248	224	static int
krh@248	225	fix_file_map(uint32_t *map,
krh@248	226	struct razor_entry *files,
krh@248	227	struct razor_entry *top)
krh@248	228	{
krh@248	229	uint32_t e;
krh@248	230	int found_file = 0;
krh@248	231
krh@248	232	e = top->start;
krh@248	233	do {
krh@248	234	if (files[e].start)
krh@248	235	fix_file_map(map, files, &files[e]);
krh@248	236	if (map[e])
krh@248	237	found_file = 1;
krh@248	238	} while (!(files[e++].flags & RAZOR_ENTRY_LAST));
krh@248	239
krh@248	240	if (found_file)
krh@248	241	map[top - files] = 1;
krh@248	242	return found_file;
krh@248	243	}
krh@248	244
krh@248	245	struct merge_directory {
krh@248	246	uint32_t merged, dir1, dir2;
krh@248	247	};
krh@248	248
krh@248	249	static void
krh@248	250	merge_one_directory(struct razor_merger merger, struct merge_directory md)
krh@248	251	{
krh@248	252	struct razor_entry root1, root2, mroot, e1, *e2;
krh@248	253	struct razor_set set1, set2;
krh@248	254	struct array merge_stack;
krh@248	255	struct merge_directory child_md, end_md;
krh@248	256	uint32_t map1, map2, start, last;
krh@248	257	int cmp;
krh@248	258	char pool1, pool2;
krh@248	259
krh@248	260	set1 = merger->source1.set;
krh@248	261	set2 = merger->source2.set;
krh@248	262	map1 = merger->source1.file_map;
krh@248	263	map2 = merger->source2.file_map;
krh@248	264	pool1 = set1->string_pool.data;
krh@248	265	pool2 = set2->string_pool.data;
krh@248	266	root1 = (struct razor_entry *) set1->files.data;
krh@248	267	root2 = (struct razor_entry *) set2->files.data;
krh@248	268
krh@248	269	array_init(&merge_stack);
krh@248	270
krh@248	271	start = merger->set->files.size / sizeof (struct razor_entry);
krh@248	272	last = 0;
krh@248	273	e1 = md->dir1 ? root1 + md->dir1 : NULL;
krh@248	274	e2 = md->dir2 ? root2 + md->dir2 : NULL;
krh@248	275	while (e1 \|\| e2) {
krh@248	276	if (!e2 && !map1[e1 - root1]) {
krh@248	277	if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248	278	e1 = NULL;
krh@248	279	continue;
krh@248	280	}
krh@248	281	if (!e1 && !map2[e2 - root2]) {
krh@248	282	if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248	283	e2 = NULL;
krh@248	284	continue;
krh@248	285	}
krh@248	286	if (e1 && !map1[e1 - root1] &&
krh@248	287	e2 && !map1[e2 - root2]) {
krh@248	288	if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248	289	e1 = NULL;
krh@248	290	if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248	291	e2 = NULL;
krh@248	292	continue;
krh@248	293	}
krh@248	294
krh@248	295	if (!e1)
krh@248	296	cmp = 1;
krh@248	297	else if (!e2)
krh@248	298	cmp = -1;
krh@248	299	else {
krh@248	300	cmp = strcmp (&pool1[e1->name],
krh@248	301	&pool2[e2->name]);
krh@248	302	}
krh@248	303
krh@248	304	if (cmp < 0) {
krh@248	305	if (map1[e1 - root1]) {
krh@248	306	map1[e1 - root1] = last =
krh@248	307	add_file(merger, &pool1[e1->name]);
krh@248	308	if (e1->start) {
krh@248	309	child_md = array_add(&merge_stack, sizeof (struct merge_directory));
krh@248	310	child_md->merged = last;
krh@248	311	child_md->dir1 = e1->start;
krh@248	312	child_md->dir2 = 0;
krh@248	313	}
krh@248	314	}
krh@248	315	if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248	316	e1 = NULL;
krh@248	317	} else if (cmp > 0) {
krh@248	318	if (map2[e2 - root2]) {
krh@248	319	map2[e2 - root2] = last =
krh@248	320	add_file(merger, &pool2[e2->name]);
krh@248	321	if (e2->start) {
krh@248	322	child_md = array_add(&merge_stack, sizeof (struct merge_directory));
krh@248	323	child_md->merged = last;
krh@248	324	child_md->dir1 = 0;
krh@248	325	child_md->dir2 = e2->start;
krh@248	326	}
krh@248	327	}
krh@248	328	if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248	329	e2 = NULL;
krh@248	330	} else {
krh@248	331	map1[e1 - root1] = map2[e2- root2] = last =
krh@248	332	add_file(merger, &pool1[e1->name]);
krh@248	333	if (e1->start \|\| e2->start) {
krh@248	334	child_md = array_add(&merge_stack, sizeof (struct merge_directory));
krh@248	335	child_md->merged = last;
krh@248	336	child_md->dir1 = e1->start;
krh@248	337	child_md->dir2 = e2->start;
krh@248	338	}
krh@248	339	if ((e1++)->flags & RAZOR_ENTRY_LAST)
krh@248	340	e1 = NULL;
krh@248	341	if ((e2++)->flags & RAZOR_ENTRY_LAST)
krh@248	342	e2 = NULL;
krh@248	343	}
krh@248	344	}
krh@248	345
krh@248	346	mroot = (struct razor_entry *)merger->set->files.data;
krh@248	347	if (last) {
krh@248	348	mroot[last].flags = RAZOR_ENTRY_LAST;
krh@248	349	mroot[md->merged].start = start;
krh@248	350	} else
krh@248	351	mroot[md->merged].start = 0;
krh@248	352
krh@248	353	end_md = merge_stack.data + merge_stack.size;
krh@248	354	for (child_md = merge_stack.data; child_md < end_md; child_md++)
krh@248	355	merge_one_directory(merger, child_md);
krh@248	356	array_release(&merge_stack);
krh@248	357	}
krh@248	358
krh@248	359	static void
krh@248	360	merge_files(struct razor_merger *merger)
krh@248	361	{
krh@248	362	struct razor_entry *root;
krh@248	363	struct merge_directory md;
krh@248	364	uint32_t map1, map2;
krh@248	365
krh@248	366	map1 = merger->source1.file_map;
krh@248	367	map2 = merger->source2.file_map;
krh@248	368
krh@248	369	md.merged = 0;
krh@248	370
krh@248	371	if (merger->source1.set->files.size) {
krh@248	372	root = (struct razor_entry *) merger->source1.set->files.data;
krh@248	373	if (root->start)
krh@248	374	fix_file_map(map1, root, root);
krh@248	375	md.dir1 = root->start;
krh@248	376	} else
krh@248	377	md.dir1 = 0;
krh@248	378
krh@248	379	if (merger->source2.set->files.size) {
krh@248	380	root = (struct razor_entry *) merger->source2.set->files.data;
krh@248	381	if (root->start)
krh@248	382	fix_file_map(map2, root, root);
krh@248	383	md.dir2 = root->start;
krh@248	384	} else
krh@248	385	md.dir2 = 0;
krh@248	386
krh@248	387	merge_one_directory(merger, &md);
krh@248	388	}
krh@248	389
krh@248	390	static void
krh@248	391	emit_files(struct list_head files, struct array source_pool,
krh@248	392	uint32_t map, struct array pool)
krh@248	393	{
krh@248	394	uint32_t r;
krh@248	395	struct list p, q;
krh@248	396
krh@248	397	r = pool->size / sizeof *q;
krh@248	398	p = list_first(files, source_pool);
krh@248	399	while (p) {
krh@248	400	q = array_add(pool, sizeof *q);
krh@248	401	q->data = map[p->data];
krh@248	402	q->flags = p->flags;
krh@248	403	p = list_next(p);
krh@248	404	}
krh@248	405
krh@248	406	list_set_ptr(files, r);
krh@248	407	}
krh@248	408
krh@248	409	/* Rebuild property->packages maps. We can't just remap these, as a
krh@248	410	* property may have lost or gained a number of packages. Allocate an
krh@248	411	* array per property and loop through the packages and add them to
krh@248	412	* the arrays for their properties. */
krh@248	413	static void
krh@248	414	rebuild_property_package_lists(struct razor_set *set)
krh@248	415	{
krh@248	416	struct array pkgs, a;
krh@248	417	struct razor_package pkg, pkg_end;
krh@248	418	struct razor_property prop, prop_end;
krh@248	419	struct list *r;
krh@248	420	uint32_t *q;
krh@248	421	int count;
krh@248	422
krh@248	423	count = set->properties.size / sizeof (struct razor_property);
krh@248	424	pkgs = zalloc(count * sizeof *pkgs);
krh@248	425	pkg_end = set->packages.data + set->packages.size;
krh@248	426
krh@248	427	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
krh@248	428	r = list_first(&pkg->properties, &set->property_pool);
krh@248	429	while (r) {
krh@248	430	q = array_add(&pkgs[r->data], sizeof *q);
krh@248	431	q = pkg - (struct razor_package ) set->packages.data;
krh@248	432	r = list_next(r);
krh@248	433	}
krh@248	434	}
krh@248	435
krh@248	436	prop_end = set->properties.data + set->properties.size;
krh@248	437	a = pkgs;
krh@248	438	for (prop = set->properties.data; prop < prop_end; prop++, a++) {
krh@248	439	list_set_array(&prop->packages, &set->package_pool, a, 0);
krh@248	440	array_release(a);
krh@248	441	}
krh@248	442	free(pkgs);
krh@248	443	}
krh@248	444
krh@248	445	static void
krh@248	446	rebuild_file_package_lists(struct razor_set *set)
krh@248	447	{
krh@248	448	struct array pkgs, a;
krh@248	449	struct razor_package pkg, pkg_end;
krh@248	450	struct razor_entry entry, entry_end;
krh@248	451	struct list *r;
krh@248	452	uint32_t *q;
krh@248	453	int count;
krh@248	454
krh@248	455	count = set->files.size / sizeof (struct razor_entry);
krh@248	456	pkgs = zalloc(count * sizeof *pkgs);
krh@248	457	pkg_end = set->packages.data + set->packages.size;
krh@248	458
krh@248	459	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
krh@248	460	r = list_first(&pkg->files, &set->file_pool);
krh@248	461	while (r) {
krh@248	462	q = array_add(&pkgs[r->data], sizeof *q);
krh@248	463	q = pkg - (struct razor_package ) set->packages.data;
krh@248	464	r = list_next(r);
krh@248	465	}
krh@248	466	}
krh@248	467
krh@248	468	entry_end = set->files.data + set->files.size;
krh@248	469	a = pkgs;
krh@248	470	for (entry = set->files.data; entry < entry_end; entry++, a++) {
krh@248	471	list_set_array(&entry->packages, &set->package_pool, a, 0);
krh@248	472	array_release(a);
krh@248	473	}
krh@248	474	free(pkgs);
krh@248	475	}
krh@248	476
krh@248	477	struct razor_set *
krh@248	478	razor_merger_finish(struct razor_merger *merger)
krh@248	479	{
krh@248	480	struct razor_set *result;
krh@248	481	struct razor_package p, pend;
krh@248	482
krh@248	483	/* As we built the package list, we filled out a bitvector of
krh@248	484	* the properties that are referenced by the packages in the
krh@248	485	* new set. Now we do a parallel loop through the properties
krh@248	486	* and emit those marked in the bit vector to the new set. In
krh@248	487	* the process, we update the bit vector to actually map from
krh@248	488	* indices in the old property list to indices in the new
krh@248	489	* property list for both sets. */
krh@248	490
krh@248	491	merge_properties(merger);
krh@248	492	merge_files(merger);
krh@248	493
krh@248	494	/* Now we loop through the packages again and emit the
krh@248	495	* property lists, remapped to point to the new properties. */
krh@248	496
krh@248	497	pend = merger->set->packages.data + merger->set->packages.size;
krh@248	498	for (p = merger->set->packages.data; p < pend; p++) {
krh@248	499	struct source *src;
krh@248	500
krh@248	501	if (p->flags & UPSTREAM_SOURCE)
krh@248	502	src = &merger->source2;
krh@248	503	else
krh@248	504	src = &merger->source1;
krh@248	505
krh@248	506	emit_properties(&p->properties,
krh@248	507	&src->set->property_pool,
krh@248	508	src->property_map,
krh@248	509	&merger->set->property_pool);
krh@248	510	emit_files(&p->files,
krh@248	511	&src->set->file_pool,
krh@248	512	src->file_map,
krh@248	513	&merger->set->file_pool);
krh@248	514	p->flags &= ~UPSTREAM_SOURCE;
krh@248	515	}
krh@248	516
krh@248	517	rebuild_property_package_lists(merger->set);
krh@248	518	rebuild_file_package_lists(merger->set);
krh@248	519
krh@248	520	result = merger->set;
krh@248	521	hashtable_release(&merger->table);
krh@248	522	free(merger);
krh@248	523
krh@248	524	return result;
krh@248	525	}

author	Kristian H?gsberg <krh@redhat.com>
	Fri Jun 20 21:56:43 2008 -0400 (2008-06-20)
changeset 254	ccb1c11968ab
child 313	643c4a94c2ae
permissions	-rw-r--r--