1.1 --- a/main.c Sat Apr 05 01:02:12 2008 -0400
1.2 +++ b/main.c Sat Apr 05 01:15:04 2008 -0400
1.3 @@ -1,8 +1,8 @@
1.4 #include <stdlib.h>
1.5 #include <stddef.h>
1.6 #include <stdio.h>
1.7 +#include <stdint.h>
1.8 #include <string.h>
1.9 -#include <sys/types.h>
1.10 #include <sys/stat.h>
1.11 #include <unistd.h>
1.12 #include <dirent.h>
2.1 --- a/razor-internal.h Sat Apr 05 01:02:12 2008 -0400
2.2 +++ b/razor-internal.h Sat Apr 05 01:15:04 2008 -0400
2.3 @@ -8,4 +8,12 @@
2.4 int razor_create_dir(const char *root, const char *path);
2.5 int razor_write(int fd, const void *data, size_t size);
2.6
2.7 +
2.8 +typedef int (*razor_compare_with_data_func_t)(const void *p1,
2.9 + const void *p,
2.10 + void *data);
2.11 +uint32_t *
2.12 +razor_qsort_with_data(void *base, size_t nelem, size_t size,
2.13 + razor_compare_with_data_func_t compare, void *data);
2.14 +
2.15 #endif /* _RAZOR_INTERNAL_H_ */
3.1 --- a/razor.c Sat Apr 05 01:02:12 2008 -0400
3.2 +++ b/razor.c Sat Apr 05 01:15:04 2008 -0400
3.3 @@ -351,104 +351,6 @@
3.4 /* FIXME: write this */
3.5 }
3.6
3.7 -
3.8 -typedef int (*compare_with_data_func_t)(const void *p1,
3.9 - const void *p,
3.10 - void *data);
3.11 -
3.12 -struct qsort_context {
3.13 - size_t size;
3.14 - compare_with_data_func_t compare;
3.15 - void *data;
3.16 -};
3.17 -
3.18 -static void
3.19 -qsort_swap(void *p1, void *p2, size_t size)
3.20 -{
3.21 - char buffer[size];
3.22 -
3.23 - memcpy(buffer, p1, size);
3.24 - memcpy(p1, p2, size);
3.25 - memcpy(p2, buffer, size);
3.26 -}
3.27 -
3.28 -static void
3.29 -__qsort_with_data(void *base, size_t nelem, uint32_t *map,
3.30 - struct qsort_context *ctx)
3.31 -{
3.32 - void *p, *start, *end, *pivot;
3.33 - uint32_t *mp, *mstart, *mend, tmp;
3.34 - int left, right, result;
3.35 - size_t size = ctx->size;
3.36 -
3.37 - p = base;
3.38 - start = base;
3.39 - end = base + nelem * size;
3.40 - mp = map;
3.41 - mstart = map;
3.42 - mend = map + nelem;
3.43 - pivot = base + (random() % nelem) * size;
3.44 -
3.45 - while (p < end) {
3.46 - result = ctx->compare(p, pivot, ctx->data);
3.47 - if (result < 0) {
3.48 - qsort_swap(p, start, size);
3.49 - tmp = *mp;
3.50 - *mp = *mstart;
3.51 - *mstart = tmp;
3.52 - if (start == pivot)
3.53 - pivot = p;
3.54 - start += size;
3.55 - mstart++;
3.56 - p += size;
3.57 - mp++;
3.58 - } else if (result == 0) {
3.59 - p += size;
3.60 - mp++;
3.61 - } else {
3.62 - end -= size;
3.63 - mend--;
3.64 - qsort_swap(p, end, size);
3.65 - tmp = *mp;
3.66 - *mp = *mend;
3.67 - *mend = tmp;
3.68 - if (end == pivot)
3.69 - pivot = p;
3.70 - }
3.71 - }
3.72 -
3.73 - left = (start - base) / size;
3.74 - right = (base + nelem * size - end) / size;
3.75 - if (left > 1)
3.76 - __qsort_with_data(base, left, map, ctx);
3.77 - if (right > 1)
3.78 - __qsort_with_data(end, right, mend, ctx);
3.79 -}
3.80 -
3.81 -static uint32_t *
3.82 -qsort_with_data(void *base, size_t nelem, size_t size,
3.83 - compare_with_data_func_t compare, void *data)
3.84 -{
3.85 - struct qsort_context ctx;
3.86 - uint32_t *map;
3.87 - int i;
3.88 -
3.89 - if (nelem == 0)
3.90 - return NULL;
3.91 -
3.92 - ctx.size = size;
3.93 - ctx.compare = compare;
3.94 - ctx.data = data;
3.95 -
3.96 - map = malloc(nelem * sizeof (uint32_t));
3.97 - for (i = 0; i < nelem; i++)
3.98 - map[i] = i;
3.99 -
3.100 - __qsort_with_data(base, nelem, map, &ctx);
3.101 -
3.102 - return map;
3.103 -}
3.104 -
3.105 static int
3.106 versioncmp(const char *s1, const char *s2)
3.107 {
3.108 @@ -527,11 +429,11 @@
3.109 int i, count, unique;
3.110
3.111 count = set->properties.size / sizeof(struct razor_property);
3.112 - map = qsort_with_data(set->properties.data,
3.113 - count,
3.114 - sizeof(struct razor_property),
3.115 - compare_properties,
3.116 - set);
3.117 + map = razor_qsort_with_data(set->properties.data,
3.118 + count,
3.119 + sizeof(struct razor_property),
3.120 + compare_properties,
3.121 + set);
3.122
3.123 rp_end = set->properties.data + set->properties.size;
3.124 rmap = malloc(count * sizeof *map);
3.125 @@ -668,11 +570,11 @@
3.126 struct razor_entry *e;
3.127
3.128 count = importer->files.size / sizeof (struct import_entry);
3.129 - qsort_with_data(importer->files.data,
3.130 - count,
3.131 - sizeof (struct import_entry),
3.132 - compare_filenames,
3.133 - NULL);
3.134 + razor_qsort_with_data(importer->files.data,
3.135 + count,
3.136 + sizeof (struct import_entry),
3.137 + compare_filenames,
3.138 + NULL);
3.139
3.140 root.name = hashtable_tokenize(&importer->table, "");
3.141 array_init(&root.files);
3.142 @@ -767,8 +669,8 @@
3.143
3.144 req = req_start = importer->file_requires.data;
3.145 req_end = importer->file_requires.data + importer->file_requires.size;
3.146 - map = qsort_with_data(req, req_end - req, sizeof *req,
3.147 - compare_file_requires, pool);
3.148 + map = razor_qsort_with_data(req, req_end - req, sizeof *req,
3.149 + compare_file_requires, pool);
3.150 free(map);
3.151
3.152 for (req = req_start; req < req_end; req++) {
3.153 @@ -846,11 +748,11 @@
3.154 free(map);
3.155
3.156 count = importer->set->packages.size / sizeof(struct razor_package);
3.157 - map = qsort_with_data(importer->set->packages.data,
3.158 - count,
3.159 - sizeof(struct razor_package),
3.160 - compare_packages,
3.161 - importer->set);
3.162 + map = razor_qsort_with_data(importer->set->packages.data,
3.163 + count,
3.164 + sizeof(struct razor_package),
3.165 + compare_packages,
3.166 + importer->set);
3.167
3.168 rmap = malloc(count * sizeof *rmap);
3.169 for (i = 0; i < count; i++)
3.170 @@ -2896,17 +2798,17 @@
3.171 *pkg = *trans->packages[p].old_package;
3.172 }
3.173 }
3.174 - map = qsort_with_data(install_packages.data,
3.175 - install_packages.size / sizeof *pkg,
3.176 - sizeof *pkg,
3.177 - compare_packages,
3.178 - trans->upstream);
3.179 + map = razor_qsort_with_data(install_packages.data,
3.180 + install_packages.size / sizeof *pkg,
3.181 + sizeof *pkg,
3.182 + compare_packages,
3.183 + trans->upstream);
3.184 free(map);
3.185 - map = qsort_with_data(remove_packages.data,
3.186 - remove_packages.size / sizeof *pkg,
3.187 - sizeof *pkg,
3.188 - compare_packages,
3.189 - trans->system);
3.190 + map = razor_qsort_with_data(remove_packages.data,
3.191 + remove_packages.size / sizeof *pkg,
3.192 + sizeof *pkg,
3.193 + compare_packages,
3.194 + trans->system);
3.195 free(map);
3.196
3.197 merger = razor_merger_create(trans->system, trans->upstream);
4.1 --- a/util.c Sat Apr 05 01:02:12 2008 -0400
4.2 +++ b/util.c Sat Apr 05 01:15:04 2008 -0400
4.3 @@ -3,6 +3,7 @@
4.4 #include <sys/stat.h>
4.5 #include <stdlib.h>
4.6 #include <stdio.h>
4.7 +#include <stdint.h>
4.8 #include <unistd.h>
4.9
4.10 #include "razor-internal.h"
4.11 @@ -71,3 +72,96 @@
4.12
4.13 return 0;
4.14 }
4.15 +
4.16 +struct qsort_context {
4.17 + size_t size;
4.18 + razor_compare_with_data_func_t compare;
4.19 + void *data;
4.20 +};
4.21 +
4.22 +static void
4.23 +qsort_swap(void *p1, void *p2, size_t size)
4.24 +{
4.25 + char buffer[size];
4.26 +
4.27 + memcpy(buffer, p1, size);
4.28 + memcpy(p1, p2, size);
4.29 + memcpy(p2, buffer, size);
4.30 +}
4.31 +
4.32 +static void
4.33 +__qsort_with_data(void *base, size_t nelem, uint32_t *map,
4.34 + struct qsort_context *ctx)
4.35 +{
4.36 + void *p, *start, *end, *pivot;
4.37 + uint32_t *mp, *mstart, *mend, tmp;
4.38 + int left, right, result;
4.39 + size_t size = ctx->size;
4.40 +
4.41 + p = base;
4.42 + start = base;
4.43 + end = base + nelem * size;
4.44 + mp = map;
4.45 + mstart = map;
4.46 + mend = map + nelem;
4.47 + pivot = base + (random() % nelem) * size;
4.48 +
4.49 + while (p < end) {
4.50 + result = ctx->compare(p, pivot, ctx->data);
4.51 + if (result < 0) {
4.52 + qsort_swap(p, start, size);
4.53 + tmp = *mp;
4.54 + *mp = *mstart;
4.55 + *mstart = tmp;
4.56 + if (start == pivot)
4.57 + pivot = p;
4.58 + start += size;
4.59 + mstart++;
4.60 + p += size;
4.61 + mp++;
4.62 + } else if (result == 0) {
4.63 + p += size;
4.64 + mp++;
4.65 + } else {
4.66 + end -= size;
4.67 + mend--;
4.68 + qsort_swap(p, end, size);
4.69 + tmp = *mp;
4.70 + *mp = *mend;
4.71 + *mend = tmp;
4.72 + if (end == pivot)
4.73 + pivot = p;
4.74 + }
4.75 + }
4.76 +
4.77 + left = (start - base) / size;
4.78 + right = (base + nelem * size - end) / size;
4.79 + if (left > 1)
4.80 + __qsort_with_data(base, left, map, ctx);
4.81 + if (right > 1)
4.82 + __qsort_with_data(end, right, mend, ctx);
4.83 +}
4.84 +
4.85 +uint32_t *
4.86 +razor_qsort_with_data(void *base, size_t nelem, size_t size,
4.87 + razor_compare_with_data_func_t compare, void *data)
4.88 +{
4.89 + struct qsort_context ctx;
4.90 + uint32_t *map;
4.91 + int i;
4.92 +
4.93 + if (nelem == 0)
4.94 + return NULL;
4.95 +
4.96 + ctx.size = size;
4.97 + ctx.compare = compare;
4.98 + ctx.data = data;
4.99 +
4.100 + map = malloc(nelem * sizeof (uint32_t));
4.101 + for (i = 0; i < nelem; i++)
4.102 + map[i] = i;
4.103 +
4.104 + __qsort_with_data(base, nelem, map, &ctx);
4.105 +
4.106 + return map;
4.107 +}