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

author	Dan Winship <danw@gnome.org>
	Tue Mar 04 10:55:01 2008 -0500 (2008-03-04)
changeset 143	59a9513fac54
parent 142	4819c228434c
child 144	56c487a56fa2
permissions	-rw-r--r--