1.1 --- a/razor.c Thu Mar 20 14:36:50 2008 -0400
1.2 +++ b/razor.c Sat Apr 05 01:15:04 2008 -0400
1.3 @@ -351,104 +351,6 @@
1.4 /* FIXME: write this */
1.5 }
1.6
1.7 -
1.8 -typedef int (*compare_with_data_func_t)(const void *p1,
1.9 - const void *p,
1.10 - void *data);
1.11 -
1.12 -struct qsort_context {
1.13 - size_t size;
1.14 - compare_with_data_func_t compare;
1.15 - void *data;
1.16 -};
1.17 -
1.18 -static void
1.19 -qsort_swap(void *p1, void *p2, size_t size)
1.20 -{
1.21 - char buffer[size];
1.22 -
1.23 - memcpy(buffer, p1, size);
1.24 - memcpy(p1, p2, size);
1.25 - memcpy(p2, buffer, size);
1.26 -}
1.27 -
1.28 -static void
1.29 -__qsort_with_data(void *base, size_t nelem, uint32_t *map,
1.30 - struct qsort_context *ctx)
1.31 -{
1.32 - void *p, *start, *end, *pivot;
1.33 - uint32_t *mp, *mstart, *mend, tmp;
1.34 - int left, right, result;
1.35 - size_t size = ctx->size;
1.36 -
1.37 - p = base;
1.38 - start = base;
1.39 - end = base + nelem * size;
1.40 - mp = map;
1.41 - mstart = map;
1.42 - mend = map + nelem;
1.43 - pivot = base + (random() % nelem) * size;
1.44 -
1.45 - while (p < end) {
1.46 - result = ctx->compare(p, pivot, ctx->data);
1.47 - if (result < 0) {
1.48 - qsort_swap(p, start, size);
1.49 - tmp = *mp;
1.50 - *mp = *mstart;
1.51 - *mstart = tmp;
1.52 - if (start == pivot)
1.53 - pivot = p;
1.54 - start += size;
1.55 - mstart++;
1.56 - p += size;
1.57 - mp++;
1.58 - } else if (result == 0) {
1.59 - p += size;
1.60 - mp++;
1.61 - } else {
1.62 - end -= size;
1.63 - mend--;
1.64 - qsort_swap(p, end, size);
1.65 - tmp = *mp;
1.66 - *mp = *mend;
1.67 - *mend = tmp;
1.68 - if (end == pivot)
1.69 - pivot = p;
1.70 - }
1.71 - }
1.72 -
1.73 - left = (start - base) / size;
1.74 - right = (base + nelem * size - end) / size;
1.75 - if (left > 1)
1.76 - __qsort_with_data(base, left, map, ctx);
1.77 - if (right > 1)
1.78 - __qsort_with_data(end, right, mend, ctx);
1.79 -}
1.80 -
1.81 -static uint32_t *
1.82 -qsort_with_data(void *base, size_t nelem, size_t size,
1.83 - compare_with_data_func_t compare, void *data)
1.84 -{
1.85 - struct qsort_context ctx;
1.86 - uint32_t *map;
1.87 - int i;
1.88 -
1.89 - if (nelem == 0)
1.90 - return NULL;
1.91 -
1.92 - ctx.size = size;
1.93 - ctx.compare = compare;
1.94 - ctx.data = data;
1.95 -
1.96 - map = malloc(nelem * sizeof (uint32_t));
1.97 - for (i = 0; i < nelem; i++)
1.98 - map[i] = i;
1.99 -
1.100 - __qsort_with_data(base, nelem, map, &ctx);
1.101 -
1.102 - return map;
1.103 -}
1.104 -
1.105 static int
1.106 versioncmp(const char *s1, const char *s2)
1.107 {
1.108 @@ -527,11 +429,11 @@
1.109 int i, count, unique;
1.110
1.111 count = set->properties.size / sizeof(struct razor_property);
1.112 - map = qsort_with_data(set->properties.data,
1.113 - count,
1.114 - sizeof(struct razor_property),
1.115 - compare_properties,
1.116 - set);
1.117 + map = razor_qsort_with_data(set->properties.data,
1.118 + count,
1.119 + sizeof(struct razor_property),
1.120 + compare_properties,
1.121 + set);
1.122
1.123 rp_end = set->properties.data + set->properties.size;
1.124 rmap = malloc(count * sizeof *map);
1.125 @@ -668,11 +570,11 @@
1.126 struct razor_entry *e;
1.127
1.128 count = importer->files.size / sizeof (struct import_entry);
1.129 - qsort_with_data(importer->files.data,
1.130 - count,
1.131 - sizeof (struct import_entry),
1.132 - compare_filenames,
1.133 - NULL);
1.134 + razor_qsort_with_data(importer->files.data,
1.135 + count,
1.136 + sizeof (struct import_entry),
1.137 + compare_filenames,
1.138 + NULL);
1.139
1.140 root.name = hashtable_tokenize(&importer->table, "");
1.141 array_init(&root.files);
1.142 @@ -767,8 +669,8 @@
1.143
1.144 req = req_start = importer->file_requires.data;
1.145 req_end = importer->file_requires.data + importer->file_requires.size;
1.146 - map = qsort_with_data(req, req_end - req, sizeof *req,
1.147 - compare_file_requires, pool);
1.148 + map = razor_qsort_with_data(req, req_end - req, sizeof *req,
1.149 + compare_file_requires, pool);
1.150 free(map);
1.151
1.152 for (req = req_start; req < req_end; req++) {
1.153 @@ -846,11 +748,11 @@
1.154 free(map);
1.155
1.156 count = importer->set->packages.size / sizeof(struct razor_package);
1.157 - map = qsort_with_data(importer->set->packages.data,
1.158 - count,
1.159 - sizeof(struct razor_package),
1.160 - compare_packages,
1.161 - importer->set);
1.162 + map = razor_qsort_with_data(importer->set->packages.data,
1.163 + count,
1.164 + sizeof(struct razor_package),
1.165 + compare_packages,
1.166 + importer->set);
1.167
1.168 rmap = malloc(count * sizeof *rmap);
1.169 for (i = 0; i < count; i++)
1.170 @@ -2896,17 +2798,17 @@
1.171 *pkg = *trans->packages[p].old_package;
1.172 }
1.173 }
1.174 - map = qsort_with_data(install_packages.data,
1.175 - install_packages.size / sizeof *pkg,
1.176 - sizeof *pkg,
1.177 - compare_packages,
1.178 - trans->upstream);
1.179 + map = razor_qsort_with_data(install_packages.data,
1.180 + install_packages.size / sizeof *pkg,
1.181 + sizeof *pkg,
1.182 + compare_packages,
1.183 + trans->upstream);
1.184 free(map);
1.185 - map = qsort_with_data(remove_packages.data,
1.186 - remove_packages.size / sizeof *pkg,
1.187 - sizeof *pkg,
1.188 - compare_packages,
1.189 - trans->system);
1.190 + map = razor_qsort_with_data(remove_packages.data,
1.191 + remove_packages.size / sizeof *pkg,
1.192 + sizeof *pkg,
1.193 + compare_packages,
1.194 + trans->system);
1.195 free(map);
1.196
1.197 merger = razor_merger_create(trans->system, trans->upstream);