razor: razor.c@cfe57117efee

     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_ENTRY_LAST	0x80000000ul

    39 #define RAZOR_IMMEDIATE		0x80000000ul

    40 #define RAZOR_ENTRY_MASK	0x00fffffful

    42 #define RAZOR_STRING_POOL	0

    43 #define RAZOR_PACKAGES		1

    44 #define RAZOR_PROPERTIES	2

    45 #define RAZOR_FILES		3

    46 #define RAZOR_PACKAGE_POOL	4

    47 #define RAZOR_PROPERTY_POOL	5

    48 #define RAZOR_FILE_POOL		6

    50 struct razor_package {

    51 	unsigned long name;

    52 	unsigned long version;

    53 	unsigned long properties;

    54 	unsigned long files;

    55 };

    57 struct razor_property {

    58 	unsigned long name;

    59 	unsigned long version;

    60 	unsigned long packages;

    61 };

    63 struct razor_entry {

    64 	unsigned long name;

    65 	unsigned long start;

    66 	unsigned long packages;

    67 };

    69 struct razor_set {

    70 	struct array string_pool;

    71  	struct array packages;

    72  	struct array properties;

    73  	struct array files;

    74 	struct array package_pool;

    75  	struct array property_pool;

    76  	struct array file_pool;

    77 	struct razor_set_header *header;

    78 };

    80 struct import_entry {

    81 	unsigned long package;

    82 	char *name;

    83 };

    85 struct import_directory {

    86 	unsigned long name, count;

    87 	struct array files;

    88 	struct array packages;

    89 	struct import_directory *last;

    90 };

    92 struct razor_importer {

    93 	struct razor_set *set;

    94 	struct array buckets;

    95 	struct razor_package *package;

    96 	struct array properties;

    97 	struct array files;

    98 };

   100 static void

   101 array_init(struct array *array)

   102 {

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

   104 }

   106 static void

   107 array_release(struct array *array)

   108 {

   109 	free(array->data);

   110 }

   112 static void *

   113 array_add(struct array *array, int size)

   114 {

   115 	int alloc;

   116 	void *data, *p;

   118 	if (array->alloc > 0)

   119 		alloc = array->alloc;

   120 	else

   121 		alloc = 16;

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

   124 		alloc *= 2;

   126 	if (array->alloc < alloc) {

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

   128 		if (data == NULL)

   129 			return 0;

   130 		array->data = data;

   131 		array->alloc = alloc;

   132 	}

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

   135 	array->size += size;

   137 	return p;

   138 }

   140 static int

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

   142 {

   143 	int rest, len;

   145 	rest = size;

   146 	while (rest > 0) {

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

   148 		if (len < 0)

   149 			return -1;

   150 		rest -= len;

   151 	}

   153 	return 0;

   154 }

   156 static void *

   157 zalloc(size_t size)

   158 {

   159 	void *p;

   161 	p = malloc(size);

   162 	memset(p, 0, size);

   164 	return p;

   165 }

   167 struct razor_set_section razor_sections[] = {

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

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

   170 	{ RAZOR_PROPERTIES,	offsetof(struct razor_set, properties) },

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

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

   173 	{ RAZOR_PROPERTY_POOL,	offsetof(struct razor_set, property_pool) },

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

   175 };

   177 struct razor_set *

   178 razor_set_create(void)

   179 {

   180 	return zalloc(sizeof(struct razor_set));

   181 }

   183 struct razor_set *

   184 razor_set_open(const char *filename)

   185 {

   186 	struct razor_set *set;

   187 	struct razor_set_section *s;

   188 	struct stat stat;

   189 	struct array *array;

   190 	int fd;

   192 	set = zalloc(sizeof *set);

   193 	fd = open(filename, O_RDONLY);

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

   195 		return NULL;

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

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

   198 		free(set);

   199 		return NULL;

   200 	}

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

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

   204 			continue;

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

   206 			continue;

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

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

   209 		array->size = s->size;

   210 		array->alloc = s->size;

   211 	}

   212 	close(fd);

   214 	return set;

   215 }

   217 void

   218 razor_set_destroy(struct razor_set *set)

   219 {

   220 	unsigned int size;

   221 	struct array *a;

   222 	int i;

   224 	if (set->header) {

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

   226 			;

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

   228 		munmap(set->header, size);

   229 	} else {

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

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

   232 			free(a->data);

   233 		}

   234 	}

   236 	free(set);

   237 }

   239 int

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

   241 {

   242 	char data[4096];

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

   244 	struct array *a;

   245 	unsigned long offset;

   246 	int i, fd;

   248 	memset(data, 0, sizeof data);

   249 	header->magic = RAZOR_MAGIC;

   250 	header->version = RAZOR_VERSION;

   251 	offset = sizeof data;

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

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

   255 			continue;

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

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

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

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

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

   261 	}

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

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

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

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

   268 	if (fd < 0)

   269 		return -1;

   271 	write_to_fd(fd, data, sizeof data);

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

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

   274 			continue;

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

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

   277 	}

   279 	close(fd);

   281 	return 0;

   282 }

   284 static unsigned int

   285 hash_string(const char *key)

   286 {

   287 	const char *p;

   288 	unsigned int hash = 0;

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

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

   293 	return hash;

   294 }

   296 static unsigned long

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

   298 {

   299 	unsigned int mask, start, i;

   300 	unsigned long *b;

   301 	char *pool;

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

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

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

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

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

   310 		if (*b == 0)

   311 			return 0;

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

   314 			return *b;

   315 	}

   317 	return 0;

   318 }

   320 static unsigned long

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

   322 {

   323 	int len;

   324 	char *p;

   326 	len = strlen(key) + 1;

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

   328 	memcpy(p, key, len);

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

   331 }

   333 static unsigned long

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

   335 {

   336 	unsigned long  *p;

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

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

   340 	p[properties->size / sizeof *p - 1] |= RAZOR_IMMEDIATE;

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

   343 }

   345 static void

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

   347 {

   348 	unsigned int mask, start, i;

   349 	unsigned long *b;

   350 	const char *key;

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

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

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

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

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

   358 		if (*b == 0) {

   359 			*b = value;

   360 			break;

   361 		}

   362 	}

   363 }

   365 static unsigned long

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

   367 {

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

   369 	int alloc;

   371 	alloc = importer->buckets.alloc;

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

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

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

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

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

   377 			value = *b;

   378 			if (value != 0) {

   379 				*b = 0;

   380 				do_insert(importer, value);

   381 			}

   382 		}

   383 	}

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

   386 	do_insert (importer, value);

   388 	return value;

   389 }

   391 static unsigned long

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

   393 {

   394 	unsigned long token;

   396 	if (string == NULL)

   397 		return razor_importer_tokenize(importer, "");

   399 	token = razor_importer_lookup(importer, string);

   400 	if (token != 0)

   401 		return token;

   403 	return razor_importer_insert(importer, string);

   404 }

   406 void

   407 razor_importer_begin_package(struct razor_importer *importer,

   408 			     const char *name, const char *version)

   409 {

   410 	struct razor_package *p;

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

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

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

   416 	importer->package = p;

   417 	array_init(&importer->properties);

   418 }

   420 void

   421 razor_importer_finish_package(struct razor_importer *importer)

   422 {

   423 	struct razor_package *p;

   425 	p = importer->package;

   426 	p->properties = add_to_property_pool(&importer->set->property_pool,

   427 					     &importer->properties);

   429 	array_release(&importer->properties);

   430 }

   432 void

   433 razor_importer_add_property(struct razor_importer *importer,

   434 			    const char *name, const char *version,

   435 			    enum razor_property_type type)

   436 {

   437 	struct razor_property *p;

   438 	unsigned long *r;

   440 	p = array_add(&importer->set->properties, sizeof *p);

   441 	p->name = razor_importer_tokenize(importer, name) | (type << 30);

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

   443 	p->packages = importer->package -

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

   446 	r = array_add(&importer->properties, sizeof *r);

   447 	*r = p - (struct razor_property *) importer->set->properties.data;

   448 }

   450 void

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

   452 {

   453 	struct import_entry *e;

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

   457 	e->package = importer->package -

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

   459 	e->name = strdup(name);

   460 }

   462 struct razor_importer *

   463 razor_importer_new(void)

   464 {

   465 	struct razor_importer *importer;

   467 	importer = zalloc(sizeof *importer);

   468 	importer->set = razor_set_create();

   470 	return importer;

   471 }

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

   474 					const void *p,

   475 					void *data);

   477 struct qsort_context {

   478 	size_t size;

   479 	compare_with_data_func_t compare;

   480 	void *data;

   481 };

   483 static void

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

   485 {

   486 	char buffer[size];

   488 	memcpy(buffer, p1, size);

   489 	memcpy(p1, p2, size);

   490 	memcpy(p2, buffer, size);

   491 }

   493 static void

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

   495 		  struct qsort_context *ctx)

   496 {

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

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

   499 	int left, right, result;

   500 	size_t size = ctx->size;

   502 	p = base;

   503 	start = base;

   504 	end = base + nelem * size;

   505 	mp = map;

   506 	mstart = map;

   507 	mend = map + nelem;

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

   510 	while (p < end) {

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

   512 		if (result < 0) {

   513 			qsort_swap(p, start, size);

   514 			tmp = *mp;

   515 			*mp = *mstart;

   516 			*mstart = tmp;

   517 			if (start == pivot)

   518 				pivot = p;

   519 			start += size;

   520 			mstart++;

   521 			p += size;

   522 			mp++;

   523 		} else if (result == 0) {

   524 			p += size;

   525 			mp++;

   526 		} else {

   527  			end -= size;

   528 			mend--;

   529 			qsort_swap(p, end, size);

   530 			tmp = *mp;

   531 			*mp = *mend;

   532 			*mend = tmp;

   533 			if (end == pivot)

   534 				pivot = p;

   535 		}

   536 	}

   538 	left = (start - base) / size;

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

   540 	if (left > 1)

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

   542 	if (right > 1)

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

   544 }

   546 unsigned long *

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

   548 		compare_with_data_func_t compare, void *data)

   549 {

   550 	struct qsort_context ctx;

   551 	unsigned long *map;

   552 	int i;

   554 	ctx.size = size;

   555 	ctx.compare = compare;

   556 	ctx.data = data;

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

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

   560 		map[i] = i;

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

   564 	return map;

   565 }

   567 static int

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

   569 {

   570 	const char *p1, *p2;

   571 	long n1, n2;

   572 	int res;

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

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

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

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

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

   580 	if (res < 0) {

   581 		n1 = 0;

   582 		p1 = s1;

   583 		p2++;

   584 	} else if (res > 0) {

   585 		p1++;

   586 		n2 = 0;

   587 		p2 = s2;

   588 	}

   590 	if (n1 != n2)

   591 		return n1 - n2;

   592 	while (*p1 && *p2) {

   593 		if (*p1 != *p2)

   594 			return *p1 - *p2;

   595 		p1++;

   596 		p2++;

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

   598 			return versioncmp(p1, p2);

   599 	}

   601 	return *p1 - *p2;

   602 }

   605 static int

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

   607 {

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

   609 	struct razor_set *set = data;

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

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

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

   614 	else

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

   616 }

   618 static int

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

   620 {

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

   622 	struct razor_set *set = data;

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

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

   626 		return versioncmp(&pool[prop1->version],

   627 				  &pool[prop2->version]);

   628 	else if ((prop1->name & RAZOR_ENTRY_MASK) == (prop2->name & RAZOR_ENTRY_MASK))

   629 		return (prop1->name >> 30) - (prop2->name >> 30);

   630 	else

   631 		return strcmp(&pool[prop1->name & RAZOR_ENTRY_MASK],

   632 			      &pool[prop2->name & RAZOR_ENTRY_MASK]);

   633 }

   635 static unsigned long *

   636 uniqueify_properties(struct razor_set *set)

   637 {

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

   639 	struct array *pkgs, *p;

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

   641 	int i, count, unique;

   643 	count = set->properties.size / sizeof(struct razor_property);

   644 	map = qsort_with_data(set->properties.data,

   645 			      count,

   646 			      sizeof(struct razor_property),

   647 			      compare_properties,

   648 			      set);

   650 	rp_end = set->properties.data + set->properties.size;

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

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

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

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

   655 			up++;

   656 			up->name = rp->name;

   657 			up->version = rp->version;

   658 		}

   660 		unique = up - (struct razor_property *) set->properties.data;

   661 		rmap[map[i]] = unique;

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

   663 		*r = rp->packages;

   664 	}

   665 	free(map);

   667 	up++;

   668 	set->properties.size = (void *) up - set->properties.data;

   669 	rp_end = up;

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

   671 		if (p->size / sizeof *r == 1) {

   672 			r = p->data;

   673 			rp->packages = *r | RAZOR_IMMEDIATE;

   674 		} else {

   675 			rp->packages =

   676 				add_to_property_pool(&set->package_pool, p);

   677 		}

   678 		array_release(p);

   679 	}

   681 	free(pkgs);

   683 	return rmap;

   684 }

   686 static void

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

   688 {

   689 	unsigned long *p, *end;

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

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

   693 		*p = map[*p & RAZOR_ENTRY_MASK] | (*p & ~RAZOR_ENTRY_MASK);

   694 }

   696 static int

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

   698 {

   699 	const struct import_entry *e1 = p1;

   700 	const struct import_entry *e2 = p2;

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

   703 }

   705 static void

   706 count_entries(struct import_directory *d)

   707 {

   708 	struct import_directory *p, *end;

   710 	p = d->files.data;

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

   712 	d->count = 0;

   713 	while (p < end) {

   714 		count_entries(p);

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

   716 		p++;

   717 	}

   718 }

   720 static void

   721 serialize_files(struct razor_set *set,

   722 		struct import_directory *d, struct array *array)

   723 {

   724 	struct import_directory *p, *end;

   725 	struct razor_entry *e = NULL;

   726 	unsigned long s, *r;

   728 	p = d->files.data;

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

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

   731 	while (p < end) {

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

   733 		e->name = p->name;

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

   735 		s += p->count;

   737 		if (p->packages.size == 0) {

   738 			/* FIXME: We need to make sure this is handled

   739 			 * correctly as the empty list. */

   740 			e->packages = 0 | RAZOR_IMMEDIATE;

   741 		} else if (p->packages.size / sizeof *r == 1) {

   742 			r = p->packages.data;

   743 			e->packages = *r | RAZOR_IMMEDIATE;

   744 		} else {

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

   746 							   &p->packages);

   747 		}

   748 		array_release(&p->packages);

   749 		p++;

   750 	}

   751 	if (e != NULL)

   752 		e->name |= RAZOR_ENTRY_LAST;

   754 	p = d->files.data;

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

   756 	while (p < end) {

   757 		serialize_files(set, p, array);

   758 		p++;

   759 	}

   760 }

   762 static void

   763 remap_property_package_links(struct array *properties, unsigned long *rmap)

   764 {

   765 	struct razor_property *p, *end;

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

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

   769 		if (p->packages & RAZOR_IMMEDIATE)

   770 			p->packages = rmap[p->packages & RAZOR_ENTRY_MASK] |

   771 				RAZOR_IMMEDIATE;

   772 }

   774 static void

   775 build_file_tree(struct razor_importer *importer)

   776 {

   777 	int count, i, length;

   778 	struct import_entry *filenames;

   779 	char *f, *end;

   780 	unsigned long name, *r;

   781 	char dirname[256];

   782 	struct import_directory *d, root;

   783 	struct razor_entry *e;

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

   786 	qsort_with_data(importer->files.data,

   787 			count,

   788 			sizeof (struct import_entry),

   789 			compare_filenames,

   790 			NULL);

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

   793 	array_init(&root.files);

   794 	array_init(&root.packages);

   795 	root.last = NULL;

   797 	filenames = importer->files.data;

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

   799 		f = filenames[i].name;

   800 		if (*f != '/')

   801 			continue;

   802 		f++;

   804 		d = &root;

   805 		while (*f) {

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

   807 			if (end == NULL)

   808 				end = f + strlen(f);

   809 			length = end - f;

   810 			memcpy(dirname, f, length);

   811 			dirname[length] ='\0';

   812 			name = razor_importer_tokenize(importer, dirname);

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

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

   815 				d->last->name = name;

   816 				d->last->last = NULL;

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

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

   819 			}

   820 			d = d->last;

   821 			f = end + 1;

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

   823 				break;

   824 		}

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

   827 		*r = filenames[i].package;

   828 		free(filenames[i].name);

   829 	}

   831 	count_entries(&root);

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

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

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

   836 	e->start = 1;

   837 	e->packages = 0;

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

   841 	array_release(&importer->files);

   842 }

   844 static void

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

   846 {

   847 	struct razor_package *p, *packages;

   848 	struct array *pkgs;

   849 	struct razor_entry *e, *end;

   850 	unsigned long *r, *q;

   851 	int i, count;

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

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

   856 	e = set->files.data;

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

   858 	while (e < end) {

   859 		if (e->packages & RAZOR_IMMEDIATE) {

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

   861 				RAZOR_IMMEDIATE;

   862 			r = &e->packages;

   863 		} else {

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

   865 		}

   867 		while (1) {

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

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

   870 			if (*r++ & RAZOR_IMMEDIATE)

   871 				break;

   872 		}

   873 		e++;

   874 	}

   876 	packages = set->packages.data;

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

   878 		packages[i].files =

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

   880 		array_release(&pkgs[i]);

   881 	}

   882 	free(pkgs);

   883 }

   885 struct razor_set *

   886 razor_importer_finish(struct razor_importer *importer)

   887 {

   888 	struct razor_set *set;

   889 	unsigned long *map, *rmap;

   890 	int i, count;

   892 	map = uniqueify_properties(importer->set);

   893 	remap_links(&importer->set->property_pool, map);

   894 	free(map);

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

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

   898 			      count,

   899 			      sizeof(struct razor_package),

   900 			      compare_packages,

   901 			      importer->set);

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

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

   905 		rmap[map[i]] = i;

   906 	free(map);

   908 	build_file_tree(importer);

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

   910 	build_package_file_lists(importer->set, rmap);

   911 	remap_property_package_links(&importer->set->properties, rmap);

   912 	free(rmap);

   914 	set = importer->set;

   915 	array_release(&importer->buckets);

   916 	free(importer);

   918 	return set;

   919 }

   921 void

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

   923 {

   924 	struct razor_package *p, *end;

   925 	int with_version = 0;

   926 	char *pool;

   928 	pool = set->string_pool.data;

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

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

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

   932 		    continue;

   933 		if (with_version)

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

   935 		else

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

   937 	}

   938 }

   940 struct razor_set *bsearch_set;

   942 static int

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

   944 {

   945 	const struct razor_package *p = data;

   946 	char *pool;

   948 	pool = bsearch_set->string_pool.data;

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

   951 }

   953 struct razor_package *

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

   955 {

   956 	bsearch_set = set;

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

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

   959 		       sizeof(struct razor_package), compare_package_name);

   960 }

   962 static int

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

   964 {

   965 	const struct razor_property *p = data;

   966 	char *pool;

   968 	pool = bsearch_set->string_pool.data;

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

   971 }

   973 struct razor_property *

   974 razor_set_get_property(struct razor_set *set, const char *property)

   975 {

   976 	struct razor_property *p, *start;

   978 	bsearch_set = set;

   979 	p = bsearch(property, set->properties.data,

   980 		    set->properties.size / sizeof(struct razor_property),

   981 		    sizeof(struct razor_property), compare_property_name);

   983 	start = set->properties.data;

   984 	while (p > start &&

   985 	       ((p - 1)->name & RAZOR_ENTRY_MASK) ==

   986 	       (p->name & RAZOR_ENTRY_MASK))

   987 		p--;

   989 	return p;

   990 }

   992 void

   993 razor_set_list_properties(struct razor_set *set, const char *name,

   994 			  enum razor_property_type type)

   995 {

   996 	struct razor_property *p, *properties, *end;

   997 	struct razor_package *package;

   998 	unsigned long *r;

   999 	char *pool;

  1001 	pool = set->string_pool.data;

  1003 	if (name) {

  1004 		package = razor_set_get_package(set, name);

  1005 		r = (unsigned long *) set->property_pool.data +

  1006 			package->properties;

  1007 		properties = set->properties.data;

  1008 		while (1) {

  1009 			p = &properties[*r & RAZOR_ENTRY_MASK];

  1010 			if ((p->name >> 30) != type)

  1011 				goto next;

  1012 			if (pool[p->version] == '\0')

  1013 				printf("%s\n",

  1014 				       &pool[p->name & RAZOR_ENTRY_MASK]);

  1015 			else

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

  1017 				       &pool[p->name & RAZOR_ENTRY_MASK],

  1018 				       &pool[p->version]);

  1019 		next:

  1020 			if (*r++ & RAZOR_IMMEDIATE)

  1021 				break;

  1022 		}

  1023 	} else {

  1024 		end = set->properties.data + set->properties.size;

  1025 		for (p = set->properties.data; p < end; p++) {

  1026 			if ((p->name >> 30) != type)

  1027 				continue;

  1028 			if (pool[p->version] == '\0')

  1029 				printf("%s\n",

  1030 				       &pool[p->name & RAZOR_ENTRY_MASK]);

  1031 			else

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

  1033 				       &pool[p->name & RAZOR_ENTRY_MASK],

  1034 				       &pool[p->version]);

  1035 		}

  1036 	}

  1037 }

  1039 void

  1040 razor_set_list_property_packages(struct razor_set *set,

  1041 				 const char *name,

  1042 				 const char *version,

  1043 				 enum razor_property_type type)

  1044 {

  1045 	struct razor_property *property, *end;

  1046 	struct razor_package *p, *packages;

  1047 	unsigned long *r;

  1048 	char *pool;

  1050 	if (name == NULL)

  1051 		return;

  1053 	property = razor_set_get_property(set, name);

  1054 	packages = set->packages.data;

  1055 	pool = set->string_pool.data;

  1056 	end = set->properties.data + set->properties.size;

  1057 	while (property < end &&

  1058 	       strcmp(name, &pool[property->name & RAZOR_ENTRY_MASK]) == 0) {

  1059 		if (version &&

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

  1061 			goto next;

  1062 		if (type != (property->name >> 30))

  1063 			goto next;

  1065 		if (property->packages & RAZOR_IMMEDIATE)

  1066 			r = &property->packages;

  1067 		else

  1068 			r = (unsigned long *)

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

  1070 		while (1) {

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

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

  1073 			       &pool[p->name & RAZOR_ENTRY_MASK],

  1074 			       &pool[p->version]);

  1075 			if (*r++ & RAZOR_IMMEDIATE)

  1076 				break;

  1077 		}

  1078 	next:

  1079 		property++;

  1080 	}

  1081 }

  1083 static struct razor_entry *

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

  1085 {

  1086 	struct razor_entry *e;

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

  1088 	int len;

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

  1091 	do {

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

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

  1094 			return e;

  1095 		len = strlen(n);

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

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

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

  1099 		}

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

  1102 	return NULL;

  1103 }

  1105 static void

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

  1107 	 const char *prefix, const char *pattern)

  1108 {

  1109 	struct razor_entry *e;

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

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

  1113 	do {

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

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

  1116 			continue;

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

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

  1119 }

  1121 void

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

  1123 {

  1124 	struct razor_entry *e;

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

  1127 	if (pattern == NULL)

  1128 		pattern = "/";

  1130 	strcpy(buffer, pattern);

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

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

  1133 		base = NULL;

  1134 	} else {

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

  1136 		if (p) {

  1137 			*p = '\0';

  1138 			base = p + 1;

  1139 		} else {

  1140 			base = NULL;

  1141 		}

  1142 	}

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

  1144 	if (e->start != 0)

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

  1146 }

  1148 void

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

  1150 {

  1151 	struct razor_entry *e;

  1152 	struct razor_package *packages, *p;

  1153 	const char *pool;

  1154 	unsigned long *r;

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

  1157 	if (e == NULL)

  1158 		return;

  1160 	if (e->packages & RAZOR_IMMEDIATE)

  1161 		r = &e->packages;

  1162 	else

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

  1165 	packages = set->packages.data;

  1166 	pool = set->string_pool.data;

  1167 	while (1) {

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

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

  1170 		if (*r++ & RAZOR_IMMEDIATE)

  1171 			break;

  1172 	}

  1173 }

  1175 static unsigned long *

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

  1177 		   struct razor_entry *dir, unsigned long end,

  1178 		   char *prefix)

  1179 {

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

  1181 	unsigned long next;

  1182 	char *pool;

  1183 	int len;

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

  1186 	pool = set->string_pool.data;

  1188 	e = entries + dir->start;

  1189 	do {

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

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

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

  1193 			r++;

  1194 			if (*r >= end)

  1195 				break;

  1196 		}

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

  1199 	e = entries + dir->start;

  1200 	do {

  1201 		if (e->start == 0)

  1202 			continue;

  1204 		if (e->name & RAZOR_ENTRY_LAST)

  1205 			next = end;

  1206 		else {

  1207 			f = e + 1;

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

  1209 				f++;

  1210 			if (f->start == 0)

  1211 				next = end;

  1212 			else

  1213 				next = f->start;

  1214 		}

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

  1217 			len = strlen(prefix);

  1218 			prefix[len] = '/';

  1219 			strcpy(prefix + len + 1,

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

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

  1222 			prefix[len] = '\0';

  1223 			if (*r >= end)

  1224 				break;

  1225 		}

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

  1228 	return r;

  1229 }

  1231 void

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

  1233 {

  1234 	struct razor_package *package;

  1235 	unsigned long *r, end;

  1236 	char buffer[512];

  1238 	package = razor_set_get_package(set, name);

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

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

  1242 	buffer[0] = '\0';

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

  1244 }

  1246 static void

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

  1248 {

  1249 	struct razor_property *r, *p, *end;

  1250 	unsigned long *u;

  1251 	char *pool;

  1253 	end = set->properties.data + set->properties.size;

  1254 	pool = set->string_pool.data;

  1256 	for (r = set->properties.data, p = r; r < end; r++) {

  1257 		if (r->name >> 30 != RAZOR_PROPERTY_REQUIRES)

  1258 			continue;

  1260 		if ((r->name & RAZOR_ENTRY_MASK) != (p->name & RAZOR_ENTRY_MASK)) {

  1261 			p = r;

  1262 			while (p < end && p->name == r->name)

  1263 				p++;

  1264 		}

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

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

  1268 		/* FIXME: This doesn't work if we have a series of

  1269 		 * requires a = 1, provides a = 1, requires a = 2,

  1270 		 * provides a = 2, as the kernel and kernel-devel

  1271 		 * does.*/

  1272 		while (p + 1 < end && p->name == (p + 1)->name)

  1273 			p++;

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

  1276 		 * etc) to properly determine if a requires is

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

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

  1280 		if (p == end ||

  1281 		    (p->name >> 30) != RAZOR_PROPERTY_PROVIDES ||

  1282 		    (r->name & RAZOR_ENTRY_MASK) != (p->name & RAZOR_ENTRY_MASK) ||

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

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

  1285 			if (pool[r->name & RAZOR_ENTRY_MASK] == '/')

  1286 				continue;

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

  1288 			*u = r - (struct razor_property *) set->properties.data;

  1289 		}

  1290 	}

  1291 }

  1293 void

  1294 razor_set_list_unsatisfied(struct razor_set *set)

  1295 {

  1296 	struct array unsatisfied;

  1297 	struct razor_property *properties, *r;

  1298 	unsigned long *u, *end;

  1299 	char *pool;

  1301 	array_init(&unsatisfied);

  1302 	razor_set_validate(set, &unsatisfied);

  1304 	end = unsatisfied.data + unsatisfied.size;

  1305 	properties = set->properties.data;

  1306 	pool = set->string_pool.data;

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

  1309 		r = properties + *u;

  1310 		if (pool[r->version] == '\0')

  1311 			printf("%ss not satisfied\n",

  1312 			       &pool[r->name & RAZOR_ENTRY_MASK]);

  1313 		else

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

  1315 			       &pool[r->name & RAZOR_ENTRY_MASK],

  1316 			       &pool[r->version]);

  1317 	}

  1319 	array_release(&unsatisfied);

  1320 }

  1322 #define UPSTREAM_SOURCE 0x80000000ul

  1323 #define INDEX_MASK 0x00fffffful

  1325 struct source {

  1326 	struct razor_set *set;

  1327 	unsigned long *property_map;

  1328 };

  1330 static void

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

  1332 {

  1333 	int count;

  1334 	size_t size;

  1336 	source->set = set;

  1338 	count = set->properties.size / sizeof (struct razor_property);

  1339 	size = count * sizeof *source->property_map;

  1340 	source->property_map = zalloc(size);

  1341 }

  1343 static void

  1344 add_package(struct razor_importer *importer,

  1345 	    struct razor_package *package, struct source *source,

  1346 	    unsigned long flags)

  1347 {

  1348 	char *pool;

  1349 	unsigned long *r;

  1350 	struct razor_package *p;

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

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

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

  1355 	p->name |= flags;

  1356 	p->version = razor_importer_tokenize(importer,

  1357 					     &pool[package->version]);

  1358 	p->properties = package->properties;

  1360 	if (package->properties & RAZOR_IMMEDIATE)

  1361 		r = &package->properties;

  1362 	else

  1363 		r = (unsigned long *)

  1364 			source->set->property_pool.data + package->properties;

  1365 	while (1) {

  1366 		source->property_map[*r & RAZOR_ENTRY_MASK] = 1;

  1367 		if (*r++ & RAZOR_IMMEDIATE)

  1368 			break;

  1369 	}

  1370 }

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

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

  1375  * the importer). */

  1376 static void

  1377 merge_packages(struct razor_importer *importer,

  1378 	       struct source *source1, struct source *source2,

  1379 	       struct array *packages)

  1380 {

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

  1382 	char *spool, *upool;

  1383 	unsigned long *u, *uend;

  1384 	int cmp;

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

  1388 	u = packages->data;

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

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

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

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

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

  1396 	while (s < send) {

  1397 		p = upstream_packages + *u;

  1399 		if (u < uend)

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

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

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

  1403 			s++;

  1404 		} else if (cmp == 0) {

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

  1406 			s++;

  1407 			u++;

  1408 		} else {

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

  1410 			u++;

  1411 		}

  1412 	}

  1413 }

  1415 static unsigned long

  1416 add_property(struct razor_importer *importer,

  1417 	     const char *name, const char *version)

  1418 {

  1419 	struct razor_property *p;

  1421 	p = array_add(&importer->set->properties, sizeof *p);

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

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

  1425 	return p - (struct razor_property *) importer->set->properties.data;

  1426 }

  1428 static void

  1429 merge_properties(struct razor_importer *importer,

  1430 		 struct razor_set *set1,

  1431 		 unsigned long *map1,

  1432 		 struct razor_set *set2,

  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 = set1->properties.size / sizeof *p1;

  1445 	count2 = set2->properties.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 *) set1->properties.data + i;

  1456 		p2 = (struct razor_property *) set2->properties.data + j;

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

  1458 			cmp = strcmp(&pool1[p1->name & RAZOR_ENTRY_MASK],

  1459 				     &pool2[p2->name & RAZOR_ENTRY_MASK]);

  1460 		else if (i < count1)

  1461 			cmp = -1;

  1462 		else

  1463 			cmp = 1;

  1464 		if (cmp == 0)

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

  1466 					 &pool2[p2->version]);

  1467 		if (cmp < 0) {

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

  1469 						 &pool1[p1->name & RAZOR_ENTRY_MASK],

  1470 						 &pool1[p1->version]);

  1471 		} else if (cmp > 0) {

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

  1473 						 &pool2[p2->name & RAZOR_ENTRY_MASK],

  1474 						 &pool2[p2->version]);

  1475 		} else  {

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

  1477 							     &pool1[p1->name & RAZOR_ENTRY_MASK],

  1478 							     &pool1[p1->version]);

  1479 		}

  1480 	}

  1481 }

  1483 static unsigned long

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

  1485 		unsigned long *map, struct array *pool)

  1486 {

  1487 	unsigned long r, *p, *q;

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

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

  1491 	while (1) {

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

  1493 		*q = map[*p & RAZOR_ENTRY_MASK] | (*p & ~RAZOR_ENTRY_MASK);

  1494 		if (*p++ & RAZOR_ENTRY_LAST)

  1495 			break;

  1496 	}

  1498 	return r;

  1499 }

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

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

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

  1504  * the arrays for their properties. */

  1505 static void

  1506 rebuild_package_lists(struct razor_set *set)

  1507 {

  1508 	struct array *pkgs, *a;

  1509 	struct razor_package *pkg, *pkg_end;

  1510 	struct razor_property *prop, *prop_end;

  1511 	unsigned long *r, *q, *pool;

  1512 	int count;

  1514 	count = set->properties.size / sizeof (struct razor_property);

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

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

  1517 	pool = set->property_pool.data;

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

  1520 		for (r = &pool[pkg->properties]; ; r++) {

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

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

  1523 			if (*r & RAZOR_IMMEDIATE)

  1524 				break;

  1525 		}

  1526 	}

  1528 	prop_end = set->properties.data + set->properties.size;

  1529 	a = pkgs;

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

  1531 		if (a->size / sizeof *r == 1) {

  1532 			r = a->data;

  1533 			prop->packages = *r | RAZOR_IMMEDIATE;

  1534 		} else {

  1535 			prop->packages =

  1536 				add_to_property_pool(&set->property_pool, a);

  1537 		}

  1538 		array_release(a);

  1539 	}

  1540 	free(pkgs);

  1541 }

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

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

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

  1546  * enforce validity of the resulting package set.

  1547  *

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

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

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

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

  1552  */

  1553 struct razor_set *

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

  1555 	      struct array *packages)

  1556 {

  1557 	struct razor_set *result;

  1558 	struct razor_importer *importer;

  1559 	struct razor_package *p, *pend;

  1560 	struct source source, upstream_source;

  1562 	importer = razor_importer_new();

  1564 	prepare_source(&upstream_source, upstream);

  1565 	prepare_source(&source, set);

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

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

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

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

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

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

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

  1575 	 * property list for both sets. */

  1577 	merge_properties(importer,

  1578 			 set, source.property_map,

  1579 			 upstream, upstream_source.property_map);

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

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

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

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

  1586 		struct source *src;

  1588 		if (p->name & UPSTREAM_SOURCE)

  1589 			src = &upstream_source;

  1590 		else

  1591 			src = &source;

  1593 		p->properties = emit_properties(&src->set->property_pool,

  1594 						p->properties,

  1595 						src->property_map,

  1596 						&importer->set->property_pool);

  1597 		p->name &= INDEX_MASK;

  1598 	}

  1600 	rebuild_package_lists(importer->set);

  1602 	result = importer->set;

  1603 	array_release(&importer->buckets);

  1604 	free(importer);

  1606 	return result;

  1607 }

  1609 void

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

  1611 		  struct razor_set *upstream, struct array *list)

  1612 {

  1613 	struct razor_property *requires, *r;

  1614 	struct razor_property *p, *pend;

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

  1616 	char *pool, *upool;

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

  1619 	requires = set->properties.data;

  1620 	pool = set->string_pool.data;

  1622 	p = upstream->properties.data;

  1623 	pend = upstream->properties.data + upstream->properties.size;

  1624 	upool = upstream->string_pool.data;

  1625 	package_pool = upstream->package_pool.data;

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

  1628 		r = requires + *u;

  1630 		while (p < pend &&

  1631 		       strcmp(&pool[r->name & RAZOR_ENTRY_MASK],

  1632 			      &upool[p->name & RAZOR_ENTRY_MASK]) > 0 &&

  1633 		       (p->name >> 30) != RAZOR_PROPERTY_PROVIDES)

  1634 			p++;

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

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

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

  1638 			p++;

  1640 		if (p == pend ||

  1641 		    strcmp(&pool[r->name & RAZOR_ENTRY_MASK],

  1642 			   &upool[p->name & RAZOR_ENTRY_MASK]) != 0 ||

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

  1644 			/* Do we need to track unsatisfiable requires

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

  1646 			 * razor_set_validate() at the end? */

  1647 		} else {

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

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

  1650 			if (p->packages & RAZOR_IMMEDIATE)

  1651 				*pkg = p->packages & RAZOR_ENTRY_MASK;

  1652 			else

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

  1654 		}

  1655 	}

  1656 }

  1658 static void

  1659 find_packages(struct razor_set *set,

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

  1661 {

  1662 	struct razor_package *p;

  1663 	unsigned long *r;

  1664 	int i;

  1666 	/* FIXME: Sort the packages. */

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

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

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

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

  1671 	}

  1672 }

  1674 static void

  1675 find_all_packages(struct razor_set *set,

  1676 		  struct razor_set *upstream, struct array *list)

  1677 {

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

  1679 	unsigned long *r;

  1680 	char *pool, *upool;

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

  1683 	pool = set->string_pool.data;

  1684 	u = upstream->packages.data;

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

  1686 	upool = upstream->string_pool.data;

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

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

  1690 			u++;

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

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

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

  1694 		}

  1695 	}

  1696 }

  1698 struct razor_set *

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

  1700 		 int count, const char **packages)

  1701 {

  1702 	struct razor_set *new;

  1703 	struct razor_package *upackages;

  1704 	struct array list, unsatisfied;

  1705 	char *pool;

  1706 	unsigned long *u, *end;

  1707 	int total = 0;

  1709 	array_init(&list);

  1710 	if (count > 0)

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

  1712 	else

  1713 		find_all_packages(set, upstream, &list);

  1715 	end = list.data + list.size;

  1716 	upackages = upstream->packages.data;

  1717 	pool = upstream->string_pool.data;

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

  1720 	while (list.size > 0) {

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

  1722 		array_release(&list);

  1723 		razor_set_destroy(set);

  1724 		set = new;

  1726 		array_init(&unsatisfied);

  1727 		razor_set_validate(new, &unsatisfied);

  1728 		array_init(&list);

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

  1730 		array_release(&unsatisfied);

  1732 		end = list.data + list.size;

  1733 		upackages = upstream->packages.data;

  1734 		pool = upstream->string_pool.data;

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

  1736 	}

  1738 	array_release(&list);

  1740 	return set;

  1741 }

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

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

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

  1746  **/

  1748 void

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

  1750 	       razor_package_callback_t callback, void *data)

  1751 {

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

  1753 	char *ppool, *upool;

  1754 	int res = 0;

  1756 	p = set->packages.data;

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

  1758 	ppool = set->string_pool.data;

  1760 	u = upstream->packages.data;

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

  1762 	upool = upstream->string_pool.data;

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

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

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

  1767 			if (res == 0)

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

  1769 						 &upool[u->version]);

  1770 		}

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

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

  1774 				 NULL, data);

  1775 			p++;

  1776 			continue;

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

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

  1779 				 data);

  1780 			u++;

  1781 			continue;

  1782 		} else {

  1783 			p++;

  1784 			u++;

  1785 		}

  1786 	}

  1787 }

author	Kristian H?gsberg <krh@redhat.com>
	Sat Nov 03 17:15:29 2007 -0400 (2007-11-03)
changeset 67	cfe57117efee
parent 64	8e37a9f8fd70
child 69	35ca1ba469ec
permissions	-rw-r--r--