razor: razor.c@5197b8e64e42 (annotated)

krh@15	1	#define _GNU_SOURCE
krh@15	2
krh@0	3	#include <stdlib.h>
krh@19	4	#include <stddef.h>
danw@108	5	#include <stdint.h>
krh@0	6	#include <stdio.h>
krh@0	7	#include <string.h>
krh@0	8	#include <sys/types.h>
krh@0	9	#include <sys/stat.h>
krh@0	10	#include <sys/mman.h>
krh@0	11	#include <unistd.h>
krh@0	12	#include <fcntl.h>
krh@15	13	#include <errno.h>
krh@35	14	#include <ctype.h>
krh@54	15	#include <fnmatch.h>
krh@0	16
krh@27	17	#include "razor.h"
krh@91	18	#include "razor-internal.h"
danw@115	19	#include "types.h"
krh@30	20
krh@30	21	struct razor_set_section {
danw@108	22	uint32_t type;
danw@108	23	uint32_t offset;
danw@108	24	uint32_t size;
krh@30	25	};
krh@30	26
krh@30	27	struct razor_set_header {
danw@108	28	uint32_t magic;
danw@108	29	uint32_t version;
krh@30	30	struct razor_set_section sections[0];
krh@30	31	};
krh@30	32
krh@30	33	#define RAZOR_MAGIC 0x7a7a7a7a
krh@30	34	#define RAZOR_VERSION 1
krh@30	35
krh@66	36	#define RAZOR_STRING_POOL 0
krh@66	37	#define RAZOR_PACKAGES 1
krh@66	38	#define RAZOR_PROPERTIES 2
krh@66	39	#define RAZOR_FILES 3
krh@66	40	#define RAZOR_PACKAGE_POOL 4
krh@66	41	#define RAZOR_PROPERTY_POOL 5
krh@66	42	#define RAZOR_FILE_POOL 6
krh@30	43
krh@30	44	struct razor_package {
danw@120	45	uint name : 24;
danw@120	46	uint flags : 8;
danw@108	47	uint32_t version;
danw@117	48	struct list_head properties;
danw@117	49	struct list_head files;
krh@30	50	};
krh@30	51
krh@30	52	struct razor_property {
danw@119	53	uint name : 24;
danw@119	54	uint flags : 6;
danw@119	55	uint type : 2;
danw@109	56	uint32_t relation;
danw@108	57	uint32_t version;
danw@117	58	struct list_head packages;
krh@30	59	};
krh@30	60
krh@48	61	struct razor_entry {
danw@120	62	uint name : 24;
danw@120	63	uint flags : 8;
danw@108	64	uint32_t start;
danw@117	65	struct list_head packages;
krh@48	66	};
krh@48	67
danw@120	68	#define RAZOR_ENTRY_LAST 0x80
danw@120	69
krh@30	70	struct razor_set {
krh@30	71	struct array string_pool;
krh@30	72	struct array packages;
krh@66	73	struct array properties;
krh@56	74	struct array files;
krh@56	75	struct array package_pool;
krh@66	76	struct array property_pool;
krh@56	77	struct array file_pool;
krh@30	78	struct razor_set_header *header;
krh@30	79	};
krh@30	80
krh@52	81	struct import_entry {
danw@108	82	uint32_t package;
krh@52	83	char *name;
krh@52	84	};
krh@52	85
krh@52	86	struct import_directory {
danw@108	87	uint32_t name, count;
krh@52	88	struct array files;
krh@52	89	struct array packages;
krh@52	90	struct import_directory *last;
krh@52	91	};
krh@52	92
krh@30	93	struct razor_importer {
krh@30	94	struct razor_set *set;
krh@78	95	struct hashtable table;
krh@30	96	struct razor_package *package;
krh@66	97	struct array properties;
krh@48	98	struct array files;
krh@30	99	};
krh@30	100
krh@0	101	static void *
krh@0	102	zalloc(size_t size)
krh@0	103	{
krh@0	104	void *p;
krh@0	105
krh@0	106	p = malloc(size);
krh@0	107	memset(p, 0, size);
krh@0	108
krh@0	109	return p;
krh@0	110	}
krh@0	111
krh@19	112	struct razor_set_section razor_sections[] = {
krh@56	113	{ RAZOR_STRING_POOL, offsetof(struct razor_set, string_pool) },
krh@19	114	{ RAZOR_PACKAGES, offsetof(struct razor_set, packages) },
krh@66	115	{ RAZOR_PROPERTIES, offsetof(struct razor_set, properties) },
krh@56	116	{ RAZOR_FILES, offsetof(struct razor_set, files) },
krh@39	117	{ RAZOR_PACKAGE_POOL, offsetof(struct razor_set, package_pool) },
krh@66	118	{ RAZOR_PROPERTY_POOL, offsetof(struct razor_set, property_pool) },
krh@56	119	{ RAZOR_FILE_POOL, offsetof(struct razor_set, file_pool) },
krh@19	120	};
krh@19	121
krh@4	122	struct razor_set *
krh@4	123	razor_set_create(void)
krh@0	124	{
krh@150	125	struct razor_set *set;
krh@150	126	struct razor_entry *e;
krh@150	127
krh@150	128	set = zalloc(sizeof *set);
krh@150	129
krh@150	130	array_init(&set->files);
krh@150	131	e = array_add(&set->files, sizeof *e);
krh@150	132	e->name = 0;
krh@150	133	e->flags = RAZOR_ENTRY_LAST;
krh@150	134	e->start = 0;
krh@150	135	list_set_empty(&e->packages);
krh@150	136
krh@150	137	return set;
krh@0	138	}
krh@0	139
krh@4	140	struct razor_set *
krh@4	141	razor_set_open(const char *filename)
krh@0	142	{
krh@4	143	struct razor_set *set;
krh@19	144	struct razor_set_section *s;
krh@0	145	struct stat stat;
krh@19	146	struct array *array;
krh@19	147	int fd;
krh@0	148
krh@4	149	set = zalloc(sizeof *set);
krh@0	150	fd = open(filename, O_RDONLY);
krh@0	151	if (fstat(fd, &stat) < 0)
krh@0	152	return NULL;
krh@4	153	set->header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
krh@4	154	if (set->header == MAP_FAILED) {
krh@4	155	free(set);
krh@0	156	return NULL;
krh@0	157	}
krh@0	158
krh@19	159	for (s = set->header->sections; ~s->type; s++) {
krh@19	160	if (s->type >= ARRAY_SIZE(razor_sections))
krh@19	161	continue;
krh@19	162	if (s->type != razor_sections[s->type].type)
krh@19	163	continue;
krh@19	164	array = (void *) set + razor_sections[s->type].offset;
krh@19	165	array->data = (void *) set->header + s->offset;
krh@19	166	array->size = s->size;
krh@19	167	array->alloc = s->size;
krh@0	168	}
krh@0	169	close(fd);
krh@0	170
krh@4	171	return set;
krh@0	172	}
krh@0	173
krh@0	174	void
krh@4	175	razor_set_destroy(struct razor_set *set)
krh@0	176	{
krh@0	177	unsigned int size;
krh@19	178	struct array *a;
krh@0	179	int i;
krh@0	180
krh@4	181	if (set->header) {
krh@4	182	for (i = 0; set->header->sections[i].type; i++)
krh@0	183	;
krh@4	184	size = set->header->sections[i].type;
krh@4	185	munmap(set->header, size);
krh@0	186	} else {
krh@19	187	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
krh@19	188	a = (void *) set + razor_sections[i].offset;
krh@19	189	free(a->data);
krh@19	190	}
krh@0	191	}
krh@0	192
krh@4	193	free(set);
krh@0	194	}
krh@0	195
krh@43	196	int
krh@4	197	razor_set_write(struct razor_set set, const char filename)
krh@0	198	{
krh@0	199	char data[4096];
krh@4	200	struct razor_set_header header = (struct razor_set_header ) data;
krh@19	201	struct array *a;
danw@108	202	uint32_t offset;
krh@17	203	int i, fd;
krh@0	204
krh@0	205	memset(data, 0, sizeof data);
krh@4	206	header->magic = RAZOR_MAGIC;
krh@4	207	header->version = RAZOR_VERSION;
krh@17	208	offset = sizeof data;
krh@0	209
krh@19	210	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
krh@19	211	if (razor_sections[i].type != i)
krh@19	212	continue;
krh@19	213	a = (void *) set + razor_sections[i].offset;
krh@19	214	header->sections[i].type = i;
krh@17	215	header->sections[i].offset = offset;
krh@19	216	header->sections[i].size = a->size;
krh@91	217	offset += ALIGN(a->size, 4096);
krh@17	218	}
krh@0	219
krh@19	220	header->sections[i].type = ~0;
krh@17	221	header->sections[i].offset = 0;
krh@17	222	header->sections[i].size = 0;
krh@10	223
krh@0	224	fd = open(filename, O_CREAT \| O_WRONLY \| O_TRUNC, 0666);
krh@0	225	if (fd < 0)
krh@0	226	return -1;
krh@0	227
krh@91	228	razor_write(fd, data, sizeof data);
danw@113	229	memset(data, 0, sizeof data);
krh@19	230	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
krh@19	231	if (razor_sections[i].type != i)
krh@19	232	continue;
krh@19	233	a = (void *) set + razor_sections[i].offset;
danw@113	234	razor_write(fd, a->data, a->size);
danw@113	235	razor_write(fd, data, ALIGN(a->size, 4096) - a->size);
krh@19	236	}
krh@17	237
krh@17	238	close(fd);
krh@0	239
krh@0	240	return 0;
krh@0	241	}
krh@0	242
krh@27	243	void
danw@143	244	razor_build_evr(char evr_buf, int size, const char epoch,
danw@143	245	const char version, const char release)
danw@143	246	{
danw@143	247	int len;
danw@143	248
danw@143	249	if (!version \|\| !*version) {
danw@143	250	*evr_buf = '\0';
danw@143	251	return;
danw@143	252	}
danw@143	253
danw@143	254	if (epoch && *epoch && strcmp(epoch, "0") != 0) {
danw@143	255	len = snprintf(evr_buf, size, "%s:", epoch);
danw@143	256	evr_buf += len;
danw@143	257	size -= len;
danw@143	258	}
danw@143	259	len = snprintf(evr_buf, size, "%s", version);
danw@143	260	evr_buf += len;
danw@143	261	size -= len;
danw@143	262	if (release && *release)
danw@143	263	snprintf(evr_buf, size, "-%s", release);
danw@143	264	}
danw@143	265
danw@143	266	void
krh@30	267	razor_importer_begin_package(struct razor_importer *importer,
krh@30	268	const char name, const char version)
krh@13	269	{
krh@25	270	struct razor_package *p;
krh@13	271
krh@30	272	p = array_add(&importer->set->packages, sizeof *p);
krh@95	273	p->name = hashtable_tokenize(&importer->table, name);
danw@120	274	p->flags = 0;
krh@95	275	p->version = hashtable_tokenize(&importer->table, version);
krh@13	276
krh@30	277	importer->package = p;
krh@66	278	array_init(&importer->properties);
krh@13	279	}
krh@13	280
krh@13	281	void
krh@30	282	razor_importer_finish_package(struct razor_importer *importer)
krh@13	283	{
danw@117	284	list_set_array(&importer->package->properties,
danw@117	285	&importer->set->property_pool,
danw@124	286	&importer->properties,
danw@124	287	1);
krh@13	288
krh@66	289	array_release(&importer->properties);
krh@13	290	}
krh@13	291
krh@66	292	void
krh@30	293	razor_importer_add_property(struct razor_importer *importer,
danw@109	294	const char *name,
danw@109	295	enum razor_version_relation relation,
danw@109	296	const char *version,
krh@66	297	enum razor_property_type type)
krh@13	298	{
krh@25	299	struct razor_property *p;
danw@108	300	uint32_t *r;
krh@13	301
krh@66	302	p = array_add(&importer->set->properties, sizeof *p);
danw@119	303	p->name = hashtable_tokenize(&importer->table, name);
danw@119	304	p->flags = 0;
danw@119	305	p->type = type;
danw@109	306	p->relation = relation;
krh@95	307	p->version = hashtable_tokenize(&importer->table, version);
danw@117	308	list_set_ptr(&p->packages, importer->package -
danw@117	309	(struct razor_package *) importer->set->packages.data);
krh@13	310
krh@66	311	r = array_add(&importer->properties, sizeof *r);
krh@66	312	r = p - (struct razor_property ) importer->set->properties.data;
krh@30	313	}
krh@30	314
krh@46	315	void
krh@46	316	razor_importer_add_file(struct razor_importer importer, const char name)
krh@46	317	{
krh@52	318	struct import_entry *e;
krh@48	319
krh@52	320	e = array_add(&importer->files, sizeof *e);
krh@52	321
krh@52	322	e->package = importer->package -
krh@52	323	(struct razor_package *) importer->set->packages.data;
krh@52	324	e->name = strdup(name);
krh@46	325	}
krh@46	326
krh@30	327	struct razor_importer *
krh@30	328	razor_importer_new(void)
krh@30	329	{
krh@30	330	struct razor_importer *importer;
krh@30	331
krh@30	332	importer = zalloc(sizeof *importer);
krh@30	333	importer->set = razor_set_create();
krh@78	334	hashtable_init(&importer->table, &importer->set->string_pool);
krh@30	335
krh@30	336	return importer;
krh@9	337	}
krh@9	338
krh@75	339	/* Destroy an importer without creating the set. */
krh@75	340	void
krh@75	341	razor_importer_destroy(struct razor_importer *importer)
krh@75	342	{
krh@75	343	/* FIXME: write this */
krh@75	344	}
krh@75	345
krh@75	346
krh@22	347	typedef int (compare_with_data_func_t)(const void p1,
krh@22	348	const void *p,
krh@22	349	void *data);
krh@22	350
krh@25	351	struct qsort_context {
krh@25	352	size_t size;
krh@25	353	compare_with_data_func_t compare;
krh@25	354	void *data;
krh@25	355	};
krh@25	356
krh@22	357	static void
krh@22	358	qsort_swap(void p1, void p2, size_t size)
krh@22	359	{
krh@22	360	char buffer[size];
krh@22	361
krh@22	362	memcpy(buffer, p1, size);
krh@22	363	memcpy(p1, p2, size);
krh@22	364	memcpy(p2, buffer, size);
krh@22	365	}
krh@22	366
krh@25	367	static void
danw@108	368	__qsort_with_data(void base, size_t nelem, uint32_t map,
krh@25	369	struct qsort_context *ctx)
krh@22	370	{
krh@22	371	void p, start, end, pivot;
danw@108	372	uint32_t mp, mstart, *mend, tmp;
krh@22	373	int left, right, result;
krh@25	374	size_t size = ctx->size;
krh@22	375
krh@22	376	p = base;
krh@22	377	start = base;
krh@22	378	end = base + nelem * size;
krh@25	379	mp = map;
krh@25	380	mstart = map;
krh@25	381	mend = map + nelem;
krh@22	382	pivot = base + (random() % nelem) * size;
krh@25	383
krh@22	384	while (p < end) {
krh@25	385	result = ctx->compare(p, pivot, ctx->data);
krh@22	386	if (result < 0) {
krh@22	387	qsort_swap(p, start, size);
krh@25	388	tmp = *mp;
krh@25	389	mp = mstart;
krh@25	390	*mstart = tmp;
krh@22	391	if (start == pivot)
krh@22	392	pivot = p;
krh@22	393	start += size;
krh@25	394	mstart++;
krh@22	395	p += size;
krh@29	396	mp++;
krh@22	397	} else if (result == 0) {
krh@22	398	p += size;
krh@25	399	mp++;
krh@22	400	} else {
krh@22	401	end -= size;
krh@25	402	mend--;
krh@22	403	qsort_swap(p, end, size);
krh@25	404	tmp = *mp;
krh@29	405	mp = mend;
krh@29	406	*mend = tmp;
krh@22	407	if (end == pivot)
krh@22	408	pivot = p;
krh@22	409	}
krh@22	410	}
krh@22	411
krh@22	412	left = (start - base) / size;
krh@22	413	right = (base + nelem * size - end) / size;
krh@22	414	if (left > 1)
krh@25	415	__qsort_with_data(base, left, map, ctx);
krh@22	416	if (right > 1)
krh@25	417	__qsort_with_data(end, right, mend, ctx);
krh@25	418	}
krh@25	419
danw@137	420	static uint32_t *
krh@25	421	qsort_with_data(void *base, size_t nelem, size_t size,
krh@25	422	compare_with_data_func_t compare, void *data)
krh@25	423	{
krh@25	424	struct qsort_context ctx;
danw@108	425	uint32_t *map;
krh@25	426	int i;
krh@25	427
krh@75	428	if (nelem == 0)
krh@75	429	return NULL;
krh@75	430
krh@25	431	ctx.size = size;
krh@25	432	ctx.compare = compare;
krh@25	433	ctx.data = data;
krh@25	434
danw@108	435	map = malloc(nelem * sizeof (uint32_t));
krh@25	436	for (i = 0; i < nelem; i++)
krh@25	437	map[i] = i;
krh@25	438
krh@25	439	__qsort_with_data(base, nelem, map, &ctx);
krh@25	440
krh@25	441	return map;
krh@22	442	}
krh@9	443
krh@9	444	static int
krh@35	445	versioncmp(const char s1, const char s2)
krh@35	446	{
krh@35	447	const char p1, p2;
krh@35	448	long n1, n2;
krh@35	449	int res;
krh@35	450
danw@153	451	n1 = strtol(s1, (char **) &p1, 10);
danw@153	452	n2 = strtol(s2, (char **) &p2, 10);
krh@35	453
krh@35	454	/* Epoch; if one but not the other has an epoch set, default
krh@35	455	* the epoch-less version to 0. */
krh@35	456	res = (p1 == ':') - (p2 == ':');
krh@35	457	if (res < 0) {
krh@35	458	n1 = 0;
krh@35	459	p1 = s1;
krh@35	460	p2++;
krh@35	461	} else if (res > 0) {
krh@35	462	p1++;
krh@35	463	n2 = 0;
krh@35	464	p2 = s2;
krh@35	465	}
krh@35	466
krh@35	467	if (n1 != n2)
krh@35	468	return n1 - n2;
krh@35	469	while (p1 && p2) {
krh@35	470	if (p1 != p2)
krh@35	471	return p1 - p2;
krh@35	472	p1++;
krh@35	473	p2++;
krh@35	474	if (isdigit(p1) && isdigit(p2))
krh@35	475	return versioncmp(p1, p2);
krh@35	476	}
krh@35	477
krh@35	478	return p1 - p2;
krh@35	479	}
krh@35	480
krh@35	481	static int
krh@22	482	compare_packages(const void p1, const void p2, void *data)
krh@9	483	{
krh@25	484	const struct razor_package pkg1 = p1, pkg2 = p2;
krh@22	485	struct razor_set *set = data;
krh@22	486	char *pool = set->string_pool.data;
krh@9	487
danw@120	488	/* FIXME: what if the flags are different? */
krh@23	489	if (pkg1->name == pkg2->name)
krh@35	490	return versioncmp(&pool[pkg1->version], &pool[pkg2->version]);
krh@23	491	else
krh@23	492	return strcmp(&pool[pkg1->name], &pool[pkg2->name]);
krh@9	493	}
krh@9	494
krh@9	495	static int
krh@22	496	compare_properties(const void p1, const void p2, void *data)
krh@9	497	{
krh@25	498	const struct razor_property prop1 = p1, prop2 = p2;
krh@22	499	struct razor_set *set = data;
krh@22	500	char *pool = set->string_pool.data;
krh@9	501
danw@119	502	if (prop1->name != prop2->name)
danw@119	503	return strcmp(&pool[prop1->name], &pool[prop2->name]);
danw@119	504	else if (prop1->type != prop2->type)
danw@119	505	return prop1->type - prop2->type;
danw@119	506	else if (prop1->relation != prop2->relation)
danw@119	507	return prop1->relation - prop2->relation;
krh@12	508	else
danw@119	509	return versioncmp(&pool[prop1->version], &pool[prop2->version]);
krh@9	510	}
krh@9	511
danw@108	512	static uint32_t *
krh@66	513	uniqueify_properties(struct razor_set *set)
krh@9	514	{
krh@25	515	struct razor_property rp, up, *rp_end;
krh@18	516	struct array pkgs, p;
danw@117	517	struct list_head *r;
danw@117	518	uint32_t map, rmap;
krh@18	519	int i, count, unique;
krh@9	520
krh@66	521	count = set->properties.size / sizeof(struct razor_property);
krh@66	522	map = qsort_with_data(set->properties.data,
krh@25	523	count,
krh@25	524	sizeof(struct razor_property),
krh@25	525	compare_properties,
krh@25	526	set);
krh@9	527
krh@66	528	rp_end = set->properties.data + set->properties.size;
krh@25	529	rmap = malloc(count * sizeof *map);
krh@25	530	pkgs = zalloc(count * sizeof *pkgs);
krh@66	531	for (rp = set->properties.data, up = rp, i = 0; rp < rp_end; rp++, i++) {
danw@119	532	if (rp->name != up->name \|\| rp->type != up->type \|\|
danw@119	533	rp->relation != up->relation \|\| rp->version != up->version) {
krh@25	534	up++;
krh@25	535	up->name = rp->name;
danw@119	536	up->flags = 0;
danw@119	537	up->type = rp->type;
danw@109	538	up->relation = rp->relation;
krh@25	539	up->version = rp->version;
krh@10	540	}
krh@25	541
krh@66	542	unique = up - (struct razor_property *) set->properties.data;
krh@25	543	rmap[map[i]] = unique;
krh@25	544	r = array_add(&pkgs[unique], sizeof *r);
krh@25	545	*r = rp->packages;
krh@10	546	}
krh@25	547	free(map);
krh@9	548
danw@124	549	if (up != rp)
danw@124	550	up++;
krh@66	551	set->properties.size = (void *) up - set->properties.data;
krh@25	552	rp_end = up;
krh@66	553	for (rp = set->properties.data, p = pkgs; rp < rp_end; rp++, p++) {
danw@124	554	list_set_array(&rp->packages, &set->package_pool, p, 0);
krh@25	555	array_release(p);
krh@18	556	}
krh@18	557
krh@18	558	free(pkgs);
krh@18	559
krh@25	560	return rmap;
krh@10	561	}
krh@10	562
krh@48	563	static int
krh@48	564	compare_filenames(const void p1, const void p2, void *data)
krh@48	565	{
krh@52	566	const struct import_entry *e1 = p1;
krh@52	567	const struct import_entry *e2 = p2;
danw@126	568	const char *n1 = e1->name;
danw@126	569	const char *n2 = e2->name;
krh@48	570
danw@126	571	/* Need to make sure that the contents of a directory
danw@126	572	* are sorted immediately after it. So "foo/bar" has to
danw@126	573	* sort before "foo.conf"
danw@126	574	*
danw@126	575	* FIXME: this is about 60% slower than strcmp
danw@126	576	*/
danw@126	577	while (n1 && n2) {
danw@126	578	if (n1 < n2)
danw@126	579	return *n2 == '/' ? 1 : -1;
danw@126	580	else if (n1 > n2)
danw@126	581	return *n1 == '/' ? -1 : 1;
danw@126	582	n1++;
danw@126	583	n2++;
danw@126	584	}
danw@126	585	if (*n1)
danw@126	586	return 1;
danw@126	587	else if (*n2)
danw@126	588	return -1;
danw@126	589	else
danw@126	590	return 0;
krh@48	591	}
krh@48	592
krh@48	593	static void
krh@52	594	count_entries(struct import_directory *d)
krh@48	595	{
krh@52	596	struct import_directory p, end;
krh@48	597
krh@48	598	p = d->files.data;
krh@48	599	end = d->files.data + d->files.size;
krh@48	600	d->count = 0;
krh@48	601	while (p < end) {
krh@48	602	count_entries(p);
krh@48	603	d->count += p->count + 1;
krh@48	604	p++;
krh@48	605	}
krh@48	606	}
krh@48	607
krh@48	608	static void
krh@52	609	serialize_files(struct razor_set *set,
krh@52	610	struct import_directory d, struct array array)
krh@48	611	{
krh@52	612	struct import_directory p, end;
krh@56	613	struct razor_entry *e = NULL;
danw@114	614	uint32_t s;
krh@48	615
krh@48	616	p = d->files.data;
krh@48	617	end = d->files.data + d->files.size;
krh@48	618	s = array->size / sizeof e + d->files.size / sizeof p;
krh@48	619	while (p < end) {
krh@48	620	e = array_add(array, sizeof *e);
krh@48	621	e->name = p->name;
danw@120	622	e->flags = 0;
krh@56	623	e->start = p->count > 0 ? s : 0;
krh@48	624	s += p->count;
krh@60	625
danw@124	626	list_set_array(&e->packages, &set->package_pool, &p->packages, 0);
krh@52	627	array_release(&p->packages);
krh@48	628	p++;
krh@48	629	}
krh@56	630	if (e != NULL)
danw@120	631	e->flags \|= RAZOR_ENTRY_LAST;
krh@48	632
krh@48	633	p = d->files.data;
krh@48	634	end = d->files.data + d->files.size;
krh@48	635	while (p < end) {
krh@52	636	serialize_files(set, p, array);
krh@48	637	p++;
krh@48	638	}
krh@48	639	}
krh@48	640
krh@48	641	static void
danw@108	642	remap_property_package_links(struct array properties, uint32_t rmap)
krh@61	643	{
krh@61	644	struct razor_property p, end;
krh@61	645
krh@61	646	end = properties->data + properties->size;
krh@61	647	for (p = properties->data; p < end; p++)
danw@117	648	list_remap_head(&p->packages, rmap);
krh@61	649	}
krh@61	650
krh@61	651	static void
krh@48	652	build_file_tree(struct razor_importer *importer)
krh@48	653	{
krh@48	654	int count, i, length;
krh@52	655	struct import_entry *filenames;
krh@52	656	char f, end;
danw@108	657	uint32_t name, *r;
krh@48	658	char dirname[256];
krh@52	659	struct import_directory *d, root;
krh@48	660	struct razor_entry *e;
krh@48	661
krh@52	662	count = importer->files.size / sizeof (struct import_entry);
krh@48	663	qsort_with_data(importer->files.data,
krh@48	664	count,
krh@52	665	sizeof (struct import_entry),
krh@48	666	compare_filenames,
krh@48	667	NULL);
krh@48	668
krh@95	669	root.name = hashtable_tokenize(&importer->table, "");
krh@48	670	array_init(&root.files);
krh@52	671	array_init(&root.packages);
krh@48	672	root.last = NULL;
krh@48	673
krh@48	674	filenames = importer->files.data;
krh@48	675	for (i = 0; i < count; i++) {
krh@52	676	f = filenames[i].name;
krh@48	677	if (*f != '/')
krh@48	678	continue;
krh@57	679	f++;
krh@48	680
krh@48	681	d = &root;
krh@48	682	while (*f) {
krh@57	683	end = strchr(f, '/');
krh@48	684	if (end == NULL)
krh@48	685	end = f + strlen(f);
krh@57	686	length = end - f;
krh@57	687	memcpy(dirname, f, length);
krh@48	688	dirname[length] ='\0';
krh@95	689	name = hashtable_tokenize(&importer->table, dirname);
krh@48	690	if (d->last == NULL \|\| d->last->name != name) {
krh@48	691	d->last = array_add(&d->files, sizeof *d);
krh@48	692	d->last->name = name;
krh@48	693	d->last->last = NULL;
krh@48	694	array_init(&d->last->files);
krh@52	695	array_init(&d->last->packages);
krh@48	696	}
krh@48	697	d = d->last;
krh@57	698	f = end + 1;
krh@57	699	if (*end == '\0')
krh@57	700	break;
krh@48	701	}
krh@48	702
krh@52	703	r = array_add(&d->packages, sizeof *r);
krh@52	704	*r = filenames[i].package;
krh@52	705	free(filenames[i].name);
krh@48	706	}
krh@48	707
krh@48	708	count_entries(&root);
krh@150	709	e = importer->set->files.data;
danw@120	710	e->name = root.name;
danw@120	711	e->flags = RAZOR_ENTRY_LAST;
danw@129	712	e->start = importer->files.size ? 1 : 0;
danw@117	713	list_set_empty(&e->packages);
krh@48	714
krh@56	715	serialize_files(importer->set, &root, &importer->set->files);
krh@48	716
krh@48	717	array_release(&importer->files);
krh@48	718	}
krh@48	719
krh@56	720	static void
danw@108	721	build_package_file_lists(struct razor_set set, uint32_t rmap)
krh@54	722	{
krh@56	723	struct razor_package p, packages;
krh@56	724	struct array *pkgs;
krh@54	725	struct razor_entry e, end;
danw@117	726	struct list *r;
danw@117	727	uint32_t *q;
krh@56	728	int i, count;
krh@54	729
krh@56	730	count = set->packages.size / sizeof *p;
krh@56	731	pkgs = zalloc(count * sizeof *pkgs);
krh@54	732
krh@56	733	end = set->files.data + set->files.size;
krh@92	734	for (e = set->files.data; e < end; e++) {
danw@117	735	list_remap_head(&e->packages, rmap);
danw@116	736	r = list_first(&e->packages, &set->package_pool);
danw@116	737	while (r) {
danw@117	738	q = array_add(&pkgs[r->data], sizeof *q);
krh@56	739	q = e - (struct razor_entry ) set->files.data;
danw@116	740	r = list_next(r);
krh@54	741	}
krh@54	742	}
krh@54	743
krh@56	744	packages = set->packages.data;
krh@56	745	for (i = 0; i < count; i++) {
danw@124	746	list_set_array(&packages[i].files, &set->file_pool, &pkgs[i], 0);
krh@56	747	array_release(&pkgs[i]);
krh@48	748	}
krh@56	749	free(pkgs);
krh@52	750	}
krh@52	751
krh@27	752	struct razor_set *
krh@30	753	razor_importer_finish(struct razor_importer *importer)
krh@9	754	{
krh@30	755	struct razor_set *set;
danw@108	756	uint32_t map, rmap;
krh@39	757	int i, count;
krh@18	758
krh@66	759	map = uniqueify_properties(importer->set);
danw@116	760	list_remap_pool(&importer->set->property_pool, map);
krh@39	761	free(map);
krh@25	762
krh@30	763	count = importer->set->packages.size / sizeof(struct razor_package);
krh@30	764	map = qsort_with_data(importer->set->packages.data,
krh@25	765	count,
krh@25	766	sizeof(struct razor_package),
krh@25	767	compare_packages,
krh@30	768	importer->set);
krh@39	769
krh@39	770	rmap = malloc(count * sizeof *rmap);
krh@39	771	for (i = 0; i < count; i++)
krh@39	772	rmap[map[i]] = i;
krh@25	773	free(map);
krh@13	774
krh@48	775	build_file_tree(importer);
danw@116	776	list_remap_pool(&importer->set->package_pool, rmap);
krh@60	777	build_package_file_lists(importer->set, rmap);
krh@66	778	remap_property_package_links(&importer->set->properties, rmap);
krh@52	779	free(rmap);
krh@48	780
krh@30	781	set = importer->set;
krh@78	782	hashtable_release(&importer->table);
krh@30	783	free(importer);
krh@30	784
krh@30	785	return set;
krh@9	786	}
krh@9	787
krh@92	788	struct razor_package_iterator {
krh@92	789	struct razor_set *set;
krh@92	790	struct razor_package package, end;
danw@117	791	struct list *index;
krh@92	792	};
krh@92	793
danw@137	794	static struct razor_package_iterator *
krh@101	795	razor_package_iterator_create_with_index(struct razor_set *set,
danw@117	796	struct list *index)
krh@3	797	{
krh@92	798	struct razor_package_iterator *pi;
krh@92	799
krh@92	800	pi = zalloc(sizeof *pi);
krh@92	801	pi->set = set;
krh@101	802	pi->index = index;
krh@92	803
krh@92	804	return pi;
krh@92	805	}
krh@92	806
krh@101	807	struct razor_package_iterator *
krh@101	808	razor_package_iterator_create(struct razor_set *set)
krh@101	809	{
danw@116	810	struct razor_package_iterator *pi;
danw@116	811
danw@116	812	pi = zalloc(sizeof *pi);
danw@116	813	pi->set = set;
danw@116	814	pi->end = set->packages.data + set->packages.size;
danw@116	815	pi->package = set->packages.data;
danw@116	816
danw@116	817	return pi;
krh@101	818	}
krh@101	819
krh@101	820	struct razor_package_iterator *
krh@101	821	razor_package_iterator_create_for_property(struct razor_set *set,
krh@101	822	struct razor_property *property)
krh@101	823	{
danw@117	824	struct list *index;
krh@101	825
danw@116	826	index = list_first(&property->packages, &set->package_pool);
krh@101	827	return razor_package_iterator_create_with_index(set, index);
krh@101	828	}
krh@101	829
krh@92	830	int
krh@92	831	razor_package_iterator_next(struct razor_package_iterator *pi,
krh@92	832	struct razor_package **package,
krh@92	833	const char name, const char version)
krh@92	834	{
krh@6	835	char *pool;
krh@101	836	int valid;
krh@101	837	struct razor_package p, packages;
krh@3	838
danw@116	839	if (pi->package) {
krh@101	840	p = pi->package++;
krh@101	841	valid = p < pi->end;
danw@116	842	} else if (pi->index) {
danw@116	843	packages = pi->set->packages.data;
danw@117	844	p = &packages[pi->index->data];
danw@116	845	pi->index = list_next(pi->index);
danw@116	846	valid = 1;
danw@116	847	} else
danw@116	848	valid = 0;
krh@92	849
krh@101	850	if (valid) {
krh@101	851	pool = pi->set->string_pool.data;
krh@101	852	*package = p;
danw@120	853	*name = &pool[p->name];
krh@101	854	*version = &pool[p->version];
krh@101	855	} else {
krh@101	856	*package = NULL;
krh@101	857	}
krh@101	858
krh@101	859	return valid;
krh@92	860	}
krh@92	861
krh@92	862	void
krh@92	863	razor_package_iterator_destroy(struct razor_package_iterator *pi)
krh@92	864	{
krh@92	865	free(pi);
krh@3	866	}
krh@3	867
krh@10	868	struct razor_package *
krh@10	869	razor_set_get_package(struct razor_set set, const char package)
krh@10	870	{
krh@97	871	struct razor_package_iterator *pi;
krh@97	872	struct razor_package *p;
krh@97	873	const char name, version;
krh@97	874
krh@97	875	pi = razor_package_iterator_create(set);
krh@97	876	while (razor_package_iterator_next(pi, &p, &name, &version)) {
krh@97	877	if (strcmp(package, name) == 0)
krh@97	878	break;
krh@97	879	}
krh@97	880	razor_package_iterator_destroy(pi);
krh@97	881
krh@97	882	return p;
krh@10	883	}
krh@10	884
krh@92	885	struct razor_property_iterator {
krh@92	886	struct razor_set *set;
krh@92	887	struct razor_property property, end;
danw@117	888	struct list *index;
krh@92	889	};
krh@92	890
krh@92	891	struct razor_property_iterator *
krh@92	892	razor_property_iterator_create(struct razor_set *set,
krh@92	893	struct razor_package *package)
krh@92	894	{
krh@92	895	struct razor_property_iterator *pi;
krh@92	896
krh@92	897	pi = zalloc(sizeof *pi);
krh@92	898	pi->set = set;
krh@98	899
danw@116	900	if (package) {
danw@117	901	pi->index = list_first(&package->properties,
danw@117	902	&set->property_pool);
danw@116	903	} else {
danw@116	904	pi->property = set->properties.data;
danw@116	905	pi->end = set->properties.data + set->properties.size;
danw@116	906	}
krh@92	907
krh@92	908	return pi;
krh@92	909	}
krh@92	910
krh@92	911	int
krh@92	912	razor_property_iterator_next(struct razor_property_iterator *pi,
krh@92	913	struct razor_property **property,
danw@109	914	const char **name,
danw@109	915	enum razor_version_relation *relation,
danw@109	916	const char **version,
krh@92	917	enum razor_property_type *type)
krh@92	918	{
krh@92	919	char *pool;
krh@92	920	int valid;
krh@92	921	struct razor_property p, properties;
krh@92	922
danw@116	923	if (pi->property) {
krh@92	924	p = pi->property++;
krh@92	925	valid = p < pi->end;
danw@116	926	} else if (pi->index) {
danw@116	927	properties = pi->set->properties.data;
danw@117	928	p = &properties[pi->index->data];
danw@116	929	pi->index = list_next(pi->index);
danw@116	930	valid = 1;
danw@116	931	} else
danw@116	932	valid = 0;
krh@92	933
krh@96	934	if (valid) {
krh@96	935	pool = pi->set->string_pool.data;
krh@96	936	*property = p;
danw@119	937	*name = &pool[p->name];
danw@109	938	*relation = p->relation;
krh@96	939	*version = &pool[p->version];
danw@119	940	*type = p->type;
krh@96	941	} else {
krh@96	942	*property = NULL;
krh@96	943	}
krh@92	944
krh@92	945	return valid;
krh@92	946	}
krh@92	947
krh@66	948	void
krh@92	949	razor_property_iterator_destroy(struct razor_property_iterator *pi)
krh@8	950	{
krh@92	951	free(pi);
krh@10	952	}
krh@10	953
krh@56	954	static struct razor_entry *
krh@56	955	find_entry(struct razor_set set, struct razor_entry dir, const char *pattern)
krh@56	956	{
krh@56	957	struct razor_entry *e;
krh@56	958	const char n, pool = set->string_pool.data;
krh@56	959	int len;
krh@56	960
krh@56	961	e = (struct razor_entry *) set->files.data + dir->start;
krh@56	962	do {
danw@120	963	n = pool + e->name;
krh@56	964	if (strcmp(pattern + 1, n) == 0)
krh@56	965	return e;
krh@57	966	len = strlen(n);
krh@56	967	if (e->start != 0 && strncmp(pattern + 1, n, len) == 0 &&
krh@56	968	pattern[len + 1] == '/') {
krh@56	969	return find_entry(set, e, pattern + len + 1);
krh@56	970	}
danw@120	971	} while (!((e++)->flags & RAZOR_ENTRY_LAST));
krh@56	972
krh@56	973	return NULL;
krh@56	974	}
krh@56	975
krh@56	976	static void
krh@56	977	list_dir(struct razor_set set, struct razor_entry dir,
danw@127	978	char prefix, const char pattern)
krh@56	979	{
krh@56	980	struct razor_entry *e;
krh@56	981	const char n, pool = set->string_pool.data;
krh@56	982
krh@56	983	e = (struct razor_entry *) set->files.data + dir->start;
krh@56	984	do {
danw@120	985	n = pool + e->name;
krh@56	986	if (pattern && pattern[0] && fnmatch(pattern, n, 0) != 0)
krh@56	987	continue;
danw@127	988	printf("%s/%s\n", prefix, n);
danw@127	989	if (e->start) {
danw@127	990	char *sub = prefix + strlen (prefix);
danw@127	991	*sub = '/';
danw@127	992	strcpy (sub + 1, n);
danw@127	993	list_dir(set, e, prefix, pattern);
danw@127	994	*sub = '\0';
danw@127	995	}
danw@120	996	} while (!((e++)->flags & RAZOR_ENTRY_LAST));
krh@56	997	}
krh@56	998
krh@56	999	void
krh@56	1000	razor_set_list_files(struct razor_set set, const char pattern)
krh@56	1001	{
krh@56	1002	struct razor_entry *e;
krh@56	1003	char buffer[512], p, base;
krh@56	1004
danw@127	1005	if (pattern == NULL \|\| !strcmp (pattern, "/")) {
danw@127	1006	buffer[0] = '\0';
danw@127	1007	list_dir(set, set->files.data, buffer, NULL);
danw@127	1008	return;
danw@127	1009	}
krh@56	1010
krh@56	1011	strcpy(buffer, pattern);
krh@56	1012	e = find_entry(set, set->files.data, buffer);
krh@56	1013	if (e && e->start > 0) {
krh@56	1014	base = NULL;
krh@56	1015	} else {
krh@56	1016	p = strrchr(buffer, '/');
krh@56	1017	if (p) {
krh@56	1018	*p = '\0';
krh@56	1019	base = p + 1;
krh@56	1020	} else {
krh@56	1021	base = NULL;
krh@56	1022	}
krh@56	1023	}
krh@56	1024	e = find_entry(set, set->files.data, buffer);
krh@56	1025	if (e->start != 0)
krh@56	1026	list_dir(set, e, buffer, base);
krh@56	1027	}
krh@56	1028
krh@102	1029	struct razor_package_iterator *
krh@102	1030	razor_package_iterator_create_for_file(struct razor_set *set,
krh@102	1031	const char *filename)
krh@56	1032	{
krh@102	1033	struct razor_entry *entry;
danw@117	1034	struct list *index;
krh@56	1035
krh@102	1036	entry = find_entry(set, set->files.data, filename);
krh@102	1037	if (entry == NULL)
krh@102	1038	return NULL;
krh@56	1039
danw@116	1040	index = list_first(&entry->packages, &set->package_pool);
krh@102	1041	return razor_package_iterator_create_with_index(set, index);
krh@56	1042	}
krh@56	1043
danw@117	1044	static struct list *
danw@117	1045	list_package_files(struct razor_set set, struct list r,
danw@108	1046	struct razor_entry *dir, uint32_t end,
krh@56	1047	char *prefix)
krh@56	1048	{
krh@56	1049	struct razor_entry e, f, *entries;
danw@108	1050	uint32_t next, file;
krh@56	1051	char *pool;
krh@56	1052	int len;
krh@56	1053
krh@56	1054	entries = (struct razor_entry *) set->files.data;
krh@56	1055	pool = set->string_pool.data;
krh@56	1056
krh@56	1057	e = entries + dir->start;
krh@56	1058	do {
danw@117	1059	if (entries + r->data == e) {
danw@120	1060	printf("%s/%s\n", prefix, pool + e->name);
danw@116	1061	r = list_next(r);
danw@116	1062	if (!r)
krh@83	1063	return NULL;
danw@117	1064	if (r->data >= end)
krh@83	1065	return r;
krh@56	1066	}
danw@120	1067	} while (!((e++)->flags & RAZOR_ENTRY_LAST));
krh@56	1068
krh@56	1069	e = entries + dir->start;
krh@56	1070	do {
krh@56	1071	if (e->start == 0)
krh@56	1072	continue;
krh@56	1073
danw@120	1074	if (e->flags & RAZOR_ENTRY_LAST)
krh@56	1075	next = end;
krh@56	1076	else {
krh@56	1077	f = e + 1;
danw@120	1078	while (f->start == 0 && !(f->flags & RAZOR_ENTRY_LAST))
krh@56	1079	f++;
krh@56	1080	if (f->start == 0)
krh@56	1081	next = end;
krh@56	1082	else
krh@56	1083	next = f->start;
krh@56	1084	}
krh@56	1085
danw@117	1086	file = r->data;
krh@83	1087	if (e->start <= file && file < next) {
krh@56	1088	len = strlen(prefix);
krh@56	1089	prefix[len] = '/';
danw@120	1090	strcpy(prefix + len + 1, pool + e->name);
krh@56	1091	r = list_package_files(set, r, e, next, prefix);
krh@56	1092	prefix[len] = '\0';
krh@56	1093	}
danw@120	1094	} while (!((e++)->flags & RAZOR_ENTRY_LAST) && r != NULL);
krh@56	1095
krh@56	1096	return r;
krh@56	1097	}
krh@56	1098
krh@56	1099	void
krh@56	1100	razor_set_list_package_files(struct razor_set set, const char name)
krh@56	1101	{
krh@56	1102	struct razor_package *package;
danw@117	1103	struct list *r;
danw@117	1104	uint32_t end;
krh@56	1105	char buffer[512];
krh@56	1106
krh@56	1107	package = razor_set_get_package(set, name);
krh@56	1108
danw@116	1109	r = list_first(&package->files, &set->file_pool);
krh@56	1110	end = set->files.size / sizeof (struct razor_entry);
krh@56	1111	buffer[0] = '\0';
krh@56	1112	list_package_files(set, r, set->files.data, end, buffer);
krh@56	1113	}
krh@56	1114
krh@43	1115	static void
krh@21	1116	razor_set_validate(struct razor_set set, struct array unsatisfied)
krh@21	1117	{
krh@66	1118	struct razor_property r, p, *end;
danw@108	1119	uint32_t *u;
krh@21	1120	char *pool;
krh@21	1121
krh@66	1122	end = set->properties.data + set->properties.size;
krh@21	1123	pool = set->string_pool.data;
krh@21	1124
krh@66	1125	for (r = set->properties.data, p = r; r < end; r++) {
danw@119	1126	if (r->type != RAZOR_PROPERTY_REQUIRES)
krh@66	1127	continue;
krh@66	1128
danw@129	1129	p = r;
danw@129	1130	while (p < end && p->name == r->name &&
danw@129	1131	p->type == r->type)
danw@129	1132	p++;
krh@37	1133
krh@35	1134	/* If there is more than one version of a provides,
krh@35	1135	* seek to the end for the highest version. */
krh@66	1136	/* FIXME: This doesn't work if we have a series of
krh@66	1137	* requires a = 1, provides a = 1, requires a = 2,
krh@66	1138	* provides a = 2, as the kernel and kernel-devel
krh@66	1139	* does.*/
danw@119	1140	while (p + 1 < end && p->name == (p + 1)->name &&
danw@119	1141	p->type == (p + 1)->type)
krh@35	1142	p++;
krh@37	1143
krh@37	1144	/* FIXME: We need to track property flags (<, <=, =
krh@37	1145	* etc) to properly determine if a requires is
krh@37	1146	* satisfied. The current code doesn't track that the
krh@37	1147	* requires a = 1 isn't satisfied by a = 2 provides. */
krh@37	1148
krh@66	1149	if (p == end \|\|
danw@119	1150	p->type != RAZOR_PROPERTY_PROVIDES \|\|
danw@119	1151	r->name != p->name \|\|
krh@35	1152	versioncmp(&pool[r->version], &pool[p->version]) > 0) {
krh@35	1153	/* FIXME: We ignore file requires for now. */
danw@119	1154	if (pool[r->name] == '/')
krh@35	1155	continue;
krh@21	1156	u = array_add(unsatisfied, sizeof *u);
krh@66	1157	u = r - (struct razor_property ) set->properties.data;
krh@21	1158	}
krh@21	1159	}
krh@21	1160	}
krh@21	1161
krh@21	1162	void
krh@21	1163	razor_set_list_unsatisfied(struct razor_set *set)
krh@21	1164	{
krh@21	1165	struct array unsatisfied;
krh@66	1166	struct razor_property properties, r;
danw@108	1167	uint32_t u, end;
krh@21	1168	char *pool;
krh@21	1169
krh@21	1170	array_init(&unsatisfied);
krh@21	1171	razor_set_validate(set, &unsatisfied);
krh@21	1172
krh@21	1173	end = unsatisfied.data + unsatisfied.size;
krh@66	1174	properties = set->properties.data;
krh@21	1175	pool = set->string_pool.data;
krh@21	1176
krh@21	1177	for (u = unsatisfied.data; u < end; u++) {
krh@66	1178	r = properties + *u;
krh@66	1179	if (pool[r->version] == '\0')
krh@66	1180	printf("%ss not satisfied\n",
danw@119	1181	&pool[r->name]);
krh@66	1182	else
krh@66	1183	printf("%s-%s not satisfied\n",
danw@119	1184	&pool[r->name],
krh@66	1185	&pool[r->version]);
krh@21	1186	}
krh@21	1187
krh@21	1188	array_release(&unsatisfied);
krh@21	1189	}
krh@21	1190
danw@120	1191	#define UPSTREAM_SOURCE 0x80
krh@41	1192
krh@41	1193	struct source {
krh@41	1194	struct razor_set *set;
danw@108	1195	uint32_t *property_map;
danw@127	1196	uint32_t *file_map;
krh@41	1197	};
krh@41	1198
krh@79	1199	struct razor_merger {
krh@79	1200	struct razor_set *set;
krh@79	1201	struct hashtable table;
krh@79	1202	struct source source1;
krh@79	1203	struct source source2;
krh@79	1204	};
krh@79	1205
krh@79	1206	static struct razor_merger *
krh@79	1207	razor_merger_create(struct razor_set set1, struct razor_set set2)
krh@41	1208	{
krh@79	1209	struct razor_merger *merger;
krh@41	1210	int count;
krh@41	1211	size_t size;
krh@41	1212
krh@79	1213	merger = zalloc(sizeof *merger);
krh@79	1214	merger->set = razor_set_create();
krh@79	1215	hashtable_init(&merger->table, &merger->set->string_pool);
krh@41	1216
danw@127	1217	merger->source1.set = set1;
krh@79	1218	count = set1->properties.size / sizeof (struct razor_property);
krh@79	1219	size = count * sizeof merger->source1.property_map[0];
krh@79	1220	merger->source1.property_map = zalloc(size);
danw@127	1221	count = set1->files.size / sizeof (struct razor_entry);
danw@127	1222	size = count * sizeof merger->source1.file_map[0];
danw@127	1223	merger->source1.file_map = zalloc(size);
krh@79	1224
danw@127	1225	merger->source2.set = set2;
krh@79	1226	count = set2->properties.size / sizeof (struct razor_property);
krh@79	1227	size = count * sizeof merger->source2.property_map[0];
krh@79	1228	merger->source2.property_map = zalloc(size);
danw@127	1229	count = set2->files.size / sizeof (struct razor_entry);
danw@127	1230	size = count * sizeof merger->source2.file_map[0];
danw@127	1231	merger->source2.file_map = zalloc(size);
krh@79	1232
krh@79	1233	return merger;
krh@41	1234	}
krh@41	1235
krh@33	1236	static void
krh@79	1237	add_package(struct razor_merger *merger,
krh@41	1238	struct razor_package package, struct source source,
danw@108	1239	uint32_t flags)
krh@33	1240	{
krh@33	1241	char *pool;
danw@117	1242	struct list *r;
krh@41	1243	struct razor_package *p;
krh@33	1244
krh@41	1245	pool = source->set->string_pool.data;
krh@79	1246	p = array_add(&merger->set->packages, sizeof *p);
krh@79	1247	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
danw@120	1248	p->flags = flags;
krh@79	1249	p->version = hashtable_tokenize(&merger->table,
krh@79	1250	&pool[package->version]);
danw@127	1251
krh@66	1252	p->properties = package->properties;
danw@116	1253	r = list_first(&package->properties, &source->set->property_pool);
danw@116	1254	while (r) {
danw@117	1255	source->property_map[r->data] = 1;
danw@116	1256	r = list_next(r);
krh@64	1257	}
danw@127	1258
danw@127	1259	p->files = package->files;
danw@127	1260	r = list_first(&package->files, &source->set->file_pool);
danw@127	1261	while (r) {
danw@127	1262	source->file_map[r->data] = 1;
danw@127	1263	r = list_next(r);
danw@127	1264	}
krh@41	1265	}
krh@41	1266
danw@108	1267	static uint32_t
krh@79	1268	add_property(struct razor_merger *merger,
danw@109	1269	const char *name, enum razor_version_relation relation,
danw@109	1270	const char *version, int type)
krh@41	1271	{
krh@41	1272	struct razor_property *p;
krh@41	1273
krh@79	1274	p = array_add(&merger->set->properties, sizeof *p);
danw@119	1275	p->name = hashtable_tokenize(&merger->table, name);
danw@119	1276	p->flags = 0;
danw@119	1277	p->type = type;
danw@109	1278	p->relation = relation;
krh@79	1279	p->version = hashtable_tokenize(&merger->table, version);
krh@41	1280
krh@79	1281	return p - (struct razor_property *) merger->set->properties.data;
krh@41	1282	}
krh@41	1283
krh@41	1284	static void
krh@79	1285	merge_properties(struct razor_merger *merger)
krh@41	1286	{
krh@41	1287	struct razor_property p1, p2;
krh@79	1288	struct razor_set set1, set2;
danw@108	1289	uint32_t map1, map2;
krh@41	1290	int i, j, cmp, count1, count2;
krh@41	1291	char pool1, pool2;
krh@41	1292
krh@79	1293	set1 = merger->source1.set;
krh@79	1294	set2 = merger->source2.set;
krh@79	1295	map1 = merger->source1.property_map;
krh@79	1296	map2 = merger->source2.property_map;
krh@79	1297
krh@41	1298	i = 0;
krh@41	1299	j = 0;
krh@41	1300	pool1 = set1->string_pool.data;
krh@41	1301	pool2 = set2->string_pool.data;
krh@41	1302
krh@66	1303	count1 = set1->properties.size / sizeof *p1;
krh@66	1304	count2 = set2->properties.size / sizeof *p2;
krh@41	1305	while (i < count1 \|\| j < count2) {
krh@41	1306	if (i < count1 && map1[i] == 0) {
krh@41	1307	i++;
krh@41	1308	continue;
krh@41	1309	}
krh@41	1310	if (j < count2 && map2[j] == 0) {
krh@41	1311	j++;
krh@41	1312	continue;
krh@41	1313	}
krh@66	1314	p1 = (struct razor_property *) set1->properties.data + i;
krh@66	1315	p2 = (struct razor_property *) set2->properties.data + j;
krh@41	1316	if (i < count1 && j < count2)
danw@119	1317	cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
krh@41	1318	else if (i < count1)
krh@41	1319	cmp = -1;
krh@41	1320	else
krh@41	1321	cmp = 1;
krh@41	1322	if (cmp == 0)
danw@121	1323	cmp = p1->type - p2->type;
danw@121	1324	if (cmp == 0)
danw@109	1325	cmp = p1->relation - p2->relation;
danw@109	1326	if (cmp == 0)
krh@41	1327	cmp = versioncmp(&pool1[p1->version],
krh@41	1328	&pool2[p2->version]);
krh@41	1329	if (cmp < 0) {
krh@79	1330	map1[i++] = add_property(merger,
danw@119	1331	&pool1[p1->name],
danw@109	1332	p1->relation,
krh@69	1333	&pool1[p1->version],
danw@119	1334	p1->type);
krh@41	1335	} else if (cmp > 0) {
krh@79	1336	map2[j++] = add_property(merger,
danw@119	1337	&pool2[p2->name],
danw@109	1338	p2->relation,
krh@69	1339	&pool2[p2->version],
danw@119	1340	p2->type);
krh@41	1341	} else {
krh@79	1342	map1[i++] = map2[j++] = add_property(merger,
danw@119	1343	&pool1[p1->name],
danw@109	1344	p1->relation,
krh@69	1345	&pool1[p1->version],
danw@119	1346	p1->type);
krh@41	1347	}
krh@41	1348	}
krh@41	1349	}
krh@41	1350
danw@116	1351	static void
danw@117	1352	emit_properties(struct list_head properties, struct array source_pool,
danw@108	1353	uint32_t map, struct array pool)
krh@41	1354	{
danw@117	1355	uint32_t r;
danw@117	1356	struct list p, q;
krh@41	1357
krh@41	1358	r = pool->size / sizeof *q;
danw@116	1359	p = list_first(properties, source_pool);
danw@116	1360	while (p) {
krh@41	1361	q = array_add(pool, sizeof *q);
danw@117	1362	q->data = map[p->data];
danw@117	1363	q->flags = p->flags;
danw@116	1364	p = list_next(p);
krh@33	1365	}
krh@33	1366
danw@117	1367	list_set_ptr(properties, r);
krh@41	1368	}
danw@127	1369
danw@127	1370	static uint32_t
danw@127	1371	add_file(struct razor_merger merger, const char name)
danw@127	1372	{
danw@127	1373	struct razor_entry *e;
danw@127	1374
danw@127	1375	e = array_add(&merger->set->files, sizeof *e);
danw@127	1376	e->name = hashtable_tokenize(&merger->table, name);
danw@127	1377	e->flags = 0;
danw@127	1378	e->start = 0;
danw@127	1379
danw@127	1380	return e - (struct razor_entry *)merger->set->files.data;
danw@127	1381	}
danw@127	1382
danw@129	1383	/* FIXME. Blah */
danw@127	1384	static int
danw@127	1385	fix_file_map(uint32_t *map,
danw@127	1386	struct razor_entry *files,
danw@127	1387	struct razor_entry *top)
danw@127	1388	{
danw@127	1389	uint32_t e;
danw@127	1390	int found_file = 0;
danw@127	1391
danw@127	1392	e = top->start;
danw@127	1393	do {
danw@127	1394	if (files[e].start)
danw@127	1395	fix_file_map(map, files, &files[e]);
danw@127	1396	if (map[e])
danw@127	1397	found_file = 1;
danw@127	1398	} while (!(files[e++].flags & RAZOR_ENTRY_LAST));
danw@127	1399
danw@127	1400	if (found_file)
danw@127	1401	map[top - files] = 1;
danw@127	1402	return found_file;
danw@127	1403	}
danw@127	1404
danw@127	1405	struct merge_directory {
danw@127	1406	uint32_t merged, dir1, dir2;
danw@127	1407	};
danw@127	1408
danw@127	1409	static void
danw@127	1410	merge_one_directory(struct razor_merger merger, struct merge_directory md)
danw@127	1411	{
danw@127	1412	struct razor_entry root1, root2, mroot, e1, *e2;
danw@127	1413	struct razor_set set1, set2;
danw@127	1414	struct array merge_stack;
danw@127	1415	struct merge_directory child_md, end_md;
danw@127	1416	uint32_t map1, map2, start, last;
danw@127	1417	int cmp;
danw@127	1418	char pool1, pool2;
danw@127	1419
danw@127	1420	set1 = merger->source1.set;
danw@127	1421	set2 = merger->source2.set;
danw@127	1422	map1 = merger->source1.file_map;
danw@127	1423	map2 = merger->source2.file_map;
danw@127	1424	pool1 = set1->string_pool.data;
danw@127	1425	pool2 = set2->string_pool.data;
danw@127	1426	root1 = (struct razor_entry *) set1->files.data;
danw@127	1427	root2 = (struct razor_entry *) set2->files.data;
danw@127	1428
danw@127	1429	array_init(&merge_stack);
danw@127	1430
danw@127	1431	start = merger->set->files.size / sizeof (struct razor_entry);
danw@127	1432	last = 0;
danw@127	1433	e1 = md->dir1 ? root1 + md->dir1 : NULL;
danw@127	1434	e2 = md->dir2 ? root2 + md->dir2 : NULL;
danw@127	1435	while (e1 \|\| e2) {
danw@127	1436	if (!e2 && !map1[e1 - root1]) {
danw@127	1437	if ((e1++)->flags & RAZOR_ENTRY_LAST)
danw@127	1438	e1 = NULL;
danw@127	1439	continue;
danw@127	1440	}
danw@127	1441	if (!e1 && !map2[e2 - root2]) {
danw@127	1442	if ((e2++)->flags & RAZOR_ENTRY_LAST)
danw@127	1443	e2 = NULL;
danw@127	1444	continue;
danw@127	1445	}
danw@127	1446	if (e1 && !map1[e1 - root1] &&
danw@127	1447	e2 && !map1[e2 - root2]) {
danw@127	1448	if ((e1++)->flags & RAZOR_ENTRY_LAST)
danw@127	1449	e1 = NULL;
danw@127	1450	if ((e2++)->flags & RAZOR_ENTRY_LAST)
danw@127	1451	e2 = NULL;
danw@127	1452	continue;
danw@127	1453	}
danw@127	1454
danw@127	1455	if (!e1)
danw@127	1456	cmp = 1;
danw@127	1457	else if (!e2)
danw@127	1458	cmp = -1;
danw@127	1459	else {
danw@127	1460	cmp = strcmp (&pool1[e1->name],
danw@127	1461	&pool2[e2->name]);
danw@127	1462	}
danw@127	1463
danw@127	1464	if (cmp < 0) {
danw@127	1465	if (map1[e1 - root1]) {
danw@127	1466	map1[e1 - root1] = last =
danw@127	1467	add_file(merger, &pool1[e1->name]);
danw@127	1468	if (e1->start) {
danw@127	1469	child_md = array_add(&merge_stack, sizeof (struct merge_directory));
danw@127	1470	child_md->merged = last;
danw@127	1471	child_md->dir1 = e1->start;
danw@127	1472	child_md->dir2 = 0;
danw@127	1473	}
danw@127	1474	}
danw@127	1475	if ((e1++)->flags & RAZOR_ENTRY_LAST)
danw@127	1476	e1 = NULL;
danw@127	1477	} else if (cmp > 0) {
danw@127	1478	if (map2[e2 - root2]) {
danw@127	1479	map2[e2 - root2] = last =
danw@127	1480	add_file(merger, &pool2[e2->name]);
danw@127	1481	if (e2->start) {
danw@127	1482	child_md = array_add(&merge_stack, sizeof (struct merge_directory));
danw@127	1483	child_md->merged = last;
danw@127	1484	child_md->dir1 = 0;
danw@127	1485	child_md->dir2 = e2->start;
danw@127	1486	}
danw@127	1487	}
danw@127	1488	if ((e2++)->flags & RAZOR_ENTRY_LAST)
danw@127	1489	e2 = NULL;
danw@127	1490	} else {
danw@127	1491	map1[e1 - root1] = map2[e2- root2] = last =
danw@127	1492	add_file(merger, &pool1[e1->name]);
danw@127	1493	if (e1->start \|\| e2->start) {
danw@127	1494	child_md = array_add(&merge_stack, sizeof (struct merge_directory));
danw@127	1495	child_md->merged = last;
danw@127	1496	child_md->dir1 = e1->start;
danw@127	1497	child_md->dir2 = e2->start;
danw@127	1498	}
danw@127	1499	if ((e1++)->flags & RAZOR_ENTRY_LAST)
danw@127	1500	e1 = NULL;
danw@127	1501	if ((e2++)->flags & RAZOR_ENTRY_LAST)
danw@127	1502	e2 = NULL;
danw@127	1503	}
danw@127	1504	}
danw@127	1505
danw@127	1506	mroot = (struct razor_entry *)merger->set->files.data;
danw@127	1507	if (last) {
danw@127	1508	mroot[last].flags = RAZOR_ENTRY_LAST;
danw@127	1509	mroot[md->merged].start = start;
danw@127	1510	} else
danw@127	1511	mroot[md->merged].start = 0;
danw@127	1512
danw@127	1513	end_md = merge_stack.data + merge_stack.size;
danw@127	1514	for (child_md = merge_stack.data; child_md < end_md; child_md++)
danw@127	1515	merge_one_directory(merger, child_md);
danw@127	1516	array_release(&merge_stack);
danw@127	1517	}
danw@127	1518
danw@127	1519	static void
danw@127	1520	merge_files(struct razor_merger *merger)
danw@127	1521	{
danw@129	1522	struct razor_entry *root;
danw@127	1523	struct merge_directory md;
danw@127	1524	uint32_t map1, map2;
danw@127	1525
danw@127	1526	map1 = merger->source1.file_map;
danw@127	1527	map2 = merger->source2.file_map;
danw@127	1528
danw@127	1529	md.merged = add_file(merger, "");
danw@129	1530
danw@129	1531	if (merger->source1.set->files.size) {
danw@129	1532	root = (struct razor_entry *) merger->source1.set->files.data;
danw@129	1533	if (root->start)
danw@129	1534	fix_file_map(map1, root, root);
danw@129	1535	md.dir1 = root->start;
danw@129	1536	} else
danw@129	1537	md.dir1 = 0;
danw@129	1538
danw@129	1539	if (merger->source2.set->files.size) {
danw@129	1540	root = (struct razor_entry *) merger->source2.set->files.data;
danw@129	1541	if (root->start)
danw@129	1542	fix_file_map(map2, root, root);
danw@129	1543	md.dir2 = root->start;
danw@129	1544	} else
danw@129	1545	md.dir2 = 0;
danw@129	1546
danw@127	1547	merge_one_directory(merger, &md);
danw@127	1548	}
danw@127	1549
danw@127	1550	static void
danw@127	1551	emit_files(struct list_head files, struct array source_pool,
danw@127	1552	uint32_t map, struct array pool)
danw@127	1553	{
danw@127	1554	uint32_t r;
danw@127	1555	struct list p, q;
danw@127	1556
danw@127	1557	r = pool->size / sizeof *q;
danw@127	1558	p = list_first(files, source_pool);
danw@127	1559	while (p) {
danw@127	1560	q = array_add(pool, sizeof *q);
danw@127	1561	q->data = map[p->data];
danw@127	1562	q->flags = p->flags;
danw@127	1563	p = list_next(p);
danw@127	1564	}
danw@127	1565
danw@127	1566	list_set_ptr(files, r);
danw@127	1567	}
danw@127	1568
krh@41	1569	/* Rebuild property->packages maps. We can't just remap these, as a
krh@41	1570	* property may have lost or gained a number of packages. Allocate an
krh@41	1571	* array per property and loop through the packages and add them to
krh@41	1572	* the arrays for their properties. */
krh@41	1573	static void
danw@127	1574	rebuild_property_package_lists(struct razor_set *set)
krh@41	1575	{
krh@66	1576	struct array pkgs, a;
krh@41	1577	struct razor_package pkg, pkg_end;
krh@41	1578	struct razor_property prop, prop_end;
danw@117	1579	struct list *r;
danw@117	1580	uint32_t *q;
krh@66	1581	int count;
krh@41	1582
krh@66	1583	count = set->properties.size / sizeof (struct razor_property);
krh@66	1584	pkgs = zalloc(count * sizeof *pkgs);
krh@41	1585	pkg_end = set->packages.data + set->packages.size;
krh@41	1586
krh@41	1587	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
danw@128	1588	r = list_first(&pkg->properties, &set->property_pool);
danw@116	1589	while (r) {
danw@117	1590	q = array_add(&pkgs[r->data], sizeof *q);
krh@41	1591	q = pkg - (struct razor_package ) set->packages.data;
danw@116	1592	r = list_next(r);
krh@41	1593	}
krh@33	1594	}
krh@33	1595
krh@66	1596	prop_end = set->properties.data + set->properties.size;
krh@66	1597	a = pkgs;
krh@66	1598	for (prop = set->properties.data; prop < prop_end; prop++, a++) {
danw@128	1599	list_set_array(&prop->packages, &set->package_pool, a, 0);
krh@41	1600	array_release(a);
krh@41	1601	}
krh@66	1602	free(pkgs);
krh@33	1603	}
krh@33	1604
danw@127	1605	static void
danw@127	1606	rebuild_file_package_lists(struct razor_set *set)
danw@127	1607	{
danw@127	1608	struct array pkgs, a;
danw@127	1609	struct razor_package pkg, pkg_end;
danw@127	1610	struct razor_entry entry, entry_end;
danw@127	1611	struct list *r;
danw@127	1612	uint32_t *q;
danw@127	1613	int count;
danw@127	1614
danw@127	1615	count = set->files.size / sizeof (struct razor_entry);
danw@127	1616	pkgs = zalloc(count * sizeof *pkgs);
danw@127	1617	pkg_end = set->packages.data + set->packages.size;
danw@127	1618
danw@127	1619	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
danw@128	1620	r = list_first(&pkg->files, &set->file_pool);
danw@127	1621	while (r) {
danw@127	1622	q = array_add(&pkgs[r->data], sizeof *q);
danw@127	1623	q = pkg - (struct razor_package ) set->packages.data;
danw@127	1624	r = list_next(r);
danw@127	1625	}
danw@127	1626	}
danw@127	1627
danw@127	1628	entry_end = set->files.data + set->files.size;
danw@127	1629	a = pkgs;
danw@127	1630	for (entry = set->files.data; entry < entry_end; entry++, a++) {
danw@128	1631	list_set_array(&entry->packages, &set->package_pool, a, 0);
danw@127	1632	array_release(a);
danw@127	1633	}
danw@127	1634	free(pkgs);
danw@127	1635	}
danw@127	1636
danw@137	1637	static struct razor_set *
krh@79	1638	razor_merger_finish(struct razor_merger *merger)
krh@79	1639	{
krh@79	1640	struct razor_set *result;
krh@41	1641	struct razor_package p, pend;
krh@33	1642
krh@41	1643	/* As we built the package list, we filled out a bitvector of
krh@41	1644	* the properties that are referenced by the packages in the
krh@41	1645	* new set. Now we do a parallel loop through the properties
krh@41	1646	* and emit those marked in the bit vector to the new set. In
krh@41	1647	* the process, we update the bit vector to actually map from
krh@41	1648	* indices in the old property list to indices in the new
krh@41	1649	* property list for both sets. */
krh@41	1650
krh@79	1651	merge_properties(merger);
danw@127	1652	merge_files(merger);
krh@41	1653
krh@41	1654	/* Now we loop through the packages again and emit the
krh@41	1655	* property lists, remapped to point to the new properties. */
krh@41	1656
krh@79	1657	pend = merger->set->packages.data + merger->set->packages.size;
krh@79	1658	for (p = merger->set->packages.data; p < pend; p++) {
krh@41	1659	struct source *src;
krh@41	1660
danw@120	1661	if (p->flags & UPSTREAM_SOURCE)
krh@79	1662	src = &merger->source2;
krh@41	1663	else
krh@79	1664	src = &merger->source1;
krh@41	1665
danw@116	1666	emit_properties(&p->properties,
danw@116	1667	&src->set->property_pool,
danw@116	1668	src->property_map,
danw@116	1669	&merger->set->property_pool);
danw@127	1670	emit_files(&p->files,
danw@127	1671	&src->set->file_pool,
danw@127	1672	src->file_map,
danw@127	1673	&merger->set->file_pool);
danw@120	1674	p->flags &= ~UPSTREAM_SOURCE;
krh@33	1675	}
krh@33	1676
danw@127	1677	rebuild_property_package_lists(merger->set);
danw@127	1678	rebuild_file_package_lists(merger->set);
krh@41	1679
danw@129	1680	result = merger->set;
danw@129	1681	hashtable_release(&merger->table);
danw@129	1682	free(merger);
danw@129	1683
danw@129	1684	return result;
danw@129	1685	}
danw@129	1686
danw@146	1687	/* The diff order matters. We should sort the packages so that a
danw@146	1688	* REMOVE of a package comes before the INSTALL, and so that all
danw@146	1689	* requires for a package have been installed before the package.
danw@146	1690	**/
danw@146	1691
danw@146	1692	void
danw@146	1693	razor_set_diff(struct razor_set set, struct razor_set upstream,
danw@146	1694	razor_package_callback_t callback, void *data)
danw@146	1695	{
danw@146	1696	struct razor_package_iterator pi1, pi2;
danw@146	1697	struct razor_package p1, p2;
danw@146	1698	const char name1, name2, version1, version2;
danw@146	1699	int res;
danw@146	1700
danw@146	1701	pi1 = razor_package_iterator_create(set);
danw@146	1702	pi2 = razor_package_iterator_create(upstream);
danw@146	1703
danw@146	1704	razor_package_iterator_next(pi1, &p1, &name1, &version1);
danw@146	1705	razor_package_iterator_next(pi2, &p2, &name2, &version2);
danw@146	1706
danw@146	1707	while (p1 \|\| p2) {
danw@146	1708	if (p1 && p2) {
danw@146	1709	res = strcmp(name1, name2);
danw@146	1710	if (res == 0)
danw@146	1711	res = versioncmp(version1, version2);
danw@146	1712	} else {
danw@146	1713	res = 0;
danw@146	1714	}
danw@146	1715
danw@146	1716	if (p2 == NULL \|\| res < 0)
danw@146	1717	callback(name1, version1, NULL, data);
danw@146	1718	else if (p1 == NULL \|\| res > 0)
danw@146	1719	callback(name2, NULL, version2, data);
danw@146	1720
danw@146	1721	if (p1 != NULL && res <= 0)
danw@146	1722	razor_package_iterator_next(pi1, &p1,
danw@146	1723	&name1, &version1);
danw@146	1724	if (p2 != NULL && res >= 0)
danw@146	1725	razor_package_iterator_next(pi2, &p2,
danw@146	1726	&name2, &version2);
danw@146	1727	}
danw@146	1728
danw@146	1729	razor_package_iterator_destroy(pi1);
danw@146	1730	razor_package_iterator_destroy(pi2);
danw@146	1731	}
danw@146	1732
danw@141	1733
danw@141	1734	struct razor_transaction_resolver {
danw@141	1735	struct razor_set system, upstream;
danw@141	1736	struct bitarray syspkgs, uppkgs;
danw@141	1737	struct array packages;
danw@141	1738	int errors;
danw@141	1739	};
danw@141	1740
danw@144	1741	static int
danw@144	1742	package_in_set(void package, struct razor_set set)
danw@144	1743	{
danw@144	1744	return package >= set->packages.data &&
danw@144	1745	package < set->packages.data + set->packages.size;
danw@144	1746	}
danw@144	1747
danw@144	1748	static int
danw@144	1749	property_in_set(void property, struct razor_set set)
danw@144	1750	{
danw@144	1751	return property >= set->properties.data &&
danw@144	1752	property < set->properties.data + set->properties.size;
danw@144	1753	}
danw@144	1754
danw@144	1755	static int
danw@144	1756	compare_transaction_packages(const void one, const void two)
danw@144	1757	{
danw@144	1758	const struct razor_transaction_package *tp1 = one;
danw@144	1759	const struct razor_transaction_package *tp2 = two;
danw@144	1760
danw@144	1761	return strcmp(tp1->name, tp2->name);
danw@144	1762	}
danw@144	1763
danw@141	1764	static void
danw@141	1765	find_packages(struct razor_transaction_resolver *trans,
danw@144	1766	int update_count, const char **update_packages,
danw@144	1767	int remove_count, const char **remove_packages)
krh@38	1768	{
danw@144	1769	struct razor_package sp, spkgs, up, upkgs, send, uend;
danw@144	1770	struct razor_transaction_package packages, tp;
danw@144	1771	const char spool, upool;
danw@144	1772	int i;
danw@144	1773
danw@144	1774	spkgs = trans->system->packages.data;
danw@144	1775	send = trans->system->packages.data + trans->system->packages.size;
danw@144	1776	spool = trans->system->string_pool.data;
danw@144	1777	upkgs = trans->upstream->packages.data;
danw@144	1778	uend = trans->upstream->packages.data + trans->upstream->packages.size;
danw@144	1779	upool = trans->upstream->string_pool.data;
danw@144	1780
danw@144	1781	for (i = 0; i < update_count; i++) {
danw@144	1782	tp = array_add(&trans->packages, sizeof *tp);
danw@144	1783	memset(tp, 0, sizeof *tp);
danw@144	1784	tp->name = update_packages[i];
danw@144	1785	tp->state = RAZOR_PACKAGE_INSTALL;
danw@141	1786	}
danw@144	1787	for (i = 0; i < remove_count; i++) {
danw@144	1788	tp = array_add(&trans->packages, sizeof *tp);
danw@144	1789	memset(tp, 0, sizeof *tp);
danw@144	1790	tp->name = remove_packages[i];
danw@144	1791	tp->state = RAZOR_PACKAGE_REMOVE;
danw@144	1792	}
danw@144	1793	qsort(trans->packages.data, update_count + remove_count,
danw@144	1794	sizeof *tp, compare_transaction_packages);
danw@144	1795	packages = trans->packages.data;
danw@144	1796
danw@144	1797	sp = spkgs;
danw@144	1798	up = upkgs;
danw@144	1799	for (i = 0; i < update_count + remove_count; i++) {
danw@144	1800	while (sp < send && strcmp(&spool[sp->name], packages[i].name) < 0)
danw@144	1801	sp++;
danw@144	1802	while (up < uend && strcmp(&upool[up->name], packages[i].name) < 0)
danw@144	1803	up++;
danw@144	1804
danw@144	1805	if (packages[i].state == RAZOR_PACKAGE_REMOVE) {
danw@144	1806	if (sp < send && strcmp(packages[i].name, &spool[sp->name]) == 0) {
danw@147	1807	packages[i].old_package = sp;
danw@144	1808	packages[i].name = &spool[sp->name];
danw@147	1809	packages[i].old_version = &spool[sp->version];
danw@144	1810	bitarray_set(&trans->syspkgs, sp - spkgs, 0);
danw@144	1811	} else {
danw@144	1812	packages[i].name = strdup(packages[i].name);
danw@145	1813	packages[i].state = RAZOR_PACKAGE_REMOVE_NOT_INSTALLED;
danw@144	1814	trans->errors++;
danw@144	1815	}
danw@144	1816	} else {
danw@144	1817	if (up < uend && strcmp(packages[i].name, &upool[up->name]) == 0) {
danw@147	1818	packages[i].new_package = up;
danw@145	1819	packages[i].name = &upool[up->name];
danw@147	1820	packages[i].new_version = &upool[up->version];
danw@144	1821	if (sp < send && strcmp(packages[i].name, &spool[sp->name]) == 0) {
danw@147	1822	packages[i].old_package = sp;
danw@147	1823	packages[i].old_version = &spool[sp->version];
danw@144	1824	if (versioncmp(&spool[sp->version], &upool[up->version]) >= 0) {
danw@145	1825	packages[i].state = RAZOR_PACKAGE_UP_TO_DATE;
danw@144	1826	trans->errors++;
danw@144	1827	continue;
danw@144	1828	}
danw@144	1829	bitarray_set(&trans->syspkgs, sp - spkgs, 0);
danw@144	1830	}
danw@144	1831	bitarray_set(&trans->uppkgs, up - upkgs, 1);
danw@144	1832	} else {
danw@144	1833	packages[i].name = strdup(packages[i].name);
danw@145	1834	packages[i].state = RAZOR_PACKAGE_INSTALL_UNAVAILABLE;
danw@144	1835	trans->errors++;
krh@105	1836	}
krh@105	1837	}
krh@38	1838	}
krh@38	1839	}
krh@38	1840
krh@38	1841	static void
danw@141	1842	find_all_packages(struct razor_transaction_resolver *trans)
krh@38	1843	{
danw@137	1844	struct razor_transaction_package *tp;
danw@144	1845	struct razor_package sp, spkgs, send, up, upkgs, uend;
danw@144	1846	const char spool, upool;
danw@144	1847
danw@144	1848	spkgs = trans->system->packages.data;
danw@144	1849	send = trans->system->packages.data + trans->system->packages.size;
danw@144	1850	spool = trans->system->string_pool.data;
danw@144	1851	up = upkgs = trans->upstream->packages.data;
danw@141	1852	uend = trans->upstream->packages.data + trans->upstream->packages.size;
danw@141	1853	upool = trans->upstream->string_pool.data;
krh@38	1854
danw@144	1855	for (sp = spkgs; sp < send; sp++) {
danw@144	1856	while (up < uend && strcmp(&spool[sp->name], &upool[up->name]) > 0)
danw@144	1857	up++;
danw@144	1858	if (strcmp(&spool[sp->name], &upool[up->name]) == 0) {
danw@141	1859	tp = array_add(&trans->packages, sizeof *tp);
danw@137	1860	memset(tp, 0, sizeof *tp);
danw@147	1861	tp->old_package = sp;
danw@147	1862	tp->new_package = up;
danw@144	1863	tp->name = &upool[up->name];
danw@147	1864	tp->old_version = &spool[sp->version];
danw@147	1865	tp->new_version = &upool[up->version];
danw@137	1866	tp->state = RAZOR_PACKAGE_INSTALL;
danw@144	1867	bitarray_set(&trans->uppkgs, up - upkgs, 1);
danw@144	1868	bitarray_set(&trans->syspkgs, sp - spkgs, 0);
krh@38	1869	}
krh@38	1870	}
krh@38	1871	}
krh@38	1872
danw@137	1873	static int
danw@137	1874	provider_satisfies_requirement(struct razor_property *provider,
danw@137	1875	const char *provider_strings,
danw@137	1876	struct razor_property *requirement,
danw@137	1877	const char *requirement_strings)
danw@137	1878	{
danw@137	1879	int cmp, len;
danw@137	1880	const char *provided = &provider_strings[provider->version];
danw@137	1881	const char *required = &requirement_strings[requirement->version];
danw@137	1882
danw@137	1883	if (!*required)
danw@137	1884	return 1;
danw@137	1885
danw@137	1886	cmp = versioncmp(provided, required);
danw@137	1887
danw@137	1888	switch (requirement->relation) {
danw@137	1889	case RAZOR_VERSION_LESS:
danw@137	1890	return cmp < 0;
danw@137	1891
danw@137	1892	case RAZOR_VERSION_LESS_OR_EQUAL:
danw@137	1893	if (cmp <= 0)
danw@137	1894	return 1;
danw@137	1895	/* fall through: FIXME, make sure this is correct */
danw@137	1896
danw@137	1897	case RAZOR_VERSION_EQUAL:
danw@137	1898	if (cmp == 0)
danw@137	1899	return 1;
danw@137	1900
danw@137	1901	/* "foo == 1.1" is satisfied by "foo 1.1-2" */
danw@137	1902	len = strlen(required);
danw@137	1903	if (!strncmp(required, provided, len) && provided[len] == '-')
danw@137	1904	return 1;
danw@137	1905	return 0;
danw@137	1906
danw@137	1907	case RAZOR_VERSION_GREATER_OR_EQUAL:
danw@137	1908	return cmp >= 0;
danw@137	1909
danw@137	1910	case RAZOR_VERSION_GREATER:
danw@137	1911	return cmp > 0;
danw@137	1912	}
danw@137	1913
danw@137	1914	/* shouldn't happen */
danw@137	1915	return 0;
danw@137	1916	}
danw@137	1917
danw@142	1918	static struct razor_package *
danw@144	1919	find_package_for_file(struct razor_set set, struct bitarray pkgbits,
danw@144	1920	const char *filename, int installed)
danw@134	1921	{
danw@142	1922	struct razor_package *pkgs = set->packages.data;
danw@140	1923	struct razor_entry *entry;
danw@140	1924	struct list *p;
danw@134	1925
danw@140	1926	if (filename[0] != '/')
danw@140	1927	return 0;
danw@140	1928
danw@142	1929	entry = find_entry(set, set->files.data, filename);
danw@140	1930	if (!entry)
danw@140	1931	return 0;
danw@140	1932
danw@142	1933	for (p = list_first(&entry->packages, &set->package_pool); p; p = list_next(p)) {
danw@142	1934	if (bitarray_get(pkgbits, p->data) == installed)
danw@142	1935	return &pkgs[p->data];
danw@134	1936	}
danw@142	1937	return NULL;
danw@142	1938	}
danw@142	1939
danw@142	1940	static struct razor_package *
danw@144	1941	find_installed_package_for_file(struct razor_transaction_resolver *trans,
danw@144	1942	const char *filename)
danw@142	1943	{
danw@144	1944	struct razor_package *pkg;
danw@144	1945
danw@144	1946	pkg = find_package_for_file(trans->system, &trans->syspkgs,
danw@144	1947	filename, 1);
danw@144	1948	if (!pkg)
danw@144	1949	pkg = find_package_for_file(trans->upstream, &trans->uppkgs,
danw@144	1950	filename, 1);
danw@144	1951	return pkg;
danw@142	1952	}
danw@142	1953
danw@142	1954	static struct razor_package *
danw@144	1955	find_uninstalled_package_for_file(struct razor_transaction_resolver *trans,
danw@144	1956	const char *filename)
danw@142	1957	{
danw@144	1958	struct razor_package *pkg;
danw@144	1959
danw@144	1960	pkg = find_package_for_file(trans->upstream, &trans->uppkgs,
danw@144	1961	filename, 0);
danw@144	1962	if (!pkg)
danw@144	1963	pkg = find_package_for_file(trans->system, &trans->syspkgs,
danw@144	1964	filename, 0);
danw@144	1965	return pkg;
danw@134	1966	}
danw@134	1967
danw@154	1968	static struct razor_property *
danw@154	1969	skip_to_matching_property(struct razor_transaction_resolver *trans,
danw@154	1970	struct razor_property *match,
danw@154	1971	struct razor_property *prop)
danw@154	1972	{
danw@154	1973	struct razor_set mset, pset;
danw@154	1974	const char ppool, mpool;
danw@154	1975	struct razor_property *prop_end;
danw@154	1976
danw@154	1977	if (property_in_set(match, trans->system))
danw@154	1978	mset = trans->system;
danw@154	1979	else
danw@154	1980	mset = trans->upstream;
danw@154	1981
danw@154	1982	if (property_in_set(prop, trans->system))
danw@154	1983	pset = trans->system;
danw@154	1984	else if (property_in_set(prop, trans->upstream))
danw@154	1985	pset = trans->upstream;
danw@154	1986	else
danw@154	1987	return prop;
danw@154	1988
danw@154	1989	prop_end = pset->properties.data + pset->properties.size;
danw@154	1990	ppool = pset->string_pool.data;
danw@154	1991	mpool = mset->string_pool.data;
danw@154	1992
danw@154	1993	while (prop < prop_end &&
danw@154	1994	strcmp(&ppool[prop->name], &mpool[match->name]) < 0)
danw@154	1995	prop++;
danw@154	1996	return prop;
danw@154	1997	}
danw@154	1998
danw@140	1999	static struct razor_package *
danw@144	2000	find_package_matching(struct razor_transaction_resolver *trans, int installed,
danw@154	2001	struct razor_property *prop,
danw@144	2002	struct razor_property *req,
danw@144	2003	struct razor_set *req_set)
danw@138	2004	{
danw@144	2005	struct razor_set *set;
danw@144	2006	struct bitarray *pkgbits;
danw@144	2007	struct razor_package *pkgs;
danw@154	2008	struct razor_property props, prop_end;
danw@144	2009	enum razor_property_type match_type;
danw@144	2010	const char *pool;
danw@154	2011	const char *rpool;
danw@154	2012	int match_name = (req->type == RAZOR_PROPERTY_OBSOLETES);
danw@144	2013	int match;
danw@144	2014
danw@144	2015	if (property_in_set(prop, trans->system)) {
danw@144	2016	set = trans->system;
danw@144	2017	pkgbits = &trans->syspkgs;
danw@144	2018	} else if (property_in_set(prop, trans->upstream)) {
danw@144	2019	set = trans->upstream;
danw@144	2020	pkgbits = &trans->uppkgs;
danw@144	2021	} else
danw@144	2022	return NULL;
danw@144	2023
danw@154	2024	if (!req_set) {
danw@154	2025	if (property_in_set(req, trans->system))
danw@154	2026	req_set = trans->system;
danw@154	2027	else
danw@154	2028	req_set = trans->upstream;
danw@154	2029	}
danw@154	2030	rpool = req_set->string_pool.data;
danw@154	2031
danw@144	2032	if (req->type == RAZOR_PROPERTY_PROVIDES)
danw@144	2033	match_type = RAZOR_PROPERTY_CONFLICTS;
danw@144	2034	else
danw@144	2035	match_type = RAZOR_PROPERTY_PROVIDES;
danw@144	2036
danw@144	2037	pkgs = set->packages.data;
danw@144	2038	props = set->properties.data;
danw@144	2039	prop_end = set->properties.data + set->properties.size;
danw@144	2040	pool = set->string_pool.data;
danw@144	2041
danw@144	2042	/* Find first matching property */
danw@144	2043	while (prop < prop_end &&
danw@144	2044	strcmp(&pool[prop->name], &rpool[req->name]) < 0)
danw@144	2045	prop++;
danw@144	2046	if (prop == prop_end \|\|
danw@144	2047	strcmp(&pool[prop->name], &rpool[req->name]) > 0)
danw@144	2048	return NULL;
danw@144	2049
danw@144	2050	if (prop->type < match_type) {
danw@144	2051	while (prop < prop_end && prop->type != match_type)
danw@144	2052	prop++;
danw@144	2053	} else {
danw@144	2054	while (prop >= props && prop->type != match_type)
danw@144	2055	prop--;
danw@144	2056	while (prop > props + 1 && (prop - 1)->type == match_type)
danw@144	2057	prop--;
danw@144	2058	}
danw@144	2059
danw@153	2060	/* Scan matching properties */
danw@144	2061	while (prop < prop_end && prop->type == match_type &&
danw@144	2062	strcmp(&pool[prop->name], &rpool[req->name]) == 0) {
danw@144	2063	if (match_type == RAZOR_PROPERTY_PROVIDES)
danw@144	2064	match = provider_satisfies_requirement(prop, pool, req, rpool);
danw@144	2065	else
danw@144	2066	match = provider_satisfies_requirement(req, rpool, prop, pool);
danw@144	2067	if (match) {
danw@140	2068	struct list *pkg;
danw@140	2069
danw@144	2070	for (pkg = list_first(&prop->packages, &set->package_pool); pkg; pkg = list_next(pkg)) {
danw@144	2071	if (bitarray_get(pkgbits, pkg->data) != installed)
danw@140	2072	continue;
danw@140	2073	if (!match_name \|\|
danw@144	2074	strcmp(&pool[pkgs[pkg->data].name],
danw@144	2075	&rpool[req->name]) == 0)
danw@144	2076	return &pkgs[pkg->data];
danw@140	2077	}
danw@140	2078	}
danw@144	2079	prop++;
danw@140	2080	}
danw@140	2081
danw@140	2082	return NULL;
danw@138	2083	}
danw@138	2084
danw@140	2085	static struct razor_package *
danw@144	2086	find_installed_package_for_property(struct razor_transaction_resolver *trans,
danw@154	2087	struct razor_property *sys_start,
danw@154	2088	struct razor_property *up_start,
danw@144	2089	struct razor_property *req)
danw@138	2090	{
danw@144	2091	struct razor_package *pkg;
danw@144	2092
danw@154	2093	pkg = find_package_matching(trans, 1, sys_start, req, NULL);
danw@144	2094	if (!pkg)
danw@154	2095	pkg = find_package_matching(trans, 1, up_start, req, NULL);
danw@144	2096	return pkg;
danw@144	2097	}
danw@144	2098
danw@144	2099	static struct razor_package *
danw@144	2100	find_uninstalled_package_for_property(struct razor_transaction_resolver *trans,
danw@154	2101	struct razor_property *sys_start,
danw@154	2102	struct razor_property *up_start,
danw@144	2103	struct razor_property *req)
danw@144	2104	{
danw@144	2105	struct razor_package *pkg;
danw@144	2106
danw@154	2107	pkg = find_package_matching(trans, 0, up_start, req, NULL);
danw@144	2108	if (!pkg)
danw@154	2109	pkg = find_package_matching(trans, 0, sys_start, req, NULL);
danw@144	2110	return pkg;
danw@140	2111	}
danw@140	2112
danw@144	2113	/* FIXME */
danw@144	2114	static struct razor_package *
danw@144	2115	find_upgrade_for_installed_conflict(struct razor_transaction_resolver *trans,
danw@144	2116	struct razor_package *conflicting_pkg,
danw@156	2117	struct razor_property *prop)
danw@144	2118	{
danw@144	2119	struct razor_package upkgs, up, *uend;
danw@144	2120	struct razor_property *uprops;
danw@144	2121	const char spool, upool;
danw@156	2122	struct list *p;
danw@140	2123
danw@144	2124	up = upkgs = trans->upstream->packages.data;
danw@144	2125	uend = trans->upstream->packages.data + trans->upstream->packages.size;
danw@144	2126	upool = trans->upstream->string_pool.data;
danw@144	2127	uprops = trans->upstream->properties.data;
danw@144	2128	spool = trans->system->string_pool.data;
danw@144	2129
danw@144	2130	while (up < uend &&
danw@144	2131	strcmp(&upool[up->name], &spool[conflicting_pkg->name]) < 0)
danw@144	2132	up++;
danw@144	2133	if (up == uend \|\| strcmp(&upool[up->name], &spool[conflicting_pkg->name]) != 0)
danw@144	2134	return NULL;
danw@144	2135
danw@156	2136	for (p = list_first(&up->properties, &trans->upstream->property_pool); p; p = list_next(p)) {
danw@156	2137	if (prop->type == RAZOR_PROPERTY_PROVIDES &&
danw@156	2138	uprops[p->data].type == RAZOR_PROPERTY_CONFLICTS &&
danw@156	2139	provider_satisfies_requirement(prop, upool, &uprops[p->data], upool))
danw@156	2140	return NULL;
danw@156	2141	else if (prop->type == RAZOR_PROPERTY_CONFLICTS &&
danw@156	2142	uprops[p->data].type == RAZOR_PROPERTY_PROVIDES &&
danw@156	2143	provider_satisfies_requirement(&uprops[p->data], upool, prop, upool))
danw@144	2144	return NULL;
danw@144	2145	}
danw@144	2146	return up;
danw@144	2147	}
danw@144	2148
danw@144	2149	/* FIXME */
danw@144	2150	static int
danw@144	2151	prop_is_being_installed(struct razor_transaction_resolver *trans,
danw@144	2152	struct razor_property *prop)
danw@144	2153	{
danw@144	2154	struct list *pkg;
danw@144	2155
danw@144	2156	for (pkg = list_first(&prop->packages, &trans->upstream->package_pool); pkg; pkg = list_next(pkg)) {
danw@144	2157	if (bitarray_get(&trans->uppkgs, pkg->data))
danw@144	2158	return 1;
danw@144	2159	}
danw@144	2160	return 0;
danw@140	2161	}
danw@140	2162
danw@147	2163	static struct razor_transaction_package *
danw@147	2164	find_transaction_package(struct razor_transaction_resolver *trans,
danw@147	2165	const char *name)
danw@147	2166	{
danw@147	2167	struct razor_transaction_package *packages;
danw@147	2168	int count, i;
danw@147	2169
danw@147	2170	packages = trans->packages.data;
danw@147	2171	count = trans->packages.size / sizeof *packages;
danw@147	2172	for (i = 0; i < count; i++) {
danw@147	2173	if (packages[i].name && !strcmp(packages[i].name, name))
danw@147	2174	return &packages[i];
danw@147	2175	}
danw@147	2176	return NULL;
danw@147	2177	}
danw@147	2178
danw@131	2179	static void
danw@141	2180	add_transaction_package(struct razor_transaction_resolver *trans,
danw@147	2181	struct razor_package *new_package,
danw@147	2182	struct razor_package *old_package,
danw@140	2183	enum razor_transaction_package_state state,
danw@144	2184	const char *req_package,
danw@144	2185	struct razor_property *req_prop)
danw@131	2186	{
danw@147	2187	struct razor_set new_package_set, old_package_set, *req_set;
danw@147	2188	struct bitarray newpkgbits, oldpkgbits, *reqpkgbits;
danw@147	2189	struct razor_transaction_package tp, already;
danw@140	2190	const char *pool;
danw@140	2191	struct razor_package *pkgs;
danw@140	2192	struct list *pkg;
danw@147	2193	int contradiction = 0;
danw@147	2194
danw@147	2195	if (package_in_set(new_package, trans->system)) {
danw@147	2196	new_package_set = trans->system;
danw@147	2197	newpkgbits = &trans->syspkgs;
danw@147	2198	} else {
danw@147	2199	new_package_set = trans->upstream;
danw@147	2200	newpkgbits = &trans->uppkgs;
danw@147	2201	}
danw@147	2202	if (package_in_set(old_package, trans->system)) {
danw@147	2203	old_package_set = trans->system;
danw@147	2204	oldpkgbits = &trans->syspkgs;
danw@147	2205	} else {
danw@147	2206	old_package_set = trans->upstream;
danw@147	2207	oldpkgbits = &trans->uppkgs;
danw@147	2208	}
danw@145	2209	if (property_in_set(req_prop, trans->system)) {
danw@145	2210	req_set = trans->system;
danw@145	2211	reqpkgbits = &trans->syspkgs;
danw@145	2212	} else {
danw@145	2213	req_set = trans->upstream;
danw@145	2214	reqpkgbits = &trans->uppkgs;
danw@145	2215	}
danw@144	2216
danw@147	2217	if (new_package) {
danw@147	2218	pool = new_package_set->string_pool.data;
danw@147	2219	already = find_transaction_package(trans, &pool[new_package->name]);
danw@147	2220	if (already) {
danw@147	2221	if (already->new_package == new_package) {
danw@147	2222	/* Already taken care of */
danw@147	2223	return;
danw@147	2224	}
danw@147	2225	/* Oops. We lose */
danw@147	2226	if (state != RAZOR_PACKAGE_CONTRADICTION)
danw@147	2227	contradiction = 1;
danw@147	2228	}
danw@147	2229	} else if (old_package) {
danw@147	2230	pool = old_package_set->string_pool.data;
danw@147	2231	already = find_transaction_package(trans, &pool[old_package->name]);
danw@147	2232	if (already) {
danw@147	2233	if (already->old_package == old_package) {
danw@147	2234	/* Already taken care of */
danw@147	2235	return;
danw@147	2236	}
danw@147	2237	/* Oops. We lose */
danw@147	2238	if (state != RAZOR_PACKAGE_CONTRADICTION)
danw@147	2239	contradiction = 1;
danw@147	2240	}
danw@147	2241	} else
danw@147	2242	state = RAZOR_PACKAGE_UNSATISFIABLE;
danw@147	2243
danw@141	2244	tp = array_add(&trans->packages, sizeof *tp);
danw@140	2245	memset(tp, 0, sizeof *tp);
danw@131	2246
danw@147	2247	if (new_package) {
danw@147	2248	pool = new_package_set->string_pool.data;
danw@147	2249	tp->new_package = new_package;
danw@147	2250	tp->name = &pool[new_package->name];
danw@147	2251	tp->new_version = &pool[new_package->version];
danw@147	2252
danw@147	2253	pkgs = new_package_set->packages.data;
danw@147	2254	bitarray_set(newpkgbits, new_package - pkgs, 1);
danw@147	2255	}
danw@147	2256	if (old_package) {
danw@147	2257	pool = old_package_set->string_pool.data;
danw@147	2258	tp->old_package = old_package;
danw@147	2259	tp->name = &pool[old_package->name];
danw@147	2260	tp->old_version = &pool[old_package->version];
danw@147	2261
danw@147	2262	pkgs = old_package_set->packages.data;
danw@147	2263	bitarray_set(oldpkgbits, old_package - pkgs, 0);
danw@147	2264	}
danw@147	2265
danw@147	2266	tp->state = state;
danw@147	2267	if (state != RAZOR_PACKAGE_INSTALL &&
danw@154	2268	state != RAZOR_PACKAGE_FORCED_UPDATE &&
danw@154	2269	state != RAZOR_PACKAGE_REMOVE &&
danw@154	2270	state != RAZOR_PACKAGE_OBSOLETED)
danw@145	2271	trans->errors++;
danw@147	2272
danw@147	2273	if (contradiction) {
danw@147	2274	/* Do this now, after adding tp, so that it ends up
danw@147	2275	* after both the INSTALL and the REMOVE in the array.
danw@147	2276	*/
danw@147	2277	add_transaction_package(trans, new_package, old_package,
danw@147	2278	RAZOR_PACKAGE_CONTRADICTION,
danw@147	2279	NULL, NULL);
danw@145	2280	}
danw@140	2281
danw@144	2282	if (req_package)
danw@145	2283	tp->dep_package = req_package;
danw@145	2284	if (!req_prop)
danw@145	2285	return;
danw@145	2286
danw@145	2287	pool = req_set->string_pool.data;
danw@145	2288	pkgs = req_set->packages.data;
danw@145	2289	if (!req_package) {
danw@145	2290	for (pkg = list_first(&req_prop->packages, &req_set->package_pool); pkg; pkg = list_next(pkg)) {
danw@145	2291	if (bitarray_get(reqpkgbits, pkg->data))
danw@144	2292	break;
danw@144	2293	}
danw@145	2294	if (pkg)
danw@145	2295	tp->dep_package = &pool[pkgs[pkg->data].name];
danw@131	2296	}
danw@144	2297
danw@145	2298	tp->dep_type = req_prop->type;
danw@145	2299	tp->dep_property = &pool[req_prop->name];
danw@145	2300	tp->dep_relation = req_prop->relation;
danw@145	2301	tp->dep_version = &pool[req_prop->version];
danw@140	2302	}
danw@140	2303
danw@144	2304	/* FIXME: make this more efficient */
danw@147	2305	static struct razor_package *
danw@147	2306	find_old_version(struct razor_transaction_resolver *trans,
danw@147	2307	struct razor_package *pkg)
danw@147	2308	{
danw@147	2309	struct razor_package spkgs, sp, *send;
danw@147	2310	const char spool, upool;
danw@147	2311
danw@147	2312	if (!package_in_set(pkg, trans->upstream))
danw@147	2313	return NULL;
danw@147	2314
danw@147	2315	sp = spkgs = trans->system->packages.data;
danw@147	2316	send = trans->system->packages.data + trans->system->packages.size;
danw@147	2317	spool = trans->system->string_pool.data;
danw@147	2318	upool = trans->upstream->string_pool.data;
danw@147	2319
danw@147	2320	while (sp < send &&
danw@147	2321	strcmp(&spool[sp->name], &upool[pkg->name]) < 0)
danw@147	2322	sp++;
danw@147	2323	if (sp < send && strcmp(&spool[sp->name], &upool[pkg->name]) == 0)
danw@147	2324	return sp;
danw@147	2325	return NULL;
danw@147	2326	}
danw@147	2327
danw@137	2328	static void
danw@141	2329	razor_transaction_satisfy_installs(struct razor_transaction_resolver *trans)
krh@33	2330	{
danw@144	2331	struct razor_package spkgs, upkgs, pkg, upgrade;
danw@144	2332	struct razor_property sp, sprops, *sprop_end;
danw@144	2333	struct razor_property up, uprops, *uprop_end;
danw@145	2334	const char spool, upool;
danw@134	2335
danw@140	2336	spkgs = trans->system->packages.data;
danw@140	2337	sprops = trans->system->properties.data;
danw@144	2338	sprop_end = trans->system->properties.data + trans->system->properties.size;
danw@145	2339	spool = trans->system->string_pool.data;
danw@140	2340	upkgs = trans->upstream->packages.data;
danw@140	2341	uprops = trans->upstream->properties.data;
danw@144	2342	uprop_end = trans->upstream->properties.data + trans->upstream->properties.size;
danw@140	2343	upool = trans->upstream->string_pool.data;
krh@33	2344
danw@144	2345	sp = sprops;
danw@144	2346	up = uprops;
danw@144	2347	while (up < uprop_end) {
danw@140	2348	/* Skip 'up' ahead to a property of a package which is
danw@140	2349	* to-be-installed.
danw@140	2350	*/
danw@144	2351	while (up < uprop_end &&
danw@144	2352	!prop_is_being_installed(trans, up))
danw@140	2353	up++;
danw@144	2354	if (up == uprop_end)
danw@140	2355	break;
danw@154	2356	sp = skip_to_matching_property(trans, up, sp);
krh@33	2357
danw@144	2358	switch (up->type) {
danw@140	2359	case RAZOR_PROPERTY_REQUIRES:
danw@144	2360	if (!strncmp(&upool[up->name], "rpmlib(", 7))
danw@140	2361	break;
danw@131	2362
danw@154	2363	if (find_installed_package_for_property(trans, sp, up, up) \|\|
danw@144	2364	find_installed_package_for_file(trans, &upool[up->name])) {
danw@140	2365	/* Requires something that is either installed
danw@140	2366	* or to-be-installed.
danw@140	2367	*/
danw@140	2368	break;
danw@137	2369	}
danw@137	2370
danw@140	2371	/* See if we can install a new upstream provider */
danw@154	2372	pkg = find_uninstalled_package_for_property(trans, sp, up, up);
danw@154	2373	if (!pkg)
danw@144	2374	pkg = find_uninstalled_package_for_file(trans, &upool[up->name]);
danw@147	2375	add_transaction_package(trans, pkg, find_old_version(trans, pkg),
danw@144	2376	RAZOR_PACKAGE_INSTALL,
danw@144	2377	NULL, up);
danw@144	2378	break;
danw@144	2379
danw@144	2380	case RAZOR_PROPERTY_PROVIDES:
danw@144	2381	/* find_installed_package_for_property works backwards
danw@144	2382	* here, finding a conflicting installed package.
danw@144	2383	*/
danw@154	2384	pkg = find_installed_package_for_property(trans, sp, up, up);
danw@140	2385	if (!pkg)
danw@144	2386	break;
danw@144	2387
danw@145	2388	if (package_in_set(pkg, trans->system)) {
danw@145	2389	/* pkg CONFLICTS with what 'up' PROVIDES. Try
danw@145	2390	* finding an upgrade
danw@145	2391	*/
danw@145	2392	upgrade = find_upgrade_for_installed_conflict(trans, pkg, up);
danw@145	2393	if (upgrade) {
danw@147	2394	add_transaction_package(trans, upgrade, pkg,
danw@145	2395	RAZOR_PACKAGE_INSTALL,
danw@145	2396	&spool[pkg->name], sp);
danw@145	2397	}
danw@145	2398	break;
danw@144	2399	}
danw@145	2400
danw@147	2401	add_transaction_package(trans, NULL, pkg,
danw@145	2402	RAZOR_PACKAGE_OLD_CONFLICT,
danw@145	2403	NULL, up);
danw@140	2404	break;
danw@140	2405
danw@140	2406	case RAZOR_PROPERTY_CONFLICTS:
danw@154	2407	pkg = find_installed_package_for_property(trans, sp, up, up);
danw@144	2408	if (!pkg)
danw@144	2409	break;
danw@144	2410
danw@144	2411	if (package_in_set(pkg, trans->system)) {
danw@140	2412	/* Conflicts with something already installed.
danw@140	2413	* Try to upgrade out.
danw@140	2414	*/
danw@156	2415	upgrade = find_upgrade_for_installed_conflict(trans, pkg, up);
danw@140	2416	if (upgrade) {
danw@147	2417	add_transaction_package(trans, upgrade, pkg,
danw@140	2418	RAZOR_PACKAGE_INSTALL,
danw@144	2419	NULL, up);
danw@145	2420	break;
danw@140	2421	}
danw@140	2422	}
danw@145	2423
danw@147	2424	add_transaction_package(trans, pkg, NULL,
danw@145	2425	RAZOR_PACKAGE_NEW_CONFLICT,
danw@145	2426	NULL, up);
danw@140	2427	break;
danw@140	2428
danw@140	2429	case RAZOR_PROPERTY_OBSOLETES:
danw@154	2430	pkg = find_installed_package_for_property(trans, sp, up, up);
danw@145	2431	if (pkg) {
danw@145	2432	/* If pkg is to-be-installed, this
danw@145	2433	* will add a CONTRADICTION error as well.
danw@145	2434	*/
danw@147	2435	add_transaction_package(trans, NULL, pkg,
danw@154	2436	RAZOR_PACKAGE_OBSOLETED,
danw@144	2437	NULL, up);
danw@140	2438	}
danw@140	2439	break;
danw@140	2440
danw@140	2441	default:
danw@140	2442	/* can't happen */
danw@140	2443	break;
danw@131	2444	}
danw@140	2445	up++;
krh@37	2446	}
krh@33	2447	}
krh@33	2448
danw@154	2449	#if 0
danw@130	2450	/* Look through pkg's PROVIDES, and for each one that no other package
danw@130	2451	* provides, add its property index to lost_provides.
danw@130	2452	*/
danw@130	2453	static void
danw@130	2454	gather_lost_provides(struct razor_set set, struct razor_package pkg,
danw@130	2455	struct array *lost_provides)
danw@130	2456	{
danw@130	2457	struct razor_property props = set->properties.data, prop;
danw@130	2458	struct list p, providers;
danw@130	2459	uint32_t *lost;
danw@130	2460
danw@130	2461	for (p = list_first(&pkg->properties, &set->property_pool); p; p = list_next(p)) {
danw@130	2462	prop = &props[p->data];
danw@130	2463	if (prop->type != RAZOR_PROPERTY_PROVIDES)
danw@130	2464	continue;
danw@130	2465
danw@130	2466	providers = list_first(&prop->packages, &set->package_pool);
danw@130	2467	if (providers && !list_next(providers)) {
danw@130	2468	lost = array_add(lost_provides, sizeof *lost);
danw@130	2469	*lost = p->data;
danw@130	2470	}
danw@130	2471	}
danw@130	2472	}
danw@130	2473
danw@130	2474	static void
danw@139	2475	gather_lost_files(struct razor_set set, struct razor_package pkg,
danw@139	2476	struct array *lost_files)
danw@130	2477	{
danw@139	2478	struct razor_entry entries = set->files.data, entry, **lost;
danw@139	2479	struct list e, providers;
danw@139	2480
danw@139	2481	for (e = list_first(&pkg->files, &set->file_pool); e; e = list_next(e)) {
danw@139	2482	entry = &entries[e->data];
danw@139	2483	providers = list_first(&entry->packages, &set->package_pool);
danw@139	2484	if (providers && !list_next(providers)) {
danw@139	2485	lost = array_add(lost_files, sizeof *lost);
danw@139	2486	*lost = entry;
danw@139	2487	}
danw@139	2488	}
danw@139	2489	}
danw@139	2490
danw@139	2491	static void
danw@141	2492	lose_required_package(struct razor_transaction_resolver *trans,
danw@139	2493	struct razor_property *req,
danw@139	2494	struct list_head *lost_package_list)
danw@139	2495	{
danw@139	2496	struct razor_package pkgs, lost_package;
danw@137	2497	char *pool = trans->system->string_pool.data;
danw@130	2498	struct list *p;
danw@130	2499
danw@137	2500	pkgs = trans->system->packages.data;
danw@139	2501	lost_package = &pkgs[list_first(lost_package_list, &trans->system->package_pool)->data];
danw@139	2502
danw@139	2503	for (p = list_first(&req->packages, &trans->system->package_pool); p; p = list_next(p)) {
danw@147	2504	add_transaction_package(trans, NULL, &pkgs[p->data],
danw@144	2505	RAZOR_PACKAGE_REMOVE,
danw@144	2506	&pool[lost_package->name], req);
danw@139	2507	}
danw@139	2508	}
danw@139	2509
danw@139	2510	static void
danw@141	2511	lose_requirement(struct razor_transaction_resolver *trans,
danw@139	2512	struct razor_property *req,
danw@139	2513	struct razor_property *lost_provider,
danw@139	2514	struct razor_property *first_provider)
danw@139	2515	{
danw@139	2516	struct razor_property provider, prop_end;
danw@139	2517	char *pool = trans->system->string_pool.data;
danw@139	2518
danw@137	2519	prop_end = trans->system->properties.data + trans->system->properties.size;
danw@130	2520
danw@137	2521	/* See if any other provider satisfies req */
danw@137	2522	for (provider = first_provider;
danw@137	2523	provider < prop_end && provider->type == RAZOR_PROPERTY_PROVIDES && provider->name == lost_provider->name;
danw@137	2524	provider++) {
danw@137	2525	if (provider == lost_provider)
danw@137	2526	continue;
danw@137	2527
danw@137	2528	if (provider_satisfies_requirement(provider, pool, req, pool))
danw@137	2529	return;
danw@137	2530	}
danw@137	2531
danw@141	2532	lose_required_package(trans, req, &lost_provider->packages);
danw@130	2533	}
danw@130	2534
danw@137	2535	static void
danw@141	2536	razor_transaction_satisfy_removes(struct razor_transaction_resolver *trans,
danw@137	2537	int start, int end)
danw@129	2538	{
danw@137	2539	struct razor_transaction_package *packages;
danw@129	2540	struct razor_package *pkgs;
danw@137	2541	int pkg_count, r;
danw@137	2542	uint32_t lost, lost_end;
danw@139	2543	struct razor_entry entry, lostf, *lostf_end;
danw@137	2544	struct razor_property props, prop_end, req, first_provider;
danw@139	2545	struct array lost_provides, lost_files;
danw@139	2546	char *pool;
danw@129	2547
danw@137	2548	pkgs = trans->system->packages.data;
danw@137	2549	pkg_count = trans->system->packages.size / sizeof (struct razor_package);
danw@137	2550	props = trans->system->properties.data;
danw@137	2551	prop_end = trans->system->properties.data + trans->system->properties.size;
danw@139	2552	pool = trans->system->string_pool.data;
danw@144	2553	packages = trans->packages.data;
danw@130	2554
danw@139	2555	array_init(&lost_files);
danw@139	2556	array_init(&lost_provides);
danw@137	2557	for (r = start; r < end; r++) {
danw@147	2558	if (!packages[r].old_package \|\|
danw@147	2559	(packages[r].state != RAZOR_PACKAGE_REMOVE &&
danw@154	2560	packages[r].state != RAZOR_PACKAGE_INSTALL &&
danw@154	2561	packages[r].state != RAZOR_PACKAGE_FORCED_UPDATE &&
danw@154	2562	packages[r].state != RAZOR_PACKAGE_OBSOLETED)
danw@137	2563	continue;
danw@137	2564
danw@147	2565	gather_lost_provides(trans->system, packages[r].old_package,
danw@137	2566	&lost_provides);
danw@147	2567	gather_lost_files(trans->system, packages[r].old_package,
danw@139	2568	&lost_files);
danw@139	2569	}
danw@130	2570
danw@139	2571	/* Handle lost_provides */
danw@139	2572	lost_end = lost_provides.data + lost_provides.size;
danw@139	2573	for (lost = lost_provides.data; lost < lost_end; lost++) {
danw@139	2574	/* Requires FOO will appear before Provides FOO */
danw@139	2575	for (req = &props[lost]; req > props && req->name == props[lost].name && req->type != RAZOR_PROPERTY_REQUIRES; req--)
danw@139	2576	;
danw@139	2577	first_provider = req + 1;
danw@137	2578
danw@139	2579	while (req > props && req->name == props[*lost].name) {
danw@141	2580	lose_requirement(trans, req, &props[*lost],
danw@141	2581	first_provider);
danw@139	2582	req--;
danw@130	2583	}
danw@130	2584	}
danw@139	2585	array_release(&lost_provides);
danw@139	2586
danw@139	2587	/* And now lost_files. FIXME, inefficient */
danw@139	2588	lostf_end = lost_files.data + lost_files.size;
danw@139	2589
danw@139	2590	req = props;
danw@139	2591	/* Due to the sorting of props, this loop is likely a no-op */
danw@140	2592	while (req < prop_end && pool[req->name] != '/')
danw@139	2593	req++;
danw@139	2594
danw@139	2595	for (; req < prop_end && pool[req->name] == '/'; req++) {
danw@139	2596	if (req->type != RAZOR_PROPERTY_REQUIRES)
danw@139	2597	continue;
danw@139	2598
danw@139	2599	entry = find_entry(trans->system, trans->system->files.data,
danw@139	2600	&pool[req->name]);
danw@139	2601	if (!entry)
danw@139	2602	continue;
danw@139	2603
danw@139	2604	for (lostf = lost_files.data; lostf < lostf_end; lostf++) {
danw@139	2605	if (*lostf == entry)
danw@139	2606	break;
danw@139	2607	}
danw@139	2608	if (lostf == lostf_end)
danw@139	2609	continue;
danw@139	2610
danw@141	2611	lose_required_package(trans, req, &entry->packages);
danw@139	2612	}
danw@139	2613	array_release(&lost_files);
danw@129	2614	}
danw@154	2615	#endif
danw@154	2616
danw@154	2617	static struct razor_package *
danw@154	2618	find_upgrade_for_lost_requirement(struct razor_transaction_resolver *trans,
danw@154	2619	struct razor_package *pkg,
danw@154	2620	struct razor_property *req)
danw@154	2621	{
danw@154	2622	struct razor_package upkgs, up, *uend;
danw@154	2623	struct razor_property *uprops;
danw@154	2624	const char spool, upool;
danw@154	2625	struct list *prop;
danw@154	2626
danw@154	2627	up = upkgs = trans->upstream->packages.data;
danw@154	2628	uend = trans->upstream->packages.data + trans->upstream->packages.size;
danw@154	2629	upool = trans->upstream->string_pool.data;
danw@154	2630	uprops = trans->upstream->properties.data;
danw@154	2631	spool = trans->system->string_pool.data;
danw@154	2632
danw@154	2633	while (up < uend &&
danw@154	2634	strcmp(&upool[up->name], &spool[pkg->name]) < 0)
danw@154	2635	up++;
danw@154	2636	if (up == uend \|\| strcmp(&upool[up->name], &spool[pkg->name]) != 0)
danw@154	2637	return NULL;
danw@154	2638
danw@154	2639	for (prop = list_first(&up->properties, &trans->system->property_pool); prop; prop = list_next(prop)) {
danw@154	2640	if (uprops[prop->data].type == RAZOR_PROPERTY_REQUIRES &&
danw@154	2641	strcmp(&upool[uprops[prop->data].name], &spool[req->name]) == 0 &&
danw@154	2642	uprops[prop->data].relation == req->relation &&
danw@154	2643	strcmp(&upool[uprops[prop->data].version], &spool[req->version]) == 0)
danw@154	2644	return NULL;
danw@154	2645	}
danw@154	2646	return up;
danw@154	2647	}
danw@154	2648
danw@154	2649	static int
danw@154	2650	prop_is_being_removed(struct razor_transaction_resolver *trans,
danw@154	2651	struct razor_property *prop)
danw@154	2652	{
danw@154	2653	struct list *pkg;
danw@154	2654
danw@154	2655	for (pkg = list_first(&prop->packages, &trans->system->package_pool); pkg; pkg = list_next(pkg)) {
danw@154	2656	if (bitarray_get(&trans->syspkgs, pkg->data))
danw@154	2657	return 0;
danw@154	2658	}
danw@154	2659	return 1;
danw@154	2660	}
danw@154	2661
danw@154	2662	static int
danw@154	2663	prop_is_being_updated(struct razor_transaction_resolver *trans,
danw@154	2664	struct razor_property *prop)
danw@154	2665	{
danw@154	2666	struct razor_package *packages = trans->system->packages.data;
danw@154	2667	const char *pool = trans->system->string_pool.data;
danw@154	2668	struct razor_transaction_package *tp;
danw@154	2669	struct list *pkg;
danw@154	2670
danw@154	2671	/* Assumes prop_is_being_removed returns true */
danw@154	2672
danw@154	2673	for (pkg = list_first(&prop->packages, &trans->system->package_pool); pkg; pkg = list_next(pkg)) {
danw@154	2674	tp = find_transaction_package(trans, &pool[packages[pkg->data].name]);
danw@154	2675	if (tp && tp->state == RAZOR_PACKAGE_REMOVE)
danw@154	2676	return 0;
danw@154	2677	}
danw@154	2678	return 1;
danw@154	2679	}
danw@154	2680
danw@154	2681	static void
danw@154	2682	razor_transaction_satisfy_removes(struct razor_transaction_resolver *trans)
danw@154	2683	{
danw@154	2684	struct razor_package spkgs, upkgs, pkg, upgrade;
danw@154	2685	struct razor_property sp, sprops, sprop_end, sr;
danw@154	2686	struct razor_property up, uprops, uprop_end, ur, *first_up;
danw@154	2687	const char spool, upool, *removed_package;
danw@154	2688	struct list *reqpkg;
danw@154	2689
danw@154	2690	spkgs = trans->system->packages.data;
danw@154	2691	sprops = trans->system->properties.data;
danw@154	2692	sprop_end = trans->system->properties.data + trans->system->properties.size;
danw@154	2693	spool = trans->system->string_pool.data;
danw@154	2694	upkgs = trans->upstream->packages.data;
danw@154	2695	uprops = trans->upstream->properties.data;
danw@154	2696	uprop_end = trans->upstream->properties.data + trans->upstream->properties.size;
danw@154	2697	upool = trans->upstream->string_pool.data;
danw@154	2698
danw@154	2699	up = uprops;
danw@154	2700	for (sp = sprops; sp < sprop_end; sp++) {
danw@154	2701	/* Skip 'sp' ahead to a PROVIDES of a package which is
danw@154	2702	* to-be-removed.
danw@154	2703	*/
danw@154	2704	while (sp < sprop_end &&
danw@154	2705	(sp->type != RAZOR_PROPERTY_PROVIDES \|\|
danw@154	2706	!prop_is_being_removed(trans, sp)))
danw@154	2707	sp++;
danw@154	2708	if (sp == sprop_end)
danw@154	2709	break;
danw@154	2710
danw@154	2711	removed_package = &spool[spkgs[list_first(&sp->packages, &trans->system->package_pool)->data].name];
danw@154	2712
danw@154	2713	/* Skip 'up' to match */
danw@154	2714	up = skip_to_matching_property(trans, sp, up);
danw@154	2715	ur = first_up = up;
danw@154	2716
danw@154	2717	/* If the package is just being upgraded, we may
danw@154	2718	* already be installing an identical PROVIDES, so
danw@154	2719	* check for that.
danw@154	2720	*/
danw@154	2721	while (up < uprop_end &&
danw@154	2722	strcmp(&spool[sp->name], &upool[up->name]) == 0 &&
danw@154	2723	(up->type != RAZOR_PROPERTY_PROVIDES \|\|
danw@154	2724	sp->relation != up->relation \|\|
danw@154	2725	strcmp(&spool[sp->name], &upool[up->name]) != 0))
danw@154	2726	up++;
danw@154	2727	if (up < uprop_end &&
danw@154	2728	up->type == RAZOR_PROPERTY_PROVIDES &&
danw@154	2729	strcmp(&spool[sp->name], &upool[up->name]) == 0 &&
danw@154	2730	sp->relation == up->relation &&
danw@154	2731	strcmp(&spool[sp->version], &upool[up->version]) == 0 &&
danw@154	2732	prop_is_being_installed(trans, up)) {
danw@154	2733	up = first_up;
danw@154	2734	continue;
danw@154	2735	}
danw@154	2736	up = first_up;
danw@154	2737
danw@154	2738	/* For all still-installed packages that require
danw@154	2739	* sp->name, see if they are satisfied by any other
danw@154	2740	* still-installed or to-be-installed property. If
danw@154	2741	* not, either remove or attempt to update the
danw@154	2742	* package, depending on why the required property has
danw@154	2743	* disappeared
danw@154	2744	*/
danw@154	2745	sr = sp;
danw@154	2746	while (sr > sprops + 1 && (sr - 1)->name == sr->name)
danw@154	2747	sr--;
danw@154	2748	for (; sr->type == RAZOR_PROPERTY_REQUIRES; sr++) {
danw@154	2749	if (prop_is_being_removed(trans, sr))
danw@154	2750	continue;
danw@154	2751	if (find_installed_package_for_property(trans, sp, up, sr))
danw@154	2752	continue;
danw@154	2753
danw@154	2754	for (reqpkg = list_first(&sr->packages, &trans->system->package_pool); reqpkg; reqpkg = list_next(reqpkg)) {
danw@154	2755	if (!bitarray_get(&trans->syspkgs, reqpkg->data))
danw@154	2756	continue;
danw@154	2757	pkg = &spkgs[reqpkg->data];
danw@154	2758	if (prop_is_being_updated(trans, sp)) {
danw@154	2759	upgrade = find_upgrade_for_lost_requirement(trans, pkg, sr);
danw@154	2760	if (upgrade) {
danw@154	2761	add_transaction_package(trans, upgrade, pkg,
danw@154	2762	RAZOR_PACKAGE_FORCED_UPDATE,
danw@154	2763	removed_package, NULL);
danw@154	2764	} else {
danw@154	2765	/* This will cause a CONTRADICTION */
danw@154	2766	add_transaction_package(trans, pkg, NULL,
danw@154	2767	RAZOR_PACKAGE_INSTALL,
danw@154	2768	removed_package, sr);
danw@154	2769	}
danw@154	2770	} else {
danw@154	2771	add_transaction_package(trans, NULL, pkg,
danw@154	2772	RAZOR_PACKAGE_REMOVE,
danw@154	2773	removed_package, sr);
danw@154	2774	}
danw@154	2775	}
danw@154	2776	}
danw@154	2777	}
danw@154	2778	}
danw@129	2779
danw@137	2780	struct razor_transaction *
danw@137	2781	razor_transaction_create(struct razor_set system, struct razor_set upstream,
danw@137	2782	int update_count, const char **update_packages,
danw@137	2783	int remove_count, const char **remove_packages)
danw@137	2784	{
danw@141	2785	struct razor_transaction_resolver trans;
danw@141	2786	struct razor_transaction *ret_trans;
danw@137	2787	int start, end;
danw@137	2788
danw@141	2789	trans.system = system;
danw@141	2790	trans.upstream = upstream ? upstream : razor_set_create();
danw@141	2791	array_init(&trans.packages);
danw@141	2792	bitarray_init(&trans.syspkgs, trans.system->packages.size / sizeof (struct razor_package), 1);
danw@141	2793	bitarray_init(&trans.uppkgs, trans.upstream->packages.size / sizeof (struct razor_package), 0);
danw@141	2794	trans.errors = 0;
danw@137	2795
danw@144	2796	if (update_count > 0 \|\| remove_count > 0) {
danw@144	2797	find_packages(&trans,
danw@144	2798	update_count, update_packages,
danw@144	2799	remove_count, remove_packages);
danw@144	2800	} else
danw@141	2801	find_all_packages(&trans);
danw@137	2802
danw@137	2803	start = 0;
danw@141	2804	end = trans.packages.size / sizeof (struct razor_transaction_package);
danw@137	2805
danw@141	2806	while (!trans.errors && start != end) {
danw@141	2807	razor_transaction_satisfy_installs(&trans);
danw@154	2808	razor_transaction_satisfy_removes(&trans);
danw@137	2809
danw@137	2810	start = end;
danw@141	2811	end = trans.packages.size / sizeof (struct razor_transaction_package);
danw@137	2812	}
danw@137	2813
danw@141	2814	ret_trans = zalloc(sizeof *ret_trans);
danw@141	2815	ret_trans->system = trans.system;
danw@141	2816	ret_trans->upstream = trans.upstream;
danw@141	2817	ret_trans->packages = trans.packages.data;
danw@141	2818	ret_trans->package_count = end;
danw@141	2819	ret_trans->errors = trans.errors;
danw@141	2820	return ret_trans;
danw@137	2821	}
danw@137	2822
danw@137	2823	const char * const razor_version_relations[] = {
danw@137	2824	/* same order as enum razor_version_relation */
danw@137	2825	"<", "<=", "=", ">=", ">"
danw@137	2826	};
danw@137	2827
danw@140	2828	const char * const razor_property_types[] = {
danw@140	2829	/* same order as enum razor_property_type */
danw@140	2830	"requires", "provides", "conflicts with", "obsoletes"
danw@140	2831	};
danw@140	2832
danw@137	2833	void
danw@137	2834	razor_transaction_describe(struct razor_transaction *trans)
danw@137	2835	{
danw@137	2836	struct razor_transaction_package p, pend, *tps;
danw@137	2837	int errors_only = 0;
danw@137	2838
danw@137	2839	tps = trans->packages;
danw@137	2840	pend = trans->packages + trans->package_count;
danw@137	2841	for (p = trans->packages; p < pend; p++) {
danw@137	2842	switch (p->state) {
danw@137	2843	case RAZOR_PACKAGE_INSTALL:
danw@137	2844	if (errors_only)
danw@137	2845	break;
danw@137	2846
danw@147	2847	printf("Installing %s %s", p->name, p->new_version);
danw@145	2848	if (p->dep_package) {
danw@145	2849	if (p->dep_type == RAZOR_PROPERTY_CONFLICTS &&
danw@145	2850	!strcmp(p->dep_package, p->name)) {
danw@147	2851	printf(" because %s %s conflicts with %s",
danw@147	2852	p->name, p->old_version, p->dep_property);
danw@145	2853	if (*p->dep_version) {
danw@145	2854	printf(" %s %s",
danw@145	2855	razor_version_relations[p->dep_relation],
danw@145	2856	p->dep_version);
danw@145	2857	}
danw@145	2858	} else {
danw@145	2859	printf(" for %s", p->dep_package);
danw@145	2860	if (*p->dep_version) {
danw@145	2861	printf(", which %s %s %s %s",
danw@145	2862	razor_property_types[p->dep_type],
danw@145	2863	p->dep_property,
danw@145	2864	razor_version_relations[p->dep_relation],
danw@145	2865	p->dep_version);
danw@145	2866	} else if (strcmp(p->dep_property, p->name) != 0) {
danw@145	2867	printf(", which %s %s",
danw@145	2868	razor_property_types[p->dep_type],
danw@145	2869	p->dep_property);
danw@145	2870	}
danw@137	2871	}
danw@137	2872	}
danw@137	2873	printf("\n");
danw@137	2874	break;
danw@137	2875
danw@154	2876	case RAZOR_PACKAGE_FORCED_UPDATE:
danw@154	2877	if (errors_only)
danw@154	2878	break;
danw@154	2879
danw@154	2880	printf("Updating %s to %s due to update of %s\n",
danw@154	2881	p->name, p->new_version, p->dep_package);
danw@154	2882	break;
danw@154	2883
danw@137	2884	case RAZOR_PACKAGE_REMOVE:
danw@137	2885	if (errors_only)
danw@137	2886	break;
danw@147	2887	printf("Removing %s %s", p->name, p->old_version);
danw@145	2888	if (p->dep_package) {
danw@154	2889	printf(" which required %s",
danw@154	2890	p->dep_package);
danw@154	2891	if (strcmp(p->dep_property, p->name) != 0)
danw@154	2892	printf(" for %s", p->dep_property);
danw@154	2893	}
danw@154	2894	printf("\n");
danw@154	2895	break;
danw@154	2896
danw@154	2897	case RAZOR_PACKAGE_OBSOLETED:
danw@154	2898	if (errors_only)
danw@154	2899	break;
danw@154	2900	printf("Removing %s %s", p->name, p->old_version);
danw@154	2901	if (p->dep_package) {
danw@154	2902	printf(" which is obsoleted by %s",
danw@154	2903	p->dep_package);
danw@137	2904	}
danw@137	2905	printf("\n");
danw@137	2906	break;
danw@137	2907
danw@145	2908	case RAZOR_PACKAGE_INSTALL_UNAVAILABLE:
danw@145	2909	printf("Error: can't install %s: not found\n", p->name);
danw@137	2910	errors_only = 1;
danw@137	2911	break;
danw@137	2912
danw@145	2913	case RAZOR_PACKAGE_REMOVE_NOT_INSTALLED:
danw@145	2914	printf("Error: can't remove %s: not installed\n", p->name);
danw@137	2915	errors_only = 1;
danw@137	2916	break;
danw@137	2917
danw@145	2918	case RAZOR_PACKAGE_UP_TO_DATE:
danw@147	2919	printf("Error: can't upgrade %s: %s is most recent version\n", p->name, p->old_version);
danw@145	2920	errors_only = 1;
danw@145	2921	break;
danw@145	2922
danw@145	2923	case RAZOR_PACKAGE_CONTRADICTION:
danw@147	2924	printf("Error: package %s is marked for both installation and removal\n", p->name);
danw@145	2925	errors_only = 1;
danw@145	2926	break;
danw@145	2927
danw@145	2928	case RAZOR_PACKAGE_OLD_CONFLICT:
danw@145	2929	printf("Error: can't install %s, because installed package %s conflicts with ",
danw@145	2930	p->name, p->dep_package);
danw@145	2931	if (*p->dep_version) {
danw@145	2932	printf("%s %s %s",
danw@145	2933	p->dep_property,
danw@145	2934	razor_version_relations[p->dep_relation],
danw@145	2935	p->dep_version);
danw@145	2936	} else
danw@145	2937	printf("it");
danw@145	2938	printf("\n");
danw@145	2939
danw@145	2940	errors_only = 1;
danw@145	2941	break;
danw@145	2942
danw@145	2943	case RAZOR_PACKAGE_NEW_CONFLICT:
danw@145	2944	printf("Error: can't install %s, because it conflicts with %s",
danw@145	2945	p->name, p->dep_package);
danw@145	2946	if (*p->dep_version) {
danw@145	2947	printf(" %s %s",
danw@145	2948	razor_version_relations[p->dep_relation],
danw@145	2949	p->dep_version);
danw@145	2950	}
danw@145	2951	printf("\n");
danw@145	2952
danw@145	2953	errors_only = 1;
danw@145	2954	break;
danw@145	2955
danw@145	2956	case RAZOR_PACKAGE_UNSATISFIABLE:
danw@145	2957	printf("Error: can't find package for %s", p->dep_property);
danw@145	2958	if (*p->dep_version) {
danw@145	2959	printf(" %s %s",
danw@145	2960	razor_version_relations[p->dep_relation],
danw@145	2961	p->dep_version);
danw@145	2962	}
danw@145	2963	printf(" which is required by %s\n",
danw@145	2964	p->dep_package);
danw@140	2965	errors_only = 1;
danw@140	2966	break;
danw@140	2967
danw@137	2968	default:
danw@137	2969	/* Shouldn't actually happen */
danw@137	2970	break;
danw@137	2971	}
danw@137	2972	}
danw@137	2973	}
danw@137	2974
danw@137	2975	struct razor_set *
danw@137	2976	razor_transaction_run(struct razor_transaction *trans)
danw@137	2977	{
danw@137	2978	struct array install_packages, remove_packages;
danw@137	2979	struct razor_merger *merger;
danw@137	2980	struct razor_package pkg, i, iend, r, rend, s, *send;
danw@137	2981	struct source source1, source2;
danw@137	2982	char spool, ipool, *rpool;
danw@137	2983	uint32_t *map;
danw@137	2984	int p, cmp;
danw@137	2985
danw@137	2986	/* FIXME */
danw@137	2987	if (trans->errors)
danw@137	2988	return NULL;
danw@137	2989
danw@137	2990	/* Sort the transaction packages into two arrays */
danw@137	2991	array_init(&install_packages);
danw@137	2992	array_init(&remove_packages);
danw@137	2993	for (p = 0; p < trans->package_count; p++) {
danw@147	2994	if (trans->packages[p].state == RAZOR_PACKAGE_INSTALL) {
danw@137	2995	pkg = array_add(&install_packages, sizeof *pkg);
danw@147	2996	pkg = trans->packages[p].new_package;
danw@147	2997	} else {
danw@137	2998	pkg = array_add(&remove_packages, sizeof *pkg);
danw@147	2999	pkg = trans->packages[p].old_package;
danw@147	3000	}
danw@137	3001	}
danw@137	3002	map = qsort_with_data(install_packages.data,
danw@137	3003	install_packages.size / sizeof *pkg,
danw@137	3004	sizeof *pkg,
danw@137	3005	compare_packages,
danw@137	3006	trans->upstream);
danw@137	3007	free(map);
danw@137	3008	map = qsort_with_data(remove_packages.data,
danw@137	3009	remove_packages.size / sizeof *pkg,
danw@137	3010	sizeof *pkg,
danw@137	3011	compare_packages,
danw@137	3012	trans->system);
danw@137	3013	free(map);
danw@137	3014
danw@137	3015	merger = razor_merger_create(trans->system, trans->upstream);
danw@137	3016
danw@137	3017	source1 = &merger->source1;
danw@137	3018	source2 = &merger->source2;
danw@137	3019
danw@137	3020	i = install_packages.data;
danw@137	3021	iend = install_packages.data + install_packages.size;
danw@137	3022	ipool = trans->upstream->string_pool.data;
danw@137	3023
danw@137	3024	r = remove_packages.data;
danw@137	3025	rend = remove_packages.data + remove_packages.size;
danw@137	3026	rpool = trans->system->string_pool.data;
danw@137	3027
danw@137	3028	s = trans->system->packages.data;
danw@137	3029	send = trans->system->packages.data + trans->system->packages.size;
danw@137	3030	spool = trans->system->string_pool.data;
danw@137	3031
danw@137	3032	while (s < send \|\| i < iend) {
danw@137	3033	/* Check if s is being removed */
danw@137	3034	if (s < send && r < rend &&
danw@137	3035	s->name == r->name && s->version && r->version) {
danw@137	3036	s++;
danw@137	3037	r++;
danw@137	3038	continue;
danw@137	3039	}
danw@137	3040
danw@137	3041	if (s < send && i < iend)
danw@137	3042	cmp = strcmp(&spool[s->name], &ipool[i->name]);
danw@137	3043	else if (s < send)
danw@137	3044	cmp = -1;
danw@137	3045	else
danw@137	3046	cmp = 1;
danw@137	3047	if (cmp < 0) {
danw@137	3048	add_package(merger, s, source1, 0);
danw@137	3049	s++;
danw@137	3050	} else if (cmp == 0) {
danw@137	3051	add_package(merger, i, source2, UPSTREAM_SOURCE);
danw@137	3052	s++;
danw@137	3053	i++;
danw@137	3054	} else {
danw@137	3055	add_package(merger, i, source2, UPSTREAM_SOURCE);
danw@137	3056	i++;
danw@137	3057	}
danw@137	3058	}
danw@137	3059
danw@137	3060	array_release(&install_packages);
danw@137	3061	array_release(&remove_packages);
danw@137	3062
danw@137	3063	return razor_merger_finish(merger);
danw@137	3064	}
danw@137	3065
danw@137	3066	void
danw@137	3067	razor_transaction_destroy(struct razor_transaction *trans)
danw@137	3068	{
danw@137	3069	int p;
danw@137	3070
danw@137	3071	for (p = 0; p < trans->package_count; p++) {
danw@145	3072	if (!trans->packages[p].dep_package &&
danw@137	3073	(trans->packages[p].state == RAZOR_PACKAGE_INSTALL_UNAVAILABLE \|\|
danw@137	3074	trans->packages[p].state == RAZOR_PACKAGE_REMOVE_NOT_INSTALLED))
danw@137	3075	free((char *)trans->packages[p].name);
danw@137	3076	}
danw@137	3077	free(trans);
danw@137	3078
danw@137	3079	/* FIXME: free upstream if it was created as an empty set */
danw@137	3080	}

author	Dan Winship <danw@gnome.org>
	Fri Mar 07 13:45:37 2008 -0500 (2008-03-07)
changeset 156	5197b8e64e42
parent 154	229fb0caa092
child 159	9307d0e0b44f
permissions	-rw-r--r--