1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/librazor/merger.c Wed Jul 02 18:46:47 2008 +0100
1.3 @@ -0,0 +1,525 @@
1.4 +/*
1.5 + * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
1.6 + * Copyright (C) 2008 Red Hat, Inc
1.7 + *
1.8 + * This program is free software; you can redistribute it and/or modify
1.9 + * it under the terms of the GNU General Public License as published by
1.10 + * the Free Software Foundation; either version 2 of the License, or
1.11 + * (at your option) any later version.
1.12 + *
1.13 + * This program is distributed in the hope that it will be useful,
1.14 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
1.15 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.16 + * GNU General Public License for more details.
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License along
1.19 + * with this program; if not, write to the Free Software Foundation, Inc.,
1.20 + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + */
1.22 +
1.23 +#include <string.h>
1.24 +#include "razor-internal.h"
1.25 +#include "razor.h"
1.26 +
1.27 +#define UPSTREAM_SOURCE 0x80
1.28 +
1.29 +struct source {
1.30 + struct razor_set *set;
1.31 + uint32_t *property_map;
1.32 + uint32_t *file_map;
1.33 +};
1.34 +
1.35 +struct razor_merger {
1.36 + struct razor_set *set;
1.37 + struct hashtable table;
1.38 + struct source source1;
1.39 + struct source source2;
1.40 +};
1.41 +
1.42 +struct razor_merger *
1.43 +razor_merger_create(struct razor_set *set1, struct razor_set *set2)
1.44 +{
1.45 + struct razor_merger *merger;
1.46 + int count;
1.47 + size_t size;
1.48 +
1.49 + merger = zalloc(sizeof *merger);
1.50 + merger->set = razor_set_create();
1.51 + hashtable_init(&merger->table, &merger->set->string_pool);
1.52 +
1.53 + merger->source1.set = set1;
1.54 + count = set1->properties.size / sizeof (struct razor_property);
1.55 + size = count * sizeof merger->source1.property_map[0];
1.56 + merger->source1.property_map = zalloc(size);
1.57 + count = set1->files.size / sizeof (struct razor_entry);
1.58 + size = count * sizeof merger->source1.file_map[0];
1.59 + merger->source1.file_map = zalloc(size);
1.60 +
1.61 + merger->source2.set = set2;
1.62 + count = set2->properties.size / sizeof (struct razor_property);
1.63 + size = count * sizeof merger->source2.property_map[0];
1.64 + merger->source2.property_map = zalloc(size);
1.65 + count = set2->files.size / sizeof (struct razor_entry);
1.66 + size = count * sizeof merger->source2.file_map[0];
1.67 + merger->source2.file_map = zalloc(size);
1.68 +
1.69 + return merger;
1.70 +}
1.71 +
1.72 +void
1.73 +razor_merger_add_package(struct razor_merger *merger,
1.74 + struct razor_package *package)
1.75 +{
1.76 + char *pool;
1.77 + struct list *r;
1.78 + struct razor_package *p;
1.79 + struct razor_set *set1;
1.80 + struct source *source;
1.81 + uint32_t flags;
1.82 +
1.83 + set1 = merger->source1.set;
1.84 + if (set1->packages.data <= (void *) package &&
1.85 + (void *) package < set1->packages.data + set1->packages.size) {
1.86 + source = &merger->source1;
1.87 + flags = 0;
1.88 + } else {
1.89 + source = &merger->source2;
1.90 + flags = UPSTREAM_SOURCE;
1.91 + }
1.92 +
1.93 + pool = source->set->string_pool.data;
1.94 + p = array_add(&merger->set->packages, sizeof *p);
1.95 + p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
1.96 + p->flags = flags;
1.97 + p->version = hashtable_tokenize(&merger->table,
1.98 + &pool[package->version]);
1.99 + p->arch = hashtable_tokenize(&merger->table,
1.100 + &pool[package->arch]);
1.101 +
1.102 + p->properties = package->properties;
1.103 + r = list_first(&package->properties, &source->set->property_pool);
1.104 + while (r) {
1.105 + source->property_map[r->data] = 1;
1.106 + r = list_next(r);
1.107 + }
1.108 +
1.109 + p->files = package->files;
1.110 + r = list_first(&package->files, &source->set->file_pool);
1.111 + while (r) {
1.112 + source->file_map[r->data] = 1;
1.113 + r = list_next(r);
1.114 + }
1.115 +}
1.116 +
1.117 +static uint32_t
1.118 +add_property(struct razor_merger *merger,
1.119 + const char *name, uint32_t flags, const char *version)
1.120 +{
1.121 + struct razor_property *p;
1.122 +
1.123 + p = array_add(&merger->set->properties, sizeof *p);
1.124 + p->name = hashtable_tokenize(&merger->table, name);
1.125 + p->flags = flags;
1.126 + p->version = hashtable_tokenize(&merger->table, version);
1.127 +
1.128 + return p - (struct razor_property *) merger->set->properties.data;
1.129 +}
1.130 +
1.131 +static void
1.132 +merge_properties(struct razor_merger *merger)
1.133 +{
1.134 + struct razor_property *p1, *p2;
1.135 + struct razor_set *set1, *set2;
1.136 + uint32_t *map1, *map2;
1.137 + int i, j, cmp, count1, count2;
1.138 + char *pool1, *pool2;
1.139 +
1.140 + set1 = merger->source1.set;
1.141 + set2 = merger->source2.set;
1.142 + map1 = merger->source1.property_map;
1.143 + map2 = merger->source2.property_map;
1.144 +
1.145 + i = 0;
1.146 + j = 0;
1.147 + pool1 = set1->string_pool.data;
1.148 + pool2 = set2->string_pool.data;
1.149 +
1.150 + count1 = set1->properties.size / sizeof *p1;
1.151 + count2 = set2->properties.size / sizeof *p2;
1.152 + while (i < count1 || j < count2) {
1.153 + if (i < count1 && map1[i] == 0) {
1.154 + i++;
1.155 + continue;
1.156 + }
1.157 + if (j < count2 && map2[j] == 0) {
1.158 + j++;
1.159 + continue;
1.160 + }
1.161 + p1 = (struct razor_property *) set1->properties.data + i;
1.162 + p2 = (struct razor_property *) set2->properties.data + j;
1.163 + if (i < count1 && j < count2)
1.164 + cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
1.165 + else if (i < count1)
1.166 + cmp = -1;
1.167 + else
1.168 + cmp = 1;
1.169 + if (cmp == 0)
1.170 + cmp = p1->flags - p2->flags;
1.171 + if (cmp == 0)
1.172 + cmp = razor_versioncmp(&pool1[p1->version],
1.173 + &pool2[p2->version]);
1.174 + if (cmp < 0) {
1.175 + map1[i++] = add_property(merger,
1.176 + &pool1[p1->name],
1.177 + p1->flags,
1.178 + &pool1[p1->version]);
1.179 + } else if (cmp > 0) {
1.180 + map2[j++] = add_property(merger,
1.181 + &pool2[p2->name],
1.182 + p2->flags,
1.183 + &pool2[p2->version]);
1.184 + } else {
1.185 + map1[i++] = map2[j++] =
1.186 + add_property(merger,
1.187 + &pool1[p1->name],
1.188 + p1->flags,
1.189 + &pool1[p1->version]);
1.190 + }
1.191 + }
1.192 +}
1.193 +
1.194 +static void
1.195 +emit_properties(struct list_head *properties, struct array *source_pool,
1.196 + uint32_t *map, struct array *pool)
1.197 +{
1.198 + uint32_t r;
1.199 + struct list *p, *q;
1.200 +
1.201 + r = pool->size / sizeof *q;
1.202 + p = list_first(properties, source_pool);
1.203 + while (p) {
1.204 + q = array_add(pool, sizeof *q);
1.205 + q->data = map[p->data];
1.206 + q->flags = p->flags;
1.207 + p = list_next(p);
1.208 + }
1.209 +
1.210 + list_set_ptr(properties, r);
1.211 +}
1.212 +
1.213 +static uint32_t
1.214 +add_file(struct razor_merger *merger, const char *name)
1.215 +{
1.216 + struct razor_entry *e;
1.217 +
1.218 + e = array_add(&merger->set->files, sizeof *e);
1.219 + e->name = hashtable_tokenize(&merger->table, name);
1.220 + e->flags = 0;
1.221 + e->start = 0;
1.222 +
1.223 + return e - (struct razor_entry *)merger->set->files.data;
1.224 +}
1.225 +
1.226 +/* FIXME. Blah */
1.227 +static int
1.228 +fix_file_map(uint32_t *map,
1.229 + struct razor_entry *files,
1.230 + struct razor_entry *top)
1.231 +{
1.232 + uint32_t e;
1.233 + int found_file = 0;
1.234 +
1.235 + e = top->start;
1.236 + do {
1.237 + if (files[e].start)
1.238 + fix_file_map(map, files, &files[e]);
1.239 + if (map[e])
1.240 + found_file = 1;
1.241 + } while (!(files[e++].flags & RAZOR_ENTRY_LAST));
1.242 +
1.243 + if (found_file)
1.244 + map[top - files] = 1;
1.245 + return found_file;
1.246 +}
1.247 +
1.248 +struct merge_directory {
1.249 + uint32_t merged, dir1, dir2;
1.250 +};
1.251 +
1.252 +static void
1.253 +merge_one_directory(struct razor_merger *merger, struct merge_directory *md)
1.254 +{
1.255 + struct razor_entry *root1, *root2, *mroot, *e1, *e2;
1.256 + struct razor_set *set1, *set2;
1.257 + struct array merge_stack;
1.258 + struct merge_directory *child_md, *end_md;
1.259 + uint32_t *map1, *map2, start, last;
1.260 + int cmp;
1.261 + char *pool1, *pool2;
1.262 +
1.263 + set1 = merger->source1.set;
1.264 + set2 = merger->source2.set;
1.265 + map1 = merger->source1.file_map;
1.266 + map2 = merger->source2.file_map;
1.267 + pool1 = set1->string_pool.data;
1.268 + pool2 = set2->string_pool.data;
1.269 + root1 = (struct razor_entry *) set1->files.data;
1.270 + root2 = (struct razor_entry *) set2->files.data;
1.271 +
1.272 + array_init(&merge_stack);
1.273 +
1.274 + start = merger->set->files.size / sizeof (struct razor_entry);
1.275 + last = 0;
1.276 + e1 = md->dir1 ? root1 + md->dir1 : NULL;
1.277 + e2 = md->dir2 ? root2 + md->dir2 : NULL;
1.278 + while (e1 || e2) {
1.279 + if (!e2 && !map1[e1 - root1]) {
1.280 + if ((e1++)->flags & RAZOR_ENTRY_LAST)
1.281 + e1 = NULL;
1.282 + continue;
1.283 + }
1.284 + if (!e1 && !map2[e2 - root2]) {
1.285 + if ((e2++)->flags & RAZOR_ENTRY_LAST)
1.286 + e2 = NULL;
1.287 + continue;
1.288 + }
1.289 + if (e1 && !map1[e1 - root1] &&
1.290 + e2 && !map1[e2 - root2]) {
1.291 + if ((e1++)->flags & RAZOR_ENTRY_LAST)
1.292 + e1 = NULL;
1.293 + if ((e2++)->flags & RAZOR_ENTRY_LAST)
1.294 + e2 = NULL;
1.295 + continue;
1.296 + }
1.297 +
1.298 + if (!e1)
1.299 + cmp = 1;
1.300 + else if (!e2)
1.301 + cmp = -1;
1.302 + else {
1.303 + cmp = strcmp (&pool1[e1->name],
1.304 + &pool2[e2->name]);
1.305 + }
1.306 +
1.307 + if (cmp < 0) {
1.308 + if (map1[e1 - root1]) {
1.309 + map1[e1 - root1] = last =
1.310 + add_file(merger, &pool1[e1->name]);
1.311 + if (e1->start) {
1.312 + child_md = array_add(&merge_stack, sizeof (struct merge_directory));
1.313 + child_md->merged = last;
1.314 + child_md->dir1 = e1->start;
1.315 + child_md->dir2 = 0;
1.316 + }
1.317 + }
1.318 + if ((e1++)->flags & RAZOR_ENTRY_LAST)
1.319 + e1 = NULL;
1.320 + } else if (cmp > 0) {
1.321 + if (map2[e2 - root2]) {
1.322 + map2[e2 - root2] = last =
1.323 + add_file(merger, &pool2[e2->name]);
1.324 + if (e2->start) {
1.325 + child_md = array_add(&merge_stack, sizeof (struct merge_directory));
1.326 + child_md->merged = last;
1.327 + child_md->dir1 = 0;
1.328 + child_md->dir2 = e2->start;
1.329 + }
1.330 + }
1.331 + if ((e2++)->flags & RAZOR_ENTRY_LAST)
1.332 + e2 = NULL;
1.333 + } else {
1.334 + map1[e1 - root1] = map2[e2- root2] = last =
1.335 + add_file(merger, &pool1[e1->name]);
1.336 + if (e1->start || e2->start) {
1.337 + child_md = array_add(&merge_stack, sizeof (struct merge_directory));
1.338 + child_md->merged = last;
1.339 + child_md->dir1 = e1->start;
1.340 + child_md->dir2 = e2->start;
1.341 + }
1.342 + if ((e1++)->flags & RAZOR_ENTRY_LAST)
1.343 + e1 = NULL;
1.344 + if ((e2++)->flags & RAZOR_ENTRY_LAST)
1.345 + e2 = NULL;
1.346 + }
1.347 + }
1.348 +
1.349 + mroot = (struct razor_entry *)merger->set->files.data;
1.350 + if (last) {
1.351 + mroot[last].flags = RAZOR_ENTRY_LAST;
1.352 + mroot[md->merged].start = start;
1.353 + } else
1.354 + mroot[md->merged].start = 0;
1.355 +
1.356 + end_md = merge_stack.data + merge_stack.size;
1.357 + for (child_md = merge_stack.data; child_md < end_md; child_md++)
1.358 + merge_one_directory(merger, child_md);
1.359 + array_release(&merge_stack);
1.360 +}
1.361 +
1.362 +static void
1.363 +merge_files(struct razor_merger *merger)
1.364 +{
1.365 + struct razor_entry *root;
1.366 + struct merge_directory md;
1.367 + uint32_t *map1, *map2;
1.368 +
1.369 + map1 = merger->source1.file_map;
1.370 + map2 = merger->source2.file_map;
1.371 +
1.372 + md.merged = 0;
1.373 +
1.374 + if (merger->source1.set->files.size) {
1.375 + root = (struct razor_entry *) merger->source1.set->files.data;
1.376 + if (root->start)
1.377 + fix_file_map(map1, root, root);
1.378 + md.dir1 = root->start;
1.379 + } else
1.380 + md.dir1 = 0;
1.381 +
1.382 + if (merger->source2.set->files.size) {
1.383 + root = (struct razor_entry *) merger->source2.set->files.data;
1.384 + if (root->start)
1.385 + fix_file_map(map2, root, root);
1.386 + md.dir2 = root->start;
1.387 + } else
1.388 + md.dir2 = 0;
1.389 +
1.390 + merge_one_directory(merger, &md);
1.391 +}
1.392 +
1.393 +static void
1.394 +emit_files(struct list_head *files, struct array *source_pool,
1.395 + uint32_t *map, struct array *pool)
1.396 +{
1.397 + uint32_t r;
1.398 + struct list *p, *q;
1.399 +
1.400 + r = pool->size / sizeof *q;
1.401 + p = list_first(files, source_pool);
1.402 + while (p) {
1.403 + q = array_add(pool, sizeof *q);
1.404 + q->data = map[p->data];
1.405 + q->flags = p->flags;
1.406 + p = list_next(p);
1.407 + }
1.408 +
1.409 + list_set_ptr(files, r);
1.410 +}
1.411 +
1.412 +/* Rebuild property->packages maps. We can't just remap these, as a
1.413 + * property may have lost or gained a number of packages. Allocate an
1.414 + * array per property and loop through the packages and add them to
1.415 + * the arrays for their properties. */
1.416 +static void
1.417 +rebuild_property_package_lists(struct razor_set *set)
1.418 +{
1.419 + struct array *pkgs, *a;
1.420 + struct razor_package *pkg, *pkg_end;
1.421 + struct razor_property *prop, *prop_end;
1.422 + struct list *r;
1.423 + uint32_t *q;
1.424 + int count;
1.425 +
1.426 + count = set->properties.size / sizeof (struct razor_property);
1.427 + pkgs = zalloc(count * sizeof *pkgs);
1.428 + pkg_end = set->packages.data + set->packages.size;
1.429 +
1.430 + for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
1.431 + r = list_first(&pkg->properties, &set->property_pool);
1.432 + while (r) {
1.433 + q = array_add(&pkgs[r->data], sizeof *q);
1.434 + *q = pkg - (struct razor_package *) set->packages.data;
1.435 + r = list_next(r);
1.436 + }
1.437 + }
1.438 +
1.439 + prop_end = set->properties.data + set->properties.size;
1.440 + a = pkgs;
1.441 + for (prop = set->properties.data; prop < prop_end; prop++, a++) {
1.442 + list_set_array(&prop->packages, &set->package_pool, a, 0);
1.443 + array_release(a);
1.444 + }
1.445 + free(pkgs);
1.446 +}
1.447 +
1.448 +static void
1.449 +rebuild_file_package_lists(struct razor_set *set)
1.450 +{
1.451 + struct array *pkgs, *a;
1.452 + struct razor_package *pkg, *pkg_end;
1.453 + struct razor_entry *entry, *entry_end;
1.454 + struct list *r;
1.455 + uint32_t *q;
1.456 + int count;
1.457 +
1.458 + count = set->files.size / sizeof (struct razor_entry);
1.459 + pkgs = zalloc(count * sizeof *pkgs);
1.460 + pkg_end = set->packages.data + set->packages.size;
1.461 +
1.462 + for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
1.463 + r = list_first(&pkg->files, &set->file_pool);
1.464 + while (r) {
1.465 + q = array_add(&pkgs[r->data], sizeof *q);
1.466 + *q = pkg - (struct razor_package *) set->packages.data;
1.467 + r = list_next(r);
1.468 + }
1.469 + }
1.470 +
1.471 + entry_end = set->files.data + set->files.size;
1.472 + a = pkgs;
1.473 + for (entry = set->files.data; entry < entry_end; entry++, a++) {
1.474 + list_set_array(&entry->packages, &set->package_pool, a, 0);
1.475 + array_release(a);
1.476 + }
1.477 + free(pkgs);
1.478 +}
1.479 +
1.480 +struct razor_set *
1.481 +razor_merger_finish(struct razor_merger *merger)
1.482 +{
1.483 + struct razor_set *result;
1.484 + struct razor_package *p, *pend;
1.485 +
1.486 + /* As we built the package list, we filled out a bitvector of
1.487 + * the properties that are referenced by the packages in the
1.488 + * new set. Now we do a parallel loop through the properties
1.489 + * and emit those marked in the bit vector to the new set. In
1.490 + * the process, we update the bit vector to actually map from
1.491 + * indices in the old property list to indices in the new
1.492 + * property list for both sets. */
1.493 +
1.494 + merge_properties(merger);
1.495 + merge_files(merger);
1.496 +
1.497 + /* Now we loop through the packages again and emit the
1.498 + * property lists, remapped to point to the new properties. */
1.499 +
1.500 + pend = merger->set->packages.data + merger->set->packages.size;
1.501 + for (p = merger->set->packages.data; p < pend; p++) {
1.502 + struct source *src;
1.503 +
1.504 + if (p->flags & UPSTREAM_SOURCE)
1.505 + src = &merger->source2;
1.506 + else
1.507 + src = &merger->source1;
1.508 +
1.509 + emit_properties(&p->properties,
1.510 + &src->set->property_pool,
1.511 + src->property_map,
1.512 + &merger->set->property_pool);
1.513 + emit_files(&p->files,
1.514 + &src->set->file_pool,
1.515 + src->file_map,
1.516 + &merger->set->file_pool);
1.517 + p->flags &= ~UPSTREAM_SOURCE;
1.518 + }
1.519 +
1.520 + rebuild_property_package_lists(merger->set);
1.521 + rebuild_file_package_lists(merger->set);
1.522 +
1.523 + result = merger->set;
1.524 + hashtable_release(&merger->table);
1.525 + free(merger);
1.526 +
1.527 + return result;
1.528 +}