1.1 --- a/TODO	Fri Sep 07 14:17:39 2007 -0400
     1.2 +++ b/TODO	Tue Sep 11 19:25:32 2007 -0400
     1.3 @@ -52,3 +52,15 @@
     1.4    and we need to control the on-disk format for these tools.
     1.5  
     1.6  - 20740 requires, 2246 unique... hmm.
     1.7 +
     1.8 +- diff from one package set to another answers: "what changed in
     1.9 +  rawhide between since yesterday?"
    1.10 +
    1.11 +- rewrite qsort and bsearch that doesn't require global context var
    1.12 +  and can output a map describing the permutaion.
    1.13 +
    1.14 +- move package lists out of the property pool, remap properties and
    1.15 +  packages in the two pools by just iterating through the pools.
    1.16 +
    1.17 +- use hash table for package and property lists so we only store
    1.18 +  unique lists (like for string pool).

     2.1 --- a/razor.c	Fri Sep 07 14:17:39 2007 -0400
     2.2 +++ b/razor.c	Tue Sep 11 19:25:32 2007 -0400
     2.3 @@ -141,14 +141,7 @@
     2.4  struct razor_set *
     2.5  razor_set_create(void)
     2.6  {
     2.7 -	struct razor_set *set;
     2.8 -	char *p;
     2.9 -
    2.10 -	set = zalloc(sizeof(struct razor_set));
    2.11 -	p = array_add(&set->string_pool, 1);
    2.12 -	*p = '\0';
    2.13 -
    2.14 -	return set;
    2.15 +	return zalloc(sizeof(struct razor_set));
    2.16  }
    2.17  
    2.18  struct razor_set *
    2.19 @@ -331,7 +324,7 @@
    2.20  	unsigned long  *p;
    2.21  
    2.22  	p = array_add(properties, sizeof *p);
    2.23 -	*p = 0;
    2.24 +	*p = ~0ul;
    2.25  	p = array_add(&set->property_pool, properties->size);
    2.26  	memcpy(p, properties->data, properties->size);
    2.27  
    2.28 @@ -390,7 +383,7 @@
    2.29  	unsigned long token;
    2.30  
    2.31  	if (string == NULL)
    2.32 -		return 0;
    2.33 +		return razor_set_tokenize(set, "");
    2.34  
    2.35  	token = razor_set_lookup(set, string);
    2.36  	if (token != 0)
    2.37 @@ -408,11 +401,20 @@
    2.38  	struct razor_set *set;
    2.39  	struct import_property_context requires;
    2.40  	struct import_property_context provides;
    2.41 -	unsigned long package;
    2.42 +	struct array packages;
    2.43 +	struct import_package *package;
    2.44  	unsigned long *requires_map;
    2.45  	unsigned long *provides_map;
    2.46  };
    2.47  
    2.48 +struct import_package {
    2.49 +	unsigned long name;
    2.50 +	unsigned long version;
    2.51 +	unsigned long requires;
    2.52 +	unsigned long provides;
    2.53 +	unsigned long index;
    2.54 +};
    2.55 +
    2.56  struct import_property {
    2.57  	unsigned long name;
    2.58  	unsigned long version;
    2.59 @@ -425,13 +427,14 @@
    2.60  import_context_add_package(struct import_context *ctx,
    2.61  			   const char *name, const char *version)
    2.62  {
    2.63 -	struct razor_package *p;
    2.64 +	struct import_package *p;
    2.65  
    2.66 -	p = array_add(&ctx->set->packages, sizeof *p);
    2.67 +	p = array_add(&ctx->packages, sizeof *p);
    2.68  	p->name = razor_set_tokenize(ctx->set, name);
    2.69  	p->version = razor_set_tokenize(ctx->set, version);
    2.70 +	p->index = p - (struct import_package *) ctx->packages.data;
    2.71  
    2.72 -	ctx->package = p - (struct razor_package *) ctx->set->packages.data;
    2.73 +	ctx->package = p;
    2.74  	array_init(&ctx->requires.package);
    2.75  	array_init(&ctx->provides.package);
    2.76  }
    2.77 @@ -439,9 +442,9 @@
    2.78  void
    2.79  import_context_finish_package(struct import_context *ctx)
    2.80  {
    2.81 -	struct razor_package *p;
    2.82 +	struct import_package *p;
    2.83  
    2.84 -	p = (struct razor_package *) ctx->set->packages.data + ctx->package;
    2.85 +	p = ctx->package;
    2.86  	p->requires = add_to_property_pool(ctx->set, &ctx->requires.package);
    2.87  	p->provides = add_to_property_pool(ctx->set, &ctx->provides.package);
    2.88  
    2.89 @@ -460,7 +463,7 @@
    2.90  	p = array_add(&pctx->all, sizeof *p);
    2.91  	p->name = razor_set_tokenize(ctx->set, name);
    2.92  	p->version = razor_set_tokenize(ctx->set, version);
    2.93 -	p->package = ctx->package;
    2.94 +	p->package = ctx->package->index;
    2.95  	p->index = p - (struct import_property *) pctx->all.data;
    2.96  
    2.97  	r = array_add(&pctx->package, sizeof *r);
    2.98 @@ -609,7 +612,7 @@
    2.99  static int
   2.100  compare_packages(const void *p1, const void *p2)
   2.101  {
   2.102 -	const struct razor_package *pkg1 = p1, *pkg2 = p2;
   2.103 +	const struct import_package *pkg1 = p1, *pkg2 = p2;
   2.104  	char *pool = qsort_set->string_pool.data;
   2.105  
   2.106  	return strcmp(&pool[pkg1->name], &pool[pkg2->name]);
   2.107 @@ -630,12 +633,14 @@
   2.108  }
   2.109  
   2.110  static unsigned long *
   2.111 -uniqueify_properties(struct array *in, struct array *out)
   2.112 +uniqueify_properties(struct razor_set *set,
   2.113 +		     struct array *in, struct array *out)
   2.114  {
   2.115  	struct import_property *ip, *end;
   2.116 -	struct razor_property *rp;
   2.117 -	unsigned long *map;
   2.118 -	int i, count;
   2.119 +	struct razor_property *rp, *rp_end;
   2.120 +	struct array *pkgs, *p;
   2.121 +	unsigned long *map, *r;
   2.122 +	int i, count, unique;
   2.123  
   2.124  	count = in->size / sizeof(struct import_property);
   2.125  	qsort(in->data, count,
   2.126 @@ -658,40 +663,107 @@
   2.127  	for (i = 0; i < count; i++)
   2.128  		map[ip[i].index] = ip[i].unique_index;
   2.129  
   2.130 +	unique = out->size / sizeof(*rp);
   2.131 +	pkgs = zalloc(unique * sizeof *pkgs);
   2.132 +	for (ip = in->data; ip < end; ip++) {
   2.133 +		r = array_add(&pkgs[ip->unique_index], sizeof *r);
   2.134 +		*r = ip->package;
   2.135 +	}
   2.136 +
   2.137 +	rp_end = out->data + out->size;
   2.138 +	for (rp = out->data, p = pkgs; rp < rp_end; rp++, p++)
   2.139 +		rp->packages = add_to_property_pool(set, p);
   2.140 +
   2.141 +	free(pkgs);
   2.142 +
   2.143  	return map;
   2.144  }
   2.145  
   2.146  static void
   2.147 -sort_packages(struct import_context *ctx)
   2.148 +remap_package_links(struct import_context *ctx)
   2.149  {
   2.150 -	struct razor_package *p, *end;
   2.151 +	struct import_package *p, *end;
   2.152  	unsigned long *pool, *r;
   2.153  
   2.154  	pool = ctx->set->property_pool.data;
   2.155 -	end = ctx->set->packages.data + ctx->set->packages.size;
   2.156 -	for (p = ctx->set->packages.data; p < end; p++) {
   2.157 -		for (r = &pool[p->requires]; *r; r++)
   2.158 +	end = ctx->packages.data + ctx->packages.size;
   2.159 +	for (p = ctx->packages.data; p < end; p++) {
   2.160 +		for (r = &pool[p->requires]; ~*r; r++)
   2.161  			*r = ctx->requires_map[*r];
   2.162 -		for (r = &pool[p->provides]; *r; r++)
   2.163 +		for (r = &pool[p->provides]; ~*r; r++)
   2.164  			*r = ctx->provides_map[*r];
   2.165  	}
   2.166 +}
   2.167  
   2.168 -	qsort(ctx->set->packages.data,
   2.169 -	      ctx->set->packages.size / sizeof(struct razor_package),
   2.170 -	      sizeof(struct razor_package), compare_packages);
   2.171 +static void
   2.172 +remap_property_links(struct import_context *ctx)
   2.173 +{
   2.174 +	struct razor_property *p, *end;
   2.175 +	struct import_package *ip;
   2.176 +	unsigned long *map, *pool, *r;
   2.177 +	int i, count;
   2.178 +
   2.179 +	pool = ctx->set->property_pool.data;
   2.180 +	count = ctx->packages.size / sizeof(struct import_package);
   2.181 +	map = malloc(count * sizeof *map);
   2.182 +	ip = ctx->packages.data;
   2.183 +	for (i = 0; i < count; i++)
   2.184 +		map[ip[i].index] = i;
   2.185 +
   2.186 +	/* FIXME: This will break if we implement package list sharing
   2.187 +	 * for all properties, since we'll remap those lists more than
   2.188 +	 * once. We should just have a separate pool for property
   2.189 +	 * lists and a separate pool for package lists and remap it as
   2.190 +	 * a flat pool.  Right now, as property lists and package
   2.191 +	 * lists are mixed, we can't do that. */
   2.192 +
   2.193 +	end = ctx->set->requires.data + ctx->set->requires.size;
   2.194 +	for (p = ctx->set->requires.data; p < end; p++)
   2.195 +		for (r = &pool[p->packages]; ~*r; r++)
   2.196 +			*r = map[*r];
   2.197 +
   2.198 +	end = ctx->set->provides.data + ctx->set->provides.size;
   2.199 +	for (p = ctx->set->provides.data; p < end; p++)
   2.200 +		for (r = &pool[p->packages]; ~*r; r++)
   2.201 +			*r = map[*r];
   2.202 +
   2.203 +	free(map);
   2.204  }
   2.205  
   2.206  static struct razor_set *
   2.207  razor_finish_import(struct import_context *ctx)
   2.208  {
   2.209 +	struct import_package *ip;
   2.210 +	struct razor_package *rp;
   2.211 +	int i, count;
   2.212 +
   2.213  	qsort_set = ctx->set;
   2.214  
   2.215  	ctx->requires_map =
   2.216 -		uniqueify_properties(&ctx->requires.all, &ctx->set->requires);
   2.217 +		uniqueify_properties(ctx->set, 
   2.218 +				     &ctx->requires.all,
   2.219 +				     &ctx->set->requires);
   2.220  	ctx->provides_map =
   2.221 -		uniqueify_properties(&ctx->provides.all, &ctx->set->provides);
   2.222 +		uniqueify_properties(ctx->set,
   2.223 +				     &ctx->provides.all,
   2.224 +				     &ctx->set->provides);
   2.225  
   2.226 -	sort_packages(ctx);
   2.227 +	remap_package_links(ctx);
   2.228 +
   2.229 +	count = ctx->packages.size / sizeof(struct import_package);
   2.230 +	qsort(ctx->packages.data, count,
   2.231 +	      sizeof(struct import_package), compare_packages);
   2.232 +
   2.233 +	ip = ctx->packages.data;
   2.234 +	for (i = 0; i < count; i++, ip++, rp++) {
   2.235 +		rp = array_add(&ctx->set->packages, sizeof *rp);
   2.236 +		rp->name = ip->name;
   2.237 +		rp->version = ip->version;
   2.238 +		rp->requires = ip->requires;
   2.239 +		rp->provides = ip->provides;
   2.240 +	}
   2.241 +
   2.242 +	remap_property_links(ctx);
   2.243  
   2.244  	free(ctx->requires.all.data);
   2.245  	free(ctx->provides.all.data);
   2.246 @@ -862,6 +934,36 @@
   2.247  		       sizeof(struct razor_package), compare_package_name);
   2.248  }
   2.249  
   2.250 +static int
   2.251 +compare_property_name(const void *key, const void *data)
   2.252 +{
   2.253 +	const struct razor_property *p = data;
   2.254 +	char *pool;
   2.255 +
   2.256 +	pool = bsearch_set->string_pool.data;
   2.257 +
   2.258 +	return strcmp(key, &pool[p->name]);
   2.259 +}
   2.260 +
   2.261 +struct razor_property *
   2.262 +razor_set_get_property(struct razor_set *set,
   2.263 +		       struct array *properties,
   2.264 +		       const char *property)
   2.265 +{
   2.266 +	struct razor_property *p, *start;
   2.267 +
   2.268 +	bsearch_set = set;
   2.269 +	p = bsearch(property, properties->data,
   2.270 +		    properties->size / sizeof(struct razor_property),
   2.271 +		    sizeof(struct razor_property), compare_property_name);
   2.272 +
   2.273 +	start = properties->data;
   2.274 +	while (p > start && (p - 1)->name == p->name)
   2.275 +		p--;
   2.276 +
   2.277 +	return p;
   2.278 +}
   2.279 +
   2.280  static void
   2.281  razor_set_list_all_properties(struct razor_set *set, struct array *properties)
   2.282  {
   2.283 @@ -888,7 +990,7 @@
   2.284  			package->requires;
   2.285  		requires = set->requires.data;
   2.286  		pool = set->string_pool.data;
   2.287 -		while (*r) {
   2.288 +		while (~*r) {
   2.289  			p = &requires[*r++];
   2.290  			printf("%s %s\n", &pool[p->name], &pool[p->version]);
   2.291  		}
   2.292 @@ -910,7 +1012,7 @@
   2.293  			package->provides;
   2.294  		provides = set->provides.data;
   2.295  		pool = set->string_pool.data;
   2.296 -		while (*r) {
   2.297 +		while (~*r) {
   2.298  			p = &provides[*r++];
   2.299  			printf("%s %s\n", &pool[p->name], &pool[p->version]);
   2.300  		}
   2.301 @@ -919,6 +1021,35 @@
   2.302  }
   2.303  
   2.304  void
   2.305 +razor_set_list_property_packages(struct razor_set *set,
   2.306 +				 struct array *properties,
   2.307 +				 const char *name)
   2.308 +{
   2.309 +	struct razor_property *property, *end;
   2.310 +	struct razor_package *p, *packages;
   2.311 +	unsigned long *r;
   2.312 +	char *pool;
   2.313 +
   2.314 +	if (name == NULL)
   2.315 +		return;
   2.316 +
   2.317 +	property = razor_set_get_property(set, properties, name);
   2.318 +	packages = set->packages.data;
   2.319 +	pool = set->string_pool.data;
   2.320 +	end = properties->data + properties->size;
   2.321 +	while (property < end && strcmp(name, &pool[property->name]) == 0) {
   2.322 +		r = (unsigned long *)
   2.323 +			set->property_pool.data + property->packages;
   2.324 +		while (~*r) {
   2.325 +			p = &packages[*r++];
   2.326 +			printf("%s %s\n",
   2.327 +			       &pool[p->name], &pool[p->version]);
   2.328 +		}
   2.329 +		property++;
   2.330 +	}
   2.331 +}
   2.332 +
   2.333 +void
   2.334  razor_set_info(struct razor_set *set)
   2.335  {
   2.336  	unsigned int offset, size;
   2.337 @@ -926,7 +1057,7 @@
   2.338  
   2.339  	for (i = 0; i < set->header->sections[i].type; i++) {
   2.340  		offset = set->header->sections[i].offset;
   2.341 -		size = set->header->sections[i + 1].offset - offset;
   2.342 +		size = set->header->sections[i].size;
   2.343  
   2.344  		switch (set->header->sections[i].type) {
   2.345  		case RAZOR_STRINGS:
   2.346 @@ -941,6 +1072,9 @@
   2.347  		case RAZOR_PROVIDES:
   2.348  			printf("provides section:\t%dkb\n", size / 1024);
   2.349  			break;
   2.350 +		case RAZOR_PROPERTIES:
   2.351 +			printf("properties section:\t%dkb\n", size / 1024);
   2.352 +			break;
   2.353  		}
   2.354  	}
   2.355  }
   2.356 @@ -1019,6 +1153,14 @@
   2.357  		set = razor_set_open(repo_filename);
   2.358  		razor_set_list_provides(set, argv[2]);
   2.359  		razor_set_destroy(set);
   2.360 +	} else if (strcmp(argv[1], "what-requires") == 0) {
   2.361 +		set = razor_set_open(repo_filename);
   2.362 +		razor_set_list_property_packages(set, &set->requires, argv[2]);
   2.363 +		razor_set_destroy(set);
   2.364 +	} else if (strcmp(argv[1], "what-provides") == 0) {
   2.365 +		set = razor_set_open(repo_filename);
   2.366 +		razor_set_list_property_packages(set, &set->provides, argv[2]);
   2.367 +		razor_set_destroy(set);
   2.368  	} else if (strcmp(argv[1], "info") == 0) {
   2.369  		set = razor_set_open(repo_filename);
   2.370  		razor_set_info(set);
   2.371 @@ -1029,6 +1171,7 @@
   2.372  			return 1;
   2.373  		razor_set_write(set, rawhide_repo_filename);
   2.374  		razor_set_destroy(set);
   2.375 +		printf("wrote %s\n", rawhide_repo_filename);
   2.376  	} else {
   2.377  		usage();
   2.378  	}