librazor/merger.c
author J. Ali Harlow <ali@juiblex.co.uk>
Sat Jun 11 17:56:45 2016 +0100 (2016-06-11)
changeset 473 2e8a0b26d579
parent 458 3f841a46eab5
permissions -rw-r--r--
Release 0.6.3
     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 "config.h"
    22 #include <string.h>
    23 #include <assert.h>
    24 #include "razor-internal.h"
    25 #include "razor.h"
    26 
    27 #define UPSTREAM_SOURCE 0x80
    28 
    29 struct source {
    30 	struct razor_set *set;
    31 	uint32_t *property_map;
    32 	uint32_t *file_map;
    33 };
    34 
    35 struct razor_merger {
    36 	int committed;
    37 	struct razor_set *set;
    38 	struct hashtable table;
    39 	struct hashtable file_table;
    40 	struct hashtable details_table;
    41 	struct source source1;
    42 	struct source source2;
    43 };
    44 
    45 struct razor_merger *
    46 razor_merger_create(struct razor_set *set1, struct razor_set *set2)
    47 {
    48 	struct razor_merger *merger;
    49 	int count;
    50 	size_t size;
    51 	uint32_t header_version;
    52 
    53 	merger = zalloc(sizeof *merger);
    54 	merger->set = razor_set_create();
    55 	if (set1->packages.size) {
    56 		header_version = razor_set_get_header_version(set1);
    57 		if (set2->packages.size &&
    58 		    razor_set_get_header_version(set2) > header_version)
    59 			header_version = razor_set_get_header_version(set2);
    60 	} else
    61 		header_version = razor_set_get_header_version(set2);
    62 	razor_set_set_header_version(merger->set, header_version);
    63 	hashtable_init(&merger->table, &merger->set->string_pool);
    64 	hashtable_init(&merger->file_table, &merger->set->file_string_pool);
    65 	hashtable_init(&merger->details_table,
    66 		       &merger->set->details_string_pool);
    67 
    68 	merger->source1.set = set1;
    69 	count = set1->properties.size / sizeof (struct razor_property);
    70 	size = count * sizeof merger->source1.property_map[0];
    71 	merger->source1.property_map = zalloc(size);
    72 	count = set1->files.size / sizeof (struct razor_entry);
    73 	size = count * sizeof merger->source1.file_map[0];
    74 	merger->source1.file_map = zalloc(size);
    75 
    76 	merger->source2.set = set2;
    77 	count = set2->properties.size / sizeof (struct razor_property);
    78 	size = count * sizeof merger->source2.property_map[0];
    79 	merger->source2.property_map = zalloc(size);
    80 	count = set2->files.size / sizeof (struct razor_entry);
    81 	size = count * sizeof merger->source2.file_map[0];
    82 	merger->source2.file_map = zalloc(size);
    83 
    84 	return merger;
    85 }
    86 
    87 void
    88 razor_merger_add_package(struct razor_merger *merger,
    89 			 struct razor_package *package)
    90 {
    91 	char *pool, *details_pool, *s;
    92 	struct list *r;
    93 	struct razor_package *p;
    94 	struct razor_set *set1;
    95 	struct source *source;
    96 	uint32_t flags, *prefix;
    97 	struct array install_prefixes;
    98 
    99 	assert(merger->committed == 0);
   100 
   101 	set1 = merger->source1.set;
   102 	if (set1->packages.data <= (void *) package &&
   103 	    (void *) package < set1->packages.data + set1->packages.size) {
   104 		source = &merger->source1;
   105 		flags = 0;
   106 	} else {
   107 		source = &merger->source2;
   108 		flags = UPSTREAM_SOURCE;
   109 	}
   110 
   111 	pool = source->set->string_pool.data;
   112 	details_pool = source->set->details_string_pool.data;
   113 	p = array_add(&merger->set->packages, sizeof *p);
   114 	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
   115 	p->flags = flags;
   116 	p->version = hashtable_tokenize(&merger->table,
   117 					&pool[package->version]);
   118 	p->arch = hashtable_tokenize(&merger->table,
   119 				     &pool[package->arch]);
   120 	if (source->set->details_string_pool.size) {
   121 		p->summary = hashtable_tokenize(&merger->details_table,
   122 						&details_pool[package->summary]);
   123 		p->description = hashtable_tokenize(&merger->details_table,
   124 						    &details_pool[package->description]);
   125 		p->url = hashtable_tokenize(&merger->details_table,
   126 					    &details_pool[package->url]);
   127 		p->license = hashtable_tokenize(&merger->details_table,
   128 						&details_pool[package->license]);
   129 	} else {
   130 		p->summary = hashtable_tokenize(&merger->details_table, "");
   131 		p->description = hashtable_tokenize(&merger->details_table, "");
   132 		p->url = hashtable_tokenize(&merger->details_table, "");
   133 		p->license = hashtable_tokenize(&merger->details_table, "");
   134 	}
   135 
   136 	p->properties = package->properties;
   137 	r = list_first(&package->properties, &source->set->property_pool);
   138 	while (r) {
   139 		source->property_map[r->data] = 1;
   140 		r = list_next(r);
   141 	}
   142 
   143 	p->files = package->files;
   144 	r = list_first(&package->files, &source->set->file_pool);
   145 	while (r) {
   146 		source->file_map[r->data] = 1;
   147 		r = list_next(r);
   148 	}
   149 
   150 	array_init(&install_prefixes);
   151 	r = list_first(&package->install_prefixes, &source->set->prefix_pool);
   152 	while (r) {
   153 		s = (char *)source->set->string_pool.data + r->data;
   154 		prefix = array_add(&install_prefixes, sizeof *prefix);
   155 		*prefix = hashtable_tokenize(&merger->table, s);
   156 		r = list_next(r);
   157 	}
   158 	list_set_array(&p->install_prefixes, &merger->set->prefix_pool,
   159                        &install_prefixes, 0);
   160 	array_release(&install_prefixes);
   161 
   162 	p->preun.program = hashtable_tokenize(&merger->table,
   163 					      &pool[package->preun.program]);
   164 	p->preun.body = hashtable_tokenize(&merger->table,
   165 					   &pool[package->preun.body]);
   166 	p->postun.program = hashtable_tokenize(&merger->table,
   167 					       &pool[package->postun.program]);
   168 	p->postun.body = hashtable_tokenize(&merger->table,
   169 					    &pool[package->postun.body]);
   170 }
   171 
   172 static uint32_t
   173 add_property(struct razor_merger *merger,
   174 	     const char *name, uint32_t flags, const char *version)
   175 {
   176 	struct razor_property *p;
   177 
   178 	p = array_add(&merger->set->properties, sizeof *p);
   179 	p->name = hashtable_tokenize(&merger->table, name);
   180 	p->flags = flags;
   181 	p->version = hashtable_tokenize(&merger->table, version);
   182 
   183 	return p - (struct razor_property *) merger->set->properties.data;
   184 }
   185 
   186 static void
   187 merge_properties(struct razor_merger *merger)
   188 {
   189 	struct razor_property *p1, *p2;
   190 	struct razor_set *set1, *set2;
   191 	uint32_t *map1, *map2;
   192 	int i, j, cmp, count1, count2;
   193 	char *pool1, *pool2;
   194 
   195 	set1 = merger->source1.set;
   196 	set2 = merger->source2.set;
   197 	map1 = merger->source1.property_map;
   198 	map2 = merger->source2.property_map;
   199 
   200 	i = 0;
   201 	j = 0;
   202 	pool1 = set1->string_pool.data;
   203 	pool2 = set2->string_pool.data;
   204 
   205 	count1 = set1->properties.size / sizeof *p1;
   206 	count2 = set2->properties.size / sizeof *p2;
   207 	while (i < count1 || j < count2) {
   208 		if (i < count1 && map1[i] == 0) {
   209 			i++;
   210 			continue;
   211 		}
   212 		if (j < count2 && map2[j] == 0) {
   213 			j++;
   214 			continue;
   215 		}
   216 		p1 = (struct razor_property *) set1->properties.data + i;
   217 		p2 = (struct razor_property *) set2->properties.data + j;
   218 		if (i < count1 && j < count2)
   219 			cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
   220 		else if (i < count1)
   221 			cmp = -1;
   222 		else
   223 			cmp = 1;
   224 		if (cmp == 0)
   225 			cmp = p1->flags - p2->flags;
   226 		if (cmp == 0)
   227 			cmp = razor_versioncmp(&pool1[p1->version],
   228 					       &pool2[p2->version]);
   229 		if (cmp < 0) {
   230 			map1[i++] = add_property(merger,
   231 						 &pool1[p1->name],
   232 						 p1->flags,
   233 						 &pool1[p1->version]);
   234 		} else if (cmp > 0) {
   235 			map2[j++] = add_property(merger,
   236 						 &pool2[p2->name],
   237 						 p2->flags,
   238 						 &pool2[p2->version]);
   239 		} else  {
   240 			map1[i++] = map2[j++] =
   241 				add_property(merger,
   242 					     &pool1[p1->name],
   243 					     p1->flags,
   244 					     &pool1[p1->version]);
   245 		}
   246 	}
   247 }
   248 
   249 static void
   250 emit_properties(struct list_head *properties, struct array *source_pool,
   251 		uint32_t *map, struct array *pool)
   252 {
   253 	uint32_t r;
   254 	struct list *p, *q;
   255 
   256 	r = pool->size / sizeof *q;
   257 	p = list_first(properties, source_pool);
   258 	while (p) {
   259 		q = array_add(pool, sizeof *q);
   260 		q->data = map[p->data];
   261 		q->flags = p->flags;
   262 		p = list_next(p);
   263 	}
   264 
   265 	list_set_ptr(properties, r);
   266 }
   267 
   268 static uint32_t
   269 add_file(struct razor_merger *merger, const char *name)
   270 {
   271 	struct razor_entry *e;
   272 
   273 	e = array_add(&merger->set->files, sizeof *e);
   274 	e->name = hashtable_tokenize(&merger->file_table, name);
   275 	e->flags = 0;
   276 	e->start = 0;
   277 
   278 	return e - (struct razor_entry *)merger->set->files.data;
   279 }
   280 
   281 /* FIXME. Blah */
   282 static int
   283 fix_file_map(uint32_t *map,
   284 	     struct razor_entry *files,
   285 	     struct razor_entry *top)
   286 {
   287 	uint32_t e;
   288 	int found_file = 0;
   289 
   290 	e = top - files;
   291 	do {
   292 		if (files[e].start &&
   293 		    fix_file_map(map, files, &files[files[e].start]))
   294 			map[e] = 1;
   295 		if (map[e])
   296 			found_file = 1;
   297 	} while (!(files[e++].flags & RAZOR_ENTRY_LAST));
   298 
   299 	return found_file;
   300 }
   301 
   302 struct merge_directory {
   303 	uint32_t merged, dir1, dir2;
   304 };
   305 
   306 static void
   307 merge_one_directory(struct razor_merger *merger, struct merge_directory *md)
   308 {
   309 	struct razor_entry *root1, *root2, *mroot, *e1, *e2;
   310 	struct razor_set *set1, *set2;
   311 	struct array merge_stack;
   312 	struct merge_directory *child_md, *end_md;
   313 	uint32_t *map1, *map2, start, last;
   314 	int cmp;
   315 	char *pool1, *pool2;
   316 
   317 	set1 = merger->source1.set;
   318 	set2 = merger->source2.set;
   319 	map1 = merger->source1.file_map;
   320 	map2 = merger->source2.file_map;
   321 	if (set1->file_string_pool.size)
   322 		pool1 = set1->file_string_pool.data;
   323 	else
   324 		pool1 = NULL;
   325 	if (set2->file_string_pool.size)
   326 		pool2 = set2->file_string_pool.data;
   327 	else
   328 		pool2 = NULL;
   329 	root1 = (struct razor_entry *) set1->files.data;
   330 	root2 = (struct razor_entry *) set2->files.data;
   331 
   332 	array_init(&merge_stack);
   333 
   334 	start = merger->set->files.size / sizeof (struct razor_entry);
   335 	last = 0xFFFFFFFF;
   336 	e1 = md->dir1 != 0xFFFFFFFF ? root1 + md->dir1 : NULL;
   337 	e2 = md->dir2 != 0xFFFFFFFF ? root2 + md->dir2 : NULL;
   338 	while (e1 || e2) {
   339 		if (!e2 && !map1[e1 - root1]) {
   340 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   341 				e1 = NULL;
   342 			continue;
   343 		}
   344 		if (!e1 && !map2[e2 - root2]) {
   345 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   346 				e2 = NULL;
   347 			continue;
   348 		}
   349 		if (e1 && !map1[e1 - root1] &&
   350 		    e2 && !map2[e2 - root2]) {
   351 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   352 				e1 = NULL;
   353 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   354 				e2 = NULL;
   355 			continue;
   356 		}
   357 
   358 		if (!e1 || !pool1)
   359 			cmp = 1;
   360 		else if (!e2 || !pool2)
   361 			cmp = -1;
   362 		else {
   363 			cmp = strcmp (&pool1[e1->name],
   364 				      &pool2[e2->name]);
   365 		}
   366 
   367 		if (cmp < 0) {
   368 			if (map1[e1 - root1]) {
   369 				map1[e1 - root1] = last =
   370 					add_file(merger, &pool1[e1->name]);
   371 				if (e1->start) {
   372 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
   373 					child_md->merged = last;
   374 					child_md->dir1 = e1->start;
   375 					child_md->dir2 = 0xFFFFFFFF;
   376 				}
   377 			}
   378 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   379 				e1 = NULL;
   380 		} else if (cmp > 0) {
   381 			if (map2[e2 - root2]) {
   382 				map2[e2 - root2] = last =
   383 					add_file(merger, &pool2[e2->name]);
   384 				if (e2->start) {
   385 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
   386 					child_md->merged = last;
   387 					child_md->dir1 = 0xFFFFFFFF;
   388 					child_md->dir2 = e2->start;
   389 				}
   390 			}
   391 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   392 				e2 = NULL;
   393 		} else {
   394 			map1[e1 - root1] = map2[e2- root2] = last =
   395 				add_file(merger, &pool1[e1->name]);
   396 			if (e1->start || e2->start) {
   397 				child_md = array_add(&merge_stack, sizeof (struct merge_directory));
   398 				child_md->merged = last;
   399 				child_md->dir1 = e1->start ? e1->start : 0xFFFFFFFF;
   400 				child_md->dir2 = e2->start ? e2->start : 0xFFFFFFFF;
   401 			}
   402 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   403 				e1 = NULL;
   404 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   405 				e2 = NULL;
   406 		}
   407 	}
   408 
   409 	mroot = (struct razor_entry *)merger->set->files.data;
   410 	if (last != 0xFFFFFFFF) {
   411 		mroot[last].flags = RAZOR_ENTRY_LAST;
   412 		mroot[md->merged].start = start;
   413 	}
   414 
   415 	end_md = merge_stack.data + merge_stack.size;
   416 	for (child_md = merge_stack.data; child_md < end_md; child_md++)
   417 		merge_one_directory(merger, child_md);
   418 	array_release(&merge_stack);
   419 }
   420 
   421 static void
   422 merge_files(struct razor_merger *merger)
   423 {
   424 	struct razor_entry *root;
   425 	struct merge_directory md;
   426 	uint32_t *map1, *map2;
   427 
   428 	map1 = merger->source1.file_map;
   429 	map2 = merger->source2.file_map;
   430 
   431 	md.merged = 0;
   432 
   433 	if (merger->source1.set->files.size) {
   434 		root = (struct razor_entry *) merger->source1.set->files.data;
   435 		if (root->start)
   436 			fix_file_map(map1, root, root);
   437 		md.dir1 = 0;
   438 	} else {
   439 		md.dir1 = 0xFFFFFFFF;
   440 	}
   441 
   442 	if (merger->source2.set->files.size) {
   443 		root = (struct razor_entry *) merger->source2.set->files.data;
   444 		if (root->start)
   445 			fix_file_map(map2, root, root);
   446 		md.dir2 = 0;
   447 	} else {
   448 		md.dir2 = 0xFFFFFFFF;
   449 	}
   450 
   451 	/* Remove the unnamed root which razor_set_create() added */
   452 	array_release(&merger->set->files);
   453 	array_init(&merger->set->files);
   454 
   455 	merge_one_directory(merger, &md);
   456 }
   457 
   458 static void
   459 emit_files(struct list_head *files, struct array *source_pool,
   460 	   uint32_t *map, struct array *pool)
   461 {
   462 	uint32_t r;
   463 	struct list *p, *q;
   464 
   465 	r = pool->size / sizeof *q;
   466 	p = list_first(files, source_pool);
   467 
   468 	if (!p)
   469 		return;
   470 
   471 	while (p) {
   472 		q = array_add(pool, sizeof *q);
   473 		q->data = map[p->data];
   474 		q->flags = p->flags;
   475 		p = list_next(p);
   476 	}
   477 
   478 	list_set_ptr(files, r);
   479 }
   480 
   481 /* Rebuild property->packages maps.  We can't just remap these, as a
   482  * property may have lost or gained a number of packages.  Allocate an
   483  * array per property and loop through the packages and add them to
   484  * the arrays for their properties. */
   485 static void
   486 rebuild_property_package_lists(struct razor_set *set)
   487 {
   488 	struct array *pkgs, *a;
   489 	struct razor_package *pkg, *pkg_end;
   490 	struct razor_property *prop, *prop_end;
   491 	struct list *r;
   492 	uint32_t *q;
   493 	int count;
   494 
   495 	count = set->properties.size / sizeof (struct razor_property);
   496 	pkgs = zalloc(count * sizeof *pkgs);
   497 	pkg_end = set->packages.data + set->packages.size;
   498 
   499 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
   500 		r = list_first(&pkg->properties, &set->property_pool);
   501 		while (r) {
   502 			q = array_add(&pkgs[r->data], sizeof *q);
   503 			*q = pkg - (struct razor_package *) set->packages.data;
   504 			r = list_next(r);
   505 		}
   506 	}
   507 
   508 	prop_end = set->properties.data + set->properties.size;
   509 	a = pkgs;
   510 	for (prop = set->properties.data; prop < prop_end; prop++, a++) {
   511 		list_set_array(&prop->packages, &set->package_pool, a, 0);
   512 		array_release(a);
   513 	}
   514 	free(pkgs);
   515 }
   516 
   517 static void
   518 rebuild_file_package_lists(struct razor_set *set)
   519 {
   520 	struct array *pkgs, *a;
   521 	struct razor_package *pkg, *pkg_end;
   522 	struct razor_entry *entry, *entry_end;
   523 	struct list *r;
   524 	uint32_t *q;
   525 	int count;
   526 
   527 	count = set->files.size / sizeof (struct razor_entry);
   528 	pkgs = zalloc(count * sizeof *pkgs);
   529 	pkg_end = set->packages.data + set->packages.size;
   530 
   531 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
   532 		r = list_first(&pkg->files, &set->file_pool);
   533 		while (r) {
   534 			q = array_add(&pkgs[r->data], sizeof *q);
   535 			*q = pkg - (struct razor_package *) set->packages.data;
   536 			r = list_next(r);
   537 		}
   538 	}
   539 
   540 	entry_end = set->files.data + set->files.size;
   541 	a = pkgs;
   542 	for (entry = set->files.data; entry < entry_end; entry++, a++) {
   543 		list_set_array(&entry->packages, &set->package_pool, a, 0);
   544 		array_release(a);
   545 	}
   546 	free(pkgs);
   547 }
   548 
   549 struct razor_set *
   550 razor_merger_commit(struct razor_merger *merger)
   551 {
   552 	struct razor_package *p, *pend;
   553 
   554 	/* As we built the package list, we filled out a bitvector of
   555 	 * the properties that are referenced by the packages in the
   556 	 * new set.  Now we do a parallel loop through the properties
   557 	 * and emit those marked in the bit vector to the new set.  In
   558 	 * the process, we update the bit vector to actually map from
   559 	 * indices in the old property list to indices in the new
   560 	 * property list for both sets. */
   561 
   562 	merge_properties(merger);
   563 	merge_files(merger);
   564 
   565 	/* Now we loop through the packages again and emit the
   566 	 * property lists, remapped to point to the new properties. */
   567 
   568 	pend = merger->set->packages.data + merger->set->packages.size;
   569 	for (p = merger->set->packages.data; p < pend; p++) {
   570 		struct source *src;
   571 
   572 		if (p->flags & UPSTREAM_SOURCE)
   573 			src = &merger->source2;
   574 		else
   575 			src = &merger->source1;
   576 
   577 		emit_properties(&p->properties,
   578 				&src->set->property_pool,
   579 				src->property_map,
   580 				&merger->set->property_pool);
   581 		emit_files(&p->files,
   582 			   &src->set->file_pool,
   583 			   src->file_map,
   584 			   &merger->set->file_pool);
   585 		p->flags &= ~UPSTREAM_SOURCE;
   586 	}
   587 
   588 	rebuild_property_package_lists(merger->set);
   589 	rebuild_file_package_lists(merger->set);
   590 
   591 	merger->committed = 1;
   592 
   593 	return merger->set;
   594 }
   595 
   596 void
   597 razor_merger_package_add_script(struct razor_merger *merger,
   598 				struct razor_package *package,
   599 				enum razor_property_flags script,
   600 				const char *program, const char *body)
   601 {
   602 	uint32_t p, b;
   603 	char *pool;
   604 	struct razor_set *set = merger->set;
   605 	assert ((void *)package >= set->packages.data && \
   606 	    (void *)package < set->packages.data + set->packages.size);
   607 
   608 	p = hashtable_tokenize(&merger->table, program);
   609 	b = hashtable_tokenize(&merger->table, body);
   610 
   611 	pool = merger->set->string_pool.data;
   612 
   613 	switch (script) {
   614 	case RAZOR_PROPERTY_PREUN:
   615 		if (package->preun.program != p) {
   616 			assert(pool[package->preun.program] == '\0');
   617 			package->preun.program = p;
   618 		}
   619 		if (package->preun.body != b) {
   620 			assert(pool[package->preun.body] == '\0');
   621 			package->preun.body = b;
   622 		}
   623 		break;
   624 	case RAZOR_PROPERTY_POSTUN:
   625 		if (package->postun.program != p) {
   626 			assert(pool[package->postun.program] == '\0');
   627 			package->postun.program = p;
   628 		}
   629 		if (package->postun.body != b) {
   630 			assert(pool[package->postun.body] == '\0');
   631 			package->postun.body = b;
   632 		}
   633 		break;
   634 	default:
   635 		break;
   636 	}
   637 }
   638 
   639 void razor_merger_destroy(struct razor_merger *merger)
   640 {
   641 	hashtable_release(&merger->table);
   642 	hashtable_release(&merger->file_table);
   643 	hashtable_release(&merger->details_table);
   644 	free(merger->source1.property_map);
   645 	free(merger->source1.file_map);
   646 	free(merger->source2.property_map);
   647 	free(merger->source2.file_map);
   648 	free(merger);
   649 }