1.1 --- a/razor.c Thu Sep 20 19:28:09 2007 -0400
1.2 +++ b/razor.c Sat Sep 29 19:25:38 2007 -0400
1.3 @@ -79,8 +79,6 @@
1.4 struct import_property_context requires;
1.5 struct import_property_context provides;
1.6 struct razor_package *package;
1.7 - unsigned long *requires_map;
1.8 - unsigned long *provides_map;
1.9 };
1.10
1.11 static void
1.12 @@ -932,92 +930,318 @@
1.13 array_release(&unsatisfied);
1.14 }
1.15
1.16 +#define UPSTREAM_SOURCE 0x80000000ul
1.17 +#define INDEX_MASK 0x00fffffful
1.18 +
1.19 +struct source {
1.20 + struct razor_set *set;
1.21 + unsigned long *requires_map;
1.22 + unsigned long *provides_map;
1.23 +};
1.24 +
1.25 +static void
1.26 +prepare_source(struct source *source, struct razor_set *set)
1.27 +{
1.28 + int count;
1.29 + size_t size;
1.30 +
1.31 + source->set = set;
1.32 +
1.33 + count = set->requires.size / sizeof (struct razor_property);
1.34 + size = count * sizeof *source->requires_map;
1.35 + source->requires_map = zalloc(size);
1.36 +
1.37 + count = set->provides.size / sizeof (struct razor_property);
1.38 + size = count * sizeof *source->provides_map;
1.39 + source->provides_map = zalloc(size);
1.40 +}
1.41 +
1.42 static void
1.43 add_package(struct razor_importer *importer,
1.44 - struct razor_package *package, struct razor_set *set)
1.45 + struct razor_package *package, struct source *source,
1.46 + unsigned long flags)
1.47 {
1.48 char *pool;
1.49 unsigned long *r;
1.50 - struct razor_property *p, *properties;
1.51 + struct razor_package *p;
1.52
1.53 - pool = set->string_pool.data;
1.54 - razor_importer_begin_package(importer,
1.55 - &pool[package->name],
1.56 - &pool[package->version]);
1.57 + pool = source->set->string_pool.data;
1.58 + p = array_add(&importer->set->packages, sizeof *p);
1.59 + p->name = razor_importer_tokenize(importer, &pool[package->name]);
1.60 + p->name |= flags;
1.61 + p->version = razor_importer_tokenize(importer,
1.62 + &pool[package->version]);
1.63 + p->requires = package->requires;
1.64 + p->provides = package->provides;
1.65
1.66 - r = (unsigned long *) set->requires_pool.data + package->requires;
1.67 - properties = set->requires.data;
1.68 - while (~*r) {
1.69 - p = &properties[*r++];
1.70 - razor_importer_add_requires(importer,
1.71 - &pool[p->name], &pool[p->version]);
1.72 + r = (unsigned long *)
1.73 + source->set->requires_pool.data + package->requires;
1.74 + while (*r != ~0)
1.75 + source->requires_map[*r++] = 1;
1.76 +
1.77 + r = (unsigned long *)
1.78 + source->set->provides_pool.data + package->provides;
1.79 + while (*r != ~0)
1.80 + source->provides_map[*r++] = 1;
1.81 +}
1.82 +
1.83 +
1.84 +/* Build the new package list sorted by merging the two package lists.
1.85 + * Build new string pool as we go. (for now we just re-use that part of
1.86 + * the importer). */
1.87 +static void
1.88 +merge_packages(struct razor_importer *importer,
1.89 + struct source *source1, struct source *source2,
1.90 + struct array *packages)
1.91 +{
1.92 + struct razor_package *upstream_packages, *p, *s, *send;
1.93 + char *spool, *upool;
1.94 + unsigned long *u, *uend;
1.95 + int cmp;
1.96 +
1.97 + upstream_packages = source2->set->packages.data;
1.98 +
1.99 + u = packages->data;
1.100 + uend = packages->data + packages->size;
1.101 + upool = source2->set->string_pool.data;
1.102 +
1.103 + s = source1->set->packages.data;
1.104 + send = source1->set->packages.data + source1->set->packages.size;
1.105 + spool = source1->set->string_pool.data;
1.106 +
1.107 + while (s < send) {
1.108 + p = upstream_packages + *u;
1.109 +
1.110 + if (u < uend)
1.111 + cmp = strcmp(&spool[s->name], &upool[p->name]);
1.112 + if (u >= uend || cmp < 0) {
1.113 + add_package(importer, s, source1, 0);
1.114 + s++;
1.115 + } else if (cmp == 0) {
1.116 + add_package(importer, p, source2, UPSTREAM_SOURCE);
1.117 + s++;
1.118 + u++;
1.119 + } else {
1.120 + add_package(importer, p, source2, UPSTREAM_SOURCE);
1.121 + u++;
1.122 + }
1.123 + }
1.124 +}
1.125 +
1.126 +static unsigned long
1.127 +add_property(struct razor_importer *importer, struct array *properties,
1.128 + const char *name, const char *version)
1.129 +{
1.130 + struct razor_property *p;
1.131 +
1.132 + p = array_add(properties, sizeof *p);
1.133 + p->name = razor_importer_tokenize(importer, name);
1.134 + p->version = razor_importer_tokenize(importer, version);
1.135 +
1.136 + return p - (struct razor_property *) properties->data;
1.137 +}
1.138 +
1.139 +static void
1.140 +merge_properties(struct array *properties,
1.141 + struct razor_importer *importer,
1.142 + struct razor_set *set1,
1.143 + struct array *properties1,
1.144 + unsigned long *map1,
1.145 + struct razor_set *set2,
1.146 + struct array *properties2,
1.147 + unsigned long *map2)
1.148 +{
1.149 + struct razor_property *p1, *p2;
1.150 + int i, j, cmp, count1, count2;
1.151 + char *pool1, *pool2;
1.152 +
1.153 + i = 0;
1.154 + j = 0;
1.155 + pool1 = set1->string_pool.data;
1.156 + pool2 = set2->string_pool.data;
1.157 +
1.158 + count1 = properties1->size / sizeof *p1;
1.159 + count2 = properties2->size / sizeof *p2;
1.160 + while (i < count1 || j < count2) {
1.161 + if (i < count1 && map1[i] == 0) {
1.162 + i++;
1.163 + continue;
1.164 + }
1.165 + if (j < count2 && map2[j] == 0) {
1.166 + j++;
1.167 + continue;
1.168 + }
1.169 + p1 = (struct razor_property *) properties1->data + i;
1.170 + p2 = (struct razor_property *) properties2->data + j;
1.171 + if (i < count1 && j < count2)
1.172 + cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
1.173 + else if (i < count1)
1.174 + cmp = -1;
1.175 + else
1.176 + cmp = 1;
1.177 + if (cmp == 0)
1.178 + cmp = versioncmp(&pool1[p1->version],
1.179 + &pool2[p2->version]);
1.180 + if (cmp < 0) {
1.181 + map1[i++] = add_property(importer,
1.182 + properties,
1.183 + &pool1[p1->name],
1.184 + &pool1[p1->version]);
1.185 + } else if (cmp > 0) {
1.186 + map2[j++] = add_property(importer,
1.187 + properties,
1.188 + &pool2[p2->name],
1.189 + &pool2[p2->version]);
1.190 + } else {
1.191 + map1[i++] = map2[j++] = add_property(importer,
1.192 + properties,
1.193 + &pool1[p1->name],
1.194 + &pool1[p1->version]);
1.195 + }
1.196 + }
1.197 +}
1.198 +
1.199 +static unsigned long
1.200 +emit_properties(struct array *source_pool, unsigned long index,
1.201 + unsigned long *map, struct array *pool)
1.202 +{
1.203 + unsigned long r, *p, *q;
1.204 +
1.205 + r = pool->size / sizeof *q;
1.206 + p = (unsigned long *) source_pool->data + index;
1.207 + while (*p != ~0) {
1.208 + q = array_add(pool, sizeof *q);
1.209 + *q = map[*p++];
1.210 }
1.211
1.212 - r = (unsigned long *) set->provides_pool.data + package->provides;
1.213 - properties = set->provides.data;
1.214 - while (~*r) {
1.215 - p = &properties[*r++];
1.216 - razor_importer_add_provides(importer,
1.217 - &pool[p->name], &pool[p->version]);
1.218 + q = array_add(pool, sizeof *q);
1.219 + *q = ~0;
1.220 +
1.221 + return r;
1.222 +}
1.223 +
1.224 +/* Rebuild property->packages maps. We can't just remap these, as a
1.225 + * property may have lost or gained a number of packages. Allocate an
1.226 + * array per property and loop through the packages and add them to
1.227 + * the arrays for their properties. */
1.228 +static void
1.229 +rebuild_package_lists(struct razor_set *set)
1.230 +{
1.231 + int requires_count, provides_count;
1.232 + struct array *requires_pkgs, *provides_pkgs, *a;
1.233 + struct razor_package *pkg, *pkg_end;
1.234 + struct razor_property *prop, *prop_end;
1.235 + unsigned long *r, *q, *rpool, *ppool;
1.236 +
1.237 + requires_count = set->requires.size / sizeof (struct razor_property);
1.238 + provides_count = set->provides.size / sizeof (struct razor_property);
1.239 + requires_pkgs = zalloc(requires_count * sizeof *requires_pkgs);
1.240 + provides_pkgs = zalloc(provides_count * sizeof *provides_pkgs);
1.241 + pkg_end = set->packages.data + set->packages.size;
1.242 + rpool = set->requires_pool.data;
1.243 + ppool = set->provides_pool.data;
1.244 +
1.245 + for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
1.246 + for (r = &rpool[pkg->requires]; *r != ~0; r++) {
1.247 + q = array_add(&requires_pkgs[*r], sizeof *q);
1.248 + *q = pkg - (struct razor_package *) set->packages.data;
1.249 + }
1.250 + for (r = &ppool[pkg->provides]; *r != ~0; r++) {
1.251 + q = array_add(&provides_pkgs[*r], sizeof *q);
1.252 + *q = pkg - (struct razor_package *) set->packages.data;
1.253 + }
1.254 }
1.255
1.256 - razor_importer_finish_package(importer);
1.257 + prop_end = set->requires.data + set->requires.size;
1.258 + a = requires_pkgs;
1.259 + for (prop = set->requires.data; prop < prop_end; prop++, a++) {
1.260 + prop->packages = add_to_property_pool(&set->requires_pool, a);
1.261 + array_release(a);
1.262 + }
1.263 + free(requires_pkgs);
1.264 +
1.265 + prop_end = set->provides.data + set->provides.size;
1.266 + a = provides_pkgs;
1.267 + for (prop = set->provides.data; prop < prop_end; prop++, a++) {
1.268 + prop->packages = add_to_property_pool(&set->provides_pool, a);
1.269 + array_release(a);
1.270 + }
1.271 + free(provides_pkgs);
1.272 }
1.273
1.274 /* Add packages from 'upstream' to 'set'. The packages to add are
1.275 * specified by the 'packages' array, which is a sorted list of
1.276 * package indexes. Returns a newly allocated package set. Does not
1.277 - * enforce validity of the resulting package set. */
1.278 -
1.279 -/* FIXME: We can do this in a linear sweep instead of using an
1.280 - * importer and the sorting that incurs: build the new package list
1.281 - * sorted, build up a map from package index in old set to package
1.282 - * index in new set for both sets. ~0 means 'not in new set'. build
1.283 - * new string pool as we go, probably just re-use that part of the
1.284 - * importer. as we build the package list, fill out a bitvector of
1.285 - * the properties that are referenced by the pacakges in the new
1.286 - * set. then do a parallel loop through the properties and emit them
1.287 - * to the new set and build a map from indices in the old set to
1.288 - * indices in the new set. then loop through the packages again and
1.289 - * emit the property lists. */
1.290 -
1.291 + * enforce validity of the resulting package set.
1.292 + *
1.293 + * This looks more complicated than it is. An easy way to merge two
1.294 + * package sets would be to just use a razor_importer, but that
1.295 + * requires resorting, and is thus O(n log n). We can do this in a
1.296 + * linear sweep, but it gets a little more complicated.
1.297 + */
1.298 struct razor_set *
1.299 razor_set_add(struct razor_set *set, struct razor_set *upstream,
1.300 struct array *packages)
1.301 {
1.302 + struct razor_set *result;
1.303 struct razor_importer *importer;
1.304 - struct razor_package *upstream_packages, *p, *s, *send;
1.305 - char *spool, *upool;
1.306 - unsigned long *u, *uend;
1.307 - int cmp;
1.308 + struct razor_package *p, *pend;
1.309 + struct source source, upstream_source;
1.310
1.311 importer = razor_importer_new();
1.312 - upstream_packages = upstream->packages.data;
1.313 - u = packages->data;
1.314 - uend = packages->data + packages->size;
1.315 - upool = upstream->string_pool.data;
1.316 - s = set->packages.data;
1.317 - send = set->packages.data + set->packages.size;
1.318 - spool = set->string_pool.data;
1.319
1.320 - while (s < send) {
1.321 - p = upstream_packages + *u;
1.322 - if (u < uend)
1.323 - cmp = strcmp(&spool[s->name], &upool[p->name]);
1.324 - if (u >= uend || cmp < 0) {
1.325 - add_package(importer, s, set);
1.326 - s++;
1.327 - } else if (cmp == 0) {
1.328 - add_package(importer, p, upstream);
1.329 - s++;
1.330 - u++;
1.331 - } else {
1.332 - add_package(importer, p, upstream);
1.333 - u++;
1.334 - }
1.335 + prepare_source(&upstream_source, upstream);
1.336 + prepare_source(&source, set);
1.337 +
1.338 + merge_packages(importer, &source, &upstream_source, packages);
1.339 +
1.340 + /* As we built the package list, we filled out a bitvector of
1.341 + * the properties that are referenced by the packages in the
1.342 + * new set. Now we do a parallel loop through the properties
1.343 + * and emit those marked in the bit vector to the new set. In
1.344 + * the process, we update the bit vector to actually map from
1.345 + * indices in the old property list to indices in the new
1.346 + * property list for both sets. */
1.347 +
1.348 + merge_properties(&importer->set->requires, importer,
1.349 + set, &set->requires, source.requires_map,
1.350 + upstream, &upstream->requires,
1.351 + upstream_source.requires_map);
1.352 + merge_properties(&importer->set->provides, importer,
1.353 + set, &set->provides, source.provides_map,
1.354 + upstream, &upstream->provides,
1.355 + upstream_source.provides_map);
1.356 +
1.357 + /* Now we loop through the packages again and emit the
1.358 + * property lists, remapped to point to the new properties. */
1.359 +
1.360 + pend = importer->set->packages.data + importer->set->packages.size;
1.361 + for (p = importer->set->packages.data; p < pend; p++) {
1.362 + struct source *src;
1.363 +
1.364 + if (p->name & UPSTREAM_SOURCE)
1.365 + src = &upstream_source;
1.366 + else
1.367 + src = &source;
1.368 +
1.369 + p->requires = emit_properties(&src->set->requires_pool,
1.370 + p->requires,
1.371 + src->requires_map,
1.372 + &importer->set->requires_pool);
1.373 + p->provides = emit_properties(&src->set->provides_pool,
1.374 + p->provides,
1.375 + src->provides_map,
1.376 + &importer->set->provides_pool);
1.377 + p->name &= INDEX_MASK;
1.378 }
1.379
1.380 - return razor_importer_finish(importer);
1.381 + rebuild_package_lists(importer->set);
1.382 +
1.383 + result = importer->set;
1.384 + array_release(&importer->buckets);
1.385 + free(importer);
1.386 +
1.387 + return result;
1.388 }
1.389
1.390 void
1.391 @@ -1278,6 +1502,19 @@
1.392 return 1;
1.393 razor_set_list_unsatisfied(set);
1.394 razor_set_destroy(set);
1.395 + } else if (strcmp(argv[1], "add") == 0) {
1.396 + struct array list;
1.397 +
1.398 + set = razor_set_open(repo_filename);
1.399 + upstream = razor_set_open(rawhide_repo_filename);
1.400 + if (set == NULL || upstream == NULL)
1.401 + return 1;
1.402 + array_init(&list);
1.403 + find_packages(upstream, argc - 2, argv + 2, &list);
1.404 + set = razor_set_add(set, upstream, &list);
1.405 + razor_set_write(set, "system-updated.repo");
1.406 + razor_set_destroy(set);
1.407 + printf("wrote system-updated.repo\n");
1.408 } else if (strcmp(argv[1], "update") == 0) {
1.409 set = razor_set_open(repo_filename);
1.410 upstream = razor_set_open(rawhide_repo_filename);