razor: razor.c@fca1ef50dd2c

     1 #define _GNU_SOURCE

     3 #include <stdlib.h>

     4 #include <stddef.h>

     5 #include <stdio.h>

     6 #include <string.h>

     7 #include <sys/types.h>

     8 #include <sys/stat.h>

     9 #include <sys/mman.h>

    10 #include <unistd.h>

    11 #include <fcntl.h>

    12 #include <errno.h>

    13 #include <ctype.h>

    14 #include <fnmatch.h>

    16 #include "razor.h"

    18 struct array {

    19 	void *data;

    20 	int size, alloc;

    21 };

    23 struct razor_set_section {

    24 	unsigned int type;

    25 	unsigned int offset;

    26 	unsigned int size;

    27 };

    29 struct razor_set_header {

    30 	unsigned int magic;

    31 	unsigned int version;

    32 	struct razor_set_section sections[0];

    33 };

    35 #define RAZOR_MAGIC 0x7a7a7a7a

    36 #define RAZOR_VERSION 1

    38 #define RAZOR_STRING_POOL 0

    39 #define RAZOR_PACKAGES 1

    40 #define RAZOR_REQUIRES 2

    41 #define RAZOR_PROVIDES 3

    42 #define RAZOR_FILES 4

    43 #define RAZOR_PACKAGE_POOL 5

    44 #define RAZOR_REQUIRES_POOL 6

    45 #define RAZOR_PROVIDES_POOL 7

    46 #define RAZOR_FILE_POOL 8

    48 struct razor_package {

    49 	unsigned long name;

    50 	unsigned long version;

    51 	unsigned long requires;

    52 	unsigned long provides;

    53 	unsigned long files;

    54 };

    56 struct razor_property {

    57 	unsigned long name;

    58 	unsigned long version;

    59 	unsigned long packages;

    60 };

    62 struct razor_entry {

    63 	unsigned long name;

    64 	unsigned long start;

    65 	unsigned long packages;

    66 };

    68 struct razor_set {

    69 	struct array string_pool;

    70  	struct array packages;

    71  	struct array requires;

    72  	struct array provides;

    73  	struct array files;

    74 	struct array package_pool;

    75  	struct array requires_pool;

    76  	struct array provides_pool;

    77  	struct array file_pool;

    78 	struct razor_set_header *header;

    79 };

    81 struct import_entry {

    82 	unsigned long package;

    83 	char *name;

    84 };

    86 struct import_directory {

    87 	unsigned long name, count;

    88 	struct array files;

    89 	struct array packages;

    90 	struct import_directory *last;

    91 };

    93 struct import_property_context {

    94 	struct array *all;

    95 	struct array package;

    96 };

    98 struct razor_importer {

    99 	struct razor_set *set;

   100 	struct array buckets;

   101 	struct import_property_context requires;

   102 	struct import_property_context provides;

   103 	struct razor_package *package;

   104 	struct array files;

   105 };

   107 static void

   108 array_init(struct array *array)

   109 {

   110 	memset(array, 0, sizeof *array);

   111 }

   113 static void

   114 array_release(struct array *array)

   115 {

   116 	free(array->data);

   117 }

   119 static void *

   120 array_add(struct array *array, int size)

   121 {

   122 	int alloc;

   123 	void *data, *p;

   125 	if (array->alloc > 0)

   126 		alloc = array->alloc;

   127 	else

   128 		alloc = 16;

   130 	while (alloc < array->size + size)

   131 		alloc *= 2;

   133 	if (array->alloc < alloc) {

   134 		data = realloc(array->data, alloc);

   135 		if (data == NULL)

   136 			return 0;

   137 		array->data = data;

   138 		array->alloc = alloc;

   139 	}

   141 	p = array->data + array->size;

   142 	array->size += size;

   144 	return p;

   145 }

   147 static int

   148 write_to_fd(int fd, void *p, size_t size)

   149 {

   150 	int rest, len;

   152 	rest = size;

   153 	while (rest > 0) {

   154 		len = write(fd, p, rest);

   155 		if (len < 0)

   156 			return -1;

   157 		rest -= len;

   158 	}

   160 	return 0;

   161 }

   163 static void *

   164 zalloc(size_t size)

   165 {

   166 	void *p;

   168 	p = malloc(size);

   169 	memset(p, 0, size);

   171 	return p;

   172 }

   174 struct razor_set_section razor_sections[] = {

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

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

   177 	{ RAZOR_REQUIRES,	offsetof(struct razor_set, requires) },

   178 	{ RAZOR_PROVIDES,	offsetof(struct razor_set, provides) },

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

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

   181 	{ RAZOR_REQUIRES_POOL,	offsetof(struct razor_set, requires_pool) },

   182 	{ RAZOR_PROVIDES_POOL,	offsetof(struct razor_set, provides_pool) },

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

   184 };

   186 struct razor_set *

   187 razor_set_create(void)

   188 {

   189 	return zalloc(sizeof(struct razor_set));

   190 }

   192 struct razor_set *

   193 razor_set_open(const char *filename)

   194 {

   195 	struct razor_set *set;

   196 	struct razor_set_section *s;

   197 	struct stat stat;

   198 	struct array *array;

   199 	int fd;

   201 	set = zalloc(sizeof *set);

   202 	fd = open(filename, O_RDONLY);

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

   204 		return NULL;

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

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

   207 		free(set);

   208 		return NULL;

   209 	}

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

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

   213 			continue;

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

   215 			continue;

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

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

   218 		array->size = s->size;

   219 		array->alloc = s->size;

   220 	}

   221 	close(fd);

   223 	return set;

   224 }

   226 void

   227 razor_set_destroy(struct razor_set *set)

   228 {

   229 	unsigned int size;

   230 	struct array *a;

   231 	int i;

   233 	if (set->header) {

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

   235 			;

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

   237 		munmap(set->header, size);

   238 	} else {

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

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

   241 			free(a->data);

   242 		}

   243 	}

   245 	free(set);

   246 }

   248 int

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

   250 {

   251 	char data[4096];

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

   253 	struct array *a;

   254 	unsigned long offset;

   255 	int i, fd;

   257 	memset(data, 0, sizeof data);

   258 	header->magic = RAZOR_MAGIC;

   259 	header->version = RAZOR_VERSION;

   260 	offset = sizeof data;

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

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

   264 			continue;

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

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

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

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

   269 		offset += (a->size + 4095) & ~4095;

   270 	}

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

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

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

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

   277 	if (fd < 0)

   278 		return -1;

   280 	write_to_fd(fd, data, sizeof data);

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

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

   283 			continue;

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

   285 		write_to_fd(fd, a->data, (a->size + 4095) & ~4095);

   286 	}

   288 	close(fd);

   290 	return 0;

   291 }

   293 static unsigned int

   294 hash_string(const char *key)

   295 {

   296 	const char *p;

   297 	unsigned int hash = 0;

   299 	for (p = key; *p; p++)

   300 		hash = (hash * 617) ^ *p;

   302 	return hash;

   303 }

   305 static unsigned long

   306 razor_importer_lookup(struct razor_importer *importer, const char *key)

   307 {

   308 	unsigned int mask, start, i;

   309 	unsigned long *b;

   310 	char *pool;

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

   313 	mask = importer->buckets.alloc - 1;

   314 	start = hash_string(key) * sizeof(unsigned long);

   316 	for (i = 0; i < importer->buckets.alloc; i += sizeof *b) {

   317 		b = importer->buckets.data + ((start + i) & mask);

   319 		if (*b == 0)

   320 			return 0;

   322 		if (strcmp(key, &pool[*b]) == 0)

   323 			return *b;

   324 	}

   326 	return 0;

   327 }

   329 static unsigned long

   330 add_to_string_pool(struct razor_set *set, const char *key)

   331 {

   332 	int len;

   333 	char *p;

   335 	len = strlen(key) + 1;

   336 	p = array_add(&set->string_pool, len);

   337 	memcpy(p, key, len);

   339 	return p - (char *) set->string_pool.data;

   340 }

   342 static unsigned long

   343 add_to_property_pool(struct array *pool, struct array *properties)

   344 {

   345 	unsigned long  *p;

   347 	p = array_add(properties, sizeof *p);

   348 	*p = ~0ul;

   349 	p = array_add(pool, properties->size);

   350 	memcpy(p, properties->data, properties->size);

   352 	return p - (unsigned long *) pool->data;

   353 }

   355 static void

   356 do_insert(struct razor_importer *importer, unsigned long value)

   357 {

   358 	unsigned int mask, start, i;

   359 	unsigned long *b;

   360 	const char *key;

   362 	key = (char *) importer->set->string_pool.data + value;

   363 	mask = importer->buckets.alloc - 1;

   364 	start = hash_string(key) * sizeof(unsigned long);

   366 	for (i = 0; i < importer->buckets.alloc; i += sizeof *b) {

   367 		b = importer->buckets.data + ((start + i) & mask);

   368 		if (*b == 0) {

   369 			*b = value;

   370 			break;

   371 		}

   372 	}

   373 }

   375 static unsigned long

   376 razor_importer_insert(struct razor_importer *importer, const char *key)

   377 {

   378 	unsigned long value, *buckets, *b, *end;

   379 	int alloc;

   381 	alloc = importer->buckets.alloc;

   382 	array_add(&importer->buckets, 4 * sizeof *buckets);

   383 	if (alloc != importer->buckets.alloc) {

   384 		end = importer->buckets.data + alloc;

   385 		memset(end, 0, importer->buckets.alloc - alloc);

   386 		for (b = importer->buckets.data; b < end; b++) {

   387 			value = *b;

   388 			if (value != 0) {

   389 				*b = 0;

   390 				do_insert(importer, value);

   391 			}

   392 		}

   393 	}

   395 	value = add_to_string_pool(importer->set, key);

   396 	do_insert (importer, value);

   398 	return value;

   399 }

   401 static unsigned long

   402 razor_importer_tokenize(struct razor_importer *importer, const char *string)

   403 {

   404 	unsigned long token;

   406 	if (string == NULL)

   407 		return razor_importer_tokenize(importer, "");

   409 	token = razor_importer_lookup(importer, string);

   410 	if (token != 0)

   411 		return token;

   413 	return razor_importer_insert(importer, string);

   414 }

   416 void

   417 razor_importer_begin_package(struct razor_importer *importer,

   418 			     const char *name, const char *version)

   419 {

   420 	struct razor_package *p;

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

   423 	p->name = razor_importer_tokenize(importer, name);

   424 	p->version = razor_importer_tokenize(importer, version);

   426 	importer->package = p;

   427 	array_init(&importer->requires.package);

   428 	array_init(&importer->provides.package);

   429 }

   431 void

   432 razor_importer_finish_package(struct razor_importer *importer)

   433 {

   434 	struct razor_package *p;

   436 	p = importer->package;

   437 	p->requires = add_to_property_pool(&importer->set->requires_pool,

   438 					   &importer->requires.package);

   439 	p->provides = add_to_property_pool(&importer->set->provides_pool,

   440 					   &importer->provides.package);

   442 	array_release(&importer->requires.package);

   443 	array_release(&importer->provides.package);

   444 }

   446 static void

   447 razor_importer_add_property(struct razor_importer *importer,

   448 			    struct import_property_context *pctx,

   449 			    const char *name, const char *version)

   450 {

   451 	struct razor_property *p;

   452 	unsigned long *r;

   454 	p = array_add(pctx->all, sizeof *p);

   455 	p->name = razor_importer_tokenize(importer, name);

   456 	p->version = razor_importer_tokenize(importer, version);

   457 	p->packages = importer->package -

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

   460 	r = array_add(&pctx->package, sizeof *r);

   461 	*r = p - (struct razor_property *) pctx->all->data;

   462 }

   464 void

   465 razor_importer_add_requires(struct razor_importer *importer,

   466 			    const char *name, const char *version)

   467 {

   468 	razor_importer_add_property(importer,

   469 				    &importer->requires, name, version);

   470 }

   472 void

   473 razor_importer_add_provides(struct razor_importer *importer,

   474 			    const char *name, const char *version)

   475 {

   476 	razor_importer_add_property(importer,

   477 				    &importer->provides, name, version);

   478 }

   480 void

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

   482 {

   483 	struct import_entry *e;

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

   487 	e->package = importer->package -

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

   489 	e->name = strdup(name);

   490 }

   492 struct razor_importer *

   493 razor_importer_new(void)

   494 {

   495 	struct razor_importer *importer;

   497 	importer = zalloc(sizeof *importer);

   498 	importer->set = razor_set_create();

   499 	importer->requires.all = &importer->set->requires;

   500 	importer->provides.all = &importer->set->provides;

   502 	return importer;

   503 }

   505 typedef int (*compare_with_data_func_t)(const void *p1,

   506 					const void *p,

   507 					void *data);

   509 struct qsort_context {

   510 	size_t size;

   511 	compare_with_data_func_t compare;

   512 	void *data;

   513 };

   515 static void

   516 qsort_swap(void *p1, void *p2, size_t size)

   517 {

   518 	char buffer[size];

   520 	memcpy(buffer, p1, size);

   521 	memcpy(p1, p2, size);

   522 	memcpy(p2, buffer, size);

   523 }

   525 static void

   526 __qsort_with_data(void *base, size_t nelem, unsigned long *map,

   527 		  struct qsort_context *ctx)

   528 {

   529 	void *p, *start, *end, *pivot;

   530 	unsigned long *mp, *mstart, *mend, tmp;

   531 	int left, right, result;

   532 	size_t size = ctx->size;

   534 	p = base;

   535 	start = base;

   536 	end = base + nelem * size;

   537 	mp = map;

   538 	mstart = map;

   539 	mend = map + nelem;

   540 	pivot = base + (random() % nelem) * size;

   542 	while (p < end) {

   543 		result = ctx->compare(p, pivot, ctx->data);

   544 		if (result < 0) {

   545 			qsort_swap(p, start, size);

   546 			tmp = *mp;

   547 			*mp = *mstart;

   548 			*mstart = tmp;

   549 			if (start == pivot)

   550 				pivot = p;

   551 			start += size;

   552 			mstart++;

   553 			p += size;

   554 			mp++;

   555 		} else if (result == 0) {

   556 			p += size;

   557 			mp++;

   558 		} else {

   559  			end -= size;

   560 			mend--;

   561 			qsort_swap(p, end, size);

   562 			tmp = *mp;

   563 			*mp = *mend;

   564 			*mend = tmp;

   565 			if (end == pivot)

   566 				pivot = p;

   567 		}

   568 	}

   570 	left = (start - base) / size;

   571 	right = (base + nelem * size - end) / size;

   572 	if (left > 1)

   573 		__qsort_with_data(base, left, map, ctx);

   574 	if (right > 1)

   575 		__qsort_with_data(end, right, mend, ctx);

   576 }

   578 unsigned long *

   579 qsort_with_data(void *base, size_t nelem, size_t size,

   580 		compare_with_data_func_t compare, void *data)

   581 {

   582 	struct qsort_context ctx;

   583 	unsigned long *map;

   584 	int i;

   586 	ctx.size = size;

   587 	ctx.compare = compare;

   588 	ctx.data = data;

   590 	map = malloc(nelem * sizeof (unsigned long));

   591 	for (i = 0; i < nelem; i++)

   592 		map[i] = i;

   594 	__qsort_with_data(base, nelem, map, &ctx);

   596 	return map;

   597 }

   599 static int

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

   601 {

   602 	const char *p1, *p2;

   603 	long n1, n2;

   604 	int res;

   606 	n1 = strtol(s1, (char **) &p1, 0);

   607 	n2 = strtol(s2, (char **) &p2, 0);

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

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

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

   612 	if (res < 0) {

   613 		n1 = 0;

   614 		p1 = s1;

   615 		p2++;

   616 	} else if (res > 0) {

   617 		p1++;

   618 		n2 = 0;

   619 		p2 = s2;

   620 	}

   622 	if (n1 != n2)

   623 		return n1 - n2;

   624 	while (*p1 && *p2) {

   625 		if (*p1 != *p2)

   626 			return *p1 - *p2;

   627 		p1++;

   628 		p2++;

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

   630 			return versioncmp(p1, p2);

   631 	}

   633 	return *p1 - *p2;

   634 }

   637 static int

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

   639 {

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

   641 	struct razor_set *set = data;

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

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

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

   646 	else

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

   648 }

   650 static int

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

   652 {

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

   654 	struct razor_set *set = data;

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

   657 	if (prop1->name == prop2->name)

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

   659 	else

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

   661 }

   663 static unsigned long *

   664 uniqueify_properties(struct razor_set *set, struct array *properties)

   665 {

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

   667 	struct array *pkgs, *p;

   668 	unsigned long *map, *rmap, *r;

   669 	int i, count, unique;

   671 	count = properties->size / sizeof(struct razor_property);

   672 	map = qsort_with_data(properties->data,

   673 			      count,

   674 			      sizeof(struct razor_property),

   675 			      compare_properties,

   676 			      set);

   678 	rp_end = properties->data + properties->size;

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

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

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

   682 		if (rp->name != up->name || rp->version != up->version) {

   683 			up++;

   684 			up->name = rp->name;

   685 			up->version = rp->version;

   686 		}

   688 		unique = up - (struct razor_property *) properties->data;

   689 		rmap[map[i]] = unique;

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

   691 		*r = rp->packages;

   692 	}

   693 	free(map);

   695 	up++;

   696 	properties->size = (void *) up - properties->data;

   697 	rp_end = up;

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

   699 		rp->packages = add_to_property_pool(&set->package_pool, p);

   700 		array_release(p);

   701 	}

   703 	free(pkgs);

   705 	return rmap;

   706 }

   708 static void

   709 remap_links(struct array *links, unsigned long *map)

   710 {

   711 	unsigned long *p, *end;

   713 	end = links->data + links->size;

   714 	for (p = links->data; p < end; p++)

   715 		if (*p != ~0)

   716 			*p = map[*p];

   717 }

   719 static int

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

   721 {

   722 	const struct import_entry *e1 = p1;

   723 	const struct import_entry *e2 = p2;

   725 	return strcmp(e1->name, e2->name);

   726 }

   728 static void

   729 count_entries(struct import_directory *d)

   730 {

   731 	struct import_directory *p, *end;

   733 	p = d->files.data;

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

   735 	d->count = 0;

   736 	while (p < end) {

   737 		count_entries(p);

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

   739 		p++;

   740 	}

   741 }

   743 #define RAZOR_ENTRY_LAST	0x80000000ul

   744 #define RAZOR_IMMEDIATE		0x80000000ul

   745 #define RAZOR_ENTRY_MASK	0x00fffffful

   747 static void

   748 serialize_files(struct razor_set *set,

   749 		struct import_directory *d, struct array *array)

   750 {

   751 	struct import_directory *p, *end;

   752 	struct razor_entry *e = NULL;

   753 	unsigned long s, *r;

   755 	p = d->files.data;

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

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

   758 	while (p < end) {

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

   760 		e->name = p->name;

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

   762 		s += p->count;

   764 		if (p->packages.size / sizeof (unsigned long) == 1) {

   765 			r = p->packages.data;

   766 			e->packages = *r | RAZOR_IMMEDIATE;

   767 		} else {

   768 			e->packages = add_to_property_pool(&set->package_pool,

   769 							   &p->packages);

   770 		}

   771 		array_release(&p->packages);

   772 		p++;

   773 	}

   774 	if (e != NULL)

   775 		e->name |= RAZOR_ENTRY_LAST;

   777 	p = d->files.data;

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

   779 	while (p < end) {

   780 		serialize_files(set, p, array);

   781 		p++;

   782 	}

   783 }

   785 static void

   786 build_file_tree(struct razor_importer *importer)

   787 {

   788 	int count, i, length;

   789 	struct import_entry *filenames;

   790 	char *f, *end;

   791 	unsigned long name, *r;

   792 	char dirname[256];

   793 	struct import_directory *d, root;

   794 	struct razor_entry *e;

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

   797 	qsort_with_data(importer->files.data,

   798 			count,

   799 			sizeof (struct import_entry),

   800 			compare_filenames,

   801 			NULL);

   803 	root.name = razor_importer_tokenize(importer, "");

   804 	array_init(&root.files);

   805 	array_init(&root.packages);

   806 	root.last = NULL;

   808 	filenames = importer->files.data;

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

   810 		f = filenames[i].name;

   811 		if (*f != '/')

   812 			continue;

   813 		f++;

   815 		d = &root;

   816 		while (*f) {

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

   818 			if (end == NULL)

   819 				end = f + strlen(f);

   820 			length = end - f;

   821 			memcpy(dirname, f, length);

   822 			dirname[length] ='\0';

   823 			name = razor_importer_tokenize(importer, dirname);

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

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

   826 				d->last->name = name;

   827 				d->last->last = NULL;

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

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

   830 			}

   831 			d = d->last;

   832 			f = end + 1;

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

   834 				break;

   835 		}

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

   838 		*r = filenames[i].package;

   839 		free(filenames[i].name);

   840 	}

   842 	count_entries(&root);

   843 	array_init(&importer->set->files);

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

   846 	e->name = root.name | RAZOR_ENTRY_LAST;

   847 	e->start = 1;

   848 	e->packages = 0;

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

   852 	array_release(&importer->files);

   853 }

   855 static void

   856 build_package_file_lists(struct razor_set *set, unsigned long *rmap)

   857 {

   858 	struct razor_package *p, *packages;

   859 	struct array *pkgs;

   860 	struct razor_entry *e, *end;

   861 	unsigned long *r, *q;

   862 	int i, count;

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

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

   867 	e = set->files.data;

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

   869 	while (e < end) {

   870 		if (e->packages & RAZOR_IMMEDIATE) {

   871 			e->packages = rmap[e->packages & RAZOR_ENTRY_MASK] |

   872 				RAZOR_IMMEDIATE;

   873 			r = &e->packages;

   874 		} else {

   875 			r = (unsigned long *) set->package_pool.data + e->packages;

   876 		}

   878 		while (~*r) {

   879 			q = array_add(&pkgs[*r & RAZOR_ENTRY_MASK], sizeof *q);

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

   881 			if (*r++ & RAZOR_IMMEDIATE)

   882 				break;

   883 		}

   884 		e++;

   885 	}

   887 	packages = set->packages.data;

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

   889 		packages[i].files =

   890 			add_to_property_pool(&set->file_pool, &pkgs[i]);

   891 		array_release(&pkgs[i]);

   892 	}

   893 	free(pkgs);

   894 }

   896 struct razor_set *

   897 razor_importer_finish(struct razor_importer *importer)

   898 {

   899 	struct razor_set *set;

   900 	unsigned long *map, *rmap;

   901 	int i, count;

   903 	map = uniqueify_properties(importer->set, &importer->set->requires);

   904 	remap_links(&importer->set->requires_pool, map);

   905 	free(map);

   907 	map = uniqueify_properties(importer->set, &importer->set->provides);

   908 	remap_links(&importer->set->provides_pool, map);

   909 	free(map);

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

   912 	map = qsort_with_data(importer->set->packages.data,

   913 			      count,

   914 			      sizeof(struct razor_package),

   915 			      compare_packages,

   916 			      importer->set);

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

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

   920 		rmap[map[i]] = i;

   921 	free(map);

   923 	build_file_tree(importer);

   924 	remap_links(&importer->set->package_pool, rmap);

   925 	build_package_file_lists(importer->set, rmap);

   926 	free(rmap);

   929 	set = importer->set;

   930 	array_release(&importer->buckets);

   931 	free(importer);

   933 	return set;

   934 }

   936 void

   937 razor_set_list(struct razor_set *set, const char *pattern)

   938 {

   939 	struct razor_package *p, *end;

   940 	int with_version = 0;

   941 	char *pool;

   943 	pool = set->string_pool.data;

   944 	end = set->packages.data + set->packages.size;

   945 	for (p = set->packages.data; p < end; p++) {

   946 		if (pattern && fnmatch(pattern, &pool[p->name], 0) != 0)

   947 		    continue;

   948 		if (with_version)

   949 			printf("%s-%s\n", &pool[p->name], &pool[p->version]);

   950 		else

   951 			printf("%s\n", &pool[p->name]);

   952 	}

   953 }

   955 struct razor_set *bsearch_set;

   957 static int

   958 compare_package_name(const void *key, const void *data)

   959 {

   960 	const struct razor_package *p = data;

   961 	char *pool;

   963 	pool = bsearch_set->string_pool.data;

   965 	return strcmp(key, &pool[p->name]);

   966 }

   968 struct razor_package *

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

   970 {

   971 	bsearch_set = set;

   972 	return bsearch(package, set->packages.data,

   973 		       set->packages.size / sizeof(struct razor_package),

   974 		       sizeof(struct razor_package), compare_package_name);

   975 }

   977 static int

   978 compare_property_name(const void *key, const void *data)

   979 {

   980 	const struct razor_property *p = data;

   981 	char *pool;

   983 	pool = bsearch_set->string_pool.data;

   985 	return strcmp(key, &pool[p->name]);

   986 }

   988 struct razor_property *

   989 razor_set_get_property(struct razor_set *set,

   990 		       struct array *properties,

   991 		       const char *property)

   992 {

   993 	struct razor_property *p, *start;

   995 	bsearch_set = set;

   996 	p = bsearch(property, properties->data,

   997 		    properties->size / sizeof(struct razor_property),

   998 		    sizeof(struct razor_property), compare_property_name);

  1000 	start = properties->data;

  1001 	while (p > start && (p - 1)->name == p->name)

  1002 		p--;

  1004 	return p;

  1005 }

  1007 static void

  1008 razor_set_list_all_properties(struct razor_set *set, struct array *properties)

  1009 {

  1010 	struct razor_property *p, *end;

  1011 	char *pool;

  1013 	pool = set->string_pool.data;

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

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

  1016 		printf("%s-%s\n", &pool[p->name], &pool[p->version]);

  1017 }

  1019 void

  1020 razor_set_list_requires(struct razor_set *set, const char *name)

  1021 {

  1022 	struct razor_property *p, *requires;

  1023 	struct razor_package *package;

  1024 	unsigned long *r;

  1025 	char *pool;

  1027 	if (name) {

  1028 		package = razor_set_get_package(set, name);

  1029 		r = (unsigned long *) set->requires_pool.data +

  1030 			package->requires;

  1031 		requires = set->requires.data;

  1032 		pool = set->string_pool.data;

  1033 		while (~*r) {

  1034 			p = &requires[*r++];

  1035 			printf("%s-%s\n", &pool[p->name], &pool[p->version]);

  1036 		}

  1037 	} else

  1038 		razor_set_list_all_properties(set, &set->requires);

  1039 }

  1041 void

  1042 razor_set_list_provides(struct razor_set *set, const char *name)

  1043 {

  1044 	struct razor_property *p, *provides;

  1045 	struct razor_package *package;

  1046 	unsigned long *r;

  1047 	char *pool;

  1049 	if (name) {

  1050 		package = razor_set_get_package(set, name);

  1051 		r = (unsigned long *) set->provides_pool.data +

  1052 			package->provides;

  1053 		provides = set->provides.data;

  1054 		pool = set->string_pool.data;

  1055 		while (~*r) {

  1056 			p = &provides[*r++];

  1057 			printf("%s-%s\n", &pool[p->name], &pool[p->version]);

  1058 		}

  1059 	} else

  1060 		razor_set_list_all_properties(set, &set->provides);

  1061 }

  1063 static void

  1064 razor_set_list_property_packages(struct razor_set *set,

  1065 				 struct array *properties,

  1066 				 const char *name,

  1067 				 const char *version)

  1068 {

  1069 	struct razor_property *property, *end;

  1070 	struct razor_package *p, *packages;

  1071 	unsigned long *r;

  1072 	char *pool;

  1074 	if (name == NULL)

  1075 		return;

  1077 	property = razor_set_get_property(set, properties, name);

  1078 	packages = set->packages.data;

  1079 	pool = set->string_pool.data;

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

  1081 	while (property < end && strcmp(name, &pool[property->name]) == 0) {

  1082 		if (version && versioncmp(version, &pool[property->version]) != 0)

  1083 			goto next;

  1084 		r = (unsigned long *)

  1085 			set->package_pool.data + property->packages;

  1086 		while (~*r) {

  1087 			p = &packages[*r++];

  1088 			printf("%s-%s\n",

  1089 			       &pool[p->name], &pool[p->version]);

  1090 		}

  1091 	next:

  1092 		property++;

  1093 	}

  1094 }

  1096 void

  1097 razor_set_list_requires_packages(struct razor_set *set,

  1098 				 const char *name,

  1099 				 const char *version)

  1100 {

  1101 	razor_set_list_property_packages(set, &set->requires, name, version);

  1102 }

  1104 void

  1105 razor_set_list_provides_packages(struct razor_set *set,

  1106 				 const char *name,

  1107 				 const char *version)

  1108 {

  1109 	razor_set_list_property_packages(set, &set->provides, name, version);

  1110 }

  1112 static struct razor_entry *

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

  1114 {

  1115 	struct razor_entry *e;

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

  1117 	int len;

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

  1120 	do {

  1121 		n = pool + (e->name & RAZOR_ENTRY_MASK);

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

  1123 			return e;

  1124 		len = strlen(n);

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

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

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

  1128 		}

  1129 	} while (((e++)->name & RAZOR_ENTRY_LAST) == 0);

  1131 	return NULL;

  1132 }

  1134 static void

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

  1136 	 const char *prefix, const char *pattern)

  1137 {

  1138 	struct razor_entry *e;

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

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

  1142 	do {

  1143 		n = pool + (e->name & RAZOR_ENTRY_MASK);

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

  1145 			continue;

  1146 		printf("%s/%s%s\n", prefix, n, e->start > 0 ? "/" : "");

  1147 	} while (((e++)->name & RAZOR_ENTRY_LAST) == 0);

  1148 }

  1150 void

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

  1152 {

  1153 	struct razor_entry *e;

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

  1156 	if (pattern == NULL)

  1157 		pattern = "/";

  1159 	strcpy(buffer, pattern);

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

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

  1162 		base = NULL;

  1163 	} else {

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

  1165 		if (p) {

  1166 			*p = '\0';

  1167 			base = p + 1;

  1168 		} else {

  1169 			base = NULL;

  1170 		}

  1171 	}

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

  1173 	if (e->start != 0)

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

  1175 }

  1177 void

  1178 razor_set_list_file_packages(struct razor_set *set, const char *filename)

  1179 {

  1180 	struct razor_entry *e;

  1181 	struct razor_package *packages, *p;

  1182 	const char *pool;

  1183 	unsigned long *r;

  1185 	e = find_entry(set, set->files.data, filename);

  1186 	if (e == NULL)

  1187 		return;

  1189 	if (e->packages & RAZOR_IMMEDIATE)

  1190 		r = &e->packages;

  1191 	else

  1192 		r = (unsigned long *) set->package_pool.data + e->packages;

  1194 	packages = set->packages.data;

  1195 	pool = set->string_pool.data;

  1196 	while (~*r) {

  1197 		p = &packages[*r & RAZOR_ENTRY_MASK];

  1198 		printf("%s-%s\n", &pool[p->name], &pool[p->version]);

  1199 		if (*r++ & RAZOR_IMMEDIATE)

  1200 			break;

  1201 	}

  1202 }

  1204 static unsigned long *

  1205 list_package_files(struct razor_set *set, unsigned long *r,

  1206 		   struct razor_entry *dir, unsigned long end,

  1207 		   char *prefix)

  1208 {

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

  1210 	unsigned long next;

  1211 	char *pool;

  1212 	int len;

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

  1215 	pool = set->string_pool.data;

  1217 	e = entries + dir->start;

  1218 	do {

  1219 		if (entries + *r == e) {

  1220 			printf("%s/%s\n", prefix,

  1221 			       pool + (e->name & RAZOR_ENTRY_MASK));

  1222 			r++;

  1223 			if (*r >= end)

  1224 				break;

  1225 		}

  1226 	} while (((e++)->name & RAZOR_ENTRY_LAST) == 0);

  1228 	e = entries + dir->start;

  1229 	do {

  1230 		if (e->start == 0)

  1231 			continue;

  1233 		if (e->name & RAZOR_ENTRY_LAST)

  1234 			next = end;

  1235 		else {

  1236 			f = e + 1;

  1237 			while (f->start == 0 && !(f->name & RAZOR_ENTRY_LAST))

  1238 				f++;

  1239 			if (f->start == 0)

  1240 				next = end;

  1241 			else

  1242 				next = f->start;

  1243 		}

  1245 		if (e->start <= *r && *r < next) {

  1246 			len = strlen(prefix);

  1247 			prefix[len] = '/';

  1248 			strcpy(prefix + len + 1,

  1249 			       pool + (e->name & RAZOR_ENTRY_MASK));

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

  1251 			prefix[len] = '\0';

  1252 			if (*r >= end)

  1253 				break;

  1254 		}

  1255 	} while (((e++)->name & RAZOR_ENTRY_LAST) == 0);

  1257 	return r;

  1258 }

  1260 void

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

  1262 {

  1263 	struct razor_package *package;

  1264 	unsigned long *r, end;

  1265 	char buffer[512];

  1267 	package = razor_set_get_package(set, name);

  1269 	r = (unsigned long *) set->file_pool.data + package->files;

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

  1271 	buffer[0] = '\0';

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

  1273 }

  1275 static void

  1276 razor_set_validate(struct razor_set *set, struct array *unsatisfied)

  1277 {

  1278 	struct razor_property *r, *p, *rend, *pend;

  1279 	unsigned long *u;

  1280 	char *pool;

  1282 	p = set->provides.data;

  1283 	rend = set->requires.data + set->requires.size;

  1284 	pend = set->provides.data + set->provides.size;

  1285 	pool = set->string_pool.data;

  1287 	for (r = set->requires.data; r < rend; r++) {

  1288 		while (p < pend && strcmp(&pool[r->name], &pool[p->name]) > 0)

  1289 			p++;

  1291 		/* If there is more than one version of a provides,

  1292 		 * seek to the end for the highest version. */

  1293 		while (p + 1 < pend && p->name == (p + 1)->name)

  1294 			p++;

  1296 		/* FIXME: We need to track property flags (<, <=, =

  1297 		 * etc) to properly determine if a requires is

  1298 		 * satisfied.  The current code doesn't track that the

  1299 		 * requires a = 1 isn't satisfied by a = 2 provides. */

  1301 		if (p == pend || strcmp(&pool[r->name], &pool[p->name]) != 0 ||

  1302 		    versioncmp(&pool[r->version], &pool[p->version]) > 0) {

  1303 			/* FIXME: We ignore file requires for now. */

  1304 			if (pool[r->name] == '/')

  1305 				continue;

  1306 			u = array_add(unsatisfied, sizeof *u);

  1307 			*u = r - (struct razor_property *) set->requires.data;

  1308 		}

  1309 	}

  1310 }

  1312 void

  1313 razor_set_list_unsatisfied(struct razor_set *set)

  1314 {

  1315 	struct array unsatisfied;

  1316 	struct razor_property *requires, *r;

  1317 	unsigned long *u, *end;

  1318 	char *pool;

  1320 	array_init(&unsatisfied);

  1321 	razor_set_validate(set, &unsatisfied);

  1323 	end = unsatisfied.data + unsatisfied.size;

  1324 	requires = set->requires.data;

  1325 	pool = set->string_pool.data;

  1327 	for (u = unsatisfied.data; u < end; u++) {

  1328 		r = requires + *u;

  1329 		printf("%s-%s not satisfied\n",

  1330 		       &pool[r->name], &pool[r->version]);

  1331 	}

  1333 	array_release(&unsatisfied);

  1334 }

  1336 #define UPSTREAM_SOURCE 0x80000000ul

  1337 #define INDEX_MASK 0x00fffffful

  1339 struct source {

  1340 	struct razor_set *set;

  1341 	unsigned long *requires_map;

  1342 	unsigned long *provides_map;

  1343 };

  1345 static void

  1346 prepare_source(struct source *source, struct razor_set *set)

  1347 {

  1348 	int count;

  1349 	size_t size;

  1351 	source->set = set;

  1353 	count = set->requires.size / sizeof (struct razor_property);

  1354 	size = count * sizeof *source->requires_map;

  1355 	source->requires_map = zalloc(size);

  1357 	count = set->provides.size / sizeof (struct razor_property);

  1358 	size = count * sizeof *source->provides_map;

  1359 	source->provides_map = zalloc(size);

  1360 }

  1362 static void

  1363 add_package(struct razor_importer *importer,

  1364 	    struct razor_package *package, struct source *source,

  1365 	    unsigned long flags)

  1366 {

  1367 	char *pool;

  1368 	unsigned long *r;

  1369 	struct razor_package *p;

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

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

  1373 	p->name = razor_importer_tokenize(importer, &pool[package->name]);

  1374 	p->name |= flags;

  1375 	p->version = razor_importer_tokenize(importer,

  1376 					     &pool[package->version]);

  1377 	p->requires = package->requires;

  1378 	p->provides = package->provides;

  1380 	r = (unsigned long *)

  1381 		source->set->requires_pool.data + package->requires;

  1382 	while (*r != ~0)

  1383 		source->requires_map[*r++] = 1;

  1385 	r = (unsigned long *)

  1386 		source->set->provides_pool.data + package->provides;

  1387 	while (*r != ~0)

  1388 		source->provides_map[*r++] = 1;

  1389 }

  1392 /* Build the new package list sorted by merging the two package lists.

  1393  * Build new string pool as we go. (for now we just re-use that part of

  1394  * the importer). */

  1395 static void

  1396 merge_packages(struct razor_importer *importer,

  1397 	       struct source *source1, struct source *source2,

  1398 	       struct array *packages)

  1399 {

  1400 	struct razor_package *upstream_packages, *p, *s, *send;

  1401 	char *spool, *upool;

  1402 	unsigned long *u, *uend;

  1403 	int cmp;

  1405 	upstream_packages = source2->set->packages.data;

  1407 	u = packages->data;

  1408 	uend = packages->data + packages->size;

  1409 	upool = source2->set->string_pool.data;

  1411 	s = source1->set->packages.data;

  1412 	send = source1->set->packages.data + source1->set->packages.size;

  1413 	spool = source1->set->string_pool.data;

  1415 	while (s < send) {

  1416 		p = upstream_packages + *u;

  1418 		if (u < uend)

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

  1420 		if (u >= uend || cmp < 0) {

  1421 			add_package(importer, s, source1, 0);

  1422 			s++;

  1423 		} else if (cmp == 0) {

  1424 			add_package(importer, p, source2, UPSTREAM_SOURCE);

  1425 			s++;

  1426 			u++;

  1427 		} else {

  1428 			add_package(importer, p, source2, UPSTREAM_SOURCE);

  1429 			u++;

  1430 		}

  1431 	}

  1432 }

  1434 static unsigned long

  1435 add_property(struct razor_importer *importer, struct array *properties,

  1436 	     const char *name, const char *version)

  1437 {

  1438 	struct razor_property *p;

  1440 	p = array_add(properties, sizeof *p);

  1441 	p->name = razor_importer_tokenize(importer, name);

  1442 	p->version = razor_importer_tokenize(importer, version);

  1444 	return p - (struct razor_property *) properties->data;

  1445 }

  1447 static void

  1448 merge_properties(struct array *properties,

  1449 		 struct razor_importer *importer,

  1450 		 struct razor_set *set1,

  1451 		 struct array *properties1,

  1452 		 unsigned long *map1,

  1453 		 struct razor_set *set2,

  1454 		 struct array *properties2,

  1455 		 unsigned long *map2)

  1456 {

  1457 	struct razor_property *p1, *p2;

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

  1459 	char *pool1, *pool2;

  1461 	i = 0;

  1462 	j = 0;

  1463 	pool1 = set1->string_pool.data;

  1464 	pool2 = set2->string_pool.data;

  1466 	count1 = properties1->size / sizeof *p1;

  1467 	count2 = properties2->size / sizeof *p2;

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

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

  1470 			i++;

  1471 			continue;

  1472 		}

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

  1474 			j++;

  1475 			continue;

  1476 		}

  1477 		p1 = (struct razor_property *) properties1->data + i;

  1478 		p2 = (struct razor_property *) properties2->data + j;

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

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

  1481 		else if (i < count1)

  1482 			cmp = -1;

  1483 		else

  1484 			cmp = 1;

  1485 		if (cmp == 0)

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

  1487 					 &pool2[p2->version]);

  1488 		if (cmp < 0) {

  1489 			map1[i++] = add_property(importer,

  1490 						 properties,

  1491 						 &pool1[p1->name],

  1492 						 &pool1[p1->version]);

  1493 		} else if (cmp > 0) {

  1494 			map2[j++] = add_property(importer,

  1495 						 properties,

  1496 						 &pool2[p2->name],

  1497 						 &pool2[p2->version]);

  1498 		} else  {

  1499 			map1[i++] = map2[j++] = add_property(importer,

  1500 							     properties,

  1501 							     &pool1[p1->name],

  1502 							     &pool1[p1->version]);

  1503 		}

  1504 	}

  1505 }

  1507 static unsigned long

  1508 emit_properties(struct array *source_pool, unsigned long index,

  1509 		unsigned long *map, struct array *pool)

  1510 {

  1511 	unsigned long r, *p, *q;

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

  1514 	p = (unsigned long *) source_pool->data + index;

  1515 	while (*p != ~0) {

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

  1517 		*q = map[*p++];

  1518 	}

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

  1521 	*q = ~0;

  1523 	return r;

  1524 }

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

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

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

  1529  * the arrays for their properties. */

  1530 static void

  1531 rebuild_package_lists(struct razor_set *set)

  1532 {

  1533 	int requires_count, provides_count;

  1534 	struct array *requires_pkgs, *provides_pkgs, *a;

  1535 	struct razor_package *pkg, *pkg_end;

  1536 	struct razor_property *prop, *prop_end;

  1537 	unsigned long *r, *q, *rpool, *ppool;

  1539 	requires_count = set->requires.size / sizeof (struct razor_property);

  1540 	provides_count = set->provides.size / sizeof (struct razor_property);

  1541 	requires_pkgs = zalloc(requires_count * sizeof *requires_pkgs);

  1542 	provides_pkgs = zalloc(provides_count * sizeof *provides_pkgs);

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

  1544 	rpool = set->requires_pool.data;

  1545 	ppool = set->provides_pool.data;

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

  1548 		for (r = &rpool[pkg->requires]; *r != ~0; r++) {

  1549 			q = array_add(&requires_pkgs[*r], sizeof *q);

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

  1551 		}

  1552 		for (r = &ppool[pkg->provides]; *r != ~0; r++) {

  1553 			q = array_add(&provides_pkgs[*r], sizeof *q);

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

  1555 		}

  1556 	}

  1558 	prop_end = set->requires.data + set->requires.size;

  1559 	a = requires_pkgs;

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

  1561 		prop->packages = add_to_property_pool(&set->requires_pool, a);

  1562 		array_release(a);

  1563 	}

  1564 	free(requires_pkgs);

  1566 	prop_end = set->provides.data + set->provides.size;

  1567 	a = provides_pkgs;

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

  1569 		prop->packages = add_to_property_pool(&set->provides_pool, a);

  1570 		array_release(a);

  1571 	}

  1572 	free(provides_pkgs);

  1573 }

  1575 /* Add packages from 'upstream' to 'set'.  The packages to add are

  1576  * specified by the 'packages' array, which is a sorted list of

  1577  * package indexes.  Returns a newly allocated package set.  Does not

  1578  * enforce validity of the resulting package set.

  1579  *

  1580  * This looks more complicated than it is.  An easy way to merge two

  1581  * package sets would be to just use a razor_importer, but that

  1582  * requires resorting, and is thus O(n log n).  We can do this in a

  1583  * linear sweep, but it gets a little more complicated.

  1584  */

  1585 struct razor_set *

  1586 razor_set_add(struct razor_set *set, struct razor_set *upstream,

  1587 	      struct array *packages)

  1588 {

  1589 	struct razor_set *result;

  1590 	struct razor_importer *importer;

  1591 	struct razor_package *p, *pend;

  1592 	struct source source, upstream_source;

  1594 	importer = razor_importer_new();

  1596 	prepare_source(&upstream_source, upstream);

  1597 	prepare_source(&source, set);

  1599 	merge_packages(importer, &source, &upstream_source, packages);

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

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

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

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

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

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

  1607 	 * property list for both sets. */

  1609 	merge_properties(&importer->set->requires, importer,

  1610 			 set, &set->requires, source.requires_map,

  1611 			 upstream, &upstream->requires,

  1612 			 upstream_source.requires_map);

  1613 	merge_properties(&importer->set->provides, importer,

  1614 			 set, &set->provides, source.provides_map,

  1615 			 upstream, &upstream->provides,

  1616 			 upstream_source.provides_map);

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

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

  1621 	pend = importer->set->packages.data + importer->set->packages.size;

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

  1623 		struct source *src;

  1625 		if (p->name & UPSTREAM_SOURCE)

  1626 			src = &upstream_source;

  1627 		else

  1628 			src = &source;

  1630 		p->requires = emit_properties(&src->set->requires_pool,

  1631 					      p->requires,

  1632 					      src->requires_map,

  1633 					      &importer->set->requires_pool);

  1634 		p->provides = emit_properties(&src->set->provides_pool,

  1635 					      p->provides,

  1636 					      src->provides_map,

  1637 					      &importer->set->provides_pool);

  1638 		p->name &= INDEX_MASK;

  1639 	}

  1641 	rebuild_package_lists(importer->set);

  1643 	result = importer->set;

  1644 	array_release(&importer->buckets);

  1645 	free(importer);

  1647 	return result;

  1648 }

  1650 void

  1651 razor_set_satisfy(struct razor_set *set, struct array *unsatisfied,

  1652 		  struct razor_set *upstream, struct array *list)

  1653 {

  1654 	struct razor_property *requires, *r;

  1655 	struct razor_property *p, *pend;

  1656 	unsigned long *u, *end, *pkg, *package_pool;

  1657 	char *pool, *upool;

  1659 	end = unsatisfied->data + unsatisfied->size;

  1660 	requires = set->requires.data;

  1661 	pool = set->string_pool.data;

  1663 	p = upstream->provides.data;

  1664 	pend = upstream->provides.data + upstream->provides.size;

  1665 	upool = upstream->string_pool.data;

  1666 	package_pool = upstream->package_pool.data;

  1668 	for (u = unsatisfied->data; u < end; u++) {

  1669 		r = requires + *u;

  1671 		while (p < pend && strcmp(&pool[r->name], &upool[p->name]) > 0)

  1672 			p++;

  1673 		/* If there is more than one version of a provides,

  1674 		 * seek to the end for the highest version. */

  1675 		while (p + 1 < pend && p->name == (p + 1)->name)

  1676 			p++;

  1678 		if (p == pend ||

  1679 		    strcmp(&pool[r->name], &upool[p->name]) != 0 ||

  1680 		    versioncmp(&pool[r->version], &upool[p->version]) > 0) {

  1681 			/* Do we need to track unsatisfiable requires

  1682 			 * as we go, or should we just do a

  1683 			 * razor_set_validate() at the end? */

  1684 		} else {

  1685 			pkg = array_add(list, sizeof *pkg);

  1686 			/* We just pull in the first package that provides */

  1687 			*pkg = package_pool[p->packages];

  1688 		}

  1689 	}

  1690 }

  1692 static void

  1693 find_packages(struct razor_set *set,

  1694 	      int count, const char **packages, struct array *list)

  1695 {

  1696 	struct razor_package *p;

  1697 	unsigned long *r;

  1698 	int i;

  1700 	/* FIXME: Sort the packages. */

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

  1702 		p = razor_set_get_package(set, packages[i]);

  1703 		r = array_add(list, sizeof *r);

  1704 		*r = p - (struct razor_package *) set->packages.data;

  1705 	}

  1706 }

  1708 static void

  1709 find_all_packages(struct razor_set *set,

  1710 		  struct razor_set *upstream, struct array *list)

  1711 {

  1712 	struct razor_package *p, *u, *pend, *uend;

  1713 	unsigned long *r;

  1714 	char *pool, *upool;

  1716 	pend = set->packages.data + set->packages.size;

  1717 	pool = set->string_pool.data;

  1718 	u = upstream->packages.data;

  1719 	uend = upstream->packages.data + upstream->packages.size;

  1720 	upool = upstream->string_pool.data;

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

  1723 		while (u < uend && strcmp(&pool[p->name], &upool[u->name]) > 0)

  1724 			u++;

  1725 		if (strcmp(&pool[p->name], &upool[u->name]) == 0) {

  1726 			r = array_add(list, sizeof *r);

  1727 			*r = u - (struct razor_package *) upstream->packages.data;

  1728 		}

  1729 	}

  1730 }

  1732 struct razor_set *

  1733 razor_set_update(struct razor_set *set, struct razor_set *upstream,

  1734 		 int count, const char **packages)

  1735 {

  1736 	struct razor_set *new;

  1737 	struct razor_package *upackages;

  1738 	struct array list, unsatisfied;

  1739 	char *pool;

  1740 	unsigned long *u, *end;

  1741 	int total = 0;

  1743 	array_init(&list);

  1744 	if (count > 0)

  1745 		find_packages(upstream, count, packages, &list);

  1746 	else

  1747 		find_all_packages(set, upstream, &list);

  1749 	end = list.data + list.size;

  1750 	upackages = upstream->packages.data;

  1751 	pool = upstream->string_pool.data;

  1752 	total += list.size / sizeof *u;

  1754 	while (list.size > 0) {

  1755 		new = razor_set_add(set, upstream, &list);

  1756 		array_release(&list);

  1757 		razor_set_destroy(set);

  1758 		set = new;

  1760 		array_init(&unsatisfied);

  1761 		razor_set_validate(new, &unsatisfied);

  1762 		array_init(&list);

  1763 		razor_set_satisfy(new, &unsatisfied, upstream, &list);

  1764 		array_release(&unsatisfied);

  1766 		end = list.data + list.size;

  1767 		upackages = upstream->packages.data;

  1768 		pool = upstream->string_pool.data;

  1769 		total += list.size / sizeof *u;

  1770 	}

  1772 	array_release(&list);

  1774 	return set;

  1775 }

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

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

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

  1780  **/

  1782 void

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

  1784 	       razor_package_callback_t callback, void *data)

  1785 {

  1786 	struct razor_package *p, *pend, *u, *uend;

  1787 	char *ppool, *upool;

  1788 	int res = 0;

  1790 	p = set->packages.data;

  1791 	pend = set->packages.data + set->packages.size;

  1792 	ppool = set->string_pool.data;

  1794 	u = upstream->packages.data;

  1795 	uend = upstream->packages.data + upstream->packages.size;

  1796 	upool = upstream->string_pool.data;

  1798 	while (p < pend || u < uend) {

  1799 		if (p < pend && u < uend) {

  1800 			res = strcmp(&ppool[p->name], &upool[u->name]);

  1801 			if (res == 0)

  1802 				res = versioncmp(&ppool[p->version],

  1803 						 &upool[u->version]);

  1804 		}

  1806 		if (u == uend || res < 0) {

  1807 			callback(&ppool[p->name], &ppool[p->version],

  1808 				 NULL, data);

  1809 			p++;

  1810 			continue;

  1811 		} else if (p == pend || res > 0) {

  1812 			callback(&upool[u->name], NULL, &upool[u->version],

  1813 				 data);

  1814 			u++;

  1815 			continue;

  1816 		} else {

  1817 			p++;

  1818 			u++;

  1819 		}

  1820 	}

  1821 }

author	Kristian H?gsberg <krh@redhat.com>
	Wed Oct 24 13:20:12 2007 -0400 (2007-10-24)
changeset 60	fca1ef50dd2c
parent 59	c525dec02ef4
child 61	b0e1638a9f96
permissions	-rw-r--r--