1.1 --- a/razor.c Thu Sep 13 10:54:13 2007 -0400
1.2 +++ b/razor.c Fri Sep 14 13:22:44 2007 -0400
1.3 @@ -387,7 +387,7 @@
1.4 }
1.5
1.6 struct import_property_context {
1.7 - struct array all;
1.8 + struct array *all;
1.9 struct array package;
1.10 };
1.11
1.12 @@ -395,38 +395,20 @@
1.13 struct razor_set *set;
1.14 struct import_property_context requires;
1.15 struct import_property_context provides;
1.16 - struct array packages;
1.17 - struct import_package *package;
1.18 + struct razor_package *package;
1.19 unsigned long *requires_map;
1.20 unsigned long *provides_map;
1.21 };
1.22
1.23 -struct import_package {
1.24 - unsigned long name;
1.25 - unsigned long version;
1.26 - unsigned long requires;
1.27 - unsigned long provides;
1.28 - unsigned long index;
1.29 -};
1.30 -
1.31 -struct import_property {
1.32 - unsigned long name;
1.33 - unsigned long version;
1.34 - unsigned long package;
1.35 - unsigned long index;
1.36 - unsigned long unique_index;
1.37 -};
1.38 -
1.39 static void
1.40 import_context_add_package(struct import_context *ctx,
1.41 const char *name, const char *version)
1.42 {
1.43 - struct import_package *p;
1.44 + struct razor_package *p;
1.45
1.46 - p = array_add(&ctx->packages, sizeof *p);
1.47 + p = array_add(&ctx->set->packages, sizeof *p);
1.48 p->name = razor_set_tokenize(ctx->set, name);
1.49 p->version = razor_set_tokenize(ctx->set, version);
1.50 - p->index = p - (struct import_package *) ctx->packages.data;
1.51
1.52 ctx->package = p;
1.53 array_init(&ctx->requires.package);
1.54 @@ -436,7 +418,7 @@
1.55 void
1.56 import_context_finish_package(struct import_context *ctx)
1.57 {
1.58 - struct import_package *p;
1.59 + struct razor_package *p;
1.60
1.61 p = ctx->package;
1.62 p->requires = add_to_property_pool(ctx->set, &ctx->requires.package);
1.63 @@ -451,17 +433,17 @@
1.64 struct import_property_context *pctx,
1.65 const char *name, const char *version)
1.66 {
1.67 - struct import_property *p;
1.68 + struct razor_property *p;
1.69 unsigned long *r;
1.70
1.71 - p = array_add(&pctx->all, sizeof *p);
1.72 + p = array_add(pctx->all, sizeof *p);
1.73 p->name = razor_set_tokenize(ctx->set, name);
1.74 p->version = razor_set_tokenize(ctx->set, version);
1.75 - p->package = ctx->package->index;
1.76 - p->index = p - (struct import_property *) pctx->all.data;
1.77 + p->packages = ctx->package -
1.78 + (struct razor_package *) ctx->set->packages.data;
1.79
1.80 r = array_add(&pctx->package, sizeof *r);
1.81 - *r = p->index;
1.82 + *r = p - (struct razor_property *) pctx->all->data;
1.83 }
1.84
1.85 static void
1.86 @@ -553,6 +535,8 @@
1.87 {
1.88 memset(ctx, 0, sizeof *ctx);
1.89 ctx->set = razor_set_create();
1.90 + ctx->requires.all = &ctx->set->requires;
1.91 + ctx->provides.all = &ctx->set->provides;
1.92 }
1.93
1.94 static int
1.95 @@ -605,6 +589,12 @@
1.96 const void *p,
1.97 void *data);
1.98
1.99 +struct qsort_context {
1.100 + size_t size;
1.101 + compare_with_data_func_t compare;
1.102 + void *data;
1.103 +};
1.104 +
1.105 static void
1.106 qsort_swap(void *p1, void *p2, size_t size)
1.107 {
1.108 @@ -615,31 +605,45 @@
1.109 memcpy(p2, buffer, size);
1.110 }
1.111
1.112 -void
1.113 -qsort_with_data(void *base, size_t nelem, size_t size,
1.114 - compare_with_data_func_t compare, void *data)
1.115 +static void
1.116 +__qsort_with_data(void *base, size_t nelem, unsigned long *map,
1.117 + struct qsort_context *ctx)
1.118 {
1.119 void *p, *start, *end, *pivot;
1.120 + unsigned long *mp, *mstart, *mend, tmp;
1.121 int left, right, result;
1.122 + size_t size = ctx->size;
1.123
1.124 p = base;
1.125 start = base;
1.126 end = base + nelem * size;
1.127 + mp = map;
1.128 + mstart = map;
1.129 + mend = map + nelem;
1.130 pivot = base + (random() % nelem) * size;
1.131 -
1.132 +
1.133 while (p < end) {
1.134 - result = compare(p, pivot, data);
1.135 + result = ctx->compare(p, pivot, ctx->data);
1.136 if (result < 0) {
1.137 qsort_swap(p, start, size);
1.138 + tmp = *mp;
1.139 + *mp = *mstart;
1.140 + *mstart = tmp;
1.141 if (start == pivot)
1.142 pivot = p;
1.143 start += size;
1.144 + mstart++;
1.145 p += size;
1.146 } else if (result == 0) {
1.147 p += size;
1.148 + mp++;
1.149 } else {
1.150 end -= size;
1.151 + mend--;
1.152 qsort_swap(p, end, size);
1.153 + tmp = *mp;
1.154 + *mp = *mstart;
1.155 + *mstart = tmp;
1.156 if (end == pivot)
1.157 pivot = p;
1.158 }
1.159 @@ -648,15 +652,36 @@
1.160 left = (start - base) / size;
1.161 right = (base + nelem * size - end) / size;
1.162 if (left > 1)
1.163 - qsort_with_data(base, left, size, compare, data);
1.164 + __qsort_with_data(base, left, map, ctx);
1.165 if (right > 1)
1.166 - qsort_with_data(end, right, size, compare, data);
1.167 + __qsort_with_data(end, right, mend, ctx);
1.168 +}
1.169 +
1.170 +unsigned long *
1.171 +qsort_with_data(void *base, size_t nelem, size_t size,
1.172 + compare_with_data_func_t compare, void *data)
1.173 +{
1.174 + struct qsort_context ctx;
1.175 + unsigned long *map;
1.176 + int i;
1.177 +
1.178 + ctx.size = size;
1.179 + ctx.compare = compare;
1.180 + ctx.data = data;
1.181 +
1.182 + map = malloc(nelem * sizeof (unsigned long));
1.183 + for (i = 0; i < nelem; i++)
1.184 + map[i] = i;
1.185 +
1.186 + __qsort_with_data(base, nelem, map, &ctx);
1.187 +
1.188 + return map;
1.189 }
1.190
1.191 static int
1.192 compare_packages(const void *p1, const void *p2, void *data)
1.193 {
1.194 - const struct import_package *pkg1 = p1, *pkg2 = p2;
1.195 + const struct razor_package *pkg1 = p1, *pkg2 = p2;
1.196 struct razor_set *set = data;
1.197 char *pool = set->string_pool.data;
1.198
1.199 @@ -669,7 +694,7 @@
1.200 static int
1.201 compare_properties(const void *p1, const void *p2, void *data)
1.202 {
1.203 - const struct import_property *prop1 = p1, *prop2 = p2;
1.204 + const struct razor_property *prop1 = p1, *prop2 = p2;
1.205 struct razor_set *set = data;
1.206 char *pool = set->string_pool.data;
1.207
1.208 @@ -680,64 +705,59 @@
1.209 }
1.210
1.211 static unsigned long *
1.212 -uniqueify_properties(struct razor_set *set,
1.213 - struct array *in, struct array *out)
1.214 +uniqueify_properties(struct razor_set *set, struct array *properties)
1.215 {
1.216 - struct import_property *ip, *end;
1.217 - struct razor_property *rp, *rp_end;
1.218 + struct razor_property *rp, *up, *rp_end;
1.219 struct array *pkgs, *p;
1.220 - unsigned long *map, *r;
1.221 + unsigned long *map, *rmap, *r;
1.222 int i, count, unique;
1.223
1.224 - count = in->size / sizeof(struct import_property);
1.225 - qsort_with_data(in->data,
1.226 - count,
1.227 - sizeof(struct import_property),
1.228 - compare_properties,
1.229 - set);
1.230 + count = properties->size / sizeof(struct razor_property);
1.231 + map = qsort_with_data(properties->data,
1.232 + count,
1.233 + sizeof(struct razor_property),
1.234 + compare_properties,
1.235 + set);
1.236
1.237 - rp = NULL;
1.238 - end = in->data + in->size;
1.239 - for (ip = in->data; ip < end; ip++) {
1.240 - if (rp == NULL ||
1.241 - ip->name != rp->name || ip->version != rp->version) {
1.242 - rp = array_add(out, sizeof *rp);
1.243 - rp->name = ip->name;
1.244 - rp->version = ip->version;
1.245 + rp_end = properties->data + properties->size;
1.246 + rmap = malloc(count * sizeof *map);
1.247 + pkgs = zalloc(count * sizeof *pkgs);
1.248 + for (rp = properties->data, up = rp, i = 0; rp < rp_end; rp++, i++) {
1.249 + if (rp->name != up->name || rp->version != up->version) {
1.250 + up++;
1.251 + up->name = rp->name;
1.252 + up->version = rp->version;
1.253 }
1.254 - ip->unique_index = rp - (struct razor_property *) out->data;
1.255 +
1.256 + unique = up - (struct razor_property *) properties->data;
1.257 + rmap[map[i]] = unique;
1.258 + r = array_add(&pkgs[unique], sizeof *r);
1.259 + *r = rp->packages;
1.260 }
1.261 + free(map);
1.262
1.263 - map = malloc(count * sizeof (unsigned long));
1.264 - ip = in->data;
1.265 - for (i = 0; i < count; i++)
1.266 - map[ip[i].index] = ip[i].unique_index;
1.267 -
1.268 - unique = out->size / sizeof(*rp);
1.269 - pkgs = zalloc(unique * sizeof *pkgs);
1.270 - for (ip = in->data; ip < end; ip++) {
1.271 - r = array_add(&pkgs[ip->unique_index], sizeof *r);
1.272 - *r = ip->package;
1.273 + up++;
1.274 + properties->size = (void *) up - properties->data;
1.275 + rp_end = up;
1.276 + for (rp = properties->data, p = pkgs; rp < rp_end; rp++, p++) {
1.277 + rp->packages = add_to_property_pool(set, p);
1.278 + array_release(p);
1.279 }
1.280
1.281 - rp_end = out->data + out->size;
1.282 - for (rp = out->data, p = pkgs; rp < rp_end; rp++, p++)
1.283 - rp->packages = add_to_property_pool(set, p);
1.284 -
1.285 free(pkgs);
1.286
1.287 - return map;
1.288 + return rmap;
1.289 }
1.290
1.291 static void
1.292 remap_package_links(struct import_context *ctx)
1.293 {
1.294 - struct import_package *p, *end;
1.295 + struct razor_package *p, *end;
1.296 unsigned long *pool, *r;
1.297
1.298 pool = ctx->set->property_pool.data;
1.299 - end = ctx->packages.data + ctx->packages.size;
1.300 - for (p = ctx->packages.data; p < end; p++) {
1.301 + end = ctx->set->packages.data + ctx->set->packages.size;
1.302 + for (p = ctx->set->packages.data; p < end; p++) {
1.303 for (r = &pool[p->requires]; ~*r; r++)
1.304 *r = ctx->requires_map[*r];
1.305 for (r = &pool[p->provides]; ~*r; r++)
1.306 @@ -746,19 +766,19 @@
1.307 }
1.308
1.309 static void
1.310 -remap_property_links(struct import_context *ctx)
1.311 +remap_property_links(struct import_context *ctx, unsigned long *map)
1.312 {
1.313 struct razor_property *p, *end;
1.314 - struct import_package *ip;
1.315 - unsigned long *map, *pool, *r;
1.316 + struct razor_package *rp;
1.317 + unsigned long *pool, *r, *rmap;
1.318 int i, count;
1.319
1.320 pool = ctx->set->property_pool.data;
1.321 - count = ctx->packages.size / sizeof(struct import_package);
1.322 - map = malloc(count * sizeof *map);
1.323 - ip = ctx->packages.data;
1.324 + count = ctx->set->packages.size / sizeof(struct razor_package);
1.325 + rmap = malloc(count * sizeof *map);
1.326 + rp = ctx->set->packages.data;
1.327 for (i = 0; i < count; i++)
1.328 - map[ip[i].index] = i;
1.329 + rmap[map[i]] = i;
1.330
1.331 /* FIXME: This will break if we implement package list sharing
1.332 * for all properties, since we'll remap those lists more than
1.333 @@ -770,63 +790,36 @@
1.334 end = ctx->set->requires.data + ctx->set->requires.size;
1.335 for (p = ctx->set->requires.data; p < end; p++)
1.336 for (r = &pool[p->packages]; ~*r; r++)
1.337 - *r = map[*r];
1.338 + *r = rmap[*r];
1.339
1.340 end = ctx->set->provides.data + ctx->set->provides.size;
1.341 for (p = ctx->set->provides.data; p < end; p++)
1.342 for (r = &pool[p->packages]; ~*r; r++)
1.343 - *r = map[*r];
1.344 + *r = rmap[*r];
1.345
1.346 - free(map);
1.347 + free(rmap);
1.348 }
1.349
1.350 static struct razor_set *
1.351 razor_finish_import(struct import_context *ctx)
1.352 {
1.353 - struct import_package *ip;
1.354 - struct razor_package *rp;
1.355 - int i, count;
1.356 + unsigned long *map;
1.357 + int count;
1.358
1.359 - ctx->requires_map =
1.360 - uniqueify_properties(ctx->set,
1.361 - &ctx->requires.all,
1.362 - &ctx->set->requires);
1.363 - ctx->provides_map =
1.364 - uniqueify_properties(ctx->set,
1.365 - &ctx->provides.all,
1.366 - &ctx->set->provides);
1.367 -
1.368 + ctx->requires_map = uniqueify_properties(ctx->set, ctx->requires.all);
1.369 + ctx->provides_map = uniqueify_properties(ctx->set, ctx->provides.all);
1.370 remap_package_links(ctx);
1.371 -
1.372 - count = ctx->packages.size / sizeof(struct import_package);
1.373 - qsort_with_data(ctx->packages.data,
1.374 - count,
1.375 - sizeof(struct import_package),
1.376 - compare_packages,
1.377 - ctx->set);
1.378 -
1.379 - ip = ctx->packages.data;
1.380 - for (i = 0; i < count; i++, ip++, rp++) {
1.381 - rp = array_add(&ctx->set->packages, sizeof *rp);
1.382 - rp->name = ip->name;
1.383 - rp->version = ip->version;
1.384 - rp->requires = ip->requires;
1.385 - rp->provides = ip->provides;
1.386 - }
1.387 -
1.388 - remap_property_links(ctx);
1.389 -
1.390 - free(ctx->requires.all.data);
1.391 - free(ctx->provides.all.data);
1.392 free(ctx->requires_map);
1.393 free(ctx->provides_map);
1.394 -
1.395 - fprintf(stderr, "parsed %d requires, %d unique\n",
1.396 - ctx->requires.all.size / sizeof(struct import_property),
1.397 - ctx->set->requires.size / sizeof(struct razor_property));
1.398 - fprintf(stderr, "parsed %d provides, %d unique\n",
1.399 - ctx->provides.all.size / sizeof(struct import_property),
1.400 - ctx->set->provides.size / sizeof(struct razor_property));
1.401 +
1.402 + count = ctx->set->packages.size / sizeof(struct razor_package);
1.403 + map = qsort_with_data(ctx->set->packages.data,
1.404 + count,
1.405 + sizeof(struct razor_package),
1.406 + compare_packages,
1.407 + ctx->set);
1.408 + remap_property_links(ctx, map);
1.409 + free(map);
1.410
1.411 return ctx->set;
1.412 }