razor: razor.c@8fec3db93757 (annotated)

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

author	Kristian H?gsberg <krh@redhat.com>
	Sun Oct 28 22:50:57 2007 -0400 (2007-10-28)
changeset 65	8fec3db93757
parent 61	b0e1638a9f96
child 66	bb4ca4a47f66
permissions	-rw-r--r--