Mercurialrazor / file revision
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | revisions | annotate | diff | raw
librazor/merger.c
author Kristian H?gsberg <krh@redhat.com>
Mon Jun 23 17:19:20 2008 -0400 (2008-06-23)
changeset 269 03fc85294bc9
child 313 643c4a94c2ae
permissions -rw-r--r--
Use GCC 4 -fvisibility to control exported symbols. 
     1 /*

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

     3  * Copyright (C) 2008  Red Hat, Inc

     4  *

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

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

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

     8  * (at your option) any later version.

     9  *

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

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

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

    13  * GNU General Public License for more details.

    14  *

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

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

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

    18  */

    19 

    20 #include <string.h>

    21 #include "razor-internal.h"

    22 #include "razor.h"

    23 

    24 #define UPSTREAM_SOURCE 0x80

    25 

    26 struct source {

    27 	struct razor_set *set;

    28 	uint32_t *property_map;

    29 	uint32_t *file_map;

    30 };

    31 

    32 struct razor_merger {

    33 	struct razor_set *set;

    34 	struct hashtable table;

    35 	struct source source1;

    36 	struct source source2;

    37 };

    38 

    39 struct razor_merger *

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

    41 {

    42 	struct razor_merger *merger;

    43 	int count;

    44 	size_t size;

    45 

    46 	merger = zalloc(sizeof *merger);

    47 	merger->set = razor_set_create();

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

    49 

    50 	merger->source1.set = set1;

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

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

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

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

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

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

    57 

    58 	merger->source2.set = set2;

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

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

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

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

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

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

    65 

    66 	return merger;

    67 }

    68 

    69 void

    70 razor_merger_add_package(struct razor_merger *merger,

    71 			 struct razor_package *package)

    72 {

    73 	char *pool;

    74 	struct list *r;

    75 	struct razor_package *p;

    76 	struct razor_set *set1;

    77 	struct source *source;

    78 	uint32_t flags;

    79 

    80 	set1 = merger->source1.set;

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

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

    83 		source = &merger->source1;

    84 		flags = 0;

    85 	} else {

    86 		source = &merger->source2;

    87 		flags = UPSTREAM_SOURCE;

    88 	}

    89 

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

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

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

    93 	p->flags = flags;

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

    95 					&pool[package->version]);

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

    97 				     &pool[package->arch]);

    98 

    99 	p->properties = package->properties;

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

   101 	while (r) {

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

   103 		r = list_next(r);

   104 	}

   105 

   106 	p->files = package->files;

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

   108 	while (r) {

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

   110 		r = list_next(r);

   111 	}

   112 }

   113 

   114 static uint32_t

   115 add_property(struct razor_merger *merger,

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

   117 {

   118 	struct razor_property *p;

   119 

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

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

   122 	p->flags = flags;

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

   124 

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

   126 }

   127 

   128 static void

   129 merge_properties(struct razor_merger *merger)

   130 {

   131 	struct razor_property *p1, *p2;

   132 	struct razor_set *set1, *set2;

   133 	uint32_t *map1, *map2;

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

   135 	char *pool1, *pool2;

   136 

   137 	set1 = merger->source1.set;

   138 	set2 = merger->source2.set;

   139 	map1 = merger->source1.property_map;

   140 	map2 = merger->source2.property_map;

   141 

   142 	i = 0;

   143 	j = 0;

   144 	pool1 = set1->string_pool.data;

   145 	pool2 = set2->string_pool.data;

   146 

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

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

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

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

   151 			i++;

   152 			continue;

   153 		}

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

   155 			j++;

   156 			continue;

   157 		}

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

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

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

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

   162 		else if (i < count1)

   163 			cmp = -1;

   164 		else

   165 			cmp = 1;

   166 		if (cmp == 0)

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

   168 		if (cmp == 0)

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

   170 					       &pool2[p2->version]);

   171 		if (cmp < 0) {

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

   173 						 &pool1[p1->name],

   174 						 p1->flags,

   175 						 &pool1[p1->version]);

   176 		} else if (cmp > 0) {

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

   178 						 &pool2[p2->name],

   179 						 p2->flags,

   180 						 &pool2[p2->version]);

   181 		} else  {

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

   183 				add_property(merger,

   184 					     &pool1[p1->name],

   185 					     p1->flags,

   186 					     &pool1[p1->version]);

   187 		}

   188 	}

   189 }

   190 

   191 static void

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

   193 		uint32_t *map, struct array *pool)

   194 {

   195 	uint32_t r;

   196 	struct list *p, *q;

   197 

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

   199 	p = list_first(properties, source_pool);

   200 	while (p) {

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

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

   203 		q->flags = p->flags;

   204 		p = list_next(p);

   205 	}

   206 

   207 	list_set_ptr(properties, r);

   208 }

   209 

   210 static uint32_t

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

   212 {

   213 	struct razor_entry *e;

   214 

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

   216 	e->name = hashtable_tokenize(&merger->table, name);

   217 	e->flags = 0;

   218 	e->start = 0;

   219 

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

   221 }

   222 

   223 /* FIXME. Blah */

   224 static int

   225 fix_file_map(uint32_t *map,

   226 	     struct razor_entry *files,

   227 	     struct razor_entry *top)

   228 {

   229 	uint32_t e;

   230 	int found_file = 0;

   231 

   232 	e = top->start;

   233 	do {

   234 		if (files[e].start)

   235 			fix_file_map(map, files, &files[e]);

   236 		if (map[e])

   237 			found_file = 1;

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

   239 

   240 	if (found_file)

   241 		map[top - files] = 1;

   242 	return found_file;

   243 }

   244 

   245 struct merge_directory {

   246 	uint32_t merged, dir1, dir2;

   247 };

   248 

   249 static void

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

   251 {

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

   253 	struct razor_set *set1, *set2;

   254 	struct array merge_stack;

   255 	struct merge_directory *child_md, *end_md;

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

   257 	int cmp;

   258 	char *pool1, *pool2;

   259 

   260 	set1 = merger->source1.set;

   261 	set2 = merger->source2.set;

   262 	map1 = merger->source1.file_map;

   263 	map2 = merger->source2.file_map;

   264 	pool1 = set1->string_pool.data;

   265 	pool2 = set2->string_pool.data;

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

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

   268 

   269 	array_init(&merge_stack);

   270 

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

   272 	last = 0;

   273 	e1 = md->dir1 ? root1 + md->dir1 : NULL;

   274 	e2 = md->dir2 ? root2 + md->dir2 : NULL;

   275 	while (e1 || e2) {

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

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

   278 				e1 = NULL;

   279 			continue;

   280 		}

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

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

   283 				e2 = NULL;

   284 			continue;

   285 		}

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

   287 		    e2 && !map1[e2 - root2]) {

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

   289 				e1 = NULL;

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

   291 				e2 = NULL;

   292 			continue;

   293 		}

   294 

   295 		if (!e1)

   296 			cmp = 1;

   297 		else if (!e2)

   298 			cmp = -1;

   299 		else {

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

   301 				      &pool2[e2->name]);

   302 		}

   303 

   304 		if (cmp < 0) {

   305 			if (map1[e1 - root1]) {

   306 				map1[e1 - root1] = last =

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

   308 				if (e1->start) {

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

   310 					child_md->merged = last;

   311 					child_md->dir1 = e1->start;

   312 					child_md->dir2 = 0;

   313 				}

   314 			}

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

   316 				e1 = NULL;

   317 		} else if (cmp > 0) {

   318 			if (map2[e2 - root2]) {

   319 				map2[e2 - root2] = last =

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

   321 				if (e2->start) {

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

   323 					child_md->merged = last;

   324 					child_md->dir1 = 0;

   325 					child_md->dir2 = e2->start;

   326 				}

   327 			}

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

   329 				e2 = NULL;

   330 		} else {

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

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

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

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

   335 				child_md->merged = last;

   336 				child_md->dir1 = e1->start;

   337 				child_md->dir2 = e2->start;

   338 			}

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

   340 				e1 = NULL;

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

   342 				e2 = NULL;

   343 		}

   344 	}

   345 

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

   347 	if (last) {

   348 		mroot[last].flags = RAZOR_ENTRY_LAST;

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

   350 	} else

   351 		mroot[md->merged].start = 0;

   352 

   353 	end_md = merge_stack.data + merge_stack.size;

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

   355 		merge_one_directory(merger, child_md);

   356 	array_release(&merge_stack);

   357 }

   358 

   359 static void

   360 merge_files(struct razor_merger *merger)

   361 {

   362 	struct razor_entry *root;

   363 	struct merge_directory md;

   364 	uint32_t *map1, *map2;

   365 

   366 	map1 = merger->source1.file_map;

   367 	map2 = merger->source2.file_map;

   368 

   369 	md.merged = 0;

   370 

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

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

   373 		if (root->start)

   374 			fix_file_map(map1, root, root);

   375 		md.dir1 = root->start;

   376 	} else

   377 		md.dir1 = 0;

   378 

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

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

   381 		if (root->start)

   382 			fix_file_map(map2, root, root);

   383 		md.dir2 = root->start;

   384 	} else

   385 		md.dir2 = 0;

   386 

   387 	merge_one_directory(merger, &md);

   388 }

   389 

   390 static void

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

   392 	   uint32_t *map, struct array *pool)

   393 {

   394 	uint32_t r;

   395 	struct list *p, *q;

   396 

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

   398 	p = list_first(files, source_pool);

   399 	while (p) {

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

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

   402 		q->flags = p->flags;

   403 		p = list_next(p);

   404 	}

   405 

   406 	list_set_ptr(files, r);

   407 }

   408 

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

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

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

   412  * the arrays for their properties. */

   413 static void

   414 rebuild_property_package_lists(struct razor_set *set)

   415 {

   416 	struct array *pkgs, *a;

   417 	struct razor_package *pkg, *pkg_end;

   418 	struct razor_property *prop, *prop_end;

   419 	struct list *r;

   420 	uint32_t *q;

   421 	int count;

   422 

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

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

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

   426 

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

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

   429 		while (r) {

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

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

   432 			r = list_next(r);

   433 		}

   434 	}

   435 

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

   437 	a = pkgs;

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

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

   440 		array_release(a);

   441 	}

   442 	free(pkgs);

   443 }

   444 

   445 static void

   446 rebuild_file_package_lists(struct razor_set *set)

   447 {

   448 	struct array *pkgs, *a;

   449 	struct razor_package *pkg, *pkg_end;

   450 	struct razor_entry *entry, *entry_end;

   451 	struct list *r;

   452 	uint32_t *q;

   453 	int count;

   454 

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

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

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

   458 

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

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

   461 		while (r) {

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

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

   464 			r = list_next(r);

   465 		}

   466 	}

   467 

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

   469 	a = pkgs;

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

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

   472 		array_release(a);

   473 	}

   474 	free(pkgs);

   475 }

   476 

   477 struct razor_set *

   478 razor_merger_finish(struct razor_merger *merger)

   479 {

   480 	struct razor_set *result;

   481 	struct razor_package *p, *pend;

   482 

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

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

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

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

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

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

   489 	 * property list for both sets. */

   490 

   491 	merge_properties(merger);

   492 	merge_files(merger);

   493 

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

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

   496 

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

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

   499 		struct source *src;

   500 

   501 		if (p->flags & UPSTREAM_SOURCE)

   502 			src = &merger->source2;

   503 		else

   504 			src = &merger->source1;

   505 

   506 		emit_properties(&p->properties,

   507 				&src->set->property_pool,

   508 				src->property_map,

   509 				&merger->set->property_pool);

   510 		emit_files(&p->files,

   511 			   &src->set->file_pool,

   512 			   src->file_map,

   513 			   &merger->set->file_pool);

   514 		p->flags &= ~UPSTREAM_SOURCE;

   515 	}

   516 

   517 	rebuild_property_package_lists(merger->set);

   518 	rebuild_file_package_lists(merger->set);

   519 

   520 	result = merger->set;

   521 	hashtable_release(&merger->table);

   522 	free(merger);

   523 

   524 	return result;

   525 }
razor