Fix swapping of map entries in __qsort_with_data.
17 array_init(struct array *array)
19 memset(array, 0, sizeof *array);
23 array_release(struct array *array)
29 array_add(struct array *array, int size)
39 while (alloc < array->size + size)
42 if (array->alloc < alloc) {
43 data = realloc(array->data, alloc);
50 p = array->data + array->size;
57 write_to_fd(int fd, void *p, size_t size)
63 len = write(fd, p, rest);
83 struct razor_set_section razor_sections[] = {
84 { RAZOR_PACKAGES, offsetof(struct razor_set, packages) },
85 { RAZOR_REQUIRES, offsetof(struct razor_set, requires) },
86 { RAZOR_PROVIDES, offsetof(struct razor_set, provides) },
87 { RAZOR_STRING_POOL, offsetof(struct razor_set, string_pool) },
88 { RAZOR_PROPERTY_POOL, offsetof(struct razor_set, property_pool) },
92 razor_set_create(void)
94 return zalloc(sizeof(struct razor_set));
98 razor_set_open(const char *filename)
100 struct razor_set *set;
101 struct razor_set_section *s;
106 set = zalloc(sizeof *set);
107 fd = open(filename, O_RDONLY);
108 if (fstat(fd, &stat) < 0)
110 set->header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
111 if (set->header == MAP_FAILED) {
116 for (s = set->header->sections; ~s->type; s++) {
117 if (s->type >= ARRAY_SIZE(razor_sections))
119 if (s->type != razor_sections[s->type].type)
121 array = (void *) set + razor_sections[s->type].offset;
122 array->data = (void *) set->header + s->offset;
123 array->size = s->size;
124 array->alloc = s->size;
132 razor_set_destroy(struct razor_set *set)
139 for (i = 0; set->header->sections[i].type; i++)
141 size = set->header->sections[i].type;
142 munmap(set->header, size);
143 free(set->buckets.data);
145 for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
146 a = (void *) set + razor_sections[i].offset;
149 free(set->buckets.data);
156 razor_set_write(struct razor_set *set, const char *filename)
159 struct razor_set_header *header = (struct razor_set_header *) data;
161 unsigned long offset;
164 memset(data, 0, sizeof data);
165 header->magic = RAZOR_MAGIC;
166 header->version = RAZOR_VERSION;
167 offset = sizeof data;
169 for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
170 if (razor_sections[i].type != i)
172 a = (void *) set + razor_sections[i].offset;
173 header->sections[i].type = i;
174 header->sections[i].offset = offset;
175 header->sections[i].size = a->size;
176 offset += (a->size + 4095) & ~4095;
179 header->sections[i].type = ~0;
180 header->sections[i].offset = 0;
181 header->sections[i].size = 0;
183 fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, 0666);
187 write_to_fd(fd, data, sizeof data);
188 for (i = 0; i < ARRAY_SIZE(razor_sections); i++) {
189 if (razor_sections[i].type != i)
191 a = (void *) set + razor_sections[i].offset;
192 write_to_fd(fd, a->data, (a->size + 4095) & ~4095);
201 hash_string(const char *key)
204 unsigned int hash = 0;
206 for (p = key; *p; p++)
207 hash = (hash * 617) ^ *p;
213 razor_set_lookup(struct razor_set *set, const char *key)
215 unsigned int mask, start, i;
219 pool = set->string_pool.data;
220 mask = set->buckets.alloc - 1;
221 start = hash_string(key) * sizeof(unsigned long);
223 for (i = 0; i < set->buckets.alloc; i += sizeof *b) {
224 b = set->buckets.data + ((start + i) & mask);
229 if (strcmp(key, &pool[*b]) == 0)
237 add_to_string_pool(struct razor_set *set, const char *key)
242 len = strlen(key) + 1;
243 p = array_add(&set->string_pool, len);
246 return p - (char *) set->string_pool.data;
250 add_to_property_pool(struct razor_set *set, struct array *properties)
254 p = array_add(properties, sizeof *p);
256 p = array_add(&set->property_pool, properties->size);
257 memcpy(p, properties->data, properties->size);
259 return p - (unsigned long *) set->property_pool.data;
263 do_insert(struct razor_set *set, unsigned long value)
265 unsigned int mask, start, i;
269 key = (char *) set->string_pool.data + value;
270 mask = set->buckets.alloc - 1;
271 start = hash_string(key) * sizeof(unsigned long);
273 for (i = 0; i < set->buckets.alloc; i += sizeof *b) {
274 b = set->buckets.data + ((start + i) & mask);
283 razor_set_insert(struct razor_set *set, const char *key)
285 unsigned long value, *buckets, *b, *end;
288 alloc = set->buckets.alloc;
289 array_add(&set->buckets, 4 * sizeof *buckets);
290 if (alloc != set->buckets.alloc) {
291 end = set->buckets.data + alloc;
292 memset(end, 0, set->buckets.alloc - alloc);
293 for (b = set->buckets.data; b < end; b++) {
297 do_insert(set, value);
302 value = add_to_string_pool(set, key);
303 do_insert (set, value);
309 razor_set_tokenize(struct razor_set *set, const char *string)
314 return razor_set_tokenize(set, "");
316 token = razor_set_lookup(set, string);
320 return razor_set_insert(set, string);
324 import_context_add_package(struct import_context *ctx,
325 const char *name, const char *version)
327 struct razor_package *p;
329 p = array_add(&ctx->set->packages, sizeof *p);
330 p->name = razor_set_tokenize(ctx->set, name);
331 p->version = razor_set_tokenize(ctx->set, version);
334 array_init(&ctx->requires.package);
335 array_init(&ctx->provides.package);
339 import_context_finish_package(struct import_context *ctx)
341 struct razor_package *p;
344 p->requires = add_to_property_pool(ctx->set, &ctx->requires.package);
345 p->provides = add_to_property_pool(ctx->set, &ctx->provides.package);
347 array_release(&ctx->requires.package);
348 array_release(&ctx->provides.package);
352 import_context_add_property(struct import_context *ctx,
353 struct import_property_context *pctx,
354 const char *name, const char *version)
356 struct razor_property *p;
359 p = array_add(pctx->all, sizeof *p);
360 p->name = razor_set_tokenize(ctx->set, name);
361 p->version = razor_set_tokenize(ctx->set, version);
362 p->packages = ctx->package -
363 (struct razor_package *) ctx->set->packages.data;
365 r = array_add(&pctx->package, sizeof *r);
366 *r = p - (struct razor_property *) pctx->all->data;
370 razor_prepare_import(struct import_context *ctx)
372 memset(ctx, 0, sizeof *ctx);
373 ctx->set = razor_set_create();
374 ctx->requires.all = &ctx->set->requires;
375 ctx->provides.all = &ctx->set->provides;
378 typedef int (*compare_with_data_func_t)(const void *p1,
382 struct qsort_context {
384 compare_with_data_func_t compare;
389 qsort_swap(void *p1, void *p2, size_t size)
393 memcpy(buffer, p1, size);
394 memcpy(p1, p2, size);
395 memcpy(p2, buffer, size);
399 __qsort_with_data(void *base, size_t nelem, unsigned long *map,
400 struct qsort_context *ctx)
402 void *p, *start, *end, *pivot;
403 unsigned long *mp, *mstart, *mend, tmp;
404 int left, right, result;
405 size_t size = ctx->size;
409 end = base + nelem * size;
413 pivot = base + (random() % nelem) * size;
416 result = ctx->compare(p, pivot, ctx->data);
418 qsort_swap(p, start, size);
428 } else if (result == 0) {
434 qsort_swap(p, end, size);
443 left = (start - base) / size;
444 right = (base + nelem * size - end) / size;
446 __qsort_with_data(base, left, map, ctx);
448 __qsort_with_data(end, right, mend, ctx);
452 qsort_with_data(void *base, size_t nelem, size_t size,
453 compare_with_data_func_t compare, void *data)
455 struct qsort_context ctx;
460 ctx.compare = compare;
463 map = malloc(nelem * sizeof (unsigned long));
464 for (i = 0; i < nelem; i++)
467 __qsort_with_data(base, nelem, map, &ctx);
473 compare_packages(const void *p1, const void *p2, void *data)
475 const struct razor_package *pkg1 = p1, *pkg2 = p2;
476 struct razor_set *set = data;
477 char *pool = set->string_pool.data;
479 if (pkg1->name == pkg2->name)
482 return strcmp(&pool[pkg1->name], &pool[pkg2->name]);
486 compare_properties(const void *p1, const void *p2, void *data)
488 const struct razor_property *prop1 = p1, *prop2 = p2;
489 struct razor_set *set = data;
490 char *pool = set->string_pool.data;
492 if (prop1->name == prop2->name)
493 return strcmp(&pool[prop1->version], &pool[prop2->version]);
495 return strcmp(&pool[prop1->name], &pool[prop2->name]);
498 static unsigned long *
499 uniqueify_properties(struct razor_set *set, struct array *properties)
501 struct razor_property *rp, *up, *rp_end;
502 struct array *pkgs, *p;
503 unsigned long *map, *rmap, *r;
504 int i, count, unique;
506 count = properties->size / sizeof(struct razor_property);
507 map = qsort_with_data(properties->data,
509 sizeof(struct razor_property),
513 rp_end = properties->data + properties->size;
514 rmap = malloc(count * sizeof *map);
515 pkgs = zalloc(count * sizeof *pkgs);
516 for (rp = properties->data, up = rp, i = 0; rp < rp_end; rp++, i++) {
517 if (rp->name != up->name || rp->version != up->version) {
520 up->version = rp->version;
523 unique = up - (struct razor_property *) properties->data;
524 rmap[map[i]] = unique;
525 r = array_add(&pkgs[unique], sizeof *r);
531 properties->size = (void *) up - properties->data;
533 for (rp = properties->data, p = pkgs; rp < rp_end; rp++, p++) {
534 rp->packages = add_to_property_pool(set, p);
544 remap_package_links(struct import_context *ctx)
546 struct razor_package *p, *end;
547 unsigned long *pool, *r;
549 pool = ctx->set->property_pool.data;
550 end = ctx->set->packages.data + ctx->set->packages.size;
551 for (p = ctx->set->packages.data; p < end; p++) {
552 for (r = &pool[p->requires]; ~*r; r++)
553 *r = ctx->requires_map[*r];
554 for (r = &pool[p->provides]; ~*r; r++)
555 *r = ctx->provides_map[*r];
560 remap_property_links(struct import_context *ctx, unsigned long *map)
562 struct razor_property *p, *end;
563 struct razor_package *rp;
564 unsigned long *pool, *r, *rmap;
567 pool = ctx->set->property_pool.data;
568 count = ctx->set->packages.size / sizeof(struct razor_package);
569 rmap = malloc(count * sizeof *map);
570 rp = ctx->set->packages.data;
571 for (i = 0; i < count; i++)
574 /* FIXME: This will break if we implement package list sharing
575 * for all properties, since we'll remap those lists more than
576 * once. We should just have a separate pool for property
577 * lists and a separate pool for package lists and remap it as
578 * a flat pool. Right now, as property lists and package
579 * lists are mixed, we can't do that. */
581 end = ctx->set->requires.data + ctx->set->requires.size;
582 for (p = ctx->set->requires.data; p < end; p++)
583 for (r = &pool[p->packages]; ~*r; r++)
586 end = ctx->set->provides.data + ctx->set->provides.size;
587 for (p = ctx->set->provides.data; p < end; p++)
588 for (r = &pool[p->packages]; ~*r; r++)
595 razor_finish_import(struct import_context *ctx)
600 ctx->requires_map = uniqueify_properties(ctx->set, ctx->requires.all);
601 ctx->provides_map = uniqueify_properties(ctx->set, ctx->provides.all);
602 remap_package_links(ctx);
603 free(ctx->requires_map);
604 free(ctx->provides_map);
606 count = ctx->set->packages.size / sizeof(struct razor_package);
607 map = qsort_with_data(ctx->set->packages.data,
609 sizeof(struct razor_package),
612 remap_property_links(ctx, map);
619 razor_set_list(struct razor_set *set)
621 struct razor_package *p, *end;
624 pool = set->string_pool.data;
625 end = set->packages.data + set->packages.size;
626 for (p = set->packages.data; p < end; p++)
627 printf("%s %s\n", &pool[p->name], &pool[p->version]);
630 struct razor_set *bsearch_set;
633 compare_package_name(const void *key, const void *data)
635 const struct razor_package *p = data;
638 pool = bsearch_set->string_pool.data;
640 return strcmp(key, &pool[p->name]);
643 struct razor_package *
644 razor_set_get_package(struct razor_set *set, const char *package)
647 return bsearch(package, set->packages.data,
648 set->packages.size / sizeof(struct razor_package),
649 sizeof(struct razor_package), compare_package_name);
653 compare_property_name(const void *key, const void *data)
655 const struct razor_property *p = data;
658 pool = bsearch_set->string_pool.data;
660 return strcmp(key, &pool[p->name]);
663 struct razor_property *
664 razor_set_get_property(struct razor_set *set,
665 struct array *properties,
666 const char *property)
668 struct razor_property *p, *start;
671 p = bsearch(property, properties->data,
672 properties->size / sizeof(struct razor_property),
673 sizeof(struct razor_property), compare_property_name);
675 start = properties->data;
676 while (p > start && (p - 1)->name == p->name)
683 razor_set_list_all_properties(struct razor_set *set, struct array *properties)
685 struct razor_property *p, *end;
688 pool = set->string_pool.data;
689 end = properties->data + properties->size;
690 for (p = properties->data; p < end; p++)
691 printf("%s %s\n", &pool[p->name], &pool[p->version]);
695 razor_set_list_requires(struct razor_set *set, const char *name)
697 struct razor_property *p, *requires;
698 struct razor_package *package;
703 package = razor_set_get_package(set, name);
704 r = (unsigned long *) set->property_pool.data +
706 requires = set->requires.data;
707 pool = set->string_pool.data;
710 printf("%s %s\n", &pool[p->name], &pool[p->version]);
713 razor_set_list_all_properties(set, &set->requires);
717 razor_set_list_provides(struct razor_set *set, const char *name)
719 struct razor_property *p, *provides;
720 struct razor_package *package;
725 package = razor_set_get_package(set, name);
726 r = (unsigned long *) set->property_pool.data +
728 provides = set->provides.data;
729 pool = set->string_pool.data;
732 printf("%s %s\n", &pool[p->name], &pool[p->version]);
735 razor_set_list_all_properties(set, &set->provides);
739 razor_set_list_property_packages(struct razor_set *set,
740 struct array *properties,
744 struct razor_property *property, *end;
745 struct razor_package *p, *packages;
752 property = razor_set_get_property(set, properties, name);
753 packages = set->packages.data;
754 pool = set->string_pool.data;
755 end = properties->data + properties->size;
756 while (property < end && strcmp(name, &pool[property->name]) == 0) {
757 if (version && strcmp(version, &pool[property->version]) != 0)
759 r = (unsigned long *)
760 set->property_pool.data + property->packages;
764 &pool[p->name], &pool[p->version]);
772 razor_set_validate(struct razor_set *set, struct array *unsatisfied)
774 struct razor_property *r, *p, *rend, *pend;
778 r = set->requires.data;
779 p = set->provides.data;
780 rend = set->requires.data + set->requires.size;
781 pend = set->provides.data + set->provides.size;
782 pool = set->string_pool.data;
785 while (p < pend && strcmp(&pool[r->name], &pool[p->name]) > 0)
787 if (p == pend || strcmp(&pool[r->name], &pool[p->name]) != 0) {
788 u = array_add(unsatisfied, sizeof *u);
789 *u = r - (struct razor_property *) set->requires.data;
796 razor_set_list_unsatisfied(struct razor_set *set)
798 struct array unsatisfied;
799 struct razor_property *requires, *r;
800 unsigned long *u, *end;
803 array_init(&unsatisfied);
804 razor_set_validate(set, &unsatisfied);
806 end = unsatisfied.data + unsatisfied.size;
807 requires = set->requires.data;
808 pool = set->string_pool.data;
810 for (u = unsatisfied.data; u < end; u++) {
812 printf("%s %s not satisfied\n",
813 &pool[r->name], &pool[r->version]);
816 array_release(&unsatisfied);
820 razor_set_info(struct razor_set *set)
822 unsigned int offset, size;
825 for (i = 0; i < set->header->sections[i].type; i++) {
826 offset = set->header->sections[i].offset;
827 size = set->header->sections[i].size;
829 switch (set->header->sections[i].type) {
831 printf("package section:\t%dkb\n", size / 1024);
834 printf("requires section:\t%dkb\n", size / 1024);
837 printf("provides section:\t%dkb\n", size / 1024);
839 case RAZOR_STRING_POOL:
840 printf("string pool:\t\t%dkb\n", size / 1024);
842 case RAZOR_PROPERTY_POOL:
843 printf("properties section:\t%dkb\n", size / 1024);
852 printf("usage: razor [ import FILES | lookup <key> | "
853 "list | list-requires | list-provides | eat-yum | info ]\n");
857 static const char *repo_filename = "system.repo";
858 static const char rawhide_repo_filename[] = "rawhide.repo";
861 main(int argc, const char *argv[])
863 struct razor_set *set;
867 repo = getenv("RAZOR_REPO");
869 repo_filename = repo;
873 } else if (strcmp(argv[1], "import") == 0) {
874 if (stat("set", &statbuf) && mkdir("set", 0777)) {
875 fprintf(stderr, "could not create directory 'set'\n");
879 set = razor_import_rzr_files(argc - 2, argv + 2);
881 printf("bucket allocation: %d\n", set->buckets.alloc);
882 printf("pool size: %d\n", set->string_pool.size);
883 printf("pool allocation: %d\n", set->string_pool.alloc);
884 printf("packages: %d\n",
885 set->packages.size / sizeof(struct razor_package));
886 printf("requires: %d\n",
887 set->requires.size / sizeof(struct razor_property));
888 printf("provides: %d\n",
889 set->provides.size / sizeof(struct razor_property));
891 razor_set_write(set, repo_filename);
893 razor_set_destroy(set);
894 } else if (strcmp(argv[1], "lookup") == 0) {
895 set = razor_set_open(repo_filename);
896 printf("%s is %lu\n", argv[2],
897 razor_set_lookup(set, argv[2]));
898 razor_set_destroy(set);
899 } else if (strcmp(argv[1], "list") == 0) {
900 set = razor_set_open(repo_filename);
902 razor_set_destroy(set);
903 } else if (strcmp(argv[1], "list-requires") == 0) {
904 set = razor_set_open(repo_filename);
905 razor_set_list_requires(set, argv[2]);
906 razor_set_destroy(set);
907 } else if (strcmp(argv[1], "list-provides") == 0) {
908 set = razor_set_open(repo_filename);
909 razor_set_list_provides(set, argv[2]);
910 razor_set_destroy(set);
911 } else if (strcmp(argv[1], "what-requires") == 0) {
912 set = razor_set_open(repo_filename);
913 razor_set_list_property_packages(set, &set->requires,
915 razor_set_destroy(set);
916 } else if (strcmp(argv[1], "what-provides") == 0) {
917 set = razor_set_open(repo_filename);
918 razor_set_list_property_packages(set, &set->provides,
920 razor_set_destroy(set);
921 } else if (strcmp(argv[1], "info") == 0) {
922 set = razor_set_open(repo_filename);
924 razor_set_destroy(set);
925 } else if (strcmp(argv[1], "eat-yum") == 0) {
926 set = razor_set_create_from_yum_filelist(STDIN_FILENO);
929 razor_set_write(set, rawhide_repo_filename);
930 razor_set_destroy(set);
931 printf("wrote %s\n", rawhide_repo_filename);
932 } else if (strcmp(argv[1], "import-rpmdb") == 0) {
933 set = razor_set_create_from_rpmdb();
936 razor_set_write(set, repo_filename);
937 razor_set_destroy(set);
938 printf("wrote %s\n", repo_filename);
939 } else if (strcmp(argv[1], "validate") == 0) {
940 set = razor_set_open(repo_filename);
943 razor_set_list_unsatisfied(set);
944 razor_set_destroy(set);