krh@248: /* krh@248: * Copyright (C) 2008 Kristian Høgsberg krh@248: * Copyright (C) 2008 Red Hat, Inc ali@403: * Copyright (C) 2009-2011 J. Ali Harlow krh@248: * krh@248: * This program is free software; you can redistribute it and/or modify krh@248: * it under the terms of the GNU General Public License as published by krh@248: * the Free Software Foundation; either version 2 of the License, or krh@248: * (at your option) any later version. krh@248: * krh@248: * This program is distributed in the hope that it will be useful, krh@248: * but WITHOUT ANY WARRANTY; without even the implied warranty of krh@248: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the krh@248: * GNU General Public License for more details. krh@248: * krh@248: * You should have received a copy of the GNU General Public License along krh@248: * with this program; if not, write to the Free Software Foundation, Inc., krh@248: * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. krh@248: */ krh@248: ali@438: #include "config.h" krh@248: #include ali@369: #include krh@248: #include "razor-internal.h" krh@248: #include "razor.h" krh@248: krh@248: #define UPSTREAM_SOURCE 0x80 krh@248: krh@248: struct source { krh@248: struct razor_set *set; krh@248: uint32_t *property_map; krh@248: uint32_t *file_map; krh@248: }; krh@248: krh@248: struct razor_merger { ali@369: int committed; krh@248: struct razor_set *set; krh@248: struct hashtable table; ali@348: struct hashtable file_table; ali@394: struct hashtable details_table; krh@248: struct source source1; krh@248: struct source source2; krh@248: }; krh@248: krh@248: struct razor_merger * krh@248: razor_merger_create(struct razor_set *set1, struct razor_set *set2) krh@248: { krh@248: struct razor_merger *merger; krh@248: int count; krh@248: size_t size; ali@403: uint32_t header_version; krh@248: krh@248: merger = zalloc(sizeof *merger); krh@248: merger->set = razor_set_create(); ali@403: if (set1->packages.size) { ali@403: header_version = razor_set_get_header_version(set1); ali@403: if (set2->packages.size && ali@403: razor_set_get_header_version(set2) > header_version) ali@403: header_version = razor_set_get_header_version(set2); ali@403: } else ali@403: header_version = razor_set_get_header_version(set2); ali@403: razor_set_set_header_version(merger->set, header_version); krh@248: hashtable_init(&merger->table, &merger->set->string_pool); ali@348: hashtable_init(&merger->file_table, &merger->set->file_string_pool); ali@394: hashtable_init(&merger->details_table, ali@394: &merger->set->details_string_pool); krh@248: krh@248: merger->source1.set = set1; krh@248: count = set1->properties.size / sizeof (struct razor_property); krh@248: size = count * sizeof merger->source1.property_map[0]; krh@248: merger->source1.property_map = zalloc(size); krh@248: count = set1->files.size / sizeof (struct razor_entry); krh@248: size = count * sizeof merger->source1.file_map[0]; krh@248: merger->source1.file_map = zalloc(size); krh@248: krh@248: merger->source2.set = set2; krh@248: count = set2->properties.size / sizeof (struct razor_property); krh@248: size = count * sizeof merger->source2.property_map[0]; krh@248: merger->source2.property_map = zalloc(size); krh@248: count = set2->files.size / sizeof (struct razor_entry); krh@248: size = count * sizeof merger->source2.file_map[0]; krh@248: merger->source2.file_map = zalloc(size); krh@248: krh@248: return merger; krh@248: } krh@248: krh@248: void krh@248: razor_merger_add_package(struct razor_merger *merger, krh@248: struct razor_package *package) krh@248: { ali@394: char *pool, *details_pool, *s; krh@248: struct list *r; krh@248: struct razor_package *p; krh@248: struct razor_set *set1; krh@248: struct source *source; ali@372: uint32_t flags, *prefix; ali@372: struct array install_prefixes; krh@248: ali@369: assert(merger->committed == 0); ali@369: krh@248: set1 = merger->source1.set; krh@248: if (set1->packages.data <= (void *) package && krh@248: (void *) package < set1->packages.data + set1->packages.size) { krh@248: source = &merger->source1; krh@248: flags = 0; krh@248: } else { krh@248: source = &merger->source2; krh@248: flags = UPSTREAM_SOURCE; krh@248: } krh@248: krh@248: pool = source->set->string_pool.data; ali@394: details_pool = source->set->details_string_pool.data; krh@248: p = array_add(&merger->set->packages, sizeof *p); krh@248: p->name = hashtable_tokenize(&merger->table, &pool[package->name]); krh@248: p->flags = flags; krh@248: p->version = hashtable_tokenize(&merger->table, krh@248: &pool[package->version]); krh@248: p->arch = hashtable_tokenize(&merger->table, krh@248: &pool[package->arch]); ali@395: if (source->set->details_string_pool.size) { ali@395: p->summary = hashtable_tokenize(&merger->details_table, ali@395: &details_pool[package->summary]); ali@395: p->description = hashtable_tokenize(&merger->details_table, ali@395: &details_pool[package->description]); ali@395: p->url = hashtable_tokenize(&merger->details_table, ali@395: &details_pool[package->url]); ali@395: p->license = hashtable_tokenize(&merger->details_table, ali@395: &details_pool[package->license]); ali@395: } else { ali@395: p->summary = hashtable_tokenize(&merger->details_table, ""); ali@395: p->description = hashtable_tokenize(&merger->details_table, ""); ali@395: p->url = hashtable_tokenize(&merger->details_table, ""); ali@395: p->license = hashtable_tokenize(&merger->details_table, ""); ali@395: } krh@248: krh@248: p->properties = package->properties; krh@248: r = list_first(&package->properties, &source->set->property_pool); krh@248: while (r) { krh@248: source->property_map[r->data] = 1; krh@248: r = list_next(r); krh@248: } krh@248: krh@248: p->files = package->files; krh@248: r = list_first(&package->files, &source->set->file_pool); krh@248: while (r) { krh@248: source->file_map[r->data] = 1; krh@248: r = list_next(r); krh@248: } ali@369: ali@372: array_init(&install_prefixes); ali@372: r = list_first(&package->install_prefixes, &source->set->prefix_pool); ali@372: while (r) { ali@372: s = (char *)source->set->string_pool.data + r->data; ali@372: prefix = array_add(&install_prefixes, sizeof *prefix); ali@372: *prefix = hashtable_tokenize(&merger->table, s); ali@372: r = list_next(r); ali@372: } ali@372: list_set_array(&p->install_prefixes, &merger->set->prefix_pool, ali@372: &install_prefixes, 0); ali@372: array_release(&install_prefixes); ali@372: ali@369: p->preun.program = hashtable_tokenize(&merger->table, ali@369: &pool[package->preun.program]); ali@369: p->preun.body = hashtable_tokenize(&merger->table, ali@369: &pool[package->preun.body]); ali@369: p->postun.program = hashtable_tokenize(&merger->table, ali@369: &pool[package->postun.program]); ali@369: p->postun.body = hashtable_tokenize(&merger->table, ali@369: &pool[package->postun.body]); krh@248: } krh@248: krh@248: static uint32_t krh@248: add_property(struct razor_merger *merger, krh@248: const char *name, uint32_t flags, const char *version) krh@248: { krh@248: struct razor_property *p; krh@248: krh@248: p = array_add(&merger->set->properties, sizeof *p); krh@248: p->name = hashtable_tokenize(&merger->table, name); krh@248: p->flags = flags; krh@248: p->version = hashtable_tokenize(&merger->table, version); krh@248: krh@248: return p - (struct razor_property *) merger->set->properties.data; krh@248: } krh@248: krh@248: static void krh@248: merge_properties(struct razor_merger *merger) krh@248: { krh@248: struct razor_property *p1, *p2; krh@248: struct razor_set *set1, *set2; krh@248: uint32_t *map1, *map2; krh@248: int i, j, cmp, count1, count2; krh@248: char *pool1, *pool2; krh@248: krh@248: set1 = merger->source1.set; krh@248: set2 = merger->source2.set; krh@248: map1 = merger->source1.property_map; krh@248: map2 = merger->source2.property_map; krh@248: krh@248: i = 0; krh@248: j = 0; krh@248: pool1 = set1->string_pool.data; krh@248: pool2 = set2->string_pool.data; krh@248: krh@248: count1 = set1->properties.size / sizeof *p1; krh@248: count2 = set2->properties.size / sizeof *p2; krh@248: while (i < count1 || j < count2) { krh@248: if (i < count1 && map1[i] == 0) { krh@248: i++; krh@248: continue; krh@248: } krh@248: if (j < count2 && map2[j] == 0) { krh@248: j++; krh@248: continue; krh@248: } krh@248: p1 = (struct razor_property *) set1->properties.data + i; krh@248: p2 = (struct razor_property *) set2->properties.data + j; krh@248: if (i < count1 && j < count2) krh@248: cmp = strcmp(&pool1[p1->name], &pool2[p2->name]); krh@248: else if (i < count1) krh@248: cmp = -1; krh@248: else krh@248: cmp = 1; krh@248: if (cmp == 0) krh@248: cmp = p1->flags - p2->flags; krh@248: if (cmp == 0) krh@248: cmp = razor_versioncmp(&pool1[p1->version], krh@248: &pool2[p2->version]); krh@248: if (cmp < 0) { krh@248: map1[i++] = add_property(merger, krh@248: &pool1[p1->name], krh@248: p1->flags, krh@248: &pool1[p1->version]); krh@248: } else if (cmp > 0) { krh@248: map2[j++] = add_property(merger, krh@248: &pool2[p2->name], krh@248: p2->flags, krh@248: &pool2[p2->version]); krh@248: } else { krh@248: map1[i++] = map2[j++] = krh@248: add_property(merger, krh@248: &pool1[p1->name], krh@248: p1->flags, krh@248: &pool1[p1->version]); krh@248: } krh@248: } krh@248: } krh@248: krh@248: static void krh@248: emit_properties(struct list_head *properties, struct array *source_pool, krh@248: uint32_t *map, struct array *pool) krh@248: { krh@248: uint32_t r; krh@248: struct list *p, *q; krh@248: krh@248: r = pool->size / sizeof *q; krh@248: p = list_first(properties, source_pool); krh@248: while (p) { krh@248: q = array_add(pool, sizeof *q); krh@248: q->data = map[p->data]; krh@248: q->flags = p->flags; krh@248: p = list_next(p); krh@248: } krh@248: krh@248: list_set_ptr(properties, r); krh@248: } krh@248: krh@248: static uint32_t krh@248: add_file(struct razor_merger *merger, const char *name) krh@248: { krh@248: struct razor_entry *e; krh@248: krh@248: e = array_add(&merger->set->files, sizeof *e); ali@348: e->name = hashtable_tokenize(&merger->file_table, name); krh@248: e->flags = 0; krh@248: e->start = 0; krh@248: krh@248: return e - (struct razor_entry *)merger->set->files.data; krh@248: } krh@248: krh@248: /* FIXME. Blah */ krh@248: static int krh@248: fix_file_map(uint32_t *map, krh@248: struct razor_entry *files, krh@248: struct razor_entry *top) krh@248: { krh@248: uint32_t e; krh@248: int found_file = 0; krh@248: ali@359: e = top - files; krh@248: do { ali@359: if (files[e].start && ali@359: fix_file_map(map, files, &files[files[e].start])) ali@359: map[e] = 1; krh@248: if (map[e]) krh@248: found_file = 1; krh@248: } while (!(files[e++].flags & RAZOR_ENTRY_LAST)); krh@248: krh@248: return found_file; krh@248: } krh@248: krh@248: struct merge_directory { krh@248: uint32_t merged, dir1, dir2; krh@248: }; krh@248: krh@248: static void krh@248: merge_one_directory(struct razor_merger *merger, struct merge_directory *md) krh@248: { krh@248: struct razor_entry *root1, *root2, *mroot, *e1, *e2; krh@248: struct razor_set *set1, *set2; krh@248: struct array merge_stack; krh@248: struct merge_directory *child_md, *end_md; krh@248: uint32_t *map1, *map2, start, last; krh@248: int cmp; krh@248: char *pool1, *pool2; krh@248: krh@248: set1 = merger->source1.set; krh@248: set2 = merger->source2.set; krh@248: map1 = merger->source1.file_map; krh@248: map2 = merger->source2.file_map; ali@458: if (set1->file_string_pool.size) ali@458: pool1 = set1->file_string_pool.data; ali@458: else ali@458: pool1 = NULL; ali@458: if (set2->file_string_pool.size) ali@458: pool2 = set2->file_string_pool.data; ali@458: else ali@458: pool2 = NULL; krh@248: root1 = (struct razor_entry *) set1->files.data; krh@248: root2 = (struct razor_entry *) set2->files.data; krh@248: krh@248: array_init(&merge_stack); krh@248: krh@248: start = merger->set->files.size / sizeof (struct razor_entry); ali@359: last = 0xFFFFFFFF; ali@359: e1 = md->dir1 != 0xFFFFFFFF ? root1 + md->dir1 : NULL; ali@359: e2 = md->dir2 != 0xFFFFFFFF ? root2 + md->dir2 : NULL; krh@248: while (e1 || e2) { krh@248: if (!e2 && !map1[e1 - root1]) { krh@248: if ((e1++)->flags & RAZOR_ENTRY_LAST) krh@248: e1 = NULL; krh@248: continue; krh@248: } krh@248: if (!e1 && !map2[e2 - root2]) { krh@248: if ((e2++)->flags & RAZOR_ENTRY_LAST) krh@248: e2 = NULL; krh@248: continue; krh@248: } krh@248: if (e1 && !map1[e1 - root1] && krh@314: e2 && !map2[e2 - root2]) { krh@248: if ((e1++)->flags & RAZOR_ENTRY_LAST) krh@248: e1 = NULL; krh@248: if ((e2++)->flags & RAZOR_ENTRY_LAST) krh@248: e2 = NULL; krh@248: continue; krh@248: } krh@248: ali@458: if (!e1 || !pool1) krh@248: cmp = 1; ali@458: else if (!e2 || !pool2) krh@248: cmp = -1; krh@248: else { krh@248: cmp = strcmp (&pool1[e1->name], krh@248: &pool2[e2->name]); krh@248: } krh@248: krh@248: if (cmp < 0) { krh@248: if (map1[e1 - root1]) { krh@248: map1[e1 - root1] = last = krh@248: add_file(merger, &pool1[e1->name]); krh@248: if (e1->start) { krh@248: child_md = array_add(&merge_stack, sizeof (struct merge_directory)); krh@248: child_md->merged = last; krh@248: child_md->dir1 = e1->start; ali@359: child_md->dir2 = 0xFFFFFFFF; krh@248: } krh@248: } krh@248: if ((e1++)->flags & RAZOR_ENTRY_LAST) krh@248: e1 = NULL; krh@248: } else if (cmp > 0) { krh@248: if (map2[e2 - root2]) { krh@248: map2[e2 - root2] = last = krh@248: add_file(merger, &pool2[e2->name]); krh@248: if (e2->start) { krh@248: child_md = array_add(&merge_stack, sizeof (struct merge_directory)); krh@248: child_md->merged = last; ali@359: child_md->dir1 = 0xFFFFFFFF; krh@248: child_md->dir2 = e2->start; krh@248: } krh@248: } krh@248: if ((e2++)->flags & RAZOR_ENTRY_LAST) krh@248: e2 = NULL; krh@248: } else { krh@248: map1[e1 - root1] = map2[e2- root2] = last = krh@248: add_file(merger, &pool1[e1->name]); krh@248: if (e1->start || e2->start) { krh@248: child_md = array_add(&merge_stack, sizeof (struct merge_directory)); krh@248: child_md->merged = last; ali@359: child_md->dir1 = e1->start ? e1->start : 0xFFFFFFFF; ali@359: child_md->dir2 = e2->start ? e2->start : 0xFFFFFFFF; krh@248: } krh@248: if ((e1++)->flags & RAZOR_ENTRY_LAST) krh@248: e1 = NULL; krh@248: if ((e2++)->flags & RAZOR_ENTRY_LAST) krh@248: e2 = NULL; krh@248: } krh@248: } krh@248: krh@248: mroot = (struct razor_entry *)merger->set->files.data; ali@359: if (last != 0xFFFFFFFF) { krh@248: mroot[last].flags = RAZOR_ENTRY_LAST; krh@248: mroot[md->merged].start = start; ali@359: } krh@248: krh@248: end_md = merge_stack.data + merge_stack.size; krh@248: for (child_md = merge_stack.data; child_md < end_md; child_md++) krh@248: merge_one_directory(merger, child_md); krh@248: array_release(&merge_stack); krh@248: } krh@248: krh@248: static void krh@248: merge_files(struct razor_merger *merger) krh@248: { krh@248: struct razor_entry *root; krh@248: struct merge_directory md; krh@248: uint32_t *map1, *map2; krh@248: krh@248: map1 = merger->source1.file_map; krh@248: map2 = merger->source2.file_map; krh@248: krh@248: md.merged = 0; krh@248: krh@248: if (merger->source1.set->files.size) { krh@248: root = (struct razor_entry *) merger->source1.set->files.data; krh@248: if (root->start) krh@248: fix_file_map(map1, root, root); krh@248: md.dir1 = 0; ali@359: } else { ali@359: md.dir1 = 0xFFFFFFFF; ali@359: } krh@248: krh@248: if (merger->source2.set->files.size) { krh@248: root = (struct razor_entry *) merger->source2.set->files.data; krh@248: if (root->start) krh@248: fix_file_map(map2, root, root); krh@248: md.dir2 = 0; ali@359: } else { ali@359: md.dir2 = 0xFFFFFFFF; ali@359: } ali@359: ali@359: /* Remove the unnamed root which razor_set_create() added */ ali@359: array_release(&merger->set->files); ali@359: array_init(&merger->set->files); krh@248: krh@248: merge_one_directory(merger, &md); krh@248: } krh@248: krh@248: static void krh@248: emit_files(struct list_head *files, struct array *source_pool, krh@248: uint32_t *map, struct array *pool) krh@248: { krh@248: uint32_t r; krh@248: struct list *p, *q; krh@248: krh@248: r = pool->size / sizeof *q; krh@248: p = list_first(files, source_pool); krh@248: while (p) { krh@248: q = array_add(pool, sizeof *q); krh@248: q->data = map[p->data]; krh@248: q->flags = p->flags; krh@248: p = list_next(p); krh@248: } krh@248: krh@248: list_set_ptr(files, r); krh@248: } krh@248: krh@248: /* Rebuild property->packages maps. We can't just remap these, as a krh@248: * property may have lost or gained a number of packages. Allocate an krh@248: * array per property and loop through the packages and add them to krh@248: * the arrays for their properties. */ krh@248: static void krh@248: rebuild_property_package_lists(struct razor_set *set) krh@248: { krh@248: struct array *pkgs, *a; krh@248: struct razor_package *pkg, *pkg_end; krh@248: struct razor_property *prop, *prop_end; krh@248: struct list *r; krh@248: uint32_t *q; krh@248: int count; krh@248: krh@248: count = set->properties.size / sizeof (struct razor_property); krh@248: pkgs = zalloc(count * sizeof *pkgs); krh@248: pkg_end = set->packages.data + set->packages.size; krh@248: krh@248: for (pkg = set->packages.data; pkg < pkg_end; pkg++) { krh@248: r = list_first(&pkg->properties, &set->property_pool); krh@248: while (r) { krh@248: q = array_add(&pkgs[r->data], sizeof *q); krh@248: *q = pkg - (struct razor_package *) set->packages.data; krh@248: r = list_next(r); krh@248: } krh@248: } krh@248: krh@248: prop_end = set->properties.data + set->properties.size; krh@248: a = pkgs; krh@248: for (prop = set->properties.data; prop < prop_end; prop++, a++) { krh@248: list_set_array(&prop->packages, &set->package_pool, a, 0); krh@248: array_release(a); krh@248: } krh@248: free(pkgs); krh@248: } krh@248: krh@248: static void krh@248: rebuild_file_package_lists(struct razor_set *set) krh@248: { krh@248: struct array *pkgs, *a; krh@248: struct razor_package *pkg, *pkg_end; krh@248: struct razor_entry *entry, *entry_end; krh@248: struct list *r; krh@248: uint32_t *q; krh@248: int count; krh@248: krh@248: count = set->files.size / sizeof (struct razor_entry); krh@248: pkgs = zalloc(count * sizeof *pkgs); krh@248: pkg_end = set->packages.data + set->packages.size; krh@248: krh@248: for (pkg = set->packages.data; pkg < pkg_end; pkg++) { krh@248: r = list_first(&pkg->files, &set->file_pool); krh@248: while (r) { krh@248: q = array_add(&pkgs[r->data], sizeof *q); krh@248: *q = pkg - (struct razor_package *) set->packages.data; krh@248: r = list_next(r); krh@248: } krh@248: } krh@248: krh@248: entry_end = set->files.data + set->files.size; krh@248: a = pkgs; krh@248: for (entry = set->files.data; entry < entry_end; entry++, a++) { krh@248: list_set_array(&entry->packages, &set->package_pool, a, 0); krh@248: array_release(a); krh@248: } krh@248: free(pkgs); krh@248: } krh@248: krh@248: struct razor_set * ali@369: razor_merger_commit(struct razor_merger *merger) krh@248: { krh@248: struct razor_package *p, *pend; krh@248: krh@248: /* As we built the package list, we filled out a bitvector of krh@248: * the properties that are referenced by the packages in the krh@248: * new set. Now we do a parallel loop through the properties krh@248: * and emit those marked in the bit vector to the new set. In krh@248: * the process, we update the bit vector to actually map from krh@248: * indices in the old property list to indices in the new krh@248: * property list for both sets. */ krh@248: krh@248: merge_properties(merger); krh@248: merge_files(merger); krh@248: krh@248: /* Now we loop through the packages again and emit the krh@248: * property lists, remapped to point to the new properties. */ krh@248: krh@248: pend = merger->set->packages.data + merger->set->packages.size; krh@248: for (p = merger->set->packages.data; p < pend; p++) { krh@248: struct source *src; krh@248: krh@248: if (p->flags & UPSTREAM_SOURCE) krh@248: src = &merger->source2; krh@248: else krh@248: src = &merger->source1; krh@248: krh@248: emit_properties(&p->properties, krh@248: &src->set->property_pool, krh@248: src->property_map, krh@248: &merger->set->property_pool); krh@248: emit_files(&p->files, krh@248: &src->set->file_pool, krh@248: src->file_map, krh@248: &merger->set->file_pool); krh@248: p->flags &= ~UPSTREAM_SOURCE; krh@248: } krh@248: krh@248: rebuild_property_package_lists(merger->set); krh@248: rebuild_file_package_lists(merger->set); krh@248: ali@369: merger->committed = 1; ali@369: ali@369: return merger->set; ali@369: } ali@369: ali@369: void ali@369: razor_merger_package_add_script(struct razor_merger *merger, ali@369: struct razor_package *package, ali@369: enum razor_property_flags script, ali@369: const char *program, const char *body) ali@369: { ali@369: uint32_t p, b; ali@369: char *pool; ali@369: struct razor_set *set = merger->set; ali@369: assert ((void *)package >= set->packages.data && \ ali@369: (void *)package < set->packages.data + set->packages.size); ali@369: ali@369: p = hashtable_tokenize(&merger->table, program); ali@369: b = hashtable_tokenize(&merger->table, body); ali@369: ali@369: pool = merger->set->string_pool.data; ali@369: ali@369: switch (script) { ali@369: case RAZOR_PROPERTY_PREUN: ali@403: if (package->preun.program != p) { ali@403: assert(pool[package->preun.program] == '\0'); ali@403: package->preun.program = p; ali@403: } ali@403: if (package->preun.body != b) { ali@403: assert(pool[package->preun.body] == '\0'); ali@403: package->preun.body = b; ali@403: } ali@369: break; ali@369: case RAZOR_PROPERTY_POSTUN: ali@403: if (package->postun.program != p) { ali@403: assert(pool[package->postun.program] == '\0'); ali@403: package->postun.program = p; ali@403: } ali@403: if (package->postun.body != b) { ali@403: assert(pool[package->postun.body] == '\0'); ali@403: package->postun.body = b; ali@403: } ali@369: break; ali@369: default: ali@369: break; ali@369: } ali@369: } ali@369: ali@369: void razor_merger_destroy(struct razor_merger *merger) ali@369: { krh@248: hashtable_release(&merger->table); ali@348: hashtable_release(&merger->file_table); ali@394: hashtable_release(&merger->details_table); ali@458: free(merger->source1.property_map); ali@458: free(merger->source1.file_map); ali@458: free(merger->source2.property_map); ali@458: free(merger->source2.file_map); krh@248: free(merger); krh@248: }