razor: librazor/razor.c@63444a10fb8e

     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  */

    20 #define _GNU_SOURCE

    22 #include <stdlib.h>

    23 #include <stddef.h>

    24 #include <stdint.h>

    25 #include <stdio.h>

    26 #include <string.h>

    27 #include <sys/types.h>

    28 #include <sys/stat.h>

    29 #include <sys/mman.h>

    30 #include <unistd.h>

    31 #include <fcntl.h>

    32 #include <errno.h>

    33 #include <ctype.h>

    34 #include <fnmatch.h>

    36 #include "razor.h"

    37 #include "razor-internal.h"

    38 #include "types.h"

    40 struct razor_set_section {

    41 	uint32_t type;

    42 	uint32_t offset;

    43 	uint32_t size;

    44 };

    46 struct razor_set_header {

    47 	uint32_t magic;

    48 	uint32_t version;

    49 	struct razor_set_section sections[0];

    50 };

    52 #define RAZOR_MAGIC 0x7a7a7a7a

    53 #define RAZOR_VERSION 1

    55 #define RAZOR_STRING_POOL	0

    56 #define RAZOR_PACKAGES		1

    57 #define RAZOR_PROPERTIES	2

    58 #define RAZOR_FILES		3

    59 #define RAZOR_PACKAGE_POOL	4

    60 #define RAZOR_PROPERTY_POOL	5

    61 #define RAZOR_FILE_POOL		6

    63 struct razor_package {

    64 	uint name  : 24;

    65 	uint flags : 8;

    66 	uint32_t version;

    67 	uint32_t arch;

    68 	struct list_head properties;

    69 	struct list_head files;

    70 };

    72 struct razor_property {

    73 	uint32_t name;

    74 	uint32_t flags;

    75 	uint32_t version;

    76 	struct list_head packages;

    77 };

    79 struct razor_entry {

    80 	uint name  : 24;

    81 	uint flags : 8;

    82 	uint32_t start;

    83 	struct list_head packages;

    84 };

    86 #define RAZOR_ENTRY_LAST	0x80

    88 struct razor_set {

    89 	struct array string_pool;

    90  	struct array packages;

    91  	struct array properties;

    92  	struct array files;

    93 	struct array package_pool;

    94  	struct array property_pool;

    95  	struct array file_pool;

    96 	struct razor_set_header *header;

    97 };

    99 struct import_entry {

   100 	uint32_t package;

   101 	char *name;

   102 };

   104 struct import_directory {

   105 	uint32_t name, count;

   106 	struct array files;

   107 	struct array packages;

   108 	struct import_directory *last;

   109 };

   111 struct razor_importer {

   112 	struct razor_set *set;

   113 	struct hashtable table;

   114 	struct razor_package *package;

   115 	struct array properties;

   116 	struct array files;

   117 	struct array file_requires;

   118 };

   120 static void *

   121 zalloc(size_t size)

   122 {

   123 	void *p;

   125 	p = malloc(size);

   126 	memset(p, 0, size);

   128 	return p;

   129 }

   131 struct razor_set_section razor_sections[] = {

   132 	{ RAZOR_STRING_POOL,	offsetof(struct razor_set, string_pool) },

   133 	{ RAZOR_PACKAGES,	offsetof(struct razor_set, packages) },

   134 	{ RAZOR_PROPERTIES,	offsetof(struct razor_set, properties) },

   135 	{ RAZOR_FILES,		offsetof(struct razor_set, files) },

   136 	{ RAZOR_PACKAGE_POOL,	offsetof(struct razor_set, package_pool) },

   137 	{ RAZOR_PROPERTY_POOL,	offsetof(struct razor_set, property_pool) },

   138 	{ RAZOR_FILE_POOL,	offsetof(struct razor_set, file_pool) },

   139 };

   141 struct razor_set *

   142 razor_set_create(void)

   143 {

   144 	struct razor_set *set;

   145 	struct razor_entry *e;

   146 	char *empty;

   148 	set = zalloc(sizeof *set);

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

   151 	empty = array_add(&set->string_pool, 1);

   152 	*empty = '\0';

   153 	e->name = 0;

   154 	e->flags = RAZOR_ENTRY_LAST;

   155 	e->start = 0;

   156 	list_set_empty(&e->packages);

   158 	return set;

   159 }

   161 struct razor_set *

   162 razor_set_open(const char *filename)

   163 {

   164 	struct razor_set *set;

   165 	struct razor_set_section *s;

   166 	struct stat stat;

   167 	struct array *array;

   168 	int fd;

   170 	set = zalloc(sizeof *set);

   171 	fd = open(filename, O_RDONLY);

   172 	if (fstat(fd, &stat) < 0)

   173 		return NULL;

   174 	set->header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);

   175 	if (set->header == MAP_FAILED) {

   176 		free(set);

   177 		return NULL;

   178 	}

   180 	for (s = set->header->sections; ~s->type; s++) {

   181 		if (s->type >= ARRAY_SIZE(razor_sections))

   182 			continue;

   183 		if (s->type != razor_sections[s->type].type)

   184 			continue;

   185 		array = (void *) set + razor_sections[s->type].offset;

   186 		array->data = (void *) set->header + s->offset;

   187 		array->size = s->size;

   188 		array->alloc = s->size;

   189 	}

   190 	close(fd);

   192 	return set;

   193 }

   195 void

   196 razor_set_destroy(struct razor_set *set)

   197 {

   198 	unsigned int size;

   199 	struct array *a;

   200 	int i;

   202 	if (set->header) {

   203 		for (i = 0; set->header->sections[i].type; i++)

   204 			;

   205 		size = set->header->sections[i].type;

   206 		munmap(set->header, size);

   207 	} else {

   208 		for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {

   209 			a = (void *) set + razor_sections[i].offset;

   210 			free(a->data);

   211 		}

   212 	}

   214 	free(set);

   215 }

   217 int

   218 razor_set_write_to_fd(struct razor_set *set, int fd)

   219 {

   220 	char data[4096];

   221 	struct razor_set_header *header = (struct razor_set_header *) data;

   222 	struct array *a;

   223 	uint32_t offset;

   224 	int i;

   226 	memset(data, 0, sizeof data);

   227 	header->magic = RAZOR_MAGIC;

   228 	header->version = RAZOR_VERSION;

   229 	offset = sizeof data;

   231 	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {

   232 		if (razor_sections[i].type != i)

   233 			continue;

   234 		a = (void *) set + razor_sections[i].offset;

   235 		header->sections[i].type = i;

   236 		header->sections[i].offset = offset;

   237 		header->sections[i].size = a->size;

   238 		offset += ALIGN(a->size, 4096);

   239 	}

   241 	header->sections[i].type = ~0;

   242 	header->sections[i].offset = 0;

   243 	header->sections[i].size = 0;

   245 	razor_write(fd, data, sizeof data);

   246 	memset(data, 0, sizeof data);

   247 	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {

   248 		if (razor_sections[i].type != i)

   249 			continue;

   250 		a = (void *) set + razor_sections[i].offset;

   251 		razor_write(fd, a->data, a->size);

   252 		razor_write(fd, data, ALIGN(a->size, 4096) - a->size);

   253 	}

   255 	return 0;

   256 }

   258 int

   259 razor_set_write(struct razor_set *set, const char *filename)

   260 {

   261 	int fd, status;

   263 	fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, 0666);

   264 	if (fd < 0)

   265 		return -1;

   267 	status = razor_set_write_to_fd(set, fd);

   268 	if (status) {

   269 	    close(fd);

   270 	    return status;

   271 	}

   273 	return close(fd);

   274 }

   276 void

   277 razor_build_evr(char *evr_buf, int size, const char *epoch,

   278 		const char *version, const char *release)

   279 {

   280 	int len;

   282 	if (!version || !*version) {

   283 		*evr_buf = '\0';

   284 		return;

   285 	}

   287 	if (epoch && *epoch && strcmp(epoch, "0") != 0) {

   288 		len = snprintf(evr_buf, size, "%s:", epoch);

   289 		evr_buf += len;

   290 		size -= len;

   291 	}

   292 	len = snprintf(evr_buf, size, "%s", version);

   293 	evr_buf += len;

   294 	size -= len;

   295 	if (release && *release)

   296 		snprintf(evr_buf, size, "-%s", release);

   297 }

   299 void

   300 razor_importer_begin_package(struct razor_importer *importer,

   301 			     const char *name,

   302 			     const char *version,

   303 			     const char *arch)

   304 {

   305 	struct razor_package *p;

   307 	p = array_add(&importer->set->packages, sizeof *p);

   308 	p->name = hashtable_tokenize(&importer->table, name);

   309 	p->flags = 0;

   310 	p->version = hashtable_tokenize(&importer->table, version);

   311 	p->arch = hashtable_tokenize(&importer->table, arch);

   313 	importer->package = p;

   314 	array_init(&importer->properties);

   315 }

   318 void

   319 razor_importer_finish_package(struct razor_importer *importer)

   320 {

   321 	list_set_array(&importer->package->properties,

   322 		       &importer->set->property_pool,

   323 		       &importer->properties,

   324 		       1);

   326 	array_release(&importer->properties);

   327 }

   329 void

   330 razor_importer_add_property(struct razor_importer *importer,

   331 			    const char *name,

   332 			    uint32_t flags,

   333 			    const char *version)

   334 {

   335 	struct razor_property *p;

   336 	uint32_t *r;

   338 	p = array_add(&importer->set->properties, sizeof *p);

   339 	p->name = hashtable_tokenize(&importer->table, name);

   340 	p->flags = flags;

   341 	p->version = hashtable_tokenize(&importer->table, version);

   342 	list_set_ptr(&p->packages, importer->package -

   343 		     (struct razor_package *) importer->set->packages.data);

   345 	r = array_add(&importer->properties, sizeof *r);

   346 	*r = p - (struct razor_property *) importer->set->properties.data;

   348 	if (((flags & RAZOR_PROPERTY_TYPE_MASK) == RAZOR_PROPERTY_REQUIRES) &&

   349 	    *name == '/') {

   350 		r = array_add(&importer->file_requires, sizeof *r);

   351 		*r = p->name;

   352 	}

   353 }

   355 void

   356 razor_importer_add_file(struct razor_importer *importer, const char *name)

   357 {

   358 	struct import_entry *e;

   360 	e = array_add(&importer->files, sizeof *e);

   362 	e->package = importer->package -

   363 		(struct razor_package *) importer->set->packages.data;

   364 	e->name = strdup(name);

   365 }

   367 struct razor_importer *

   368 razor_importer_new(void)

   369 {

   370 	struct razor_importer *importer;

   372 	importer = zalloc(sizeof *importer);

   373 	importer->set = razor_set_create();

   374 	hashtable_init(&importer->table, &importer->set->string_pool);

   376 	return importer;

   377 }

   379 /* Destroy an importer without creating the set. */

   380 void

   381 razor_importer_destroy(struct razor_importer *importer)

   382 {

   383 	/* FIXME: write this */

   384 }

   386 static int

   387 versioncmp(const char *s1, const char *s2)

   388 {

   389 	const char *p1, *p2;

   390 	long n1, n2;

   391 	int res;

   393 	n1 = strtol(s1, (char **) &p1, 10);

   394 	n2 = strtol(s2, (char **) &p2, 10);

   396 	/* Epoch; if one but not the other has an epoch set, default

   397 	 * the epoch-less version to 0. */

   398 	res = (*p1 == ':') - (*p2 == ':');

   399 	if (res < 0) {

   400 		n1 = 0;

   401 		p1 = s1;

   402 		p2++;

   403 	} else if (res > 0) {

   404 		p1++;

   405 		n2 = 0;

   406 		p2 = s2;

   407 	}

   409 	if (n1 != n2)

   410 		return n1 - n2;

   411 	while (*p1 && *p2) {

   412 		if (*p1 != *p2)

   413 			return *p1 - *p2;

   414 		p1++;

   415 		p2++;

   416 		if (isdigit(*p1) && isdigit(*p2))

   417 			return versioncmp(p1, p2);

   418 	}

   420 	return *p1 - *p2;

   421 }

   423 static int

   424 compare_packages(const void *p1, const void *p2, void *data)

   425 {

   426 	const struct razor_package *pkg1 = p1, *pkg2 = p2;

   427 	struct razor_set *set = data;

   428 	char *pool = set->string_pool.data;

   430 	/* FIXME: what if the flags are different? */

   431 	if (pkg1->name == pkg2->name)

   432 		return versioncmp(&pool[pkg1->version], &pool[pkg2->version]);

   433 	else

   434 		return strcmp(&pool[pkg1->name], &pool[pkg2->name]);

   435 }

   437 static int

   438 compare_properties(const void *p1, const void *p2, void *data)

   439 {

   440 	const struct razor_property *prop1 = p1, *prop2 = p2;

   441 	struct razor_set *set = data;

   442 	char *pool = set->string_pool.data;

   444 	if (prop1->name != prop2->name)

   445 		return strcmp(&pool[prop1->name], &pool[prop2->name]);

   446 	else if (prop1->flags != prop2->flags)

   447 		return prop1->flags - prop2->flags;

   448 	else

   449 		return versioncmp(&pool[prop1->version], &pool[prop2->version]);

   450 }

   452 static uint32_t *

   453 uniqueify_properties(struct razor_set *set)

   454 {

   455 	struct razor_property *rp, *up, *rp_end;

   456 	struct array *pkgs, *p;

   457 	struct list_head *r;

   458 	uint32_t *map, *rmap;

   459 	int i, count, unique;

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

   462 	map = razor_qsort_with_data(set->properties.data,

   463 				    count,

   464 				    sizeof(struct razor_property),

   465 				    compare_properties,

   466 				    set);

   468 	rp_end = set->properties.data + set->properties.size;

   469 	rmap = malloc(count * sizeof *map);

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

   471 	for (rp = set->properties.data, up = rp, i = 0; rp < rp_end; rp++, i++) {

   472 		if (rp->name != up->name ||

   473 		    rp->flags != up->flags ||

   474 		    rp->version != up->version) {

   475 			up++;

   476 			up->name = rp->name;

   477 			up->flags = rp->flags;

   478 			up->version = rp->version;

   479 		}

   481 		unique = up - (struct razor_property *) set->properties.data;

   482 		rmap[map[i]] = unique;

   483 		r = array_add(&pkgs[unique], sizeof *r);

   484 		*r = rp->packages;

   485 	}

   486 	free(map);

   488 	if (up != rp)

   489 		up++;

   490 	set->properties.size = (void *) up - set->properties.data;

   491 	rp_end = up;

   492 	for (rp = set->properties.data, p = pkgs; rp < rp_end; rp++, p++) {

   493 		list_set_array(&rp->packages, &set->package_pool, p, 0);

   494 		array_release(p);

   495 	}

   497 	free(pkgs);

   499 	return rmap;

   500 }

   502 static int

   503 compare_filenames(const void *p1, const void *p2, void *data)

   504 {

   505 	const struct import_entry *e1 = p1;

   506 	const struct import_entry *e2 = p2;

   507 	const char *n1 = e1->name;

   508 	const char *n2 = e2->name;

   510 	/* Need to make sure that the contents of a directory

   511 	 * are sorted immediately after it. So "foo/bar" has to

   512 	 * sort before "foo.conf"

   513 	 *

   514 	 * FIXME: this is about 60% slower than strcmp

   515 	 */

   516 	while (*n1 && *n2) {

   517 		if (*n1 < *n2)

   518 			return *n2 == '/' ? 1 : -1;

   519 		else if (*n1 > *n2)

   520 			return *n1 == '/' ? -1 : 1;

   521 		n1++;

   522 		n2++;

   523 	}

   524 	if (*n1)

   525 		return 1;

   526 	else if (*n2)

   527 		return -1;

   528 	else

   529 		return 0;

   530 }

   532 static void

   533 count_entries(struct import_directory *d)

   534 {

   535 	struct import_directory *p, *end;

   537 	p = d->files.data;

   538 	end = d->files.data + d->files.size;

   539 	d->count = 0;

   540 	while (p < end) {

   541 		count_entries(p);

   542 		d->count += p->count + 1;

   543 		p++;

   544 	}

   545 }

   547 static void

   548 serialize_files(struct razor_set *set,

   549 		struct import_directory *d, struct array *array)

   550 {

   551 	struct import_directory *p, *end;

   552 	struct razor_entry *e = NULL;

   553 	uint32_t s;

   555 	p = d->files.data;

   556 	end = d->files.data + d->files.size;

   557 	s = array->size / sizeof *e + d->files.size / sizeof *p;

   558 	while (p < end) {

   559 		e = array_add(array, sizeof *e);

   560 		e->name = p->name;

   561 		e->flags = 0;

   562 		e->start = p->count > 0 ? s : 0;

   563 		s += p->count;

   565 		list_set_array(&e->packages, &set->package_pool, &p->packages, 0);

   566 		array_release(&p->packages);

   567 		p++;

   568 	}

   569 	if (e != NULL)

   570 		e->flags |= RAZOR_ENTRY_LAST;

   572 	p = d->files.data;

   573 	end = d->files.data + d->files.size;

   574 	while (p < end) {

   575 		serialize_files(set, p, array);

   576 		p++;

   577 	}

   578 }

   580 static void

   581 remap_property_package_links(struct array *properties, uint32_t *rmap)

   582 {

   583 	struct razor_property *p, *end;

   585 	end = properties->data + properties->size;

   586 	for (p = properties->data; p < end; p++)

   587 		list_remap_head(&p->packages, rmap);

   588 }

   590 static void

   591 build_file_tree(struct razor_importer *importer)

   592 {

   593 	int count, i, length;

   594 	struct import_entry *filenames;

   595 	char *f, *end;

   596 	uint32_t name, *r;

   597 	char dirname[256];

   598 	struct import_directory *d, root;

   599 	struct razor_entry *e;

   601 	count = importer->files.size / sizeof (struct import_entry);

   602 	razor_qsort_with_data(importer->files.data,

   603 			      count,

   604 			      sizeof (struct import_entry),

   605 			      compare_filenames,

   606 			      NULL);

   608 	root.name = hashtable_tokenize(&importer->table, "");

   609 	array_init(&root.files);

   610 	array_init(&root.packages);

   611 	root.last = NULL;

   613 	filenames = importer->files.data;

   614 	for (i = 0; i < count; i++) {

   615 		f = filenames[i].name;

   616 		if (*f != '/')

   617 			continue;

   618 		f++;

   620 		d = &root;

   621 		while (*f) {

   622 			end = strchr(f, '/');

   623 			if (end == NULL)

   624 				end = f + strlen(f);

   625 			length = end - f;

   626 			memcpy(dirname, f, length);

   627 			dirname[length] ='\0';

   628 			name = hashtable_tokenize(&importer->table, dirname);

   629 			if (d->last == NULL || d->last->name != name) {

   630 				d->last = array_add(&d->files, sizeof *d);

   631 				d->last->name = name;

   632 				d->last->last = NULL;

   633 				array_init(&d->last->files);

   634 				array_init(&d->last->packages);

   635 			}

   636 			d = d->last;

   637 			f = end + 1;

   638 			if (*end == '\0')

   639 				break;

   640 		}

   642 		r = array_add(&d->packages, sizeof *r);

   643 		*r = filenames[i].package;

   644 		free(filenames[i].name);

   645 	}

   647 	count_entries(&root);

   648 	e = importer->set->files.data;

   649 	e->name = root.name;

   650 	e->flags = RAZOR_ENTRY_LAST;

   651 	e->start = importer->files.size ? 1 : 0;

   652 	list_set_empty(&e->packages);

   654 	serialize_files(importer->set, &root, &importer->set->files);

   656 	array_release(&importer->files);

   657 }

   659 static struct razor_entry *

   660 find_entry(struct razor_set *set, struct razor_entry *dir, const char *pattern);

   662 static void

   663 list_to_array(struct list *list, struct array *array)

   664 {

   665 	uint32_t *item;

   667 	while (list) {

   668 		 item = array_add(array, sizeof *item);

   669 		 *item = list->data;

   670 		 list = list_next(list);

   671 	}

   672 }

   674 static int

   675 compare_file_requires(const void *p1, const void *p2, void *data)

   676 {

   677 	uint32_t *f1 = (void *)p1, *f2 = (void *)p2;

   678 	const char *pool = data;

   680 	return strcmp(&pool[*f1], &pool[*f2]);

   681 }

   683 static void

   684 find_file_provides(struct razor_importer *importer)

   685 {

   686 	struct razor_property *prop;

   687 	struct razor_entry *top, *entry;

   688 	struct razor_package *packages;

   689 	struct array pkgprops;

   690 	struct list *pkg;

   691 	uint32_t *req, *req_start, *req_end;

   692 	uint32_t *map, *newprop;

   693 	char *pool;

   695 	pool = importer->set->string_pool.data;

   696 	packages = importer->set->packages.data;

   697 	top = importer->set->files.data;

   699 	req = req_start = importer->file_requires.data;

   700 	req_end = importer->file_requires.data + importer->file_requires.size;

   701 	map = razor_qsort_with_data(req, req_end - req, sizeof *req,

   702 				    compare_file_requires, pool);

   703 	free(map);

   705 	for (req = req_start; req < req_end; req++) {

   706 		if (req > req_start && req[0] == req[-1])

   707 			continue;

   708 		entry = find_entry(importer->set, top, &pool[*req]);

   709 		if (!entry)

   710 			continue;

   712 		for (pkg = list_first(&entry->packages, &importer->set->package_pool); pkg; pkg = list_next(pkg)) {

   713 			prop = array_add(&importer->set->properties, sizeof *prop);

   714 			prop->name = *req;

   715 			prop->flags =

   716 				RAZOR_PROPERTY_PROVIDES | RAZOR_PROPERTY_EQUAL;

   717 			prop->version = hashtable_tokenize(&importer->table, "");

   718 			list_set_ptr(&prop->packages, pkg->data);

   720 			/* Update property list of pkg */

   721 			array_init(&pkgprops);

   722 			list_to_array(list_first(&packages[pkg->data].properties, &importer->set->property_pool), &pkgprops);

   723 			newprop = array_add(&pkgprops, sizeof *newprop);

   724 			*newprop = prop - (struct razor_property *)importer->set->properties.data;

   725 			list_set_array(&packages[pkg->data].properties, &importer->set->property_pool, &pkgprops, 1);

   726 			array_release(&pkgprops);

   727 		}

   728 	}

   730 	array_release(&importer->file_requires);

   731 }

   733 static void

   734 build_package_file_lists(struct razor_set *set, uint32_t *rmap)

   735 {

   736 	struct razor_package *p, *packages;

   737 	struct array *pkgs;

   738 	struct razor_entry *e, *end;

   739 	struct list *r;

   740 	uint32_t *q;

   741 	int i, count;

   743 	count = set->packages.size / sizeof *p;

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

   746 	end = set->files.data + set->files.size;

   747 	for (e = set->files.data; e < end; e++) {

   748 		list_remap_head(&e->packages, rmap);

   749 		r = list_first(&e->packages, &set->package_pool);

   750 		while (r) {

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

   752 			*q = e - (struct razor_entry *) set->files.data;

   753 			r = list_next(r);

   754 		}

   755 	}

   757 	packages = set->packages.data;

   758 	for (i = 0; i < count; i++) {

   759 		list_set_array(&packages[i].files, &set->file_pool, &pkgs[i], 0);

   760 		array_release(&pkgs[i]);

   761 	}

   762 	free(pkgs);

   763 }

   765 struct razor_set *

   766 razor_importer_finish(struct razor_importer *importer)

   767 {

   768 	struct razor_set *set;

   769 	uint32_t *map, *rmap;

   770 	int i, count;

   772 	build_file_tree(importer);

   773 	find_file_provides(importer);

   775 	map = uniqueify_properties(importer->set);

   776 	list_remap_pool(&importer->set->property_pool, map);

   777 	free(map);

   779 	count = importer->set->packages.size / sizeof(struct razor_package);

   780 	map = razor_qsort_with_data(importer->set->packages.data,

   781 				    count,

   782 				    sizeof(struct razor_package),

   783 				    compare_packages,

   784 				    importer->set);

   786 	rmap = malloc(count * sizeof *rmap);

   787 	for (i = 0; i < count; i++)

   788 		rmap[map[i]] = i;

   789 	free(map);

   791 	list_remap_pool(&importer->set->package_pool, rmap);

   792 	build_package_file_lists(importer->set, rmap);

   793 	remap_property_package_links(&importer->set->properties, rmap);

   794 	free(rmap);

   796 	set = importer->set;

   797 	hashtable_release(&importer->table);

   798 	free(importer);

   800 	return set;

   801 }

   803 struct razor_package_iterator {

   804 	struct razor_set *set;

   805 	struct razor_package *package, *end;

   806 	struct list *index;

   807 	int free_index;

   808 };

   810 static struct razor_package_iterator *

   811 razor_package_iterator_create_with_index(struct razor_set *set,

   812 					 struct list *index)

   813 {

   814 	struct razor_package_iterator *pi;

   816 	pi = zalloc(sizeof *pi);

   817 	pi->set = set;

   818 	pi->index = index;

   820 	return pi;

   821 }

   823 struct razor_package_iterator *

   824 razor_package_iterator_create(struct razor_set *set)

   825 {

   826 	struct razor_package_iterator *pi;

   828 	pi = zalloc(sizeof *pi);

   829 	pi->set = set;

   830 	pi->end = set->packages.data + set->packages.size;

   831 	pi->package = set->packages.data;

   833 	return pi;

   834 }

   836 static void

   837 razor_package_iterator_init_for_property(struct razor_package_iterator *pi,

   838 					 struct razor_set *set,

   839 					 struct razor_property *property)

   840 {

   841 	memset(pi, 0, sizeof *pi);

   842 	pi->set = set;

   843 	pi->index = list_first(&property->packages, &set->package_pool);

   844 }

   846 struct razor_package_iterator *

   847 razor_package_iterator_create_for_property(struct razor_set *set,

   848 					   struct razor_property *property)

   849 {

   850 	struct list *index;

   852 	index = list_first(&property->packages, &set->package_pool);

   853 	return razor_package_iterator_create_with_index(set, index);

   854 }

   856 int

   857 razor_package_iterator_next(struct razor_package_iterator *pi,

   858 			    struct razor_package **package,

   859 			    const char **name,

   860 			    const char **version,

   861 			    const char **arch)

   862 {

   863 	char *pool;

   864 	int valid;

   865 	struct razor_package *p, *packages;

   867 	if (pi->package) {

   868 		p = pi->package++;

   869 		valid = p < pi->end;

   870 	} else if (pi->index) {

   871 		packages = pi->set->packages.data;

   872 		p = &packages[pi->index->data];

   873 		pi->index = list_next(pi->index);

   874 		valid = 1;

   875 	} else

   876 		valid = 0;

   878 	if (valid) {

   879 		pool = pi->set->string_pool.data;

   880 		*package = p;

   881 		*name = &pool[p->name];

   882 		*version = &pool[p->version];

   883 		*arch = &pool[p->arch];

   884 	} else {

   885 		*package = NULL;

   886 	}

   888 	return valid;

   889 }

   891 void

   892 razor_package_iterator_destroy(struct razor_package_iterator *pi)

   893 {

   894 	if (pi->free_index)

   895 		free(pi->index);

   897 	free(pi);

   898 }

   900 struct razor_package *

   901 razor_set_get_package(struct razor_set *set, const char *package)

   902 {

   903 	struct razor_package_iterator *pi;

   904 	struct razor_package *p;

   905 	const char *name, *version, *arch;

   907 	pi = razor_package_iterator_create(set);

   908 	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {

   909 		if (strcmp(package, name) == 0)

   910 			break;

   911 	}

   912 	razor_package_iterator_destroy(pi);

   914 	return p;

   915 }

   917 struct razor_property_iterator {

   918 	struct razor_set *set;

   919 	struct razor_property *property, *end;

   920 	struct list *index;

   921 };

   923 struct razor_property_iterator *

   924 razor_property_iterator_create(struct razor_set *set,

   925 			       struct razor_package *package)

   926 {

   927 	struct razor_property_iterator *pi;

   929 	pi = zalloc(sizeof *pi);

   930 	pi->set = set;

   932 	if (package) {

   933 		pi->index = list_first(&package->properties,

   934 				       &set->property_pool);

   935 	} else {

   936 		pi->property = set->properties.data;

   937 		pi->end = set->properties.data + set->properties.size;

   938 	}

   940 	return pi;

   941 }

   943 int

   944 razor_property_iterator_next(struct razor_property_iterator *pi,

   945 			     struct razor_property **property,

   946 			     const char **name,

   947 			     uint32_t *flags,

   948 			     const char **version)

   949 {

   950 	char *pool;

   951 	int valid;

   952 	struct razor_property *p, *properties;

   954 	if (pi->property) {

   955 		p = pi->property++;

   956 		valid = p < pi->end;

   957 	} else if (pi->index) {

   958 		properties = pi->set->properties.data;

   959 		p = &properties[pi->index->data];

   960 		pi->index = list_next(pi->index);

   961 		valid = 1;

   962 	} else

   963 		valid = 0;

   965 	if (valid) {

   966 		pool = pi->set->string_pool.data;

   967 		*property = p;

   968 		*name = &pool[p->name];

   969 		*flags = p->flags;

   970 		*version = &pool[p->version];

   971 	} else {

   972 		*property = NULL;

   973 	}

   975 	return valid;

   976 }

   978 void

   979 razor_property_iterator_destroy(struct razor_property_iterator *pi)

   980 {

   981 	free(pi);

   982 }

   984 static struct razor_entry *

   985 find_entry(struct razor_set *set, struct razor_entry *dir, const char *pattern)

   986 {

   987 	struct razor_entry *e;

   988 	const char *n, *pool = set->string_pool.data;

   989 	int len;

   991 	e = (struct razor_entry *) set->files.data + dir->start;

   992 	do {

   993 		n = pool + e->name;

   994 		if (strcmp(pattern + 1, n) == 0)

   995 			return e;

   996 		len = strlen(n);

   997 		if (e->start != 0 && strncmp(pattern + 1, n, len) == 0 &&

   998 		    pattern[len + 1] == '/') {

   999 			return find_entry(set, e, pattern + len + 1);

  1000 		}

  1001 	} while (!((e++)->flags & RAZOR_ENTRY_LAST));

  1003 	return NULL;

  1004 }

  1006 static void

  1007 list_dir(struct razor_set *set, struct razor_entry *dir,

  1008 	 char *prefix, const char *pattern)

  1009 {

  1010 	struct razor_entry *e;

  1011 	const char *n, *pool = set->string_pool.data;

  1013 	e = (struct razor_entry *) set->files.data + dir->start;

  1014 	do {

  1015 		n = pool + e->name;

  1016 		if (pattern && pattern[0] && fnmatch(pattern, n, 0) != 0)

  1017 			continue;

  1018 		printf("%s/%s\n", prefix, n);

  1019 		if (e->start) {

  1020 			char *sub = prefix + strlen (prefix);

  1021 			*sub = '/';

  1022 			strcpy (sub + 1, n);

  1023 			list_dir(set, e, prefix, pattern);

  1024 			*sub = '\0';

  1025 		}

  1026 	} while (!((e++)->flags & RAZOR_ENTRY_LAST));

  1027 }

  1029 void

  1030 razor_set_list_files(struct razor_set *set, const char *pattern)

  1031 {

  1032 	struct razor_entry *e;

  1033 	char buffer[512], *p, *base;

  1035 	if (pattern == NULL || !strcmp (pattern, "/")) {

  1036 		buffer[0] = '\0';

  1037 		list_dir(set, set->files.data, buffer, NULL);

  1038 		return;

  1039 	}

  1041 	strcpy(buffer, pattern);

  1042 	e = find_entry(set, set->files.data, buffer);

  1043 	if (e && e->start > 0) {

  1044 		base = NULL;

  1045 	} else {

  1046 		p = strrchr(buffer, '/');

  1047 		if (p) {

  1048 			*p = '\0';

  1049 			base = p + 1;

  1050 		} else {

  1051 			base = NULL;

  1052 		}

  1053 	}

  1054 	e = find_entry(set, set->files.data, buffer);

  1055 	if (e->start != 0)

  1056 		list_dir(set, e, buffer, base);

  1057 }

  1059 struct razor_package_iterator *

  1060 razor_package_iterator_create_for_file(struct razor_set *set,

  1061 				       const char *filename)

  1062 {

  1063 	struct razor_entry *entry;

  1064 	struct list *index;

  1066 	entry = find_entry(set, set->files.data, filename);

  1067 	if (entry == NULL)

  1068 		return NULL;

  1070 	index = list_first(&entry->packages, &set->package_pool);

  1071 	return razor_package_iterator_create_with_index(set, index);

  1072 }

  1074 static struct list *

  1075 list_package_files(struct razor_set *set, struct list *r,

  1076 		   struct razor_entry *dir, uint32_t end,

  1077 		   char *prefix)

  1078 {

  1079 	struct razor_entry *e, *f, *entries;

  1080 	uint32_t next, file;

  1081 	char *pool;

  1082 	int len;

  1084 	entries = (struct razor_entry *) set->files.data;

  1085 	pool = set->string_pool.data;

  1087 	e = entries + dir->start;

  1088 	do {

  1089 		if (entries + r->data == e) {

  1090 			printf("%s/%s\n", prefix, pool + e->name);

  1091 			r = list_next(r);

  1092 			if (!r)

  1093 				return NULL;

  1094 			if (r->data >= end)

  1095 				return r;

  1096 		}

  1097 	} while (!((e++)->flags & RAZOR_ENTRY_LAST));

  1099 	e = entries + dir->start;

  1100 	do {

  1101 		if (e->start == 0)

  1102 			continue;

  1104 		if (e->flags & RAZOR_ENTRY_LAST)

  1105 			next = end;

  1106 		else {

  1107 			f = e + 1;

  1108 			while (f->start == 0 && !(f->flags & RAZOR_ENTRY_LAST))

  1109 				f++;

  1110 			if (f->start == 0)

  1111 				next = end;

  1112 			else

  1113 				next = f->start;

  1114 		}

  1116 		file = r->data;

  1117 		if (e->start <= file && file < next) {

  1118 			len = strlen(prefix);

  1119 			prefix[len] = '/';

  1120 			strcpy(prefix + len + 1, pool + e->name);

  1121 			r = list_package_files(set, r, e, next, prefix);

  1122 			prefix[len] = '\0';

  1123 		}

  1124 	} while (!((e++)->flags & RAZOR_ENTRY_LAST) && r != NULL);

  1126 	return r;

  1127 }

  1129 void

  1130 razor_set_list_package_files(struct razor_set *set, const char *name)

  1131 {

  1132 	struct razor_package *package;

  1133 	struct list *r;

  1134 	uint32_t end;

  1135 	char buffer[512];

  1137 	package = razor_set_get_package(set, name);

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

  1140 	end = set->files.size / sizeof (struct razor_entry);

  1141 	buffer[0] = '\0';

  1142 	list_package_files(set, r, set->files.data, end, buffer);

  1143 }

  1145 #define UPSTREAM_SOURCE 0x80

  1147 struct source {

  1148 	struct razor_set *set;

  1149 	uint32_t *property_map;

  1150 	uint32_t *file_map;

  1151 };

  1153 struct razor_merger {

  1154 	struct razor_set *set;

  1155 	struct hashtable table;

  1156 	struct source source1;

  1157 	struct source source2;

  1158 };

  1160 static struct razor_merger *

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

  1162 {

  1163 	struct razor_merger *merger;

  1164 	int count;

  1165 	size_t size;

  1167 	merger = zalloc(sizeof *merger);

  1168 	merger->set = razor_set_create();

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

  1171 	merger->source1.set = set1;

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

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

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

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

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

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

  1179 	merger->source2.set = set2;

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

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

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

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

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

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

  1187 	return merger;

  1188 }

  1190 static void

  1191 razor_merger_add_package(struct razor_merger *merger,

  1192 			 struct razor_package *package)

  1193 {

  1194 	char *pool;

  1195 	struct list *r;

  1196 	struct razor_package *p;

  1197 	struct razor_set *set1;

  1198 	struct source *source;

  1199 	uint32_t flags;

  1201 	set1 = merger->source1.set;

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

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

  1204 		source = &merger->source1;

  1205 		flags = 0;

  1206 	} else {

  1207 		source = &merger->source2;

  1208 		flags = UPSTREAM_SOURCE;

  1209 	}

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

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

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

  1214 	p->flags = flags;

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

  1216 					&pool[package->version]);

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

  1218 				     &pool[package->arch]);

  1220 	p->properties = package->properties;

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

  1222 	while (r) {

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

  1224 		r = list_next(r);

  1225 	}

  1227 	p->files = package->files;

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

  1229 	while (r) {

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

  1231 		r = list_next(r);

  1232 	}

  1233 }

  1235 static uint32_t

  1236 add_property(struct razor_merger *merger,

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

  1238 {

  1239 	struct razor_property *p;

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

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

  1243 	p->flags = flags;

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

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

  1247 }

  1249 static void

  1250 merge_properties(struct razor_merger *merger)

  1251 {

  1252 	struct razor_property *p1, *p2;

  1253 	struct razor_set *set1, *set2;

  1254 	uint32_t *map1, *map2;

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

  1256 	char *pool1, *pool2;

  1258 	set1 = merger->source1.set;

  1259 	set2 = merger->source2.set;

  1260 	map1 = merger->source1.property_map;

  1261 	map2 = merger->source2.property_map;

  1263 	i = 0;

  1264 	j = 0;

  1265 	pool1 = set1->string_pool.data;

  1266 	pool2 = set2->string_pool.data;

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

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

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

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

  1272 			i++;

  1273 			continue;

  1274 		}

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

  1276 			j++;

  1277 			continue;

  1278 		}

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

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

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

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

  1283 		else if (i < count1)

  1284 			cmp = -1;

  1285 		else

  1286 			cmp = 1;

  1287 		if (cmp == 0)

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

  1289 		if (cmp == 0)

  1290 			cmp = versioncmp(&pool1[p1->version],

  1291 					 &pool2[p2->version]);

  1292 		if (cmp < 0) {

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

  1294 						 &pool1[p1->name],

  1295 						 p1->flags,

  1296 						 &pool1[p1->version]);

  1297 		} else if (cmp > 0) {

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

  1299 						 &pool2[p2->name],

  1300 						 p2->flags,

  1301 						 &pool2[p2->version]);

  1302 		} else  {

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

  1304 				add_property(merger,

  1305 					     &pool1[p1->name],

  1306 					     p1->flags,

  1307 					     &pool1[p1->version]);

  1308 		}

  1309 	}

  1310 }

  1312 static void

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

  1314 		uint32_t *map, struct array *pool)

  1315 {

  1316 	uint32_t r;

  1317 	struct list *p, *q;

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

  1320 	p = list_first(properties, source_pool);

  1321 	while (p) {

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

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

  1324 		q->flags = p->flags;

  1325 		p = list_next(p);

  1326 	}

  1328 	list_set_ptr(properties, r);

  1329 }

  1331 static uint32_t

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

  1333 {

  1334 	struct razor_entry *e;

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

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

  1338 	e->flags = 0;

  1339 	e->start = 0;

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

  1342 }

  1344 /* FIXME. Blah */

  1345 static int

  1346 fix_file_map(uint32_t *map,

  1347 	     struct razor_entry *files,

  1348 	     struct razor_entry *top)

  1349 {

  1350 	uint32_t e;

  1351 	int found_file = 0;

  1353 	e = top->start;

  1354 	do {

  1355 		if (files[e].start)

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

  1357 		if (map[e])

  1358 			found_file = 1;

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

  1361 	if (found_file)

  1362 		map[top - files] = 1;

  1363 	return found_file;

  1364 }

  1366 struct merge_directory {

  1367 	uint32_t merged, dir1, dir2;

  1368 };

  1370 static void

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

  1372 {

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

  1374 	struct razor_set *set1, *set2;

  1375 	struct array merge_stack;

  1376 	struct merge_directory *child_md, *end_md;

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

  1378 	int cmp;

  1379 	char *pool1, *pool2;

  1381 	set1 = merger->source1.set;

  1382 	set2 = merger->source2.set;

  1383 	map1 = merger->source1.file_map;

  1384 	map2 = merger->source2.file_map;

  1385 	pool1 = set1->string_pool.data;

  1386 	pool2 = set2->string_pool.data;

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

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

  1390 	array_init(&merge_stack);

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

  1393 	last = 0;

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

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

  1396 	while (e1 || e2) {

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

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

  1399 				e1 = NULL;

  1400 			continue;

  1401 		}

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

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

  1404 				e2 = NULL;

  1405 			continue;

  1406 		}

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

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

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

  1410 				e1 = NULL;

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

  1412 				e2 = NULL;

  1413 			continue;

  1414 		}

  1416 		if (!e1)

  1417 			cmp = 1;

  1418 		else if (!e2)

  1419 			cmp = -1;

  1420 		else {

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

  1422 				      &pool2[e2->name]);

  1423 		}

  1425 		if (cmp < 0) {

  1426 			if (map1[e1 - root1]) {

  1427 				map1[e1 - root1] = last =

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

  1429 				if (e1->start) {

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

  1431 					child_md->merged = last;

  1432 					child_md->dir1 = e1->start;

  1433 					child_md->dir2 = 0;

  1434 				}

  1435 			}

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

  1437 				e1 = NULL;

  1438 		} else if (cmp > 0) {

  1439 			if (map2[e2 - root2]) {

  1440 				map2[e2 - root2] = last =

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

  1442 				if (e2->start) {

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

  1444 					child_md->merged = last;

  1445 					child_md->dir1 = 0;

  1446 					child_md->dir2 = e2->start;

  1447 				}

  1448 			}

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

  1450 				e2 = NULL;

  1451 		} else {

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

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

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

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

  1456 				child_md->merged = last;

  1457 				child_md->dir1 = e1->start;

  1458 				child_md->dir2 = e2->start;

  1459 			}

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

  1461 				e1 = NULL;

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

  1463 				e2 = NULL;

  1464 		}

  1465 	}

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

  1468 	if (last) {

  1469 		mroot[last].flags = RAZOR_ENTRY_LAST;

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

  1471 	} else

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

  1474 	end_md = merge_stack.data + merge_stack.size;

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

  1476 		merge_one_directory(merger, child_md);

  1477 	array_release(&merge_stack);

  1478 }

  1480 static void

  1481 merge_files(struct razor_merger *merger)

  1482 {

  1483 	struct razor_entry *root;

  1484 	struct merge_directory md;

  1485 	uint32_t *map1, *map2;

  1487 	map1 = merger->source1.file_map;

  1488 	map2 = merger->source2.file_map;

  1490 	md.merged = 0;

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

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

  1494 		if (root->start)

  1495 			fix_file_map(map1, root, root);

  1496 		md.dir1 = root->start;

  1497 	} else

  1498 		md.dir1 = 0;

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

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

  1502 		if (root->start)

  1503 			fix_file_map(map2, root, root);

  1504 		md.dir2 = root->start;

  1505 	} else

  1506 		md.dir2 = 0;

  1508 	merge_one_directory(merger, &md);

  1509 }

  1511 static void

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

  1513 	   uint32_t *map, struct array *pool)

  1514 {

  1515 	uint32_t r;

  1516 	struct list *p, *q;

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

  1519 	p = list_first(files, source_pool);

  1520 	while (p) {

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

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

  1523 		q->flags = p->flags;

  1524 		p = list_next(p);

  1525 	}

  1527 	list_set_ptr(files, r);

  1528 }

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

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

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

  1533  * the arrays for their properties. */

  1534 static void

  1535 rebuild_property_package_lists(struct razor_set *set)

  1536 {

  1537 	struct array *pkgs, *a;

  1538 	struct razor_package *pkg, *pkg_end;

  1539 	struct razor_property *prop, *prop_end;

  1540 	struct list *r;

  1541 	uint32_t *q;

  1542 	int count;

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

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

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

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

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

  1550 		while (r) {

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

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

  1553 			r = list_next(r);

  1554 		}

  1555 	}

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

  1558 	a = pkgs;

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

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

  1561 		array_release(a);

  1562 	}

  1563 	free(pkgs);

  1564 }

  1566 static void

  1567 rebuild_file_package_lists(struct razor_set *set)

  1568 {

  1569 	struct array *pkgs, *a;

  1570 	struct razor_package *pkg, *pkg_end;

  1571 	struct razor_entry *entry, *entry_end;

  1572 	struct list *r;

  1573 	uint32_t *q;

  1574 	int count;

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

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

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

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

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

  1582 		while (r) {

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

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

  1585 			r = list_next(r);

  1586 		}

  1587 	}

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

  1590 	a = pkgs;

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

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

  1593 		array_release(a);

  1594 	}

  1595 	free(pkgs);

  1596 }

  1598 static struct razor_set *

  1599 razor_merger_finish(struct razor_merger *merger)

  1600 {

  1601 	struct razor_set *result;

  1602 	struct razor_package *p, *pend;

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

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

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

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

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

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

  1610 	 * property list for both sets. */

  1612 	merge_properties(merger);

  1613 	merge_files(merger);

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

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

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

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

  1620 		struct source *src;

  1622 		if (p->flags & UPSTREAM_SOURCE)

  1623 			src = &merger->source2;

  1624 		else

  1625 			src = &merger->source1;

  1627 		emit_properties(&p->properties,

  1628 				&src->set->property_pool,

  1629 				src->property_map,

  1630 				&merger->set->property_pool);

  1631 		emit_files(&p->files,

  1632 			   &src->set->file_pool,

  1633 			   src->file_map,

  1634 			   &merger->set->file_pool);

  1635 		p->flags &= ~UPSTREAM_SOURCE;

  1636 	}

  1638 	rebuild_property_package_lists(merger->set);

  1639 	rebuild_file_package_lists(merger->set);

  1641 	result = merger->set;

  1642 	hashtable_release(&merger->table);

  1643 	free(merger);

  1645 	return result;

  1646 }

  1648 /* The diff order matters.  We should sort the packages so that a

  1649  * REMOVE of a package comes before the INSTALL, and so that all

  1650  * requires for a package have been installed before the package.

  1651  **/

  1653 void

  1654 razor_set_diff(struct razor_set *set, struct razor_set *upstream,

  1655 	       razor_package_callback_t callback, void *data)

  1656 {

  1657  	struct razor_package_iterator *pi1, *pi2;

  1658  	struct razor_package *p1, *p2;

  1659 	const char *name1, *name2, *version1, *version2, *arch1, *arch2;

  1660 	int res;

  1662 	pi1 = razor_package_iterator_create(set);

  1663 	pi2 = razor_package_iterator_create(upstream);

  1665 	razor_package_iterator_next(pi1, &p1, &name1, &version1, &arch1);

  1666 	razor_package_iterator_next(pi2, &p2, &name2, &version2, &arch2);

  1668 	while (p1 || p2) {

  1669 		if (p1 && p2) {

  1670 			res = strcmp(name1, name2);

  1671 			if (res == 0)

  1672 				res = versioncmp(version1, version2);

  1673 		} else {

  1674 			res = 0;

  1675 		}

  1677 		if (p2 == NULL || res < 0)

  1678 			callback(name1, version1, NULL, arch1, data);

  1679 		else if (p1 == NULL || res > 0)

  1680 			callback(name2, NULL, version2, arch2, data);

  1682 		if (p1 != NULL && res <= 0)

  1683 			razor_package_iterator_next(pi1, &p1,

  1684 						    &name1, &version1, &arch1);

  1685 		if (p2 != NULL && res >= 0)

  1686 			razor_package_iterator_next(pi2, &p2,

  1687 						    &name2, &version2, &arch2);

  1688 	}

  1690 	razor_package_iterator_destroy(pi1);

  1691 	razor_package_iterator_destroy(pi2);

  1692 }

  1694 static int

  1695 provider_satisfies_requirement(struct razor_property *provider,

  1696 			       const char *provider_strings,

  1697 			       uint32_t flags,

  1698 			       const char *required)

  1699 {

  1700 	int cmp, len;

  1701 	const char *provided = &provider_strings[provider->version];

  1703 	if (!*required)

  1704 		return 1;

  1705 	if (!*provided) {

  1706 		if (flags & RAZOR_PROPERTY_LESS)

  1707 			return 0;

  1708 		else

  1709 			return 1;

  1710 	}

  1712 	cmp = versioncmp(provided, required);

  1714 	switch (flags & RAZOR_PROPERTY_RELATION_MASK) {

  1715 	case RAZOR_PROPERTY_LESS:

  1716 		return cmp < 0;

  1718 	case RAZOR_PROPERTY_LESS | RAZOR_PROPERTY_EQUAL:

  1719 		if (cmp <= 0)

  1720 			return 1;

  1721 		/* fall through: FIXME, make sure this is correct */

  1723 	case RAZOR_PROPERTY_EQUAL:

  1724 		if (cmp == 0)

  1725 			return 1;

  1727 		/* "foo == 1.1" is satisfied by "foo 1.1-2" */

  1728 		len = strlen(required);

  1729 		if (!strncmp(required, provided, len) && provided[len] == '-')

  1730 			return 1;

  1731 		return 0;

  1733 	case RAZOR_PROPERTY_GREATER | RAZOR_PROPERTY_EQUAL:

  1734 		return cmp >= 0;

  1736 	case RAZOR_PROPERTY_GREATER:

  1737 		return cmp > 0;

  1738 	}

  1740 	/* shouldn't happen */

  1741 	return 0;

  1742 }

  1744 #define TRANS_PACKAGE_PRESENT		1

  1745 #define TRANS_PACKAGE_UPDATE		2

  1746 #define TRANS_PROPERTY_SATISFIED	0x80000000

  1748 struct transaction_set {

  1749 	struct razor_set *set;

  1750 	uint32_t *packages;

  1751 	uint32_t *properties;

  1752 };

  1754 struct razor_transaction {

  1755 	int package_count, errors;

  1756 	struct transaction_set system, upstream;

  1757 	int changes;

  1758 };

  1760 static void

  1761 transaction_set_init(struct transaction_set *ts, struct razor_set *set)

  1762 {

  1763 	int count;

  1765 	ts->set = set;

  1766 	count = set->packages.size / sizeof (struct razor_package);

  1767 	ts->packages = zalloc(count * sizeof *ts->packages);

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

  1769 	ts->properties = zalloc(count * sizeof *ts->properties);

  1770 }

  1772 static void

  1773 transaction_set_release(struct transaction_set *ts)

  1774 {

  1775 	free(ts->packages);

  1776 	free(ts->properties);

  1777 }

  1779 static void

  1780 transaction_set_install_package(struct transaction_set *ts,

  1781 				struct razor_package *package)

  1782 {

  1783 	struct razor_package *pkgs;

  1784 	struct list *prop;

  1785 	int i;

  1787 	pkgs = ts->set->packages.data;

  1788 	i = package - pkgs;

  1789 	if (ts->packages[i] == TRANS_PACKAGE_PRESENT)

  1790 		return;

  1792 	ts->packages[i] = TRANS_PACKAGE_PRESENT;

  1794 	prop = list_first(&package->properties, &ts->set->property_pool);

  1795 	while (prop) {

  1796 		ts->properties[prop->data]++;

  1797 		prop = list_next(prop);

  1798 	}

  1799 }

  1801 static void

  1802 transaction_set_remove_package(struct transaction_set *ts,

  1803 			       struct razor_package *package)

  1804 {

  1805 	struct razor_package *pkgs;

  1806 	struct list *prop;

  1807 	int i;

  1809 	pkgs = ts->set->packages.data;

  1810 	i = package - pkgs;

  1811 	if (ts->packages[i] == 0)

  1812 		return;

  1814 	ts->packages[i] = 0;

  1816 	prop = list_first(&package->properties, &ts->set->property_pool);

  1817 	while (prop) {

  1818 		ts->properties[prop->data]--;

  1819 		prop = list_next(prop);

  1820 	}

  1821 }

  1823 struct razor_transaction *

  1824 razor_transaction_create(struct razor_set *system, struct razor_set *upstream)

  1825 {

  1826 	struct razor_transaction *trans;

  1827 	struct razor_package *p, *spkgs, *pend;

  1829 	trans = zalloc(sizeof *trans);

  1830 	transaction_set_init(&trans->system, system);

  1831 	transaction_set_init(&trans->upstream, upstream);

  1833 	spkgs = trans->system.set->packages.data;

  1834 	pend = trans->system.set->packages.data +

  1835 		trans->system.set->packages.size;

  1836 	for (p = spkgs; p < pend; p++)

  1837 		transaction_set_install_package(&trans->system, p);

  1839 	return trans;

  1840 }

  1842 void

  1843 razor_transaction_install_package(struct razor_transaction *trans,

  1844 				  struct razor_package *package)

  1845 {

  1846 	transaction_set_install_package(&trans->upstream, package);

  1847 	trans->changes++;

  1848 }

  1850 void

  1851 razor_transaction_remove_package(struct razor_transaction *trans,

  1852 				 struct razor_package *package)

  1853 {

  1854 	transaction_set_remove_package(&trans->system, package);

  1855 	trans->changes++;

  1856 }

  1858 void

  1859 razor_transaction_update_package(struct razor_transaction *trans,

  1860 				  struct razor_package *package)

  1861 {

  1862 	struct razor_package *spkgs, *upkgs, *end;

  1864 	spkgs = trans->system.set->packages.data;

  1865 	upkgs = trans->upstream.set->packages.data;

  1866 	end = trans->system.set->packages.data +

  1867 		trans->system.set->packages.size;

  1868 	if (spkgs <= package && package < end)

  1869 		trans->system.packages[package - spkgs] |= TRANS_PACKAGE_UPDATE;

  1870 	else

  1871 		trans->upstream.packages[package - upkgs] |= TRANS_PACKAGE_UPDATE;

  1872 }

  1874 struct prop_iter {

  1875 	struct razor_property *p, *start, *end;

  1876 	const char *pool;

  1877 	uint32_t *present;

  1878 };

  1880 static void

  1881 prop_iter_init(struct prop_iter *pi, struct transaction_set *ts)

  1882 {

  1883 	pi->p = ts->set->properties.data;

  1884 	pi->start = ts->set->properties.data;

  1885 	pi->end = ts->set->properties.data + ts->set->properties.size;

  1886 	pi->pool = ts->set->string_pool.data;

  1887 	pi->present = ts->properties;

  1888 }

  1890 static int

  1891 prop_iter_next(struct prop_iter *pi, uint32_t flags, struct razor_property **p)

  1892 {

  1893 	while (pi->p < pi->end) {

  1894 		if ((pi->present[pi->p - pi->start] & ~TRANS_PROPERTY_SATISFIED) &&

  1895 		    (pi->p->flags & RAZOR_PROPERTY_TYPE_MASK) == flags) {

  1896 			*p = pi->p++;

  1897 			return 1;

  1898 		}

  1899 		pi->p++;

  1900 	}

  1902 	return 0;

  1903 }

  1905 static struct razor_property *

  1906 prop_iter_seek_to(struct prop_iter *pi,

  1907 		  uint32_t flags, const char *match)

  1908 {

  1909 	uint32_t name;

  1911 	while (pi->p < pi->end && strcmp(&pi->pool[pi->p->name], match) < 0)

  1912 		pi->p++;

  1914 	if (pi->p == pi->end || strcmp(&pi->pool[pi->p->name], match) > 0)

  1915 		return NULL;

  1917 	name = pi->p->name;

  1918 	while (pi->p < pi->end &&

  1919 	       pi->p->name == name &&

  1920 	       (pi->p->flags & RAZOR_PROPERTY_TYPE_MASK) != flags)

  1921 		pi->p++;

  1923 	if (pi->p == pi->end || pi->p->name != name)

  1924 		return NULL;

  1926 	return pi->p;

  1927 }

  1929 /* Remove packages from set that provide any of the matching (same

  1930  * name and type) providers from ppi onwards that match the

  1931  * requirement that rpi points to. */

  1932 static void

  1933 remove_matching_providers(struct razor_transaction *trans,

  1934 			  struct prop_iter *ppi,

  1935 			  uint32_t flags,

  1936 			  const char *version)

  1937 {

  1938 	struct razor_property *p;

  1939 	struct razor_package *pkg, *pkgs;

  1940 	struct razor_package_iterator pkg_iter;

  1941 	struct razor_set *set;

  1942 	const char *n, *v, *a;

  1943 	uint32_t type;

  1945 	if (ppi->present == trans->system.properties)

  1946 		set = trans->system.set;

  1947 	else

  1948 		set = trans->upstream.set;

  1950 	pkgs = (struct razor_package *) set->packages.data;

  1951 	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;

  1952 	for (p = ppi->p;

  1953 	     p < ppi->end &&

  1954 	     p->name == ppi->p->name &&

  1955 	     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;

  1956 	     p++) {

  1957 		if (!ppi->present[p - ppi->start])

  1958 			continue;

  1959 		if (!provider_satisfies_requirement(p, ppi->pool,

  1960 						    flags, version))

  1961 			continue;

  1963 		razor_package_iterator_init_for_property(&pkg_iter, set, p);

  1964 		while (razor_package_iterator_next(&pkg_iter,

  1965 						   &pkg, &n, &v, &a)) {

  1966 			fprintf(stderr, "removing %s-%s\n", n, v);

  1967 			razor_transaction_remove_package(trans, pkg);

  1968 		}

  1969 	}

  1970 }

  1972 static void

  1973 flag_matching_providers(struct razor_transaction *trans,

  1974 			struct prop_iter *ppi,

  1975 			struct razor_property *r,

  1976 			struct prop_iter *rpi,

  1977 			unsigned int flag)

  1978 {

  1979 	struct razor_property *p;

  1980 	struct razor_package *pkg, *pkgs;

  1981 	struct razor_package_iterator pkg_iter;

  1982 	struct razor_set *set;

  1983 	const char *name, *version, *arch;

  1984 	uint32_t *flags, type;

  1986 	if (ppi->present == trans->system.properties) {

  1987 		set = trans->system.set;

  1988 		flags = trans->system.packages;

  1989 	} else {

  1990 		set = trans->upstream.set;

  1991 		flags = trans->upstream.packages;

  1992 	}

  1994 	pkgs = (struct razor_package *) set->packages.data;

  1995 	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;

  1996 	for (p = ppi->p;

  1997 	     p < ppi->end &&

  1998 		     p->name == ppi->p->name &&

  1999 		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;

  2000 	     p++) {

  2001 		if (!ppi->present[p - ppi->start])

  2002 			continue;

  2003 		if (!provider_satisfies_requirement(p, ppi->pool,

  2004 						    r->flags,

  2005 						    &rpi->pool[r->version]))

  2006 			continue;

  2008 		razor_package_iterator_init_for_property(&pkg_iter, set, p);

  2009 		while (razor_package_iterator_next(&pkg_iter, &pkg,

  2010 						   &name, &version, &arch)) {

  2012 			fprintf(stderr, "flagging %s-%s for providing %s matching %s %s\n",

  2013 				name, version,

  2014 				ppi->pool + p->name,

  2015 				rpi->pool + r->name,

  2016 				rpi->pool + r->version);

  2017 			flags[pkg - pkgs] |= flag;

  2018 		}

  2019 	}

  2020 }

  2022 static struct razor_package *

  2023 pick_matching_provider(struct razor_set *set,

  2024 		       struct prop_iter *ppi,

  2025 		       uint32_t flags,

  2026 		       const char *version)

  2027 {

  2028 	struct razor_property *p;

  2029 	struct razor_package *pkgs;

  2030 	struct list *i;

  2031 	uint32_t type;

  2033 	/* This is where we decide which pkgs to pull in to satisfy a

  2034 	 * requirement.  There may be several different providers

  2035 	 * (different versions) and each version of a provider may

  2036 	 * come from a number of packages.  We pick the first package

  2037 	 * from the first provider that matches. */

  2039 	pkgs = set->packages.data;

  2040 	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;

  2041 	for (p = ppi->p;

  2042 	     p < ppi->end &&

  2043 		     p->name == ppi->p->name &&

  2044 		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type &&

  2045 		     ppi->present[p - ppi->start] == 0;

  2046 	     p++) {

  2047 		if (!provider_satisfies_requirement(p, ppi->pool,

  2048 						    flags, version))

  2049 			continue;

  2051 		i = list_first(&p->packages, &set->package_pool);

  2053 		return &pkgs[i->data];

  2054 	}

  2056 	return NULL;

  2057 }

  2059 static void

  2060 remove_obsoleted_packages(struct razor_transaction *trans)

  2061 {

  2062 	struct razor_property *up;

  2063 	struct razor_package *spkgs;

  2064 	struct prop_iter spi, upi;

  2066 	spkgs = trans->system.set->packages.data;

  2067 	prop_iter_init(&spi, &trans->system);

  2068 	prop_iter_init(&upi, &trans->upstream);

  2070 	while (prop_iter_next(&upi, RAZOR_PROPERTY_OBSOLETES, &up)) {

  2071 		if (!prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,

  2072 				       &upi.pool[up->name]))

  2073 			continue;

  2074 		remove_matching_providers(trans, &spi, up->flags,

  2075 					  &upi.pool[up->version]);

  2076 	}

  2077 }

  2079 static int

  2080 any_provider_satisfies_requirement(struct prop_iter *ppi,

  2081 				   uint32_t flags,

  2082 				   const char *version)

  2083 {

  2084 	struct razor_property *p;

  2085 	uint32_t type;

  2087 	type = ppi->p->flags & RAZOR_PROPERTY_TYPE_MASK;

  2088 	for (p = ppi->p;

  2089 	     p < ppi->end &&

  2090 		     p->name == ppi->p->name &&

  2091 		     (p->flags & RAZOR_PROPERTY_TYPE_MASK) == type;

  2092 	     p++) {

  2093 		if (ppi->present[p - ppi->start] > 0 &&

  2094 		    provider_satisfies_requirement(p, ppi->pool,

  2095 						   flags, version))

  2096 			return 1;

  2097 	}

  2099 	return 0;

  2100 }

  2102 static void

  2103 clear_requires_flags(struct transaction_set *ts)

  2104 {

  2105 	struct razor_property *p;

  2106 	const char *pool;

  2107 	int i, count;

  2109 	count = ts->set->properties.size / sizeof *p;

  2110 	p = ts->set->properties.data;

  2111 	pool = ts->set->string_pool.data;

  2112 	for (i = 0; i < count; i++) {

  2113 		ts->properties[i] &= ~TRANS_PROPERTY_SATISFIED;

  2114 		if (strncmp(&pool[p[i].name], "rpmlib(", 7) == 0)

  2115 			ts->properties[i] |= TRANS_PROPERTY_SATISFIED;

  2116 	}

  2117 }

  2119 const char *

  2120 razor_property_relation_to_string(struct razor_property *p)

  2121 {

  2122 	switch (p->flags & RAZOR_PROPERTY_RELATION_MASK) {

  2123 	case RAZOR_PROPERTY_LESS:

  2124 		return "<";

  2126 	case RAZOR_PROPERTY_LESS | RAZOR_PROPERTY_EQUAL:

  2127 		return "<=";

  2129 	case RAZOR_PROPERTY_EQUAL:

  2130 		return "=";

  2132 	case RAZOR_PROPERTY_GREATER | RAZOR_PROPERTY_EQUAL:

  2133 		return ">=";

  2135 	case RAZOR_PROPERTY_GREATER:

  2136 		return ">";

  2138 	default:

  2139 		return "?";

  2140 	}

  2141 }

  2143 const char *

  2144 razor_property_type_to_string(struct razor_property *p)

  2145 {

  2146 	switch (p->flags & RAZOR_PROPERTY_TYPE_MASK) {

  2147 	case RAZOR_PROPERTY_REQUIRES:

  2148 		return "requires";

  2149 	case RAZOR_PROPERTY_PROVIDES:

  2150 		return "provides";

  2151 	case RAZOR_PROPERTY_CONFLICTS:

  2152 		return "conflicts";

  2153 	case RAZOR_PROPERTY_OBSOLETES:

  2154 		return "obsoletes";

  2155 	default:

  2156 		return NULL;

  2157 	}

  2158 }

  2160 static void

  2161 mark_satisfied_requires(struct razor_transaction *trans,

  2162 			struct transaction_set *rts,

  2163 			struct transaction_set *pts)

  2164 {

  2165 	struct prop_iter rpi, ppi;

  2166 	struct razor_property *rp;

  2168 	prop_iter_init(&rpi, rts);

  2169 	prop_iter_init(&ppi, pts);

  2171 	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {

  2172 		if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES,

  2173 				       &rpi.pool[rp->name]))

  2174 			continue;

  2176 		if (any_provider_satisfies_requirement(&ppi, rp->flags,

  2177 						       &rpi.pool[rp->version]))

  2178 			rpi.present[rp - rpi.start] |= TRANS_PROPERTY_SATISFIED;

  2179 	}

  2180 }

  2182 static void

  2183 mark_all_satisfied_requires(struct razor_transaction *trans)

  2184 {

  2185 	clear_requires_flags(&trans->system);

  2186 	clear_requires_flags(&trans->upstream);

  2187 	mark_satisfied_requires(trans, &trans->system, &trans->system);

  2188 	mark_satisfied_requires(trans, &trans->system, &trans->upstream);

  2189 	mark_satisfied_requires(trans, &trans->upstream, &trans->system);

  2190 	mark_satisfied_requires(trans, &trans->upstream, &trans->upstream);

  2191 }

  2193 static void

  2194 update_unsatisfied_packages(struct razor_transaction *trans)

  2195 {

  2196 	struct razor_package *spkgs, *pkg;

  2197 	struct razor_property *sp;

  2198 	struct prop_iter spi;

  2199 	struct razor_package_iterator pkg_iter;

  2200 	const char *name, *version, *arch;

  2202 	spkgs = trans->system.set->packages.data;

  2203 	prop_iter_init(&spi, &trans->system);

  2205 	while (prop_iter_next(&spi, RAZOR_PROPERTY_REQUIRES, &sp)) {

  2206 		if (spi.present[sp - spi.start] & TRANS_PROPERTY_SATISFIED)

  2207 			continue;

  2209 		razor_package_iterator_init_for_property(&pkg_iter,

  2210 							 trans->system.set,

  2211 							 sp);

  2212 		while (razor_package_iterator_next(&pkg_iter, &pkg,

  2213 						   &name, &version, &arch)) {

  2214 			fprintf(stderr, "updating %s because %s %s %s "

  2215 				"isn't satisfied\n",

  2216 				name, spi.pool + sp->name,

  2217 				razor_property_relation_to_string(sp),

  2218 				spi.pool + sp->version);

  2219 			trans->system.packages[pkg - spkgs] |=

  2220 				TRANS_PACKAGE_UPDATE;

  2221 		}

  2222 	}

  2223 }

  2225 void

  2226 razor_transaction_update_all(struct razor_transaction *trans)

  2227 {

  2228 	struct razor_package *p;

  2229 	int i, count;

  2231 	count = trans->system.set->packages.size / sizeof *p;

  2232 	for (i = 0; i < count; i++)

  2233 		trans->system.packages[i] |= TRANS_PACKAGE_UPDATE;

  2234 }

  2236 static void

  2237 update_conflicted_packages(struct razor_transaction *trans)

  2238 {

  2239 	struct razor_package *pkg, *spkgs;

  2240 	struct razor_property *up, *sp;

  2241 	struct prop_iter spi, upi;

  2242 	struct razor_package_iterator pkg_iter;

  2243 	const char *name, *version, *arch;

  2245 	spkgs = trans->system.set->packages.data;

  2246 	prop_iter_init(&spi, &trans->system);

  2247 	prop_iter_init(&upi, &trans->upstream);

  2249 	while (prop_iter_next(&spi, RAZOR_PROPERTY_CONFLICTS, &sp)) {

  2250 		if (!prop_iter_seek_to(&upi, RAZOR_PROPERTY_PROVIDES,

  2251 				       &spi.pool[sp->name]))

  2252 			continue;

  2254 		if (!any_provider_satisfies_requirement(&upi, sp->flags,

  2255 							&spi.pool[sp->version]))

  2256 			continue;

  2258 		razor_package_iterator_init_for_property(&pkg_iter,

  2259 							 trans->system.set,

  2260 							 sp);

  2261 		while (razor_package_iterator_next(&pkg_iter, &pkg,

  2262 						   &name, &version, &arch)) {

  2263 			fprintf(stderr, "updating %s %s because it conflicts with %s",

  2264 				name, version, spi.pool + sp->name);

  2265 			trans->system.packages[pkg - spkgs] |=

  2266 				TRANS_PACKAGE_UPDATE;

  2267 		}

  2268 	}

  2270 	prop_iter_init(&spi, &trans->system);

  2271 	prop_iter_init(&upi, &trans->upstream);

  2273 	while (prop_iter_next(&upi, RAZOR_PROPERTY_CONFLICTS, &up)) {

  2274 		sp = prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES,

  2275 				       &upi.pool[upi.p->name]);

  2277 		if (sp)

  2278 			flag_matching_providers(trans, &spi, up, &upi,

  2279 						TRANS_PACKAGE_UPDATE);

  2280 	}

  2281 }

  2283 static void

  2284 pull_in_requirements(struct razor_transaction *trans,

  2285 		     struct prop_iter *rpi, struct prop_iter *ppi)

  2286 {

  2287 	struct razor_property *rp, *pp;

  2288 	struct razor_package *pkg, *upkgs;

  2290 	upkgs = trans->upstream.set->packages.data;

  2291 	while (prop_iter_next(rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {

  2292 		if (rpi->present[rp - rpi->start] & TRANS_PROPERTY_SATISFIED)

  2293 			continue;

  2295 		pp = prop_iter_seek_to(ppi, RAZOR_PROPERTY_PROVIDES,

  2296 				       &rpi->pool[rp->name]);

  2297 		if (pp == NULL)

  2298 			continue;

  2299 		pkg = pick_matching_provider(trans->upstream.set,

  2300 					     ppi, rp->flags,

  2301 					     &rpi->pool[rp->version]);

  2302 		if (pkg == NULL)

  2303 			continue;

  2305 		rpi->present[rp - rpi->start] |= TRANS_PROPERTY_SATISFIED;

  2307 		fprintf(stderr, "pulling in %s which provides %s %s %s "

  2308 			"to satisfy %s %s %s\n",

  2309 			ppi->pool + pkg->name,

  2310 			ppi->pool + pp->name,

  2311 			razor_property_relation_to_string(pp),

  2312 			ppi->pool + pp->version,

  2313 			&rpi->pool[rp->name],

  2314 			razor_property_relation_to_string(rp),

  2315 			&rpi->pool[rp->version]);

  2317 		trans->upstream.packages[pkg - upkgs] |= TRANS_PACKAGE_UPDATE;

  2318 	}

  2319 }

  2321 static void

  2322 pull_in_all_requirements(struct razor_transaction *trans)

  2323 {

  2324 	struct prop_iter rpi, ppi;

  2326 	prop_iter_init(&rpi, &trans->system);

  2327 	prop_iter_init(&ppi, &trans->upstream);

  2328 	pull_in_requirements(trans, &rpi, &ppi);

  2330 	prop_iter_init(&rpi, &trans->upstream);

  2331 	prop_iter_init(&ppi, &trans->upstream);

  2332 	pull_in_requirements(trans, &rpi, &ppi);

  2333 }

  2335 static void

  2336 flush_scheduled_system_updates(struct razor_transaction *trans)

  2337 {

  2338  	struct razor_package_iterator *pi;

  2339  	struct razor_package *p, *pkg, *spkgs;

  2340 	struct prop_iter ppi;

  2341 	const char *name, *version, *arch;

  2343 	spkgs = trans->system.set->packages.data;

  2344 	pi = razor_package_iterator_create(trans->system.set);

  2345 	prop_iter_init(&ppi, &trans->upstream);

  2347 	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {

  2348 		if (!(trans->system.packages[p - spkgs] & TRANS_PACKAGE_UPDATE))

  2349 			continue;

  2351 		if (!prop_iter_seek_to(&ppi, RAZOR_PROPERTY_PROVIDES, name))

  2352 			continue;

  2354 		pkg = pick_matching_provider(trans->upstream.set, &ppi,

  2355 					     RAZOR_PROPERTY_GREATER, version);

  2356 		if (pkg == NULL)

  2357 			continue;

  2359 		fprintf(stderr, "updating %s-%s to %s-%s\n",

  2360 			name, version,

  2361 			&ppi.pool[pkg->name], &ppi.pool[pkg->version]);

  2363 		razor_transaction_remove_package(trans, p);

  2364 		razor_transaction_install_package(trans, pkg);

  2365 	}

  2367 	razor_package_iterator_destroy(pi);

  2368 }

  2370 static void

  2371 flush_scheduled_upstream_updates(struct razor_transaction *trans)

  2372 {

  2373  	struct razor_package_iterator *pi;

  2374  	struct razor_package *p, *upkgs;

  2375 	struct prop_iter spi;

  2376 	const char *name, *version, *arch;

  2378 	upkgs = trans->upstream.set->packages.data;

  2379 	pi = razor_package_iterator_create(trans->upstream.set);

  2380 	prop_iter_init(&spi, &trans->system);

  2382 	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {

  2383 		if (!(trans->upstream.packages[p - upkgs] & TRANS_PACKAGE_UPDATE))

  2384 			continue;

  2386 		if (prop_iter_seek_to(&spi, RAZOR_PROPERTY_PROVIDES, name))

  2387 			remove_matching_providers(trans,

  2388 						  &spi,

  2389 						  RAZOR_PROPERTY_LESS,

  2390 						  version);

  2391 		razor_transaction_install_package(trans, p);

  2392 		fprintf(stderr, "installing %s-%s\n", name, version);

  2393 	}

  2394 }

  2396 int

  2397 razor_transaction_resolve(struct razor_transaction *trans)

  2398 {

  2399 	int last = 0;

  2401 	flush_scheduled_system_updates(trans);

  2402 	flush_scheduled_upstream_updates(trans);

  2404 	while (last < trans->changes) {

  2405 		last = trans->changes;

  2406 		remove_obsoleted_packages(trans);

  2407 		mark_all_satisfied_requires(trans);

  2408 		update_unsatisfied_packages(trans);

  2409 		update_conflicted_packages(trans);

  2410 		pull_in_all_requirements(trans);

  2411 		flush_scheduled_system_updates(trans);

  2412 		flush_scheduled_upstream_updates(trans);

  2413 	}

  2415 	return trans->changes;

  2416 }

  2418 static void

  2419 describe_unsatisfied(struct razor_set *set, struct razor_property *rp)

  2420 {

  2421 	struct razor_package_iterator pi;

  2422 	struct razor_package *pkg;

  2423 	const char *name, *version, *arch, *pool;

  2425 	pool = set->string_pool.data;

  2426 	if (pool[rp->version] == '\0') {

  2427 		razor_package_iterator_init_for_property(&pi, set, rp);

  2428 		while (razor_package_iterator_next(&pi, &pkg,

  2429 						   &name, &version, &arch))

  2430 			fprintf(stderr, "%s is needed by %s-%s.%s\n",

  2431 				&pool[rp->name],

  2432 				name, version, arch);

  2433 	} else {

  2434 		razor_package_iterator_init_for_property(&pi, set, rp);

  2435 		while (razor_package_iterator_next(&pi, &pkg,

  2436 						   &name, &version, &arch))

  2437 			fprintf(stderr, "%s %s %s is needed by %s-%s.%s\n",

  2438 				&pool[rp->name],

  2439 				razor_property_relation_to_string(rp),

  2440 				&pool[rp->version],

  2441 				name, version, arch);

  2442 	}

  2443 }

  2445 int

  2446 razor_transaction_describe(struct razor_transaction *trans)

  2447 {

  2448 	struct prop_iter rpi;

  2449 	struct razor_property *rp;

  2450 	int unsatisfied;

  2452 	flush_scheduled_system_updates(trans);

  2453 	flush_scheduled_upstream_updates(trans);

  2454 	mark_all_satisfied_requires(trans);

  2456 	unsatisfied = 0;

  2457 	prop_iter_init(&rpi, &trans->system);

  2458 	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {

  2459 		if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED)) {

  2460 			describe_unsatisfied(trans->system.set, rp);

  2461 		        unsatisfied++;

  2462 		}

  2463 	}

  2465 	prop_iter_init(&rpi, &trans->upstream);

  2466 	while (prop_iter_next(&rpi, RAZOR_PROPERTY_REQUIRES, &rp)) {

  2467 		if (!(rpi.present[rp - rpi.start] & TRANS_PROPERTY_SATISFIED)) {

  2468 			describe_unsatisfied(trans->upstream.set, rp);

  2469 			unsatisfied++;

  2470 		}

  2471 	}

  2473 	return unsatisfied;

  2474 }

  2476 int

  2477 razor_transaction_unsatisfied_property(struct razor_transaction *trans,

  2478 				       const char *name,

  2479 				       uint32_t flags,

  2480 				       const char *version)

  2481 {

  2482 	struct prop_iter pi;

  2483 	struct razor_property *p;

  2485 	prop_iter_init(&pi, &trans->system);

  2486 	while (prop_iter_next(&pi, flags, &p)) {

  2487 		if (!(trans->system.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&

  2488 		    p->flags == flags &&

  2489 		    strcmp(&pi.pool[p->name], name) == 0 &&

  2490 		    strcmp(&pi.pool[p->version], version) == 0)

  2492 			return 1;

  2493 	}

  2495 	prop_iter_init(&pi, &trans->upstream);

  2496 	while (prop_iter_next(&pi, flags, &p)) {

  2497 		if (!(trans->upstream.properties[p - pi.start] & TRANS_PROPERTY_SATISFIED) &&

  2498 		    p->flags == flags &&

  2499 		    strcmp(&pi.pool[p->name], name) == 0 &&

  2500 		    strcmp(&pi.pool[p->version], version) == 0)

  2502 			return 1;

  2503 	}

  2505 	return 0;

  2506 }

  2508 struct razor_set *

  2509 razor_transaction_finish(struct razor_transaction *trans)

  2510 {

  2511 	struct razor_merger *merger;

  2512 	struct razor_package *u, *uend, *upkgs, *s, *send, *spkgs;

  2513 	char *upool, *spool;

  2514 	int cmp;

  2516 	s = trans->system.set->packages.data;

  2517 	spkgs = trans->system.set->packages.data;

  2518 	send = trans->system.set->packages.data +

  2519 		trans->system.set->packages.size;

  2520 	spool = trans->system.set->string_pool.data;

  2522 	u = trans->upstream.set->packages.data;

  2523 	upkgs = trans->upstream.set->packages.data;

  2524 	uend = trans->upstream.set->packages.data +

  2525 		trans->upstream.set->packages.size;

  2526 	upool = trans->upstream.set->string_pool.data;

  2528 	merger = razor_merger_create(trans->system.set, trans->upstream.set);

  2529 	while (s < send || u < uend) {

  2530 		if (s < send && u < uend)

  2531 			cmp = strcmp(&spool[s->name], &upool[u->name]);

  2532 		else if (s < send)

  2533 			cmp = -1;

  2534 		else

  2535 			cmp = 1;

  2537 		if (cmp < 0) {

  2538 			if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)

  2539 				razor_merger_add_package(merger, s);

  2540 			s++;

  2541 		} else if (cmp == 0) {

  2542 			if (trans->system.packages[s - spkgs] & TRANS_PACKAGE_PRESENT)

  2543 				razor_merger_add_package(merger, s);

  2544 			if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)

  2545 				razor_merger_add_package(merger, u);

  2547 			s++;

  2548 			u++;

  2549 		} else {

  2550 			if (trans->upstream.packages[u - upkgs] & TRANS_PACKAGE_PRESENT)

  2551 				razor_merger_add_package(merger, u);

  2552 			u++;

  2553 		}

  2554 	}

  2556 	razor_transaction_destroy(trans);

  2558 	return razor_merger_finish(merger);

  2559 }

  2561 void

  2562 razor_transaction_destroy(struct razor_transaction *trans)

  2563 {

  2564 	transaction_set_release(&trans->system);

  2565 	transaction_set_release(&trans->upstream);

  2566 	free(trans);

  2567 }

  2569 struct razor_package_query {

  2570 	struct razor_set *set;

  2571 	char *vector;

  2572 	int count;

  2573 };

  2575 struct razor_package_query *

  2576 razor_package_query_create(struct razor_set *set)

  2577 {

  2578 	struct razor_package_query *pq;

  2579 	int count;

  2581 	pq = zalloc(sizeof *pq);

  2582 	pq->set = set;

  2583 	count = set->packages.size / sizeof(struct razor_package);

  2584 	pq->vector = zalloc(count * sizeof(char));

  2586 	return pq;

  2587 }

  2589 void

  2590 razor_package_query_add_package(struct razor_package_query *pq,

  2591 				struct razor_package *p)

  2592 {

  2593 	struct razor_package *packages;

  2595 	packages = pq->set->packages.data;

  2596 	pq->count += pq->vector[p - packages] ^ 1;

  2597 	pq->vector[p - packages] = 1;

  2598 }

  2600 void

  2601 razor_package_query_add_iterator(struct razor_package_query *pq,

  2602 				 struct razor_package_iterator *pi)

  2603 {

  2604 	struct razor_package *packages, *p;

  2605 	const char *name, *version, *arch;

  2607 	packages = pq->set->packages.data;

  2608 	while (razor_package_iterator_next(pi, &p, &name, &version, &arch)) {

  2609 		pq->count += pq->vector[p - packages] ^ 1;

  2610 		pq->vector[p - packages] = 1;

  2611 	}

  2612 }

  2614 struct razor_package_iterator *

  2615 razor_package_query_finish(struct razor_package_query *pq)

  2616 {

  2617 	struct razor_package_iterator *pi;

  2618 	struct razor_set *set;

  2619 	struct list *index;

  2620 	int i, j, count;

  2622 	set = pq->set;

  2623 	count = set->packages.size / sizeof(struct razor_package);

  2624 	index = zalloc(pq->count * sizeof *index);

  2626 	for (i = 0, j = 0; i < count; i++) {

  2627 		if (!pq->vector[i])

  2628 			continue;

  2630 		index[j].data = i;

  2631 		if (j == pq->count - 1)

  2632 			index[j].flags = 0x80;

  2633 		j++;

  2634 	}

  2636 	free(pq);

  2638 	pi = razor_package_iterator_create_with_index(set, index);

  2639 	pi->free_index = 1;

  2641 	return pi;

  2642 }

author	Kristian H?gsberg <krh@redhat.com>
	Fri Jun 20 14:18:52 2008 -0400 (2008-06-20)
changeset 247	63444a10fb8e
parent 244	708a3d9c759a
child 248	057933050c42
permissions	-rw-r--r--