Mercurialrazor / file revision
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | revisions | annotate | diff | raw
librazor/merger.c
author ali <j.a.harlow@letterboxes.org>
Fri Jan 27 08:12:19 2012 +0000 (2012-01-27)
changeset 407 925e32dcde0f
parent 395 ed134fdfe95f
child 438 fab0b8a61dcb
permissions -rw-r--r--
Release version 0.5.1 
     1 /*

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

     3  * Copyright (C) 2008  Red Hat, Inc

     4  * Copyright (C) 2009-2011  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 hashtable details_table;

    40 	struct source source1;

    41 	struct source source2;

    42 };

    43 

    44 struct razor_merger *

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

    46 {

    47 	struct razor_merger *merger;

    48 	int count;

    49 	size_t size;

    50 	uint32_t header_version;

    51 

    52 	merger = zalloc(sizeof *merger);

    53 	merger->set = razor_set_create();

    54 	if (set1->packages.size) {

    55 		header_version = razor_set_get_header_version(set1);

    56 		if (set2->packages.size &&

    57 		    razor_set_get_header_version(set2) > header_version)

    58 			header_version = razor_set_get_header_version(set2);

    59 	} else

    60 		header_version = razor_set_get_header_version(set2);

    61 	razor_set_set_header_version(merger->set, header_version);

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

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

    64 	hashtable_init(&merger->details_table,

    65 		       &merger->set->details_string_pool);

    66 

    67 	merger->source1.set = set1;

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

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

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

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

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

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

    74 

    75 	merger->source2.set = set2;

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

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

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

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

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

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

    82 

    83 	return merger;

    84 }

    85 

    86 void

    87 razor_merger_add_package(struct razor_merger *merger,

    88 			 struct razor_package *package)

    89 {

    90 	char *pool, *details_pool, *s;

    91 	struct list *r;

    92 	struct razor_package *p;

    93 	struct razor_set *set1;

    94 	struct source *source;

    95 	uint32_t flags, *prefix;

    96 	struct array install_prefixes;

    97 

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

    99 

   100 	set1 = merger->source1.set;

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

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

   103 		source = &merger->source1;

   104 		flags = 0;

   105 	} else {

   106 		source = &merger->source2;

   107 		flags = UPSTREAM_SOURCE;

   108 	}

   109 

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

   111 	details_pool = source->set->details_string_pool.data;

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

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

   114 	p->flags = flags;

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

   116 					&pool[package->version]);

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

   118 				     &pool[package->arch]);

   119 	if (source->set->details_string_pool.size) {

   120 		p->summary = hashtable_tokenize(&merger->details_table,

   121 						&details_pool[package->summary]);

   122 		p->description = hashtable_tokenize(&merger->details_table,

   123 						    &details_pool[package->description]);

   124 		p->url = hashtable_tokenize(&merger->details_table,

   125 					    &details_pool[package->url]);

   126 		p->license = hashtable_tokenize(&merger->details_table,

   127 						&details_pool[package->license]);

   128 	} else {

   129 		p->summary = hashtable_tokenize(&merger->details_table, "");

   130 		p->description = hashtable_tokenize(&merger->details_table, "");

   131 		p->url = hashtable_tokenize(&merger->details_table, "");

   132 		p->license = hashtable_tokenize(&merger->details_table, "");

   133 	}

   134 

   135 	p->properties = package->properties;

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

   137 	while (r) {

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

   139 		r = list_next(r);

   140 	}

   141 

   142 	p->files = package->files;

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

   144 	while (r) {

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

   146 		r = list_next(r);

   147 	}

   148 

   149 	array_init(&install_prefixes);

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

   151 	while (r) {

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

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

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

   155 		r = list_next(r);

   156 	}

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

   158                        &install_prefixes, 0);

   159 	array_release(&install_prefixes);

   160 

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

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

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

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

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

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

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

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

   169 }

   170 

   171 static uint32_t

   172 add_property(struct razor_merger *merger,

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

   174 {

   175 	struct razor_property *p;

   176 

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

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

   179 	p->flags = flags;

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

   181 

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

   183 }

   184 

   185 static void

   186 merge_properties(struct razor_merger *merger)

   187 {

   188 	struct razor_property *p1, *p2;

   189 	struct razor_set *set1, *set2;

   190 	uint32_t *map1, *map2;

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

   192 	char *pool1, *pool2;

   193 

   194 	set1 = merger->source1.set;

   195 	set2 = merger->source2.set;

   196 	map1 = merger->source1.property_map;

   197 	map2 = merger->source2.property_map;

   198 

   199 	i = 0;

   200 	j = 0;

   201 	pool1 = set1->string_pool.data;

   202 	pool2 = set2->string_pool.data;

   203 

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

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

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

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

   208 			i++;

   209 			continue;

   210 		}

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

   212 			j++;

   213 			continue;

   214 		}

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

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

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

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

   219 		else if (i < count1)

   220 			cmp = -1;

   221 		else

   222 			cmp = 1;

   223 		if (cmp == 0)

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

   225 		if (cmp == 0)

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

   227 					       &pool2[p2->version]);

   228 		if (cmp < 0) {

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

   230 						 &pool1[p1->name],

   231 						 p1->flags,

   232 						 &pool1[p1->version]);

   233 		} else if (cmp > 0) {

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

   235 						 &pool2[p2->name],

   236 						 p2->flags,

   237 						 &pool2[p2->version]);

   238 		} else  {

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

   240 				add_property(merger,

   241 					     &pool1[p1->name],

   242 					     p1->flags,

   243 					     &pool1[p1->version]);

   244 		}

   245 	}

   246 }

   247 

   248 static void

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

   250 		uint32_t *map, struct array *pool)

   251 {

   252 	uint32_t r;

   253 	struct list *p, *q;

   254 

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

   256 	p = list_first(properties, source_pool);

   257 	while (p) {

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

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

   260 		q->flags = p->flags;

   261 		p = list_next(p);

   262 	}

   263 

   264 	list_set_ptr(properties, r);

   265 }

   266 

   267 static uint32_t

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

   269 {

   270 	struct razor_entry *e;

   271 

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

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

   274 	e->flags = 0;

   275 	e->start = 0;

   276 

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

   278 }

   279 

   280 /* FIXME. Blah */

   281 static int

   282 fix_file_map(uint32_t *map,

   283 	     struct razor_entry *files,

   284 	     struct razor_entry *top)

   285 {

   286 	uint32_t e;

   287 	int found_file = 0;

   288 

   289 	e = top - files;

   290 	do {

   291 		if (files[e].start &&

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

   293 			map[e] = 1;

   294 		if (map[e])

   295 			found_file = 1;

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

   297 

   298 	return found_file;

   299 }

   300 

   301 struct merge_directory {

   302 	uint32_t merged, dir1, dir2;

   303 };

   304 

   305 static void

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

   307 {

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

   309 	struct razor_set *set1, *set2;

   310 	struct array merge_stack;

   311 	struct merge_directory *child_md, *end_md;

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

   313 	int cmp;

   314 	char *pool1, *pool2;

   315 

   316 	set1 = merger->source1.set;

   317 	set2 = merger->source2.set;

   318 	map1 = merger->source1.file_map;

   319 	map2 = merger->source2.file_map;

   320 	pool1 = set1->file_string_pool.data;

   321 	pool2 = set2->file_string_pool.data;

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

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

   324 

   325 	array_init(&merge_stack);

   326 

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

   328 	last = 0xFFFFFFFF;

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

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

   331 	while (e1 || e2) {

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

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

   334 				e1 = NULL;

   335 			continue;

   336 		}

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

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

   339 				e2 = NULL;

   340 			continue;

   341 		}

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

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

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

   345 				e1 = NULL;

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

   347 				e2 = NULL;

   348 			continue;

   349 		}

   350 

   351 		if (!e1)

   352 			cmp = 1;

   353 		else if (!e2)

   354 			cmp = -1;

   355 		else {

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

   357 				      &pool2[e2->name]);

   358 		}

   359 

   360 		if (cmp < 0) {

   361 			if (map1[e1 - root1]) {

   362 				map1[e1 - root1] = last =

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

   364 				if (e1->start) {

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

   366 					child_md->merged = last;

   367 					child_md->dir1 = e1->start;

   368 					child_md->dir2 = 0xFFFFFFFF;

   369 				}

   370 			}

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

   372 				e1 = NULL;

   373 		} else if (cmp > 0) {

   374 			if (map2[e2 - root2]) {

   375 				map2[e2 - root2] = last =

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

   377 				if (e2->start) {

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

   379 					child_md->merged = last;

   380 					child_md->dir1 = 0xFFFFFFFF;

   381 					child_md->dir2 = e2->start;

   382 				}

   383 			}

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

   385 				e2 = NULL;

   386 		} else {

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

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

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

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

   391 				child_md->merged = last;

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

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

   394 			}

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

   396 				e1 = NULL;

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

   398 				e2 = NULL;

   399 		}

   400 	}

   401 

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

   403 	if (last != 0xFFFFFFFF) {

   404 		mroot[last].flags = RAZOR_ENTRY_LAST;

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

   406 	}

   407 

   408 	end_md = merge_stack.data + merge_stack.size;

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

   410 		merge_one_directory(merger, child_md);

   411 	array_release(&merge_stack);

   412 }

   413 

   414 static void

   415 merge_files(struct razor_merger *merger)

   416 {

   417 	struct razor_entry *root;

   418 	struct merge_directory md;

   419 	uint32_t *map1, *map2;

   420 

   421 	map1 = merger->source1.file_map;

   422 	map2 = merger->source2.file_map;

   423 

   424 	md.merged = 0;

   425 

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

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

   428 		if (root->start)

   429 			fix_file_map(map1, root, root);

   430 		md.dir1 = 0;

   431 	} else {

   432 		md.dir1 = 0xFFFFFFFF;

   433 	}

   434 

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

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

   437 		if (root->start)

   438 			fix_file_map(map2, root, root);

   439 		md.dir2 = 0;

   440 	} else {

   441 		md.dir2 = 0xFFFFFFFF;

   442 	}

   443 

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

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

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

   447 

   448 	merge_one_directory(merger, &md);

   449 }

   450 

   451 static void

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

   453 	   uint32_t *map, struct array *pool)

   454 {

   455 	uint32_t r;

   456 	struct list *p, *q;

   457 

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

   459 	p = list_first(files, source_pool);

   460 	while (p) {

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

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

   463 		q->flags = p->flags;

   464 		p = list_next(p);

   465 	}

   466 

   467 	list_set_ptr(files, r);

   468 }

   469 

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

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

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

   473  * the arrays for their properties. */

   474 static void

   475 rebuild_property_package_lists(struct razor_set *set)

   476 {

   477 	struct array *pkgs, *a;

   478 	struct razor_package *pkg, *pkg_end;

   479 	struct razor_property *prop, *prop_end;

   480 	struct list *r;

   481 	uint32_t *q;

   482 	int count;

   483 

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

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

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

   487 

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

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

   490 		while (r) {

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

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

   493 			r = list_next(r);

   494 		}

   495 	}

   496 

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

   498 	a = pkgs;

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

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

   501 		array_release(a);

   502 	}

   503 	free(pkgs);

   504 }

   505 

   506 static void

   507 rebuild_file_package_lists(struct razor_set *set)

   508 {

   509 	struct array *pkgs, *a;

   510 	struct razor_package *pkg, *pkg_end;

   511 	struct razor_entry *entry, *entry_end;

   512 	struct list *r;

   513 	uint32_t *q;

   514 	int count;

   515 

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

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

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

   519 

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

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

   522 		while (r) {

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

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

   525 			r = list_next(r);

   526 		}

   527 	}

   528 

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

   530 	a = pkgs;

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

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

   533 		array_release(a);

   534 	}

   535 	free(pkgs);

   536 }

   537 

   538 struct razor_set *

   539 razor_merger_commit(struct razor_merger *merger)

   540 {

   541 	struct razor_package *p, *pend;

   542 

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

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

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

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

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

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

   549 	 * property list for both sets. */

   550 

   551 	merge_properties(merger);

   552 	merge_files(merger);

   553 

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

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

   556 

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

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

   559 		struct source *src;

   560 

   561 		if (p->flags & UPSTREAM_SOURCE)

   562 			src = &merger->source2;

   563 		else

   564 			src = &merger->source1;

   565 

   566 		emit_properties(&p->properties,

   567 				&src->set->property_pool,

   568 				src->property_map,

   569 				&merger->set->property_pool);

   570 		emit_files(&p->files,

   571 			   &src->set->file_pool,

   572 			   src->file_map,

   573 			   &merger->set->file_pool);

   574 		p->flags &= ~UPSTREAM_SOURCE;

   575 	}

   576 

   577 	rebuild_property_package_lists(merger->set);

   578 	rebuild_file_package_lists(merger->set);

   579 

   580 	merger->committed = 1;

   581 

   582 	return merger->set;

   583 }

   584 

   585 void

   586 razor_merger_package_add_script(struct razor_merger *merger,

   587 				struct razor_package *package,

   588 				enum razor_property_flags script,

   589 				const char *program, const char *body)

   590 {

   591 	uint32_t p, b;

   592 	char *pool;

   593 	struct razor_set *set = merger->set;

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

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

   596 

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

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

   599 

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

   601 

   602 	switch (script) {

   603 	case RAZOR_PROPERTY_PREUN:

   604 		if (package->preun.program != p) {

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

   606 			package->preun.program = p;

   607 		}

   608 		if (package->preun.body != b) {

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

   610 			package->preun.body = b;

   611 		}

   612 		break;

   613 	case RAZOR_PROPERTY_POSTUN:

   614 		if (package->postun.program != p) {

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

   616 			package->postun.program = p;

   617 		}

   618 		if (package->postun.body != b) {

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

   620 			package->postun.body = b;

   621 		}

   622 		break;

   623 	default:

   624 		break;

   625 	}

   626 }

   627 

   628 void razor_merger_destroy(struct razor_merger *merger)

   629 {

   630 	hashtable_release(&merger->table);

   631 	hashtable_release(&merger->file_table);

   632 	hashtable_release(&merger->details_table);

   633 	free(merger);

   634 }
razor