Mercurialrazor / file revision
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | revisions | annotate | diff | raw
librazor/merger.c
author J. Ali Harlow <ali@juiblex.co.uk>
Mon Sep 28 17:37:12 2009 +0100 (2009-09-28)
changeset 386 3d3fab314c4e
parent 369 f8c27fe9fe63
child 394 afe520f454bd
permissions -rw-r--r--
Fix bug causing updates to fail on systems with multiple versions of a package installed 
     1 /*

     2  * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>

     3  * Copyright (C) 2008  Red Hat, Inc

     4  * Copyright (C) 2009  J. Ali Harlow <ali@juiblex.co.uk>

     5  *

     6  * This program is free software; you can redistribute it and/or modify

     7  * it under the terms of the GNU General Public License as published by

     8  * the Free Software Foundation; either version 2 of the License, or

     9  * (at your option) any later version.

    10  *

    11  * This program is distributed in the hope that it will be useful,

    12  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    14  * GNU General Public License for more details.

    15  *

    16  * You should have received a copy of the GNU General Public License along

    17  * with this program; if not, write to the Free Software Foundation, Inc.,

    18  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

    19  */

    20 

    21 #include <string.h>

    22 #include <assert.h>

    23 #include "razor-internal.h"

    24 #include "razor.h"

    25 

    26 #define UPSTREAM_SOURCE 0x80

    27 

    28 struct source {

    29 	struct razor_set *set;

    30 	uint32_t *property_map;

    31 	uint32_t *file_map;

    32 };

    33 

    34 struct razor_merger {

    35 	int committed;

    36 	struct razor_set *set;

    37 	struct hashtable table;

    38 	struct hashtable file_table;

    39 	struct source source1;

    40 	struct source source2;

    41 };

    42 

    43 struct razor_merger *

    44 razor_merger_create(struct razor_set *set1, struct razor_set *set2)

    45 {

    46 	struct razor_merger *merger;

    47 	int count;

    48 	size_t size;

    49 

    50 	merger = zalloc(sizeof *merger);

    51 	merger->set = razor_set_create();

    52 	hashtable_init(&merger->table, &merger->set->string_pool);

    53 	hashtable_init(&merger->file_table, &merger->set->file_string_pool);

    54 

    55 	merger->source1.set = set1;

    56 	count = set1->properties.size / sizeof (struct razor_property);

    57 	size = count * sizeof merger->source1.property_map[0];

    58 	merger->source1.property_map = zalloc(size);

    59 	count = set1->files.size / sizeof (struct razor_entry);

    60 	size = count * sizeof merger->source1.file_map[0];

    61 	merger->source1.file_map = zalloc(size);

    62 

    63 	merger->source2.set = set2;

    64 	count = set2->properties.size / sizeof (struct razor_property);

    65 	size = count * sizeof merger->source2.property_map[0];

    66 	merger->source2.property_map = zalloc(size);

    67 	count = set2->files.size / sizeof (struct razor_entry);

    68 	size = count * sizeof merger->source2.file_map[0];

    69 	merger->source2.file_map = zalloc(size);

    70 

    71 	return merger;

    72 }

    73 

    74 void

    75 razor_merger_add_package(struct razor_merger *merger,

    76 			 struct razor_package *package)

    77 {

    78 	char *pool, *s;

    79 	struct list *r;

    80 	struct razor_package *p;

    81 	struct razor_set *set1;

    82 	struct source *source;

    83 	uint32_t flags, *prefix;

    84 	struct array install_prefixes;

    85 

    86 	assert(merger->committed == 0);

    87 

    88 	set1 = merger->source1.set;

    89 	if (set1->packages.data <= (void *) package &&

    90 	    (void *) package < set1->packages.data + set1->packages.size) {

    91 		source = &merger->source1;

    92 		flags = 0;

    93 	} else {

    94 		source = &merger->source2;

    95 		flags = UPSTREAM_SOURCE;

    96 	}

    97 

    98 	pool = source->set->string_pool.data;

    99 	p = array_add(&merger->set->packages, sizeof *p);

   100 	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);

   101 	p->flags = flags;

   102 	p->version = hashtable_tokenize(&merger->table,

   103 					&pool[package->version]);

   104 	p->arch = hashtable_tokenize(&merger->table,

   105 				     &pool[package->arch]);

   106 

   107 	p->properties = package->properties;

   108 	r = list_first(&package->properties, &source->set->property_pool);

   109 	while (r) {

   110 		source->property_map[r->data] = 1;

   111 		r = list_next(r);

   112 	}

   113 

   114 	p->files = package->files;

   115 	r = list_first(&package->files, &source->set->file_pool);

   116 	while (r) {

   117 		source->file_map[r->data] = 1;

   118 		r = list_next(r);

   119 	}

   120 

   121 	array_init(&install_prefixes);

   122 	r = list_first(&package->install_prefixes, &source->set->prefix_pool);

   123 	while (r) {

   124 		s = (char *)source->set->string_pool.data + r->data;

   125 		prefix = array_add(&install_prefixes, sizeof *prefix);

   126 		*prefix = hashtable_tokenize(&merger->table, s);

   127 		r = list_next(r);

   128 	}

   129 	list_set_array(&p->install_prefixes, &merger->set->prefix_pool,

   130                        &install_prefixes, 0);

   131 	array_release(&install_prefixes);

   132 

   133 	p->preun.program = hashtable_tokenize(&merger->table,

   134 					      &pool[package->preun.program]);

   135 	p->preun.body = hashtable_tokenize(&merger->table,

   136 					   &pool[package->preun.body]);

   137 	p->postun.program = hashtable_tokenize(&merger->table,

   138 					       &pool[package->postun.program]);

   139 	p->postun.body = hashtable_tokenize(&merger->table,

   140 					    &pool[package->postun.body]);

   141 }

   142 

   143 static uint32_t

   144 add_property(struct razor_merger *merger,

   145 	     const char *name, uint32_t flags, const char *version)

   146 {

   147 	struct razor_property *p;

   148 

   149 	p = array_add(&merger->set->properties, sizeof *p);

   150 	p->name = hashtable_tokenize(&merger->table, name);

   151 	p->flags = flags;

   152 	p->version = hashtable_tokenize(&merger->table, version);

   153 

   154 	return p - (struct razor_property *) merger->set->properties.data;

   155 }

   156 

   157 static void

   158 merge_properties(struct razor_merger *merger)

   159 {

   160 	struct razor_property *p1, *p2;

   161 	struct razor_set *set1, *set2;

   162 	uint32_t *map1, *map2;

   163 	int i, j, cmp, count1, count2;

   164 	char *pool1, *pool2;

   165 

   166 	set1 = merger->source1.set;

   167 	set2 = merger->source2.set;

   168 	map1 = merger->source1.property_map;

   169 	map2 = merger->source2.property_map;

   170 

   171 	i = 0;

   172 	j = 0;

   173 	pool1 = set1->string_pool.data;

   174 	pool2 = set2->string_pool.data;

   175 

   176 	count1 = set1->properties.size / sizeof *p1;

   177 	count2 = set2->properties.size / sizeof *p2;

   178 	while (i < count1 || j < count2) {

   179 		if (i < count1 && map1[i] == 0) {

   180 			i++;

   181 			continue;

   182 		}

   183 		if (j < count2 && map2[j] == 0) {

   184 			j++;

   185 			continue;

   186 		}

   187 		p1 = (struct razor_property *) set1->properties.data + i;

   188 		p2 = (struct razor_property *) set2->properties.data + j;

   189 		if (i < count1 && j < count2)

   190 			cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);

   191 		else if (i < count1)

   192 			cmp = -1;

   193 		else

   194 			cmp = 1;

   195 		if (cmp == 0)

   196 			cmp = p1->flags - p2->flags;

   197 		if (cmp == 0)

   198 			cmp = razor_versioncmp(&pool1[p1->version],

   199 					       &pool2[p2->version]);

   200 		if (cmp < 0) {

   201 			map1[i++] = add_property(merger,

   202 						 &pool1[p1->name],

   203 						 p1->flags,

   204 						 &pool1[p1->version]);

   205 		} else if (cmp > 0) {

   206 			map2[j++] = add_property(merger,

   207 						 &pool2[p2->name],

   208 						 p2->flags,

   209 						 &pool2[p2->version]);

   210 		} else  {

   211 			map1[i++] = map2[j++] =

   212 				add_property(merger,

   213 					     &pool1[p1->name],

   214 					     p1->flags,

   215 					     &pool1[p1->version]);

   216 		}

   217 	}

   218 }

   219 

   220 static void

   221 emit_properties(struct list_head *properties, struct array *source_pool,

   222 		uint32_t *map, struct array *pool)

   223 {

   224 	uint32_t r;

   225 	struct list *p, *q;

   226 

   227 	r = pool->size / sizeof *q;

   228 	p = list_first(properties, source_pool);

   229 	while (p) {

   230 		q = array_add(pool, sizeof *q);

   231 		q->data = map[p->data];

   232 		q->flags = p->flags;

   233 		p = list_next(p);

   234 	}

   235 

   236 	list_set_ptr(properties, r);

   237 }

   238 

   239 static uint32_t

   240 add_file(struct razor_merger *merger, const char *name)

   241 {

   242 	struct razor_entry *e;

   243 

   244 	e = array_add(&merger->set->files, sizeof *e);

   245 	e->name = hashtable_tokenize(&merger->file_table, name);

   246 	e->flags = 0;

   247 	e->start = 0;

   248 

   249 	return e - (struct razor_entry *)merger->set->files.data;

   250 }

   251 

   252 /* FIXME. Blah */

   253 static int

   254 fix_file_map(uint32_t *map,

   255 	     struct razor_entry *files,

   256 	     struct razor_entry *top)

   257 {

   258 	uint32_t e;

   259 	int found_file = 0;

   260 

   261 	e = top - files;

   262 	do {

   263 		if (files[e].start &&

   264 		    fix_file_map(map, files, &files[files[e].start]))

   265 			map[e] = 1;

   266 		if (map[e])

   267 			found_file = 1;

   268 	} while (!(files[e++].flags & RAZOR_ENTRY_LAST));

   269 

   270 	return found_file;

   271 }

   272 

   273 struct merge_directory {

   274 	uint32_t merged, dir1, dir2;

   275 };

   276 

   277 static void

   278 merge_one_directory(struct razor_merger *merger, struct merge_directory *md)

   279 {

   280 	struct razor_entry *root1, *root2, *mroot, *e1, *e2;

   281 	struct razor_set *set1, *set2;

   282 	struct array merge_stack;

   283 	struct merge_directory *child_md, *end_md;

   284 	uint32_t *map1, *map2, start, last;

   285 	int cmp;

   286 	char *pool1, *pool2;

   287 

   288 	set1 = merger->source1.set;

   289 	set2 = merger->source2.set;

   290 	map1 = merger->source1.file_map;

   291 	map2 = merger->source2.file_map;

   292 	pool1 = set1->file_string_pool.data;

   293 	pool2 = set2->file_string_pool.data;

   294 	root1 = (struct razor_entry *) set1->files.data;

   295 	root2 = (struct razor_entry *) set2->files.data;

   296 

   297 	array_init(&merge_stack);

   298 

   299 	start = merger->set->files.size / sizeof (struct razor_entry);

   300 	last = 0xFFFFFFFF;

   301 	e1 = md->dir1 != 0xFFFFFFFF ? root1 + md->dir1 : NULL;

   302 	e2 = md->dir2 != 0xFFFFFFFF ? root2 + md->dir2 : NULL;

   303 	while (e1 || e2) {

   304 		if (!e2 && !map1[e1 - root1]) {

   305 			if ((e1++)->flags & RAZOR_ENTRY_LAST)

   306 				e1 = NULL;

   307 			continue;

   308 		}

   309 		if (!e1 && !map2[e2 - root2]) {

   310 			if ((e2++)->flags & RAZOR_ENTRY_LAST)

   311 				e2 = NULL;

   312 			continue;

   313 		}

   314 		if (e1 && !map1[e1 - root1] &&

   315 		    e2 && !map2[e2 - root2]) {

   316 			if ((e1++)->flags & RAZOR_ENTRY_LAST)

   317 				e1 = NULL;

   318 			if ((e2++)->flags & RAZOR_ENTRY_LAST)

   319 				e2 = NULL;

   320 			continue;

   321 		}

   322 

   323 		if (!e1)

   324 			cmp = 1;

   325 		else if (!e2)

   326 			cmp = -1;

   327 		else {

   328 			cmp = strcmp (&pool1[e1->name],

   329 				      &pool2[e2->name]);

   330 		}

   331 

   332 		if (cmp < 0) {

   333 			if (map1[e1 - root1]) {

   334 				map1[e1 - root1] = last =

   335 					add_file(merger, &pool1[e1->name]);

   336 				if (e1->start) {

   337 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));

   338 					child_md->merged = last;

   339 					child_md->dir1 = e1->start;

   340 					child_md->dir2 = 0xFFFFFFFF;

   341 				}

   342 			}

   343 			if ((e1++)->flags & RAZOR_ENTRY_LAST)

   344 				e1 = NULL;

   345 		} else if (cmp > 0) {

   346 			if (map2[e2 - root2]) {

   347 				map2[e2 - root2] = last =

   348 					add_file(merger, &pool2[e2->name]);

   349 				if (e2->start) {

   350 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));

   351 					child_md->merged = last;

   352 					child_md->dir1 = 0xFFFFFFFF;

   353 					child_md->dir2 = e2->start;

   354 				}

   355 			}

   356 			if ((e2++)->flags & RAZOR_ENTRY_LAST)

   357 				e2 = NULL;

   358 		} else {

   359 			map1[e1 - root1] = map2[e2- root2] = last =

   360 				add_file(merger, &pool1[e1->name]);

   361 			if (e1->start || e2->start) {

   362 				child_md = array_add(&merge_stack, sizeof (struct merge_directory));

   363 				child_md->merged = last;

   364 				child_md->dir1 = e1->start ? e1->start : 0xFFFFFFFF;

   365 				child_md->dir2 = e2->start ? e2->start : 0xFFFFFFFF;

   366 			}

   367 			if ((e1++)->flags & RAZOR_ENTRY_LAST)

   368 				e1 = NULL;

   369 			if ((e2++)->flags & RAZOR_ENTRY_LAST)

   370 				e2 = NULL;

   371 		}

   372 	}

   373 

   374 	mroot = (struct razor_entry *)merger->set->files.data;

   375 	if (last != 0xFFFFFFFF) {

   376 		mroot[last].flags = RAZOR_ENTRY_LAST;

   377 		mroot[md->merged].start = start;

   378 	}

   379 

   380 	end_md = merge_stack.data + merge_stack.size;

   381 	for (child_md = merge_stack.data; child_md < end_md; child_md++)

   382 		merge_one_directory(merger, child_md);

   383 	array_release(&merge_stack);

   384 }

   385 

   386 static void

   387 merge_files(struct razor_merger *merger)

   388 {

   389 	struct razor_entry *root;

   390 	struct merge_directory md;

   391 	uint32_t *map1, *map2;

   392 

   393 	map1 = merger->source1.file_map;

   394 	map2 = merger->source2.file_map;

   395 

   396 	md.merged = 0;

   397 

   398 	if (merger->source1.set->files.size) {

   399 		root = (struct razor_entry *) merger->source1.set->files.data;

   400 		if (root->start)

   401 			fix_file_map(map1, root, root);

   402 		md.dir1 = 0;

   403 	} else {

   404 		md.dir1 = 0xFFFFFFFF;

   405 	}

   406 

   407 	if (merger->source2.set->files.size) {

   408 		root = (struct razor_entry *) merger->source2.set->files.data;

   409 		if (root->start)

   410 			fix_file_map(map2, root, root);

   411 		md.dir2 = 0;

   412 	} else {

   413 		md.dir2 = 0xFFFFFFFF;

   414 	}

   415 

   416 	/* Remove the unnamed root which razor_set_create() added */

   417 	array_release(&merger->set->files);

   418 	array_init(&merger->set->files);

   419 

   420 	merge_one_directory(merger, &md);

   421 }

   422 

   423 static void

   424 emit_files(struct list_head *files, struct array *source_pool,

   425 	   uint32_t *map, struct array *pool)

   426 {

   427 	uint32_t r;

   428 	struct list *p, *q;

   429 

   430 	r = pool->size / sizeof *q;

   431 	p = list_first(files, source_pool);

   432 	while (p) {

   433 		q = array_add(pool, sizeof *q);

   434 		q->data = map[p->data];

   435 		q->flags = p->flags;

   436 		p = list_next(p);

   437 	}

   438 

   439 	list_set_ptr(files, r);

   440 }

   441 

   442 /* Rebuild property->packages maps.  We can't just remap these, as a

   443  * property may have lost or gained a number of packages.  Allocate an

   444  * array per property and loop through the packages and add them to

   445  * the arrays for their properties. */

   446 static void

   447 rebuild_property_package_lists(struct razor_set *set)

   448 {

   449 	struct array *pkgs, *a;

   450 	struct razor_package *pkg, *pkg_end;

   451 	struct razor_property *prop, *prop_end;

   452 	struct list *r;

   453 	uint32_t *q;

   454 	int count;

   455 

   456 	count = set->properties.size / sizeof (struct razor_property);

   457 	pkgs = zalloc(count * sizeof *pkgs);

   458 	pkg_end = set->packages.data + set->packages.size;

   459 

   460 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {

   461 		r = list_first(&pkg->properties, &set->property_pool);

   462 		while (r) {

   463 			q = array_add(&pkgs[r->data], sizeof *q);

   464 			*q = pkg - (struct razor_package *) set->packages.data;

   465 			r = list_next(r);

   466 		}

   467 	}

   468 

   469 	prop_end = set->properties.data + set->properties.size;

   470 	a = pkgs;

   471 	for (prop = set->properties.data; prop < prop_end; prop++, a++) {

   472 		list_set_array(&prop->packages, &set->package_pool, a, 0);

   473 		array_release(a);

   474 	}

   475 	free(pkgs);

   476 }

   477 

   478 static void

   479 rebuild_file_package_lists(struct razor_set *set)

   480 {

   481 	struct array *pkgs, *a;

   482 	struct razor_package *pkg, *pkg_end;

   483 	struct razor_entry *entry, *entry_end;

   484 	struct list *r;

   485 	uint32_t *q;

   486 	int count;

   487 

   488 	count = set->files.size / sizeof (struct razor_entry);

   489 	pkgs = zalloc(count * sizeof *pkgs);

   490 	pkg_end = set->packages.data + set->packages.size;

   491 

   492 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {

   493 		r = list_first(&pkg->files, &set->file_pool);

   494 		while (r) {

   495 			q = array_add(&pkgs[r->data], sizeof *q);

   496 			*q = pkg - (struct razor_package *) set->packages.data;

   497 			r = list_next(r);

   498 		}

   499 	}

   500 

   501 	entry_end = set->files.data + set->files.size;

   502 	a = pkgs;

   503 	for (entry = set->files.data; entry < entry_end; entry++, a++) {

   504 		list_set_array(&entry->packages, &set->package_pool, a, 0);

   505 		array_release(a);

   506 	}

   507 	free(pkgs);

   508 }

   509 

   510 struct razor_set *

   511 razor_merger_commit(struct razor_merger *merger)

   512 {

   513 	struct razor_package *p, *pend;

   514 

   515 	/* As we built the package list, we filled out a bitvector of

   516 	 * the properties that are referenced by the packages in the

   517 	 * new set.  Now we do a parallel loop through the properties

   518 	 * and emit those marked in the bit vector to the new set.  In

   519 	 * the process, we update the bit vector to actually map from

   520 	 * indices in the old property list to indices in the new

   521 	 * property list for both sets. */

   522 

   523 	merge_properties(merger);

   524 	merge_files(merger);

   525 

   526 	/* Now we loop through the packages again and emit the

   527 	 * property lists, remapped to point to the new properties. */

   528 

   529 	pend = merger->set->packages.data + merger->set->packages.size;

   530 	for (p = merger->set->packages.data; p < pend; p++) {

   531 		struct source *src;

   532 

   533 		if (p->flags & UPSTREAM_SOURCE)

   534 			src = &merger->source2;

   535 		else

   536 			src = &merger->source1;

   537 

   538 		emit_properties(&p->properties,

   539 				&src->set->property_pool,

   540 				src->property_map,

   541 				&merger->set->property_pool);

   542 		emit_files(&p->files,

   543 			   &src->set->file_pool,

   544 			   src->file_map,

   545 			   &merger->set->file_pool);

   546 		p->flags &= ~UPSTREAM_SOURCE;

   547 	}

   548 

   549 	rebuild_property_package_lists(merger->set);

   550 	rebuild_file_package_lists(merger->set);

   551 

   552 	merger->committed = 1;

   553 

   554 	return merger->set;

   555 }

   556 

   557 void

   558 razor_merger_package_add_script(struct razor_merger *merger,

   559 				struct razor_package *package,

   560 				enum razor_property_flags script,

   561 				const char *program, const char *body)

   562 {

   563 	uint32_t p, b;

   564 	char *pool;

   565 	struct razor_set *set = merger->set;

   566 	assert ((void *)package >= set->packages.data && \

   567 	    (void *)package < set->packages.data + set->packages.size);

   568 

   569 	p = hashtable_tokenize(&merger->table, program);

   570 	b = hashtable_tokenize(&merger->table, body);

   571 

   572 	pool = merger->set->string_pool.data;

   573 

   574 	switch (script) {

   575 	case RAZOR_PROPERTY_PREUN:

   576 		assert(pool[package->preun.program] == '\0');

   577 		assert(pool[package->preun.body] == '\0');

   578 		package->preun.program = p;

   579 		package->preun.body = b;

   580 		break;

   581 	case RAZOR_PROPERTY_POSTUN:

   582 		assert(pool[package->postun.program] == '\0');

   583 		assert(pool[package->postun.body] == '\0');

   584 		package->postun.program = p;

   585 		package->postun.body = b;

   586 		break;

   587 	default:

   588 		break;

   589 	}

   590 }

   591 

   592 void razor_merger_destroy(struct razor_merger *merger)

   593 {

   594 	hashtable_release(&merger->table);

   595 	hashtable_release(&merger->file_table);

   596 	free(merger);

   597 }
razor