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

author	J. Ali Harlow <ali@juiblex.co.uk>
	Fri Apr 17 21:09:55 2009 +0100 (2009-04-17)
changeset 357	39f8dab73084
parent 314	df5dc9230730
child 359	c9c90315ea24
permissions	-rw-r--r--