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>
Thu Aug 25 14:22:52 2011 +0100 (2011-08-25)
changeset 402 6ed7abe8e66b
parent 394 afe520f454bd
child 403 e63951c1d0f8
permissions -rw-r--r--
Release version 0.4.1 
     1 /*

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

     3  * Copyright (C) 2008  Red Hat, Inc

     4  * Copyright (C) 2009, 2010  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 

    51 	merger = zalloc(sizeof *merger);

    52 	merger->set = razor_set_create();

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

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

    55 	hashtable_init(&merger->details_table,

    56 		       &merger->set->details_string_pool);

    57 

    58 	merger->source1.set = set1;

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

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

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

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

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

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

    65 

    66 	merger->source2.set = set2;

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

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

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

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

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

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

    73 

    74 	return merger;

    75 }

    76 

    77 void

    78 razor_merger_add_package(struct razor_merger *merger,

    79 			 struct razor_package *package)

    80 {

    81 	char *pool, *details_pool, *s;

    82 	struct list *r;

    83 	struct razor_package *p;

    84 	struct razor_set *set1;

    85 	struct source *source;

    86 	uint32_t flags, *prefix;

    87 	struct array install_prefixes;

    88 

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

    90 

    91 	set1 = merger->source1.set;

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

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

    94 		source = &merger->source1;

    95 		flags = 0;

    96 	} else {

    97 		source = &merger->source2;

    98 		flags = UPSTREAM_SOURCE;

    99 	}

   100 

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

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

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

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

   105 	p->flags = flags;

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

   107 					&pool[package->version]);

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

   109 				     &pool[package->arch]);

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

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

   112 						&details_pool[package->summary]);

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

   114 						    &details_pool[package->description]);

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

   116 					    &details_pool[package->url]);

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

   118 						&details_pool[package->license]);

   119 	} else {

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

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

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

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

   124 	}

   125 

   126 	p->properties = package->properties;

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

   128 	while (r) {

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

   130 		r = list_next(r);

   131 	}

   132 

   133 	p->files = package->files;

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

   135 	while (r) {

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

   137 		r = list_next(r);

   138 	}

   139 

   140 	array_init(&install_prefixes);

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

   142 	while (r) {

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

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

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

   146 		r = list_next(r);

   147 	}

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

   149                        &install_prefixes, 0);

   150 	array_release(&install_prefixes);

   151 

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

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

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

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

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

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

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

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

   160 }

   161 

   162 static uint32_t

   163 add_property(struct razor_merger *merger,

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

   165 {

   166 	struct razor_property *p;

   167 

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

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

   170 	p->flags = flags;

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

   172 

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

   174 }

   175 

   176 static void

   177 merge_properties(struct razor_merger *merger)

   178 {

   179 	struct razor_property *p1, *p2;

   180 	struct razor_set *set1, *set2;

   181 	uint32_t *map1, *map2;

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

   183 	char *pool1, *pool2;

   184 

   185 	set1 = merger->source1.set;

   186 	set2 = merger->source2.set;

   187 	map1 = merger->source1.property_map;

   188 	map2 = merger->source2.property_map;

   189 

   190 	i = 0;

   191 	j = 0;

   192 	pool1 = set1->string_pool.data;

   193 	pool2 = set2->string_pool.data;

   194 

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

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

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

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

   199 			i++;

   200 			continue;

   201 		}

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

   203 			j++;

   204 			continue;

   205 		}

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

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

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

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

   210 		else if (i < count1)

   211 			cmp = -1;

   212 		else

   213 			cmp = 1;

   214 		if (cmp == 0)

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

   216 		if (cmp == 0)

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

   218 					       &pool2[p2->version]);

   219 		if (cmp < 0) {

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

   221 						 &pool1[p1->name],

   222 						 p1->flags,

   223 						 &pool1[p1->version]);

   224 		} else if (cmp > 0) {

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

   226 						 &pool2[p2->name],

   227 						 p2->flags,

   228 						 &pool2[p2->version]);

   229 		} else  {

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

   231 				add_property(merger,

   232 					     &pool1[p1->name],

   233 					     p1->flags,

   234 					     &pool1[p1->version]);

   235 		}

   236 	}

   237 }

   238 

   239 static void

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

   241 		uint32_t *map, struct array *pool)

   242 {

   243 	uint32_t r;

   244 	struct list *p, *q;

   245 

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

   247 	p = list_first(properties, source_pool);

   248 	while (p) {

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

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

   251 		q->flags = p->flags;

   252 		p = list_next(p);

   253 	}

   254 

   255 	list_set_ptr(properties, r);

   256 }

   257 

   258 static uint32_t

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

   260 {

   261 	struct razor_entry *e;

   262 

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

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

   265 	e->flags = 0;

   266 	e->start = 0;

   267 

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

   269 }

   270 

   271 /* FIXME. Blah */

   272 static int

   273 fix_file_map(uint32_t *map,

   274 	     struct razor_entry *files,

   275 	     struct razor_entry *top)

   276 {

   277 	uint32_t e;

   278 	int found_file = 0;

   279 

   280 	e = top - files;

   281 	do {

   282 		if (files[e].start &&

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

   284 			map[e] = 1;

   285 		if (map[e])

   286 			found_file = 1;

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

   288 

   289 	return found_file;

   290 }

   291 

   292 struct merge_directory {

   293 	uint32_t merged, dir1, dir2;

   294 };

   295 

   296 static void

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

   298 {

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

   300 	struct razor_set *set1, *set2;

   301 	struct array merge_stack;

   302 	struct merge_directory *child_md, *end_md;

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

   304 	int cmp;

   305 	char *pool1, *pool2;

   306 

   307 	set1 = merger->source1.set;

   308 	set2 = merger->source2.set;

   309 	map1 = merger->source1.file_map;

   310 	map2 = merger->source2.file_map;

   311 	pool1 = set1->file_string_pool.data;

   312 	pool2 = set2->file_string_pool.data;

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

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

   315 

   316 	array_init(&merge_stack);

   317 

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

   319 	last = 0xFFFFFFFF;

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

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

   322 	while (e1 || e2) {

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

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

   325 				e1 = NULL;

   326 			continue;

   327 		}

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

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

   330 				e2 = NULL;

   331 			continue;

   332 		}

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

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

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

   336 				e1 = NULL;

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

   338 				e2 = NULL;

   339 			continue;

   340 		}

   341 

   342 		if (!e1)

   343 			cmp = 1;

   344 		else if (!e2)

   345 			cmp = -1;

   346 		else {

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

   348 				      &pool2[e2->name]);

   349 		}

   350 

   351 		if (cmp < 0) {

   352 			if (map1[e1 - root1]) {

   353 				map1[e1 - root1] = last =

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

   355 				if (e1->start) {

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

   357 					child_md->merged = last;

   358 					child_md->dir1 = e1->start;

   359 					child_md->dir2 = 0xFFFFFFFF;

   360 				}

   361 			}

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

   363 				e1 = NULL;

   364 		} else if (cmp > 0) {

   365 			if (map2[e2 - root2]) {

   366 				map2[e2 - root2] = last =

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

   368 				if (e2->start) {

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

   370 					child_md->merged = last;

   371 					child_md->dir1 = 0xFFFFFFFF;

   372 					child_md->dir2 = e2->start;

   373 				}

   374 			}

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

   376 				e2 = NULL;

   377 		} else {

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

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

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

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

   382 				child_md->merged = last;

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

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

   385 			}

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

   387 				e1 = NULL;

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

   389 				e2 = NULL;

   390 		}

   391 	}

   392 

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

   394 	if (last != 0xFFFFFFFF) {

   395 		mroot[last].flags = RAZOR_ENTRY_LAST;

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

   397 	}

   398 

   399 	end_md = merge_stack.data + merge_stack.size;

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

   401 		merge_one_directory(merger, child_md);

   402 	array_release(&merge_stack);

   403 }

   404 

   405 static void

   406 merge_files(struct razor_merger *merger)

   407 {

   408 	struct razor_entry *root;

   409 	struct merge_directory md;

   410 	uint32_t *map1, *map2;

   411 

   412 	map1 = merger->source1.file_map;

   413 	map2 = merger->source2.file_map;

   414 

   415 	md.merged = 0;

   416 

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

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

   419 		if (root->start)

   420 			fix_file_map(map1, root, root);

   421 		md.dir1 = 0;

   422 	} else {

   423 		md.dir1 = 0xFFFFFFFF;

   424 	}

   425 

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

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

   428 		if (root->start)

   429 			fix_file_map(map2, root, root);

   430 		md.dir2 = 0;

   431 	} else {

   432 		md.dir2 = 0xFFFFFFFF;

   433 	}

   434 

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

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

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

   438 

   439 	merge_one_directory(merger, &md);

   440 }

   441 

   442 static void

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

   444 	   uint32_t *map, struct array *pool)

   445 {

   446 	uint32_t r;

   447 	struct list *p, *q;

   448 

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

   450 	p = list_first(files, source_pool);

   451 	while (p) {

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

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

   454 		q->flags = p->flags;

   455 		p = list_next(p);

   456 	}

   457 

   458 	list_set_ptr(files, r);

   459 }

   460 

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

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

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

   464  * the arrays for their properties. */

   465 static void

   466 rebuild_property_package_lists(struct razor_set *set)

   467 {

   468 	struct array *pkgs, *a;

   469 	struct razor_package *pkg, *pkg_end;

   470 	struct razor_property *prop, *prop_end;

   471 	struct list *r;

   472 	uint32_t *q;

   473 	int count;

   474 

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

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

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

   478 

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

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

   481 		while (r) {

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

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

   484 			r = list_next(r);

   485 		}

   486 	}

   487 

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

   489 	a = pkgs;

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

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

   492 		array_release(a);

   493 	}

   494 	free(pkgs);

   495 }

   496 

   497 static void

   498 rebuild_file_package_lists(struct razor_set *set)

   499 {

   500 	struct array *pkgs, *a;

   501 	struct razor_package *pkg, *pkg_end;

   502 	struct razor_entry *entry, *entry_end;

   503 	struct list *r;

   504 	uint32_t *q;

   505 	int count;

   506 

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

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

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

   510 

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

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

   513 		while (r) {

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

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

   516 			r = list_next(r);

   517 		}

   518 	}

   519 

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

   521 	a = pkgs;

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

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

   524 		array_release(a);

   525 	}

   526 	free(pkgs);

   527 }

   528 

   529 struct razor_set *

   530 razor_merger_commit(struct razor_merger *merger)

   531 {

   532 	struct razor_package *p, *pend;

   533 

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

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

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

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

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

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

   540 	 * property list for both sets. */

   541 

   542 	merge_properties(merger);

   543 	merge_files(merger);

   544 

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

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

   547 

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

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

   550 		struct source *src;

   551 

   552 		if (p->flags & UPSTREAM_SOURCE)

   553 			src = &merger->source2;

   554 		else

   555 			src = &merger->source1;

   556 

   557 		emit_properties(&p->properties,

   558 				&src->set->property_pool,

   559 				src->property_map,

   560 				&merger->set->property_pool);

   561 		emit_files(&p->files,

   562 			   &src->set->file_pool,

   563 			   src->file_map,

   564 			   &merger->set->file_pool);

   565 		p->flags &= ~UPSTREAM_SOURCE;

   566 	}

   567 

   568 	rebuild_property_package_lists(merger->set);

   569 	rebuild_file_package_lists(merger->set);

   570 

   571 	merger->committed = 1;

   572 

   573 	return merger->set;

   574 }

   575 

   576 void

   577 razor_merger_package_add_script(struct razor_merger *merger,

   578 				struct razor_package *package,

   579 				enum razor_property_flags script,

   580 				const char *program, const char *body)

   581 {

   582 	uint32_t p, b;

   583 	char *pool;

   584 	struct razor_set *set = merger->set;

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

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

   587 

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

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

   590 

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

   592 

   593 	switch (script) {

   594 	case RAZOR_PROPERTY_PREUN:

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

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

   597 		package->preun.program = p;

   598 		package->preun.body = b;

   599 		break;

   600 	case RAZOR_PROPERTY_POSTUN:

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

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

   603 		package->postun.program = p;

   604 		package->postun.body = b;

   605 		break;

   606 	default:

   607 		break;

   608 	}

   609 }

   610 

   611 void razor_merger_destroy(struct razor_merger *merger)

   612 {

   613 	hashtable_release(&merger->table);

   614 	hashtable_release(&merger->file_table);

   615 	hashtable_release(&merger->details_table);

   616 	free(merger);

   617 }
razor