razor: razor.c@26edeea5c95a (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@61	36	#define RAZOR_ENTRY_LAST 0x80000000ul
krh@61	37	#define RAZOR_IMMEDIATE 0x80000000ul
krh@61	38	#define RAZOR_ENTRY_MASK 0x00fffffful
krh@61	39
krh@66	40	#define RAZOR_STRING_POOL 0
krh@66	41	#define RAZOR_PACKAGES 1
krh@66	42	#define RAZOR_PROPERTIES 2
krh@66	43	#define RAZOR_FILES 3
krh@66	44	#define RAZOR_PACKAGE_POOL 4
krh@66	45	#define RAZOR_PROPERTY_POOL 5
krh@66	46	#define RAZOR_FILE_POOL 6
krh@30	47
krh@30	48	struct razor_package {
danw@108	49	uint32_t name;
danw@108	50	uint32_t version;
danw@108	51	uint32_t properties;
danw@108	52	uint32_t files;
krh@30	53	};
krh@30	54
krh@30	55	struct razor_property {
danw@108	56	uint32_t name;
danw@109	57	uint32_t relation;
danw@108	58	uint32_t version;
danw@108	59	uint32_t packages;
krh@30	60	};
krh@30	61
krh@48	62	struct razor_entry {
danw@108	63	uint32_t name;
danw@108	64	uint32_t start;
danw@108	65	uint32_t packages;
krh@48	66	};
krh@48	67
krh@30	68	struct razor_set {
krh@30	69	struct array string_pool;
krh@30	70	struct array packages;
krh@66	71	struct array properties;
krh@56	72	struct array files;
krh@56	73	struct array package_pool;
krh@66	74	struct array property_pool;
krh@56	75	struct array file_pool;
krh@30	76	struct razor_set_header *header;
krh@30	77	};
krh@30	78
krh@52	79	struct import_entry {
danw@108	80	uint32_t package;
krh@52	81	char *name;
krh@52	82	};
krh@52	83
krh@52	84	struct import_directory {
danw@108	85	uint32_t name, count;
krh@52	86	struct array files;
krh@52	87	struct array packages;
krh@52	88	struct import_directory *last;
krh@52	89	};
krh@52	90
krh@30	91	struct razor_importer {
krh@30	92	struct razor_set *set;
krh@78	93	struct hashtable table;
krh@30	94	struct razor_package *package;
krh@66	95	struct array properties;
krh@48	96	struct array files;
krh@30	97	};
krh@30	98
krh@0	99	static void *
krh@0	100	zalloc(size_t size)
krh@0	101	{
krh@0	102	void *p;
krh@0	103
krh@0	104	p = malloc(size);
krh@0	105	memset(p, 0, size);
krh@0	106
krh@0	107	return p;
krh@0	108	}
krh@0	109
krh@19	110	struct razor_set_section razor_sections[] = {
krh@56	111	{ RAZOR_STRING_POOL, offsetof(struct razor_set, string_pool) },
krh@19	112	{ RAZOR_PACKAGES, offsetof(struct razor_set, packages) },
krh@66	113	{ RAZOR_PROPERTIES, offsetof(struct razor_set, properties) },
krh@56	114	{ RAZOR_FILES, offsetof(struct razor_set, files) },
krh@39	115	{ RAZOR_PACKAGE_POOL, offsetof(struct razor_set, package_pool) },
krh@66	116	{ RAZOR_PROPERTY_POOL, offsetof(struct razor_set, property_pool) },
krh@56	117	{ RAZOR_FILE_POOL, offsetof(struct razor_set, file_pool) },
krh@19	118	};
krh@19	119
krh@4	120	struct razor_set *
krh@4	121	razor_set_create(void)
krh@0	122	{
krh@18	123	return zalloc(sizeof(struct razor_set));
krh@0	124	}
krh@0	125
krh@4	126	struct razor_set *
krh@4	127	razor_set_open(const char *filename)
krh@0	128	{
krh@4	129	struct razor_set *set;
krh@19	130	struct razor_set_section *s;
krh@0	131	struct stat stat;
krh@19	132	struct array *array;
krh@19	133	int fd;
krh@0	134
krh@4	135	set = zalloc(sizeof *set);
krh@0	136	fd = open(filename, O_RDONLY);
krh@0	137	if (fstat(fd, &stat) < 0)
krh@0	138	return NULL;
krh@4	139	set->header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
krh@4	140	if (set->header == MAP_FAILED) {
krh@4	141	free(set);
krh@0	142	return NULL;
krh@0	143	}
krh@0	144
krh@19	145	for (s = set->header->sections; ~s->type; s++) {
krh@19	146	if (s->type >= ARRAY_SIZE(razor_sections))
krh@19	147	continue;
krh@19	148	if (s->type != razor_sections[s->type].type)
krh@19	149	continue;
krh@19	150	array = (void *) set + razor_sections[s->type].offset;
krh@19	151	array->data = (void *) set->header + s->offset;
krh@19	152	array->size = s->size;
krh@19	153	array->alloc = s->size;
krh@0	154	}
krh@0	155	close(fd);
krh@0	156
krh@4	157	return set;
krh@0	158	}
krh@0	159
krh@0	160	void
krh@4	161	razor_set_destroy(struct razor_set *set)
krh@0	162	{
krh@0	163	unsigned int size;
krh@19	164	struct array *a;
krh@0	165	int i;
krh@0	166
krh@4	167	if (set->header) {
krh@4	168	for (i = 0; set->header->sections[i].type; i++)
krh@0	169	;
krh@4	170	size = set->header->sections[i].type;
krh@4	171	munmap(set->header, size);
krh@0	172	} else {
krh@19	173	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
krh@19	174	a = (void *) set + razor_sections[i].offset;
krh@19	175	free(a->data);
krh@19	176	}
krh@0	177	}
krh@0	178
krh@4	179	free(set);
krh@0	180	}
krh@0	181
krh@43	182	int
krh@4	183	razor_set_write(struct razor_set set, const char filename)
krh@0	184	{
krh@0	185	char data[4096];
krh@4	186	struct razor_set_header header = (struct razor_set_header ) data;
krh@19	187	struct array *a;
danw@108	188	uint32_t offset;
krh@17	189	int i, fd;
krh@0	190
krh@0	191	memset(data, 0, sizeof data);
krh@4	192	header->magic = RAZOR_MAGIC;
krh@4	193	header->version = RAZOR_VERSION;
krh@17	194	offset = sizeof data;
krh@0	195
krh@19	196	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
krh@19	197	if (razor_sections[i].type != i)
krh@19	198	continue;
krh@19	199	a = (void *) set + razor_sections[i].offset;
krh@19	200	header->sections[i].type = i;
krh@17	201	header->sections[i].offset = offset;
krh@19	202	header->sections[i].size = a->size;
krh@91	203	offset += ALIGN(a->size, 4096);
krh@17	204	}
krh@0	205
krh@19	206	header->sections[i].type = ~0;
krh@17	207	header->sections[i].offset = 0;
krh@17	208	header->sections[i].size = 0;
krh@10	209
krh@0	210	fd = open(filename, O_CREAT \| O_WRONLY \| O_TRUNC, 0666);
krh@0	211	if (fd < 0)
krh@0	212	return -1;
krh@0	213
krh@91	214	razor_write(fd, data, sizeof data);
danw@113	215	memset(data, 0, sizeof data);
krh@19	216	for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
krh@19	217	if (razor_sections[i].type != i)
krh@19	218	continue;
krh@19	219	a = (void *) set + razor_sections[i].offset;
danw@113	220	razor_write(fd, a->data, a->size);
danw@113	221	razor_write(fd, data, ALIGN(a->size, 4096) - a->size);
krh@19	222	}
krh@17	223
krh@17	224	close(fd);
krh@0	225
krh@0	226	return 0;
krh@0	227	}
krh@0	228
danw@108	229	static uint32_t
krh@39	230	add_to_property_pool(struct array pool, struct array properties)
krh@10	231	{
danw@108	232	uint32_t *p;
krh@92	233
krh@92	234	if (properties->size == 0)
krh@92	235	return ~0;
krh@92	236	else if (properties->size == sizeof *p)
danw@108	237	return (uint32_t ) properties->data \| RAZOR_IMMEDIATE;
krh@10	238
krh@39	239	p = array_add(pool, properties->size);
krh@10	240	memcpy(p, properties->data, properties->size);
danw@114	241	p[properties->size / sizeof *p - 1] \|= RAZOR_ENTRY_LAST;
krh@10	242
danw@108	243	return p - (uint32_t *) pool->data;
krh@10	244	}
krh@10	245
krh@27	246	void
krh@30	247	razor_importer_begin_package(struct razor_importer *importer,
krh@30	248	const char name, const char version)
krh@13	249	{
krh@25	250	struct razor_package *p;
krh@13	251
krh@30	252	p = array_add(&importer->set->packages, sizeof *p);
krh@95	253	p->name = hashtable_tokenize(&importer->table, name);
krh@95	254	p->version = hashtable_tokenize(&importer->table, version);
krh@13	255
krh@30	256	importer->package = p;
krh@66	257	array_init(&importer->properties);
krh@13	258	}
krh@13	259
krh@13	260	void
krh@30	261	razor_importer_finish_package(struct razor_importer *importer)
krh@13	262	{
danw@114	263	importer->package->properties =
danw@114	264	add_to_property_pool(&importer->set->property_pool,
danw@114	265	&importer->properties);
krh@13	266
krh@66	267	array_release(&importer->properties);
krh@13	268	}
krh@13	269
krh@66	270	void
krh@30	271	razor_importer_add_property(struct razor_importer *importer,
danw@109	272	const char *name,
danw@109	273	enum razor_version_relation relation,
danw@109	274	const char *version,
krh@66	275	enum razor_property_type type)
krh@13	276	{
krh@25	277	struct razor_property *p;
danw@108	278	uint32_t *r;
krh@13	279
krh@66	280	p = array_add(&importer->set->properties, sizeof *p);
krh@95	281	p->name = hashtable_tokenize(&importer->table, name) \| (type << 30);
danw@109	282	p->relation = relation;
krh@95	283	p->version = hashtable_tokenize(&importer->table, version);
krh@30	284	p->packages = importer->package -
krh@30	285	(struct razor_package *) importer->set->packages.data;
krh@13	286
krh@66	287	r = array_add(&importer->properties, sizeof *r);
krh@66	288	r = p - (struct razor_property ) importer->set->properties.data;
krh@30	289	}
krh@30	290
krh@46	291	void
krh@46	292	razor_importer_add_file(struct razor_importer importer, const char name)
krh@46	293	{
krh@52	294	struct import_entry *e;
krh@48	295
krh@52	296	e = array_add(&importer->files, sizeof *e);
krh@52	297
krh@52	298	e->package = importer->package -
krh@52	299	(struct razor_package *) importer->set->packages.data;
krh@52	300	e->name = strdup(name);
krh@46	301	}
krh@46	302
krh@30	303	struct razor_importer *
krh@30	304	razor_importer_new(void)
krh@30	305	{
krh@30	306	struct razor_importer *importer;
krh@30	307
krh@30	308	importer = zalloc(sizeof *importer);
krh@30	309	importer->set = razor_set_create();
krh@78	310	hashtable_init(&importer->table, &importer->set->string_pool);
krh@30	311
krh@30	312	return importer;
krh@9	313	}
krh@9	314
krh@75	315	/* Destroy an importer without creating the set. */
krh@75	316	void
krh@75	317	razor_importer_destroy(struct razor_importer *importer)
krh@75	318	{
krh@75	319	/* FIXME: write this */
krh@75	320	}
krh@75	321
krh@75	322
krh@22	323	typedef int (compare_with_data_func_t)(const void p1,
krh@22	324	const void *p,
krh@22	325	void *data);
krh@22	326
krh@25	327	struct qsort_context {
krh@25	328	size_t size;
krh@25	329	compare_with_data_func_t compare;
krh@25	330	void *data;
krh@25	331	};
krh@25	332
krh@22	333	static void
krh@22	334	qsort_swap(void p1, void p2, size_t size)
krh@22	335	{
krh@22	336	char buffer[size];
krh@22	337
krh@22	338	memcpy(buffer, p1, size);
krh@22	339	memcpy(p1, p2, size);
krh@22	340	memcpy(p2, buffer, size);
krh@22	341	}
krh@22	342
krh@25	343	static void
danw@108	344	__qsort_with_data(void base, size_t nelem, uint32_t map,
krh@25	345	struct qsort_context *ctx)
krh@22	346	{
krh@22	347	void p, start, end, pivot;
danw@108	348	uint32_t mp, mstart, *mend, tmp;
krh@22	349	int left, right, result;
krh@25	350	size_t size = ctx->size;
krh@22	351
krh@22	352	p = base;
krh@22	353	start = base;
krh@22	354	end = base + nelem * size;
krh@25	355	mp = map;
krh@25	356	mstart = map;
krh@25	357	mend = map + nelem;
krh@22	358	pivot = base + (random() % nelem) * size;
krh@25	359
krh@22	360	while (p < end) {
krh@25	361	result = ctx->compare(p, pivot, ctx->data);
krh@22	362	if (result < 0) {
krh@22	363	qsort_swap(p, start, size);
krh@25	364	tmp = *mp;
krh@25	365	mp = mstart;
krh@25	366	*mstart = tmp;
krh@22	367	if (start == pivot)
krh@22	368	pivot = p;
krh@22	369	start += size;
krh@25	370	mstart++;
krh@22	371	p += size;
krh@29	372	mp++;
krh@22	373	} else if (result == 0) {
krh@22	374	p += size;
krh@25	375	mp++;
krh@22	376	} else {
krh@22	377	end -= size;
krh@25	378	mend--;
krh@22	379	qsort_swap(p, end, size);
krh@25	380	tmp = *mp;
krh@29	381	mp = mend;
krh@29	382	*mend = tmp;
krh@22	383	if (end == pivot)
krh@22	384	pivot = p;
krh@22	385	}
krh@22	386	}
krh@22	387
krh@22	388	left = (start - base) / size;
krh@22	389	right = (base + nelem * size - end) / size;
krh@22	390	if (left > 1)
krh@25	391	__qsort_with_data(base, left, map, ctx);
krh@22	392	if (right > 1)
krh@25	393	__qsort_with_data(end, right, mend, ctx);
krh@25	394	}
krh@25	395
danw@108	396	uint32_t *
krh@25	397	qsort_with_data(void *base, size_t nelem, size_t size,
krh@25	398	compare_with_data_func_t compare, void *data)
krh@25	399	{
krh@25	400	struct qsort_context ctx;
danw@108	401	uint32_t *map;
krh@25	402	int i;
krh@25	403
krh@75	404	if (nelem == 0)
krh@75	405	return NULL;
krh@75	406
krh@25	407	ctx.size = size;
krh@25	408	ctx.compare = compare;
krh@25	409	ctx.data = data;
krh@25	410
danw@108	411	map = malloc(nelem * sizeof (uint32_t));
krh@25	412	for (i = 0; i < nelem; i++)
krh@25	413	map[i] = i;
krh@25	414
krh@25	415	__qsort_with_data(base, nelem, map, &ctx);
krh@25	416
krh@25	417	return map;
krh@22	418	}
krh@9	419
krh@9	420	static int
krh@35	421	versioncmp(const char s1, const char s2)
krh@35	422	{
krh@35	423	const char p1, p2;
krh@35	424	long n1, n2;
krh@35	425	int res;
krh@35	426
krh@35	427	n1 = strtol(s1, (char **) &p1, 0);
krh@35	428	n2 = strtol(s2, (char **) &p2, 0);
krh@35	429
krh@35	430	/* Epoch; if one but not the other has an epoch set, default
krh@35	431	* the epoch-less version to 0. */
krh@35	432	res = (p1 == ':') - (p2 == ':');
krh@35	433	if (res < 0) {
krh@35	434	n1 = 0;
krh@35	435	p1 = s1;
krh@35	436	p2++;
krh@35	437	} else if (res > 0) {
krh@35	438	p1++;
krh@35	439	n2 = 0;
krh@35	440	p2 = s2;
krh@35	441	}
krh@35	442
krh@35	443	if (n1 != n2)
krh@35	444	return n1 - n2;
krh@35	445	while (p1 && p2) {
krh@35	446	if (p1 != p2)
krh@35	447	return p1 - p2;
krh@35	448	p1++;
krh@35	449	p2++;
krh@35	450	if (isdigit(p1) && isdigit(p2))
krh@35	451	return versioncmp(p1, p2);
krh@35	452	}
krh@35	453
krh@35	454	return p1 - p2;
krh@35	455	}
krh@35	456
krh@35	457	static int
krh@22	458	compare_packages(const void p1, const void p2, void *data)
krh@9	459	{
krh@25	460	const struct razor_package pkg1 = p1, pkg2 = p2;
krh@22	461	struct razor_set *set = data;
krh@22	462	char *pool = set->string_pool.data;
krh@9	463
krh@23	464	if (pkg1->name == pkg2->name)
krh@35	465	return versioncmp(&pool[pkg1->version], &pool[pkg2->version]);
krh@23	466	else
krh@23	467	return strcmp(&pool[pkg1->name], &pool[pkg2->name]);
krh@9	468	}
krh@9	469
krh@9	470	static int
krh@22	471	compare_properties(const void p1, const void p2, void *data)
krh@9	472	{
krh@25	473	const struct razor_property prop1 = p1, prop2 = p2;
krh@22	474	struct razor_set *set = data;
krh@22	475	char *pool = set->string_pool.data;
krh@9	476
danw@109	477	if (prop1->name == prop2->name) {
danw@109	478	if (prop1->relation == prop2->relation)
danw@109	479	return versioncmp(&pool[prop1->version],
danw@109	480	&pool[prop2->version]);
danw@109	481	else
danw@109	482	return prop1->relation - prop2->relation;
danw@109	483	} else if ((prop1->name & RAZOR_ENTRY_MASK) == (prop2->name & RAZOR_ENTRY_MASK))
krh@66	484	return (prop1->name >> 30) - (prop2->name >> 30);
krh@12	485	else
krh@66	486	return strcmp(&pool[prop1->name & RAZOR_ENTRY_MASK],
krh@66	487	&pool[prop2->name & RAZOR_ENTRY_MASK]);
krh@9	488	}
krh@9	489
danw@108	490	static uint32_t *
krh@66	491	uniqueify_properties(struct razor_set *set)
krh@9	492	{
krh@25	493	struct razor_property rp, up, *rp_end;
krh@18	494	struct array pkgs, p;
danw@108	495	uint32_t map, rmap, *r;
krh@18	496	int i, count, unique;
krh@9	497
krh@66	498	count = set->properties.size / sizeof(struct razor_property);
krh@66	499	map = qsort_with_data(set->properties.data,
krh@25	500	count,
krh@25	501	sizeof(struct razor_property),
krh@25	502	compare_properties,
krh@25	503	set);
krh@9	504
krh@66	505	rp_end = set->properties.data + set->properties.size;
krh@25	506	rmap = malloc(count * sizeof *map);
krh@25	507	pkgs = zalloc(count * sizeof *pkgs);
krh@66	508	for (rp = set->properties.data, up = rp, i = 0; rp < rp_end; rp++, i++) {
danw@109	509	if (rp->name != up->name \|\| rp->relation != up->relation \|\|
danw@109	510	rp->version != up->version) {
krh@25	511	up++;
krh@25	512	up->name = rp->name;
danw@109	513	up->relation = rp->relation;
krh@25	514	up->version = rp->version;
krh@10	515	}
krh@25	516
krh@66	517	unique = up - (struct razor_property *) set->properties.data;
krh@25	518	rmap[map[i]] = unique;
krh@25	519	r = array_add(&pkgs[unique], sizeof *r);
krh@25	520	*r = rp->packages;
krh@10	521	}
krh@25	522	free(map);
krh@9	523
krh@25	524	up++;
krh@66	525	set->properties.size = (void *) up - set->properties.data;
krh@25	526	rp_end = up;
krh@66	527	for (rp = set->properties.data, p = pkgs; rp < rp_end; rp++, p++) {
danw@114	528	rp->packages =
danw@114	529	add_to_property_pool(&set->package_pool, p);
krh@25	530	array_release(p);
krh@18	531	}
krh@18	532
krh@18	533	free(pkgs);
krh@18	534
krh@25	535	return rmap;
krh@10	536	}
krh@10	537
krh@10	538	static void
danw@108	539	remap_links(struct array links, uint32_t map)
krh@10	540	{
danw@108	541	uint32_t p, end;
krh@10	542
krh@39	543	end = links->data + links->size;
krh@39	544	for (p = links->data; p < end; p++)
krh@64	545	p = map[p & RAZOR_ENTRY_MASK] \| (*p & ~RAZOR_ENTRY_MASK);
krh@9	546	}
krh@9	547
krh@48	548	static int
krh@48	549	compare_filenames(const void p1, const void p2, void *data)
krh@48	550	{
krh@52	551	const struct import_entry *e1 = p1;
krh@52	552	const struct import_entry *e2 = p2;
krh@48	553
krh@52	554	return strcmp(e1->name, e2->name);
krh@48	555	}
krh@48	556
krh@48	557	static void
krh@52	558	count_entries(struct import_directory *d)
krh@48	559	{
krh@52	560	struct import_directory p, end;
krh@48	561
krh@48	562	p = d->files.data;
krh@48	563	end = d->files.data + d->files.size;
krh@48	564	d->count = 0;
krh@48	565	while (p < end) {
krh@48	566	count_entries(p);
krh@48	567	d->count += p->count + 1;
krh@48	568	p++;
krh@48	569	}
krh@48	570	}
krh@48	571
krh@48	572	static void
krh@52	573	serialize_files(struct razor_set *set,
krh@52	574	struct import_directory d, struct array array)
krh@48	575	{
krh@52	576	struct import_directory p, end;
krh@56	577	struct razor_entry *e = NULL;
danw@114	578	uint32_t s;
krh@48	579
krh@48	580	p = d->files.data;
krh@48	581	end = d->files.data + d->files.size;
krh@48	582	s = array->size / sizeof e + d->files.size / sizeof p;
krh@48	583	while (p < end) {
krh@48	584	e = array_add(array, sizeof *e);
krh@48	585	e->name = p->name;
krh@56	586	e->start = p->count > 0 ? s : 0;
krh@48	587	s += p->count;
krh@60	588
danw@114	589	e->packages = add_to_property_pool(&set->package_pool,
danw@114	590	&p->packages);
krh@52	591	array_release(&p->packages);
krh@48	592	p++;
krh@48	593	}
krh@56	594	if (e != NULL)
krh@56	595	e->name \|= RAZOR_ENTRY_LAST;
krh@48	596
krh@48	597	p = d->files.data;
krh@48	598	end = d->files.data + d->files.size;
krh@48	599	while (p < end) {
krh@52	600	serialize_files(set, p, array);
krh@48	601	p++;
krh@48	602	}
krh@48	603	}
krh@48	604
krh@48	605	static void
danw@108	606	remap_property_package_links(struct array properties, uint32_t rmap)
krh@61	607	{
krh@61	608	struct razor_property p, end;
krh@61	609
krh@61	610	end = properties->data + properties->size;
krh@61	611	for (p = properties->data; p < end; p++)
krh@61	612	if (p->packages & RAZOR_IMMEDIATE)
krh@61	613	p->packages = rmap[p->packages & RAZOR_ENTRY_MASK] \|
krh@61	614	RAZOR_IMMEDIATE;
krh@61	615	}
krh@61	616
krh@61	617	static void
krh@48	618	build_file_tree(struct razor_importer *importer)
krh@48	619	{
krh@48	620	int count, i, length;
krh@52	621	struct import_entry *filenames;
krh@52	622	char f, end;
danw@108	623	uint32_t name, *r;
krh@48	624	char dirname[256];
krh@52	625	struct import_directory *d, root;
krh@48	626	struct razor_entry *e;
krh@48	627
krh@52	628	count = importer->files.size / sizeof (struct import_entry);
krh@48	629	qsort_with_data(importer->files.data,
krh@48	630	count,
krh@52	631	sizeof (struct import_entry),
krh@48	632	compare_filenames,
krh@48	633	NULL);
krh@48	634
krh@95	635	root.name = hashtable_tokenize(&importer->table, "");
krh@48	636	array_init(&root.files);
krh@52	637	array_init(&root.packages);
krh@48	638	root.last = NULL;
krh@48	639
krh@48	640	filenames = importer->files.data;
krh@48	641	for (i = 0; i < count; i++) {
krh@52	642	f = filenames[i].name;
krh@48	643	if (*f != '/')
krh@48	644	continue;
krh@57	645	f++;
krh@48	646
krh@48	647	d = &root;
krh@48	648	while (*f) {
krh@57	649	end = strchr(f, '/');
krh@48	650	if (end == NULL)
krh@48	651	end = f + strlen(f);
krh@57	652	length = end - f;
krh@57	653	memcpy(dirname, f, length);
krh@48	654	dirname[length] ='\0';
krh@95	655	name = hashtable_tokenize(&importer->table, dirname);
krh@48	656	if (d->last == NULL \|\| d->last->name != name) {
krh@48	657	d->last = array_add(&d->files, sizeof *d);
krh@48	658	d->last->name = name;
krh@48	659	d->last->last = NULL;
krh@48	660	array_init(&d->last->files);
krh@52	661	array_init(&d->last->packages);
krh@48	662	}
krh@48	663	d = d->last;
krh@57	664	f = end + 1;
krh@57	665	if (*end == '\0')
krh@57	666	break;
krh@48	667	}
krh@48	668
krh@52	669	r = array_add(&d->packages, sizeof *r);
krh@52	670	*r = filenames[i].package;
krh@52	671	free(filenames[i].name);
krh@48	672	}
krh@48	673
krh@48	674	count_entries(&root);
krh@56	675	array_init(&importer->set->files);
krh@48	676
krh@56	677	e = array_add(&importer->set->files, sizeof *e);
krh@56	678	e->name = root.name \| RAZOR_ENTRY_LAST;
krh@48	679	e->start = 1;
krh@92	680	e->packages = ~0;
krh@48	681
krh@56	682	serialize_files(importer->set, &root, &importer->set->files);
krh@48	683
krh@48	684	array_release(&importer->files);
krh@48	685	}
krh@48	686
krh@56	687	static void
danw@108	688	build_package_file_lists(struct razor_set set, uint32_t rmap)
krh@54	689	{
krh@56	690	struct razor_package p, packages;
krh@56	691	struct array *pkgs;
krh@54	692	struct razor_entry e, end;
danw@108	693	uint32_t r, q;
krh@56	694	int i, count;
krh@54	695
krh@56	696	count = set->packages.size / sizeof *p;
krh@56	697	pkgs = zalloc(count * sizeof *pkgs);
krh@54	698
krh@56	699	end = set->files.data + set->files.size;
krh@92	700	for (e = set->files.data; e < end; e++) {
krh@92	701	if (e->packages == ~0) {
krh@92	702	continue;
krh@92	703	} else if (e->packages & RAZOR_IMMEDIATE) {
krh@60	704	e->packages = rmap[e->packages & RAZOR_ENTRY_MASK] \|
krh@60	705	RAZOR_IMMEDIATE;
krh@60	706	r = &e->packages;
krh@60	707	} else {
danw@108	708	r = (uint32_t *) set->package_pool.data + e->packages;
krh@60	709	}
krh@60	710
krh@64	711	while (1) {
krh@60	712	q = array_add(&pkgs[r & RAZOR_ENTRY_MASK], sizeof q);
krh@56	713	q = e - (struct razor_entry ) set->files.data;
krh@60	714	if (*r++ & RAZOR_IMMEDIATE)
krh@60	715	break;
krh@54	716	}
krh@54	717	}
krh@54	718
krh@56	719	packages = set->packages.data;
krh@56	720	for (i = 0; i < count; i++) {
krh@56	721	packages[i].files =
krh@56	722	add_to_property_pool(&set->file_pool, &pkgs[i]);
krh@56	723	array_release(&pkgs[i]);
krh@48	724	}
krh@56	725	free(pkgs);
krh@52	726	}
krh@52	727
krh@27	728	struct razor_set *
krh@30	729	razor_importer_finish(struct razor_importer *importer)
krh@9	730	{
krh@30	731	struct razor_set *set;
danw@108	732	uint32_t map, rmap;
krh@39	733	int i, count;
krh@18	734
krh@66	735	map = uniqueify_properties(importer->set);
krh@66	736	remap_links(&importer->set->property_pool, map);
krh@39	737	free(map);
krh@25	738
krh@30	739	count = importer->set->packages.size / sizeof(struct razor_package);
krh@30	740	map = qsort_with_data(importer->set->packages.data,
krh@25	741	count,
krh@25	742	sizeof(struct razor_package),
krh@25	743	compare_packages,
krh@30	744	importer->set);
krh@39	745
krh@39	746	rmap = malloc(count * sizeof *rmap);
krh@39	747	for (i = 0; i < count; i++)
krh@39	748	rmap[map[i]] = i;
krh@25	749	free(map);
krh@13	750
krh@48	751	build_file_tree(importer);
krh@52	752	remap_links(&importer->set->package_pool, rmap);
krh@60	753	build_package_file_lists(importer->set, rmap);
krh@66	754	remap_property_package_links(&importer->set->properties, rmap);
krh@52	755	free(rmap);
krh@48	756
krh@30	757	set = importer->set;
krh@78	758	hashtable_release(&importer->table);
krh@30	759	free(importer);
krh@30	760
krh@30	761	return set;
krh@9	762	}
krh@9	763
krh@92	764	struct razor_package_iterator {
krh@92	765	struct razor_set *set;
krh@92	766	struct razor_package package, end;
danw@108	767	uint32_t *index;
krh@101	768	int last;
krh@92	769	};
krh@92	770
krh@92	771	struct razor_package_iterator *
krh@101	772	razor_package_iterator_create_with_index(struct razor_set *set,
danw@108	773	uint32_t *index)
krh@3	774	{
krh@92	775	struct razor_package_iterator *pi;
krh@92	776
krh@92	777	pi = zalloc(sizeof *pi);
krh@92	778	pi->set = set;
krh@101	779	pi->end = set->packages.data + set->packages.size;
krh@92	780	pi->package = set->packages.data;
krh@101	781	pi->index = index;
krh@92	782
krh@92	783	return pi;
krh@92	784	}
krh@92	785
krh@101	786	struct razor_package_iterator *
krh@101	787	razor_package_iterator_create(struct razor_set *set)
krh@101	788	{
krh@101	789	return razor_package_iterator_create_with_index(set, NULL);
krh@101	790	}
krh@101	791
krh@101	792	struct razor_package_iterator *
krh@101	793	razor_package_iterator_create_for_property(struct razor_set *set,
krh@101	794	struct razor_property *property)
krh@101	795	{
danw@108	796	uint32_t *index;
krh@101	797
krh@101	798	if (property->packages & RAZOR_IMMEDIATE)
krh@101	799	index = &property->packages;
krh@101	800	else
danw@108	801	index = (uint32_t *)
krh@101	802	set->package_pool.data + property->packages;
krh@101	803
krh@101	804	return razor_package_iterator_create_with_index(set, index);
krh@101	805	}
krh@101	806
krh@92	807	int
krh@92	808	razor_package_iterator_next(struct razor_package_iterator *pi,
krh@92	809	struct razor_package **package,
krh@92	810	const char name, const char version)
krh@92	811	{
krh@6	812	char *pool;
krh@101	813	int valid;
krh@101	814	struct razor_package p, packages;
krh@3	815
krh@101	816	if (pi->index) {
krh@101	817	packages = pi->set->packages.data;
krh@101	818	p = &packages[*pi->index & RAZOR_ENTRY_MASK];
krh@101	819	valid = !pi->last;
krh@101	820	pi->last = (*pi->index++ & RAZOR_IMMEDIATE) != 0;
krh@101	821	} else {
krh@101	822	p = pi->package++;
krh@101	823	valid = p < pi->end;
krh@101	824	}
krh@92	825
krh@101	826	if (valid) {
krh@101	827	pool = pi->set->string_pool.data;
krh@101	828	*package = p;
krh@101	829	*name = &pool[p->name & RAZOR_ENTRY_MASK];
krh@101	830	*version = &pool[p->version];
krh@101	831	} else {
krh@101	832	*package = NULL;
krh@101	833	}
krh@101	834
krh@101	835	return valid;
krh@92	836	}
krh@92	837
krh@92	838	void
krh@92	839	razor_package_iterator_destroy(struct razor_package_iterator *pi)
krh@92	840	{
krh@92	841	free(pi);
krh@3	842	}
krh@3	843
krh@10	844	struct razor_package *
krh@10	845	razor_set_get_package(struct razor_set set, const char package)
krh@10	846	{
krh@97	847	struct razor_package_iterator *pi;
krh@97	848	struct razor_package *p;
krh@97	849	const char name, version;
krh@97	850
krh@97	851	pi = razor_package_iterator_create(set);
krh@97	852	while (razor_package_iterator_next(pi, &p, &name, &version)) {
krh@97	853	if (strcmp(package, name) == 0)
krh@97	854	break;
krh@97	855	}
krh@97	856	razor_package_iterator_destroy(pi);
krh@97	857
krh@97	858	return p;
krh@10	859	}
krh@10	860
krh@92	861	struct razor_property_iterator {
krh@92	862	struct razor_set *set;
krh@92	863	struct razor_property property, end;
danw@108	864	uint32_t *index;
krh@92	865	int last;
krh@92	866	};
krh@92	867
krh@92	868	struct razor_property_iterator *
krh@92	869	razor_property_iterator_create(struct razor_set *set,
krh@92	870	struct razor_package *package)
krh@92	871	{
krh@92	872	struct razor_property_iterator *pi;
krh@92	873
krh@92	874	pi = zalloc(sizeof *pi);
krh@92	875	pi->set = set;
krh@92	876	pi->end = set->properties.data + set->properties.size;
krh@101	877	pi->property = set->properties.data;
krh@98	878
krh@98	879	if (package)
danw@108	880	pi->index = (uint32_t *)
krh@92	881	set->property_pool.data + package->properties;
krh@92	882
krh@92	883	return pi;
krh@92	884	}
krh@92	885
krh@92	886	int
krh@92	887	razor_property_iterator_next(struct razor_property_iterator *pi,
krh@92	888	struct razor_property **property,
danw@109	889	const char **name,
danw@109	890	enum razor_version_relation *relation,
danw@109	891	const char **version,
krh@92	892	enum razor_property_type *type)
krh@92	893	{
krh@92	894	char *pool;
krh@92	895	int valid;
krh@92	896	struct razor_property p, properties;
krh@92	897
krh@92	898	if (pi->index) {
krh@92	899	properties = pi->set->properties.data;
krh@92	900	p = &properties[*pi->index & RAZOR_ENTRY_MASK];
krh@92	901	valid = !pi->last;
krh@92	902	pi->last = (*pi->index++ & RAZOR_IMMEDIATE) != 0;
krh@92	903	} else {
krh@92	904	p = pi->property++;
krh@92	905	valid = p < pi->end;
krh@92	906	}
krh@92	907
krh@96	908	if (valid) {
krh@96	909	pool = pi->set->string_pool.data;
krh@96	910	*property = p;
krh@96	911	*name = &pool[p->name & RAZOR_ENTRY_MASK];
danw@109	912	*relation = p->relation;
krh@96	913	*version = &pool[p->version];
krh@96	914	*type = p->name >> 30;
krh@96	915	} else {
krh@96	916	*property = NULL;
krh@96	917	}
krh@92	918
krh@92	919	return valid;
krh@92	920	}
krh@92	921
krh@66	922	void
krh@92	923	razor_property_iterator_destroy(struct razor_property_iterator *pi)
krh@8	924	{
krh@92	925	free(pi);
krh@10	926	}
krh@10	927
krh@56	928	static struct razor_entry *
krh@56	929	find_entry(struct razor_set set, struct razor_entry dir, const char *pattern)
krh@56	930	{
krh@56	931	struct razor_entry *e;
krh@56	932	const char n, pool = set->string_pool.data;
krh@56	933	int len;
krh@56	934
krh@56	935	e = (struct razor_entry *) set->files.data + dir->start;
krh@56	936	do {
krh@56	937	n = pool + (e->name & RAZOR_ENTRY_MASK);
krh@56	938	if (strcmp(pattern + 1, n) == 0)
krh@56	939	return e;
krh@57	940	len = strlen(n);
krh@56	941	if (e->start != 0 && strncmp(pattern + 1, n, len) == 0 &&
krh@56	942	pattern[len + 1] == '/') {
krh@56	943	return find_entry(set, e, pattern + len + 1);
krh@56	944	}
krh@56	945	} while (((e++)->name & RAZOR_ENTRY_LAST) == 0);
krh@56	946
krh@56	947	return NULL;
krh@56	948	}
krh@56	949
krh@56	950	static void
krh@56	951	list_dir(struct razor_set set, struct razor_entry dir,
krh@56	952	const char prefix, const char pattern)
krh@56	953	{
krh@56	954	struct razor_entry *e;
krh@56	955	const char n, pool = set->string_pool.data;
krh@56	956
krh@56	957	e = (struct razor_entry *) set->files.data + dir->start;
krh@56	958	do {
krh@56	959	n = pool + (e->name & RAZOR_ENTRY_MASK);
krh@56	960	if (pattern && pattern[0] && fnmatch(pattern, n, 0) != 0)
krh@56	961	continue;
krh@56	962	printf("%s/%s%s\n", prefix, n, e->start > 0 ? "/" : "");
krh@56	963	} while (((e++)->name & RAZOR_ENTRY_LAST) == 0);
krh@56	964	}
krh@56	965
krh@56	966	void
krh@56	967	razor_set_list_files(struct razor_set set, const char pattern)
krh@56	968	{
krh@56	969	struct razor_entry *e;
krh@56	970	char buffer[512], p, base;
krh@56	971
krh@56	972	if (pattern == NULL)
krh@56	973	pattern = "/";
krh@56	974
krh@56	975	strcpy(buffer, pattern);
krh@56	976	e = find_entry(set, set->files.data, buffer);
krh@56	977	if (e && e->start > 0) {
krh@56	978	base = NULL;
krh@56	979	} else {
krh@56	980	p = strrchr(buffer, '/');
krh@56	981	if (p) {
krh@56	982	*p = '\0';
krh@56	983	base = p + 1;
krh@56	984	} else {
krh@56	985	base = NULL;
krh@56	986	}
krh@56	987	}
krh@56	988	e = find_entry(set, set->files.data, buffer);
krh@56	989	if (e->start != 0)
krh@56	990	list_dir(set, e, buffer, base);
krh@56	991	}
krh@56	992
krh@102	993	struct razor_package_iterator *
krh@102	994	razor_package_iterator_create_for_file(struct razor_set *set,
krh@102	995	const char *filename)
krh@56	996	{
krh@102	997	struct razor_entry *entry;
danw@108	998	uint32_t *index;
krh@56	999
krh@102	1000	entry = find_entry(set, set->files.data, filename);
krh@102	1001	if (entry == NULL)
krh@102	1002	return NULL;
krh@56	1003
krh@102	1004	if (entry->packages & RAZOR_IMMEDIATE)
krh@102	1005	index = &entry->packages;
krh@60	1006	else
danw@108	1007	index = (uint32_t *)
krh@102	1008	set->package_pool.data + entry->packages;
krh@60	1009
krh@102	1010	return razor_package_iterator_create_with_index(set, index);
krh@56	1011	}
krh@56	1012
danw@108	1013	static uint32_t *
danw@108	1014	list_package_files(struct razor_set set, uint32_t r,
danw@108	1015	struct razor_entry *dir, uint32_t end,
krh@56	1016	char *prefix)
krh@56	1017	{
krh@56	1018	struct razor_entry e, f, *entries;
danw@108	1019	uint32_t next, file;
krh@56	1020	char *pool;
krh@56	1021	int len;
krh@56	1022
krh@56	1023	entries = (struct razor_entry *) set->files.data;
krh@56	1024	pool = set->string_pool.data;
krh@56	1025
krh@56	1026	e = entries + dir->start;
krh@56	1027	do {
krh@83	1028	if (entries + (*r & RAZOR_ENTRY_MASK) == e) {
krh@56	1029	printf("%s/%s\n", prefix,
krh@56	1030	pool + (e->name & RAZOR_ENTRY_MASK));
krh@83	1031	if (*r & RAZOR_ENTRY_LAST)
krh@83	1032	return NULL;
krh@56	1033	r++;
krh@83	1034	if ((*r & RAZOR_ENTRY_MASK) >= end)
krh@83	1035	return r;
krh@56	1036	}
krh@83	1037	} while (!((e++)->name & RAZOR_ENTRY_LAST));
krh@56	1038
krh@56	1039	e = entries + dir->start;
krh@56	1040	do {
krh@56	1041	if (e->start == 0)
krh@56	1042	continue;
krh@56	1043
krh@56	1044	if (e->name & RAZOR_ENTRY_LAST)
krh@56	1045	next = end;
krh@56	1046	else {
krh@56	1047	f = e + 1;
krh@56	1048	while (f->start == 0 && !(f->name & RAZOR_ENTRY_LAST))
krh@56	1049	f++;
krh@56	1050	if (f->start == 0)
krh@56	1051	next = end;
krh@56	1052	else
krh@56	1053	next = f->start;
krh@56	1054	}
krh@56	1055
krh@83	1056	file = *r & RAZOR_ENTRY_MASK;
krh@83	1057	if (e->start <= file && file < next) {
krh@56	1058	len = strlen(prefix);
krh@56	1059	prefix[len] = '/';
krh@56	1060	strcpy(prefix + len + 1,
krh@56	1061	pool + (e->name & RAZOR_ENTRY_MASK));
krh@56	1062	r = list_package_files(set, r, e, next, prefix);
krh@56	1063	prefix[len] = '\0';
krh@56	1064	}
krh@83	1065	} while (!((e++)->name & RAZOR_ENTRY_LAST) && r != NULL);
krh@56	1066
krh@56	1067	return r;
krh@56	1068	}
krh@56	1069
krh@56	1070	void
krh@56	1071	razor_set_list_package_files(struct razor_set set, const char name)
krh@56	1072	{
krh@56	1073	struct razor_package *package;
danw@108	1074	uint32_t *r, end;
krh@56	1075	char buffer[512];
krh@56	1076
krh@56	1077	package = razor_set_get_package(set, name);
krh@56	1078
danw@108	1079	r = (uint32_t *) set->file_pool.data + package->files;
krh@56	1080	end = set->files.size / sizeof (struct razor_entry);
krh@56	1081	buffer[0] = '\0';
krh@56	1082	list_package_files(set, r, set->files.data, end, buffer);
krh@56	1083	}
krh@56	1084
krh@43	1085	static void
krh@21	1086	razor_set_validate(struct razor_set set, struct array unsatisfied)
krh@21	1087	{
krh@66	1088	struct razor_property r, p, *end;
danw@108	1089	uint32_t *u;
krh@21	1090	char *pool;
krh@21	1091
krh@66	1092	end = set->properties.data + set->properties.size;
krh@21	1093	pool = set->string_pool.data;
krh@21	1094
krh@66	1095	for (r = set->properties.data, p = r; r < end; r++) {
krh@66	1096	if (r->name >> 30 != RAZOR_PROPERTY_REQUIRES)
krh@66	1097	continue;
krh@66	1098
krh@66	1099	if ((r->name & RAZOR_ENTRY_MASK) != (p->name & RAZOR_ENTRY_MASK)) {
krh@66	1100	p = r;
krh@66	1101	while (p < end && p->name == r->name)
krh@66	1102	p++;
krh@66	1103	}
krh@37	1104
krh@35	1105	/* If there is more than one version of a provides,
krh@35	1106	* seek to the end for the highest version. */
krh@66	1107	/* FIXME: This doesn't work if we have a series of
krh@66	1108	* requires a = 1, provides a = 1, requires a = 2,
krh@66	1109	* provides a = 2, as the kernel and kernel-devel
krh@66	1110	* does.*/
krh@66	1111	while (p + 1 < end && p->name == (p + 1)->name)
krh@35	1112	p++;
krh@37	1113
krh@37	1114	/* FIXME: We need to track property flags (<, <=, =
krh@37	1115	* etc) to properly determine if a requires is
krh@37	1116	* satisfied. The current code doesn't track that the
krh@37	1117	* requires a = 1 isn't satisfied by a = 2 provides. */
krh@37	1118
krh@66	1119	if (p == end \|\|
krh@66	1120	(p->name >> 30) != RAZOR_PROPERTY_PROVIDES \|\|
krh@66	1121	(r->name & RAZOR_ENTRY_MASK) != (p->name & RAZOR_ENTRY_MASK) \|\|
krh@35	1122	versioncmp(&pool[r->version], &pool[p->version]) > 0) {
krh@35	1123	/* FIXME: We ignore file requires for now. */
krh@66	1124	if (pool[r->name & RAZOR_ENTRY_MASK] == '/')
krh@35	1125	continue;
krh@21	1126	u = array_add(unsatisfied, sizeof *u);
krh@66	1127	u = r - (struct razor_property ) set->properties.data;
krh@21	1128	}
krh@21	1129	}
krh@21	1130	}
krh@21	1131
krh@21	1132	void
krh@21	1133	razor_set_list_unsatisfied(struct razor_set *set)
krh@21	1134	{
krh@21	1135	struct array unsatisfied;
krh@66	1136	struct razor_property properties, r;
danw@108	1137	uint32_t u, end;
krh@21	1138	char *pool;
krh@21	1139
krh@21	1140	array_init(&unsatisfied);
krh@21	1141	razor_set_validate(set, &unsatisfied);
krh@21	1142
krh@21	1143	end = unsatisfied.data + unsatisfied.size;
krh@66	1144	properties = set->properties.data;
krh@21	1145	pool = set->string_pool.data;
krh@21	1146
krh@21	1147	for (u = unsatisfied.data; u < end; u++) {
krh@66	1148	r = properties + *u;
krh@66	1149	if (pool[r->version] == '\0')
krh@66	1150	printf("%ss not satisfied\n",
krh@66	1151	&pool[r->name & RAZOR_ENTRY_MASK]);
krh@66	1152	else
krh@66	1153	printf("%s-%s not satisfied\n",
krh@66	1154	&pool[r->name & RAZOR_ENTRY_MASK],
krh@66	1155	&pool[r->version]);
krh@21	1156	}
krh@21	1157
krh@21	1158	array_release(&unsatisfied);
krh@21	1159	}
krh@21	1160
krh@41	1161	#define UPSTREAM_SOURCE 0x80000000ul
krh@41	1162	#define INDEX_MASK 0x00fffffful
krh@41	1163
krh@41	1164	struct source {
krh@41	1165	struct razor_set *set;
danw@108	1166	uint32_t *property_map;
krh@41	1167	};
krh@41	1168
krh@79	1169	struct razor_merger {
krh@79	1170	struct razor_set *set;
krh@79	1171	struct hashtable table;
krh@79	1172	struct source source1;
krh@79	1173	struct source source2;
krh@79	1174	};
krh@79	1175
krh@79	1176	static struct razor_merger *
krh@79	1177	razor_merger_create(struct razor_set set1, struct razor_set set2)
krh@41	1178	{
krh@79	1179	struct razor_merger *merger;
krh@41	1180	int count;
krh@41	1181	size_t size;
krh@41	1182
krh@79	1183	merger = zalloc(sizeof *merger);
krh@79	1184	merger->set = razor_set_create();
krh@79	1185	hashtable_init(&merger->table, &merger->set->string_pool);
krh@41	1186
krh@79	1187	count = set1->properties.size / sizeof (struct razor_property);
krh@79	1188	size = count * sizeof merger->source1.property_map[0];
krh@79	1189	merger->source1.property_map = zalloc(size);
krh@79	1190	merger->source1.set = set1;
krh@79	1191
krh@79	1192	count = set2->properties.size / sizeof (struct razor_property);
krh@79	1193	size = count * sizeof merger->source2.property_map[0];
krh@79	1194	merger->source2.property_map = zalloc(size);
krh@79	1195	merger->source2.set = set2;
krh@79	1196
krh@79	1197	return merger;
krh@41	1198	}
krh@41	1199
krh@33	1200	static void
krh@79	1201	add_package(struct razor_merger *merger,
krh@41	1202	struct razor_package package, struct source source,
danw@108	1203	uint32_t flags)
krh@33	1204	{
krh@33	1205	char *pool;
danw@108	1206	uint32_t *r;
krh@41	1207	struct razor_package *p;
krh@33	1208
krh@41	1209	pool = source->set->string_pool.data;
krh@79	1210	p = array_add(&merger->set->packages, sizeof *p);
krh@79	1211	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
krh@41	1212	p->name \|= flags;
krh@79	1213	p->version = hashtable_tokenize(&merger->table,
krh@79	1214	&pool[package->version]);
krh@66	1215	p->properties = package->properties;
krh@33	1216
krh@66	1217	if (package->properties & RAZOR_IMMEDIATE)
krh@66	1218	r = &package->properties;
krh@64	1219	else
danw@108	1220	r = (uint32_t *)
krh@66	1221	source->set->property_pool.data + package->properties;
krh@64	1222	while (1) {
krh@66	1223	source->property_map[*r & RAZOR_ENTRY_MASK] = 1;
krh@64	1224	if (*r++ & RAZOR_IMMEDIATE)
krh@64	1225	break;
krh@64	1226	}
krh@41	1227	}
krh@41	1228
krh@41	1229
krh@41	1230	/* Build the new package list sorted by merging the two package lists.
krh@79	1231	* Build new string pool as we go. */
krh@41	1232	static void
krh@79	1233	merge_packages(struct razor_merger merger, struct array packages)
krh@41	1234	{
krh@41	1235	struct razor_package upstream_packages, p, s, send;
krh@79	1236	struct source source1, source2;
krh@41	1237	char spool, upool;
danw@108	1238	uint32_t u, uend;
krh@41	1239	int cmp;
krh@41	1240
krh@79	1241	source1 = &merger->source1;
krh@79	1242	source2 = &merger->source2;
krh@41	1243	upstream_packages = source2->set->packages.data;
krh@41	1244
krh@41	1245	u = packages->data;
krh@41	1246	uend = packages->data + packages->size;
krh@41	1247	upool = source2->set->string_pool.data;
krh@41	1248
krh@41	1249	s = source1->set->packages.data;
krh@41	1250	send = source1->set->packages.data + source1->set->packages.size;
krh@41	1251	spool = source1->set->string_pool.data;
krh@41	1252
krh@41	1253	while (s < send) {
krh@41	1254	p = upstream_packages + *u;
krh@41	1255
krh@41	1256	if (u < uend)
krh@41	1257	cmp = strcmp(&spool[s->name], &upool[p->name]);
krh@41	1258	if (u >= uend \|\| cmp < 0) {
krh@79	1259	add_package(merger, s, source1, 0);
krh@41	1260	s++;
krh@41	1261	} else if (cmp == 0) {
krh@79	1262	add_package(merger, p, source2, UPSTREAM_SOURCE);
krh@41	1263	s++;
krh@41	1264	u++;
krh@41	1265	} else {
krh@79	1266	add_package(merger, p, source2, UPSTREAM_SOURCE);
krh@41	1267	u++;
krh@41	1268	}
krh@41	1269	}
krh@41	1270	}
krh@41	1271
danw@108	1272	static uint32_t
krh@79	1273	add_property(struct razor_merger *merger,
danw@109	1274	const char *name, enum razor_version_relation relation,
danw@109	1275	const char *version, int type)
krh@41	1276	{
krh@41	1277	struct razor_property *p;
krh@41	1278
krh@79	1279	p = array_add(&merger->set->properties, sizeof *p);
krh@79	1280	p->name = hashtable_tokenize(&merger->table, name) \| (type << 30);
danw@109	1281	p->relation = relation;
krh@79	1282	p->version = hashtable_tokenize(&merger->table, version);
krh@41	1283
krh@79	1284	return p - (struct razor_property *) merger->set->properties.data;
krh@41	1285	}
krh@41	1286
krh@41	1287	static void
krh@79	1288	merge_properties(struct razor_merger *merger)
krh@41	1289	{
krh@41	1290	struct razor_property p1, p2;
krh@79	1291	struct razor_set set1, set2;
danw@108	1292	uint32_t map1, map2;
krh@41	1293	int i, j, cmp, count1, count2;
krh@41	1294	char pool1, pool2;
krh@41	1295
krh@79	1296	set1 = merger->source1.set;
krh@79	1297	set2 = merger->source2.set;
krh@79	1298	map1 = merger->source1.property_map;
krh@79	1299	map2 = merger->source2.property_map;
krh@79	1300
krh@41	1301	i = 0;
krh@41	1302	j = 0;
krh@41	1303	pool1 = set1->string_pool.data;
krh@41	1304	pool2 = set2->string_pool.data;
krh@41	1305
krh@66	1306	count1 = set1->properties.size / sizeof *p1;
krh@66	1307	count2 = set2->properties.size / sizeof *p2;
krh@41	1308	while (i < count1 \|\| j < count2) {
krh@41	1309	if (i < count1 && map1[i] == 0) {
krh@41	1310	i++;
krh@41	1311	continue;
krh@41	1312	}
krh@41	1313	if (j < count2 && map2[j] == 0) {
krh@41	1314	j++;
krh@41	1315	continue;
krh@41	1316	}
krh@66	1317	p1 = (struct razor_property *) set1->properties.data + i;
krh@66	1318	p2 = (struct razor_property *) set2->properties.data + j;
krh@41	1319	if (i < count1 && j < count2)
krh@66	1320	cmp = strcmp(&pool1[p1->name & RAZOR_ENTRY_MASK],
krh@66	1321	&pool2[p2->name & RAZOR_ENTRY_MASK]);
krh@41	1322	else if (i < count1)
krh@41	1323	cmp = -1;
krh@41	1324	else
krh@41	1325	cmp = 1;
krh@41	1326	if (cmp == 0)
danw@109	1327	cmp = p1->relation - p2->relation;
danw@109	1328	if (cmp == 0)
krh@41	1329	cmp = versioncmp(&pool1[p1->version],
krh@41	1330	&pool2[p2->version]);
krh@41	1331	if (cmp < 0) {
krh@79	1332	map1[i++] = add_property(merger,
krh@66	1333	&pool1[p1->name & RAZOR_ENTRY_MASK],
danw@109	1334	p1->relation,
krh@69	1335	&pool1[p1->version],
krh@69	1336	(p1->name >> 30));
krh@41	1337	} else if (cmp > 0) {
krh@79	1338	map2[j++] = add_property(merger,
krh@66	1339	&pool2[p2->name & RAZOR_ENTRY_MASK],
danw@109	1340	p2->relation,
krh@69	1341	&pool2[p2->version],
krh@69	1342	(p2->name >> 30));
krh@41	1343	} else {
krh@79	1344	map1[i++] = map2[j++] = add_property(merger,
krh@66	1345	&pool1[p1->name & RAZOR_ENTRY_MASK],
danw@109	1346	p1->relation,
krh@69	1347	&pool1[p1->version],
krh@69	1348	(p1->name >> 30));
krh@41	1349	}
krh@41	1350	}
krh@41	1351	}
krh@41	1352
danw@108	1353	static uint32_t
danw@108	1354	emit_properties(struct array *source_pool, uint32_t index,
danw@108	1355	uint32_t map, struct array pool)
krh@41	1356	{
danw@108	1357	uint32_t r, p, q;
krh@41	1358
krh@41	1359	r = pool->size / sizeof *q;
danw@108	1360	p = (uint32_t *) source_pool->data + index;
krh@64	1361	while (1) {
krh@41	1362	q = array_add(pool, sizeof *q);
krh@64	1363	q = map[p & RAZOR_ENTRY_MASK] \| (*p & ~RAZOR_ENTRY_MASK);
krh@64	1364	if (*p++ & RAZOR_ENTRY_LAST)
krh@64	1365	break;
krh@33	1366	}
krh@33	1367
krh@41	1368	return r;
krh@41	1369	}
krh@41	1370
krh@41	1371	/* Rebuild property->packages maps. We can't just remap these, as a
krh@41	1372	* property may have lost or gained a number of packages. Allocate an
krh@41	1373	* array per property and loop through the packages and add them to
krh@41	1374	* the arrays for their properties. */
krh@41	1375	static void
krh@41	1376	rebuild_package_lists(struct razor_set *set)
krh@41	1377	{
krh@66	1378	struct array pkgs, a;
krh@41	1379	struct razor_package pkg, pkg_end;
krh@41	1380	struct razor_property prop, prop_end;
danw@108	1381	uint32_t r, q, *pool;
krh@66	1382	int count;
krh@41	1383
krh@66	1384	count = set->properties.size / sizeof (struct razor_property);
krh@66	1385	pkgs = zalloc(count * sizeof *pkgs);
krh@41	1386	pkg_end = set->packages.data + set->packages.size;
krh@66	1387	pool = set->property_pool.data;
krh@41	1388
krh@41	1389	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
krh@66	1390	for (r = &pool[pkg->properties]; ; r++) {
krh@66	1391	q = array_add(&pkgs[r & RAZOR_ENTRY_MASK], sizeof q);
krh@41	1392	q = pkg - (struct razor_package ) set->packages.data;
krh@64	1393	if (*r & RAZOR_IMMEDIATE)
krh@64	1394	break;
krh@41	1395	}
krh@33	1396	}
krh@33	1397
krh@66	1398	prop_end = set->properties.data + set->properties.size;
krh@66	1399	a = pkgs;
krh@66	1400	for (prop = set->properties.data; prop < prop_end; prop++, a++) {
danw@114	1401	prop->packages =
danw@114	1402	add_to_property_pool(&set->property_pool, a);
krh@41	1403	array_release(a);
krh@41	1404	}
krh@66	1405	free(pkgs);
krh@33	1406	}
krh@33	1407
krh@79	1408	struct razor_set *
krh@79	1409	razor_merger_finish(struct razor_merger *merger)
krh@79	1410	{
krh@79	1411	struct razor_set *result;
krh@79	1412
krh@79	1413	result = merger->set;
krh@79	1414	hashtable_release(&merger->table);
krh@79	1415	free(merger);
krh@79	1416
krh@79	1417	return result;
krh@79	1418	}
krh@79	1419
krh@33	1420	/* Add packages from 'upstream' to 'set'. The packages to add are
krh@33	1421	* specified by the 'packages' array, which is a sorted list of
krh@33	1422	* package indexes. Returns a newly allocated package set. Does not
krh@41	1423	* enforce validity of the resulting package set.
krh@41	1424	*
krh@41	1425	* This looks more complicated than it is. An easy way to merge two
krh@41	1426	* package sets would be to just use a razor_importer, but that
krh@41	1427	* requires resorting, and is thus O(n log n). We can do this in a
krh@41	1428	* linear sweep, but it gets a little more complicated.
krh@41	1429	*/
krh@33	1430	struct razor_set *
krh@33	1431	razor_set_add(struct razor_set set, struct razor_set upstream,
krh@33	1432	struct array *packages)
krh@33	1433	{
krh@79	1434	struct razor_merger *merger;
krh@41	1435	struct razor_package p, pend;
krh@33	1436
krh@79	1437	merger = razor_merger_create(set, upstream);
krh@33	1438
krh@79	1439	merge_packages(merger, packages);
krh@41	1440
krh@41	1441	/* As we built the package list, we filled out a bitvector of
krh@41	1442	* the properties that are referenced by the packages in the
krh@41	1443	* new set. Now we do a parallel loop through the properties
krh@41	1444	* and emit those marked in the bit vector to the new set. In
krh@41	1445	* the process, we update the bit vector to actually map from
krh@41	1446	* indices in the old property list to indices in the new
krh@41	1447	* property list for both sets. */
krh@41	1448
krh@79	1449	merge_properties(merger);
krh@41	1450
krh@41	1451	/* Now we loop through the packages again and emit the
krh@41	1452	* property lists, remapped to point to the new properties. */
krh@41	1453
krh@79	1454	pend = merger->set->packages.data + merger->set->packages.size;
krh@79	1455	for (p = merger->set->packages.data; p < pend; p++) {
krh@41	1456	struct source *src;
krh@41	1457
krh@41	1458	if (p->name & UPSTREAM_SOURCE)
krh@79	1459	src = &merger->source2;
krh@41	1460	else
krh@79	1461	src = &merger->source1;
krh@41	1462
krh@66	1463	p->properties = emit_properties(&src->set->property_pool,
krh@66	1464	p->properties,
krh@66	1465	src->property_map,
krh@79	1466	&merger->set->property_pool);
krh@41	1467	p->name &= INDEX_MASK;
krh@33	1468	}
krh@33	1469
krh@79	1470	rebuild_package_lists(merger->set);
krh@41	1471
krh@79	1472	return razor_merger_finish(merger);
krh@33	1473	}
krh@33	1474
krh@37	1475	void
krh@37	1476	razor_set_satisfy(struct razor_set set, struct array unsatisfied,
krh@37	1477	struct razor_set upstream, struct array list)
krh@37	1478	{
krh@37	1479	struct razor_property requires, r;
krh@37	1480	struct razor_property p, pend;
danw@108	1481	uint32_t u, end, pkg, package_pool;
krh@37	1482	char pool, upool;
krh@37	1483
krh@37	1484	end = unsatisfied->data + unsatisfied->size;
krh@66	1485	requires = set->properties.data;
krh@37	1486	pool = set->string_pool.data;
krh@37	1487
krh@66	1488	p = upstream->properties.data;
krh@66	1489	pend = upstream->properties.data + upstream->properties.size;
krh@37	1490	upool = upstream->string_pool.data;
krh@39	1491	package_pool = upstream->package_pool.data;
krh@37	1492
krh@37	1493	for (u = unsatisfied->data; u < end; u++) {
krh@37	1494	r = requires + *u;
krh@37	1495
krh@66	1496	while (p < pend &&
krh@66	1497	strcmp(&pool[r->name & RAZOR_ENTRY_MASK],
krh@66	1498	&upool[p->name & RAZOR_ENTRY_MASK]) > 0 &&
krh@66	1499	(p->name >> 30) != RAZOR_PROPERTY_PROVIDES)
krh@37	1500	p++;
krh@37	1501	/* If there is more than one version of a provides,
krh@37	1502	* seek to the end for the highest version. */
krh@37	1503	while (p + 1 < pend && p->name == (p + 1)->name)
krh@37	1504	p++;
krh@37	1505
krh@37	1506	if (p == pend \|\|
krh@66	1507	strcmp(&pool[r->name & RAZOR_ENTRY_MASK],
krh@66	1508	&upool[p->name & RAZOR_ENTRY_MASK]) != 0 \|\|
krh@37	1509	versioncmp(&pool[r->version], &upool[p->version]) > 0) {
krh@37	1510	/* Do we need to track unsatisfiable requires
krh@37	1511	* as we go, or should we just do a
krh@37	1512	* razor_set_validate() at the end? */
krh@37	1513	} else {
krh@37	1514	pkg = array_add(list, sizeof *pkg);
krh@37	1515	/* We just pull in the first package that provides */
krh@61	1516	if (p->packages & RAZOR_IMMEDIATE)
krh@61	1517	*pkg = p->packages & RAZOR_ENTRY_MASK;
krh@61	1518	else
krh@61	1519	*pkg = package_pool[p->packages];
krh@37	1520	}
krh@37	1521	}
krh@37	1522	}
krh@37	1523
krh@38	1524	static void
krh@38	1525	find_packages(struct razor_set *set,
krh@105	1526	int count, const char *package_names, struct array list)
krh@38	1527	{
krh@105	1528	struct razor_package_iterator *pi;
krh@105	1529	struct razor_package p, packages;
krh@105	1530	const char name, version;
danw@108	1531	uint32_t *r;
krh@38	1532	int i;
krh@38	1533
krh@105	1534	packages = (struct razor_package *) set->packages.data;
krh@105	1535	pi = razor_package_iterator_create(set);
krh@105	1536
krh@105	1537	while (razor_package_iterator_next(pi, &p, &name, &version)) {
krh@105	1538	for (i = 0; i < count; i++) {
krh@105	1539	if (strcmp(name, package_names[i]) == 0) {
krh@105	1540	r = array_add(list, sizeof *r);
krh@105	1541	*r = p - packages;
krh@105	1542	break;
krh@105	1543	}
krh@105	1544	}
krh@38	1545	}
krh@105	1546
krh@105	1547	razor_package_iterator_destroy(pi);
krh@38	1548	}
krh@38	1549
krh@38	1550	static void
krh@38	1551	find_all_packages(struct razor_set *set,
krh@38	1552	struct razor_set upstream, struct array list)
krh@38	1553	{
krh@38	1554	struct razor_package p, u, pend, uend;
danw@108	1555	uint32_t *r;
krh@38	1556	char pool, upool;
krh@38	1557
krh@38	1558	pend = set->packages.data + set->packages.size;
krh@38	1559	pool = set->string_pool.data;
krh@38	1560	u = upstream->packages.data;
krh@38	1561	uend = upstream->packages.data + upstream->packages.size;
krh@38	1562	upool = upstream->string_pool.data;
krh@38	1563
krh@38	1564	for (p = set->packages.data; p < pend; p++) {
krh@38	1565	while (u < uend && strcmp(&pool[p->name], &upool[u->name]) > 0)
krh@38	1566	u++;
krh@38	1567	if (strcmp(&pool[p->name], &upool[u->name]) == 0) {
krh@38	1568	r = array_add(list, sizeof *r);
krh@38	1569	r = u - (struct razor_package ) upstream->packages.data;
krh@38	1570	}
krh@38	1571	}
krh@38	1572	}
krh@38	1573
krh@33	1574	struct razor_set *
krh@33	1575	razor_set_update(struct razor_set set, struct razor_set upstream,
krh@33	1576	int count, const char **packages)
krh@33	1577	{
krh@37	1578	struct razor_set *new;
krh@43	1579	struct razor_package *upackages;
krh@37	1580	struct array list, unsatisfied;
krh@37	1581	char *pool;
danw@108	1582	uint32_t u, end;
krh@38	1583	int total = 0;
krh@33	1584
krh@33	1585	array_init(&list);
krh@38	1586	if (count > 0)
krh@38	1587	find_packages(upstream, count, packages, &list);
krh@38	1588	else
krh@38	1589	find_all_packages(set, upstream, &list);
krh@33	1590
krh@37	1591	end = list.data + list.size;
krh@37	1592	upackages = upstream->packages.data;
krh@37	1593	pool = upstream->string_pool.data;
krh@38	1594	total += list.size / sizeof *u;
krh@37	1595
krh@37	1596	while (list.size > 0) {
krh@37	1597	new = razor_set_add(set, upstream, &list);
krh@37	1598	array_release(&list);
krh@37	1599	razor_set_destroy(set);
krh@37	1600	set = new;
krh@37	1601
krh@37	1602	array_init(&unsatisfied);
krh@37	1603	razor_set_validate(new, &unsatisfied);
krh@37	1604	array_init(&list);
krh@37	1605	razor_set_satisfy(new, &unsatisfied, upstream, &list);
krh@37	1606	array_release(&unsatisfied);
krh@37	1607
krh@37	1608	end = list.data + list.size;
krh@37	1609	upackages = upstream->packages.data;
krh@37	1610	pool = upstream->string_pool.data;
krh@38	1611	total += list.size / sizeof *u;
krh@37	1612	}
krh@37	1613
krh@37	1614	array_release(&list);
krh@37	1615
krh@37	1616	return set;
krh@33	1617	}
krh@33	1618
krh@44	1619	/* The diff order matters. We should sort the packages so that a
krh@44	1620	* REMOVE of a package comes before the INSTALL, and so that all
krh@44	1621	* requires for a package have been installed before the package.
krh@44	1622	**/
krh@44	1623
krh@44	1624	void
krh@44	1625	razor_set_diff(struct razor_set set, struct razor_set upstream,
krh@44	1626	razor_package_callback_t callback, void *data)
krh@44	1627	{
krh@103	1628	struct razor_package_iterator pi1, pi2;
krh@103	1629	struct razor_package p1, p2;
krh@103	1630	const char name1, name2, version1, version2;
krh@106	1631	int res;
krh@44	1632
krh@103	1633	pi1 = razor_package_iterator_create(set);
krh@103	1634	pi2 = razor_package_iterator_create(upstream);
krh@44	1635
krh@103	1636	razor_package_iterator_next(pi1, &p1, &name1, &version1);
krh@103	1637	razor_package_iterator_next(pi2, &p2, &name2, &version2);
krh@44	1638
krh@103	1639	while (p1 \|\| p2) {
krh@103	1640	if (p1 && p2) {
krh@103	1641	res = strcmp(name1, name2);
krh@44	1642	if (res == 0)
krh@103	1643	res = versioncmp(version1, version2);
krh@106	1644	} else {
krh@106	1645	res = 0;
krh@44	1646	}
krh@44	1647
krh@103	1648	if (p2 == NULL \|\| res < 0)
krh@103	1649	callback(name1, version1, NULL, data);
krh@103	1650	else if (p1 == NULL \|\| res > 0)
krh@103	1651	callback(name2, NULL, version2, data);
krh@103	1652
krh@103	1653	if (p1 != NULL && res <= 0)
krh@103	1654	razor_package_iterator_next(pi1, &p1,
krh@103	1655	&name1, &version1);
krh@103	1656	if (p2 != NULL && res >= 0)
krh@103	1657	razor_package_iterator_next(pi2, &p2,
krh@103	1658	&name2, &version2);
krh@44	1659	}
krh@103	1660
krh@103	1661	razor_package_iterator_destroy(pi1);
krh@103	1662	razor_package_iterator_destroy(pi2);
krh@44	1663	}

author	Dan Winship <danw@gnome.org>
	Thu Feb 07 09:58:48 2008 -0500 (2008-02-07)
changeset 115	26edeea5c95a
parent 114	1d54922ff920
child 116	4ec6e2a55c34
permissions	-rw-r--r--