razor: razor.c@c525dec02ef4

     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_ENTRY_MASK 0x00fffffful

   746 static void

   747 serialize_files(struct razor_set *set,

   748 		struct import_directory *d, struct array *array)

   749 {

   750 	struct import_directory *p, *end;

   751 	struct razor_entry *e = NULL;

   752 	unsigned long s;

   754 	p = d->files.data;

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

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

   757 	while (p < end) {

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

   759 		e->name = p->name;

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

   761 		s += p->count;

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

   763 						   &p->packages);

   764 		array_release(&p->packages);

   765 		p++;

   766 	}

   767 	if (e != NULL)

   768 		e->name |= RAZOR_ENTRY_LAST;

   770 	p = d->files.data;

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

   772 	while (p < end) {

   773 		serialize_files(set, p, array);

   774 		p++;

   775 	}

   776 }

   778 static void

   779 build_file_tree(struct razor_importer *importer)

   780 {

   781 	int count, i, length;

   782 	struct import_entry *filenames;

   783 	char *f, *end;

   784 	unsigned long name, *r;

   785 	char dirname[256];

   786 	struct import_directory *d, root;

   787 	struct razor_entry *e;

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

   790 	qsort_with_data(importer->files.data,

   791 			count,

   792 			sizeof (struct import_entry),

   793 			compare_filenames,

   794 			NULL);

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

   797 	array_init(&root.files);

   798 	array_init(&root.packages);

   799 	root.last = NULL;

   801 	filenames = importer->files.data;

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

   803 		f = filenames[i].name;

   804 		if (*f != '/')

   805 			continue;

   806 		f++;

   808 		d = &root;

   809 		while (*f) {

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

   811 			if (end == NULL)

   812 				end = f + strlen(f);

   813 			length = end - f;

   814 			memcpy(dirname, f, length);

   815 			dirname[length] ='\0';

   816 			name = razor_importer_tokenize(importer, dirname);

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

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

   819 				d->last->name = name;

   820 				d->last->last = NULL;

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

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

   823 			}

   824 			d = d->last;

   825 			f = end + 1;

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

   827 				break;

   828 		}

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

   831 		*r = filenames[i].package;

   832 		free(filenames[i].name);

   833 	}

   835 	count_entries(&root);

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

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

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

   840 	e->start = 1;

   841 	e->packages = 0;

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

   845 	array_release(&importer->files);

   846 }

   848 static void

   849 build_package_file_lists(struct razor_set *set)

   850 {

   851 	struct razor_package *p, *packages;

   852 	struct array *pkgs;

   853 	struct razor_entry *e, *end;

   854 	unsigned long *r, *q;

   855 	int i, count;

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

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

   860 	e = set->files.data;

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

   862 	while (e < end) {

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

   864 		while (~*r) {

   865 			q = array_add(&pkgs[*r++], sizeof *q);

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

   867 		}

   868 		e++;

   869 	}

   871 	packages = set->packages.data;

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

   873 		packages[i].files =

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

   875 		array_release(&pkgs[i]);

   876 	}

   877 	free(pkgs);

   878 }

   880 struct razor_set *

   881 razor_importer_finish(struct razor_importer *importer)

   882 {

   883 	struct razor_set *set;

   884 	unsigned long *map, *rmap;

   885 	int i, count;

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

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

   889 	free(map);

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

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

   893 	free(map);

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

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

   897 			      count,

   898 			      sizeof(struct razor_package),

   899 			      compare_packages,

   900 			      importer->set);

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

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

   904 		rmap[map[i]] = i;

   905 	free(map);

   907 	build_file_tree(importer);

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

   909 	free(rmap);

   911 	build_package_file_lists(importer->set);

   913 	set = importer->set;

   914 	array_release(&importer->buckets);

   915 	free(importer);

   917 	return set;

   918 }

   920 void

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

   922 {

   923 	struct razor_package *p, *end;

   924 	int with_version = 0;

   925 	char *pool;

   927 	pool = set->string_pool.data;

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

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

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

   931 		    continue;

   932 		if (with_version)

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

   934 		else

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

   936 	}

   937 }

   939 struct razor_set *bsearch_set;

   941 static int

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

   943 {

   944 	const struct razor_package *p = data;

   945 	char *pool;

   947 	pool = bsearch_set->string_pool.data;

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

   950 }

   952 struct razor_package *

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

   954 {

   955 	bsearch_set = set;

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

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

   958 		       sizeof(struct razor_package), compare_package_name);

   959 }

   961 static int

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

   963 {

   964 	const struct razor_property *p = data;

   965 	char *pool;

   967 	pool = bsearch_set->string_pool.data;

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

   970 }

   972 struct razor_property *

   973 razor_set_get_property(struct razor_set *set,

   974 		       struct array *properties,

   975 		       const char *property)

   976 {

   977 	struct razor_property *p, *start;

   979 	bsearch_set = set;

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

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

   982 		    sizeof(struct razor_property), compare_property_name);

   984 	start = properties->data;

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

   986 		p--;

   988 	return p;

   989 }

   991 static void

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

   993 {

   994 	struct razor_property *p, *end;

   995 	char *pool;

   997 	pool = set->string_pool.data;

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

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

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

  1001 }

  1003 void

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

  1005 {

  1006 	struct razor_property *p, *requires;

  1007 	struct razor_package *package;

  1008 	unsigned long *r;

  1009 	char *pool;

  1011 	if (name) {

  1012 		package = razor_set_get_package(set, name);

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

  1014 			package->requires;

  1015 		requires = set->requires.data;

  1016 		pool = set->string_pool.data;

  1017 		while (~*r) {

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

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

  1020 		}

  1021 	} else

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

  1023 }

  1025 void

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

  1027 {

  1028 	struct razor_property *p, *provides;

  1029 	struct razor_package *package;

  1030 	unsigned long *r;

  1031 	char *pool;

  1033 	if (name) {

  1034 		package = razor_set_get_package(set, name);

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

  1036 			package->provides;

  1037 		provides = set->provides.data;

  1038 		pool = set->string_pool.data;

  1039 		while (~*r) {

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

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

  1042 		}

  1043 	} else

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

  1045 }

  1047 static void

  1048 razor_set_list_property_packages(struct razor_set *set,

  1049 				 struct array *properties,

  1050 				 const char *name,

  1051 				 const char *version)

  1052 {

  1053 	struct razor_property *property, *end;

  1054 	struct razor_package *p, *packages;

  1055 	unsigned long *r;

  1056 	char *pool;

  1058 	if (name == NULL)

  1059 		return;

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

  1062 	packages = set->packages.data;

  1063 	pool = set->string_pool.data;

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

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

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

  1067 			goto next;

  1068 		r = (unsigned long *)

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

  1070 		while (~*r) {

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

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

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

  1074 		}

  1075 	next:

  1076 		property++;

  1077 	}

  1078 }

  1080 void

  1081 razor_set_list_requires_packages(struct razor_set *set,

  1082 				 const char *name,

  1083 				 const char *version)

  1084 {

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

  1086 }

  1088 void

  1089 razor_set_list_provides_packages(struct razor_set *set,

  1090 				 const char *name,

  1091 				 const char *version)

  1092 {

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

  1094 }

  1096 static struct razor_entry *

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

  1098 {

  1099 	struct razor_entry *e;

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

  1101 	int len;

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

  1104 	do {

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

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

  1107 			return e;

  1108 		len = strlen(n);

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

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

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

  1112 		}

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

  1115 	return NULL;

  1116 }

  1118 static void

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

  1120 	 const char *prefix, const char *pattern)

  1121 {

  1122 	struct razor_entry *e;

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

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

  1126 	do {

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

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

  1129 			continue;

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

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

  1132 }

  1134 void

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

  1136 {

  1137 	struct razor_entry *e;

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

  1140 	if (pattern == NULL)

  1141 		pattern = "/";

  1143 	strcpy(buffer, pattern);

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

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

  1146 		base = NULL;

  1147 	} else {

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

  1149 		if (p) {

  1150 			*p = '\0';

  1151 			base = p + 1;

  1152 		} else {

  1153 			base = NULL;

  1154 		}

  1155 	}

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

  1157 	if (e->start != 0)

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

  1159 }

  1161 void

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

  1163 {

  1164 	struct razor_entry *e;

  1165 	struct razor_package *packages, *p;

  1166 	const char *pool;

  1167 	unsigned long *r;

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

  1170 	if (e == NULL)

  1171 		return;

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

  1174 	packages = set->packages.data;

  1175 	pool = set->string_pool.data;

  1176 	while (~*r) {

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

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

  1179 	}

  1180 }

  1182 static unsigned long *

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

  1184 		   struct razor_entry *dir, unsigned long end,

  1185 		   char *prefix)

  1186 {

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

  1188 	unsigned long next;

  1189 	char *pool;

  1190 	int len;

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

  1193 	pool = set->string_pool.data;

  1195 	e = entries + dir->start;

  1196 	do {

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

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

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

  1200 			r++;

  1201 			if (*r >= end)

  1202 				break;

  1203 		}

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

  1206 	e = entries + dir->start;

  1207 	do {

  1208 		if (e->start == 0)

  1209 			continue;

  1211 		if (e->name & RAZOR_ENTRY_LAST)

  1212 			next = end;

  1213 		else {

  1214 			f = e + 1;

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

  1216 				f++;

  1217 			if (f->start == 0)

  1218 				next = end;

  1219 			else

  1220 				next = f->start;

  1221 		}

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

  1224 			len = strlen(prefix);

  1225 			prefix[len] = '/';

  1226 			strcpy(prefix + len + 1,

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

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

  1229 			prefix[len] = '\0';

  1230 			if (*r >= end)

  1231 				break;

  1232 		}

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

  1235 	return r;

  1236 }

  1238 void

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

  1240 {

  1241 	struct razor_package *package;

  1242 	unsigned long *r, end;

  1243 	char buffer[512];

  1245 	package = razor_set_get_package(set, name);

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

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

  1249 	buffer[0] = '\0';

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

  1251 }

  1253 static void

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

  1255 {

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

  1257 	unsigned long *u;

  1258 	char *pool;

  1260 	p = set->provides.data;

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

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

  1263 	pool = set->string_pool.data;

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

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

  1267 			p++;

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

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

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

  1272 			p++;

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

  1275 		 * etc) to properly determine if a requires is

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

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

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

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

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

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

  1283 				continue;

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

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

  1286 		}

  1287 	}

  1288 }

  1290 void

  1291 razor_set_list_unsatisfied(struct razor_set *set)

  1292 {

  1293 	struct array unsatisfied;

  1294 	struct razor_property *requires, *r;

  1295 	unsigned long *u, *end;

  1296 	char *pool;

  1298 	array_init(&unsatisfied);

  1299 	razor_set_validate(set, &unsatisfied);

  1301 	end = unsatisfied.data + unsatisfied.size;

  1302 	requires = set->requires.data;

  1303 	pool = set->string_pool.data;

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

  1306 		r = requires + *u;

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

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

  1309 	}

  1311 	array_release(&unsatisfied);

  1312 }

  1314 #define UPSTREAM_SOURCE 0x80000000ul

  1315 #define INDEX_MASK 0x00fffffful

  1317 struct source {

  1318 	struct razor_set *set;

  1319 	unsigned long *requires_map;

  1320 	unsigned long *provides_map;

  1321 };

  1323 static void

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

  1325 {

  1326 	int count;

  1327 	size_t size;

  1329 	source->set = set;

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

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

  1333 	source->requires_map = zalloc(size);

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

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

  1337 	source->provides_map = zalloc(size);

  1338 }

  1340 static void

  1341 add_package(struct razor_importer *importer,

  1342 	    struct razor_package *package, struct source *source,

  1343 	    unsigned long flags)

  1344 {

  1345 	char *pool;

  1346 	unsigned long *r;

  1347 	struct razor_package *p;

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

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

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

  1352 	p->name |= flags;

  1353 	p->version = razor_importer_tokenize(importer,

  1354 					     &pool[package->version]);

  1355 	p->requires = package->requires;

  1356 	p->provides = package->provides;

  1358 	r = (unsigned long *)

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

  1360 	while (*r != ~0)

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

  1363 	r = (unsigned long *)

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

  1365 	while (*r != ~0)

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

  1367 }

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

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

  1372  * the importer). */

  1373 static void

  1374 merge_packages(struct razor_importer *importer,

  1375 	       struct source *source1, struct source *source2,

  1376 	       struct array *packages)

  1377 {

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

  1379 	char *spool, *upool;

  1380 	unsigned long *u, *uend;

  1381 	int cmp;

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

  1385 	u = packages->data;

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

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

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

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

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

  1393 	while (s < send) {

  1394 		p = upstream_packages + *u;

  1396 		if (u < uend)

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

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

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

  1400 			s++;

  1401 		} else if (cmp == 0) {

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

  1403 			s++;

  1404 			u++;

  1405 		} else {

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

  1407 			u++;

  1408 		}

  1409 	}

  1410 }

  1412 static unsigned long

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

  1414 	     const char *name, const char *version)

  1415 {

  1416 	struct razor_property *p;

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

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

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

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

  1423 }

  1425 static void

  1426 merge_properties(struct array *properties,

  1427 		 struct razor_importer *importer,

  1428 		 struct razor_set *set1,

  1429 		 struct array *properties1,

  1430 		 unsigned long *map1,

  1431 		 struct razor_set *set2,

  1432 		 struct array *properties2,

  1433 		 unsigned long *map2)

  1434 {

  1435 	struct razor_property *p1, *p2;

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

  1437 	char *pool1, *pool2;

  1439 	i = 0;

  1440 	j = 0;

  1441 	pool1 = set1->string_pool.data;

  1442 	pool2 = set2->string_pool.data;

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

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

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

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

  1448 			i++;

  1449 			continue;

  1450 		}

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

  1452 			j++;

  1453 			continue;

  1454 		}

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

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

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

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

  1459 		else if (i < count1)

  1460 			cmp = -1;

  1461 		else

  1462 			cmp = 1;

  1463 		if (cmp == 0)

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

  1465 					 &pool2[p2->version]);

  1466 		if (cmp < 0) {

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

  1468 						 properties,

  1469 						 &pool1[p1->name],

  1470 						 &pool1[p1->version]);

  1471 		} else if (cmp > 0) {

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

  1473 						 properties,

  1474 						 &pool2[p2->name],

  1475 						 &pool2[p2->version]);

  1476 		} else  {

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

  1478 							     properties,

  1479 							     &pool1[p1->name],

  1480 							     &pool1[p1->version]);

  1481 		}

  1482 	}

  1483 }

  1485 static unsigned long

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

  1487 		unsigned long *map, struct array *pool)

  1488 {

  1489 	unsigned long r, *p, *q;

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

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

  1493 	while (*p != ~0) {

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

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

  1496 	}

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

  1499 	*q = ~0;

  1501 	return r;

  1502 }

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

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

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

  1507  * the arrays for their properties. */

  1508 static void

  1509 rebuild_package_lists(struct razor_set *set)

  1510 {

  1511 	int requires_count, provides_count;

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

  1513 	struct razor_package *pkg, *pkg_end;

  1514 	struct razor_property *prop, *prop_end;

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

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

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

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

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

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

  1522 	rpool = set->requires_pool.data;

  1523 	ppool = set->provides_pool.data;

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

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

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

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

  1529 		}

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

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

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

  1533 		}

  1534 	}

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

  1537 	a = requires_pkgs;

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

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

  1540 		array_release(a);

  1541 	}

  1542 	free(requires_pkgs);

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

  1545 	a = provides_pkgs;

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

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

  1548 		array_release(a);

  1549 	}

  1550 	free(provides_pkgs);

  1551 }

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

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

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

  1556  * enforce validity of the resulting package set.

  1557  *

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

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

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

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

  1562  */

  1563 struct razor_set *

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

  1565 	      struct array *packages)

  1566 {

  1567 	struct razor_set *result;

  1568 	struct razor_importer *importer;

  1569 	struct razor_package *p, *pend;

  1570 	struct source source, upstream_source;

  1572 	importer = razor_importer_new();

  1574 	prepare_source(&upstream_source, upstream);

  1575 	prepare_source(&source, set);

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

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

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

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

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

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

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

  1585 	 * property list for both sets. */

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

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

  1589 			 upstream, &upstream->requires,

  1590 			 upstream_source.requires_map);

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

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

  1593 			 upstream, &upstream->provides,

  1594 			 upstream_source.provides_map);

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

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

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

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

  1601 		struct source *src;

  1603 		if (p->name & UPSTREAM_SOURCE)

  1604 			src = &upstream_source;

  1605 		else

  1606 			src = &source;

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

  1609 					      p->requires,

  1610 					      src->requires_map,

  1611 					      &importer->set->requires_pool);

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

  1613 					      p->provides,

  1614 					      src->provides_map,

  1615 					      &importer->set->provides_pool);

  1616 		p->name &= INDEX_MASK;

  1617 	}

  1619 	rebuild_package_lists(importer->set);

  1621 	result = importer->set;

  1622 	array_release(&importer->buckets);

  1623 	free(importer);

  1625 	return result;

  1626 }

  1628 void

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

  1630 		  struct razor_set *upstream, struct array *list)

  1631 {

  1632 	struct razor_property *requires, *r;

  1633 	struct razor_property *p, *pend;

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

  1635 	char *pool, *upool;

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

  1638 	requires = set->requires.data;

  1639 	pool = set->string_pool.data;

  1641 	p = upstream->provides.data;

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

  1643 	upool = upstream->string_pool.data;

  1644 	package_pool = upstream->package_pool.data;

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

  1647 		r = requires + *u;

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

  1650 			p++;

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

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

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

  1654 			p++;

  1656 		if (p == pend ||

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

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

  1659 			/* Do we need to track unsatisfiable requires

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

  1661 			 * razor_set_validate() at the end? */

  1662 		} else {

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

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

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

  1666 		}

  1667 	}

  1668 }

  1670 static void

  1671 find_packages(struct razor_set *set,

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

  1673 {

  1674 	struct razor_package *p;

  1675 	unsigned long *r;

  1676 	int i;

  1678 	/* FIXME: Sort the packages. */

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

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

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

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

  1683 	}

  1684 }

  1686 static void

  1687 find_all_packages(struct razor_set *set,

  1688 		  struct razor_set *upstream, struct array *list)

  1689 {

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

  1691 	unsigned long *r;

  1692 	char *pool, *upool;

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

  1695 	pool = set->string_pool.data;

  1696 	u = upstream->packages.data;

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

  1698 	upool = upstream->string_pool.data;

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

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

  1702 			u++;

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

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

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

  1706 		}

  1707 	}

  1708 }

  1710 struct razor_set *

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

  1712 		 int count, const char **packages)

  1713 {

  1714 	struct razor_set *new;

  1715 	struct razor_package *upackages;

  1716 	struct array list, unsatisfied;

  1717 	char *pool;

  1718 	unsigned long *u, *end;

  1719 	int total = 0;

  1721 	array_init(&list);

  1722 	if (count > 0)

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

  1724 	else

  1725 		find_all_packages(set, upstream, &list);

  1727 	end = list.data + list.size;

  1728 	upackages = upstream->packages.data;

  1729 	pool = upstream->string_pool.data;

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

  1732 	while (list.size > 0) {

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

  1734 		array_release(&list);

  1735 		razor_set_destroy(set);

  1736 		set = new;

  1738 		array_init(&unsatisfied);

  1739 		razor_set_validate(new, &unsatisfied);

  1740 		array_init(&list);

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

  1742 		array_release(&unsatisfied);

  1744 		end = list.data + list.size;

  1745 		upackages = upstream->packages.data;

  1746 		pool = upstream->string_pool.data;

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

  1748 	}

  1750 	array_release(&list);

  1752 	return set;

  1753 }

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

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

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

  1758  **/

  1760 void

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

  1762 	       razor_package_callback_t callback, void *data)

  1763 {

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

  1765 	char *ppool, *upool;

  1766 	int res = 0;

  1768 	p = set->packages.data;

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

  1770 	ppool = set->string_pool.data;

  1772 	u = upstream->packages.data;

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

  1774 	upool = upstream->string_pool.data;

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

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

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

  1779 			if (res == 0)

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

  1781 						 &upool[u->version]);

  1782 		}

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

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

  1786 				 NULL, data);

  1787 			p++;

  1788 			continue;

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

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

  1791 				 data);

  1792 			u++;

  1793 			continue;

  1794 		} else {

  1795 			p++;

  1796 			u++;

  1797 		}

  1798 	}

  1799 }

author	Kristian H?gsberg <krh@redhat.com>
	Wed Oct 24 12:21:29 2007 -0400 (2007-10-24)
changeset 59	c525dec02ef4
parent 57	016c61ca11e2
child 60	fca1ef50dd2c
permissions	-rw-r--r--