1.1 --- a/razor.c Mon Sep 03 23:31:32 2007 -0400
1.2 +++ b/razor.c Tue Sep 04 23:52:59 2007 -0400
1.3 @@ -10,6 +10,39 @@
1.4 #include <expat.h>
1.5 #include "sha1.h"
1.6
1.7 +struct array {
1.8 + void *data;
1.9 + int size, alloc;
1.10 +};
1.11 +
1.12 +static void *
1.13 +array_add(struct array *array, int size)
1.14 +{
1.15 + int alloc;
1.16 + void *data, *p;
1.17 +
1.18 + if (array->alloc > 0)
1.19 + alloc = array->alloc;
1.20 + else
1.21 + alloc = 1024;
1.22 +
1.23 + while (alloc < array->size + size)
1.24 + alloc *= 2;
1.25 +
1.26 + if (array->alloc < alloc) {
1.27 + data = realloc(array->data, alloc);
1.28 + if (data == NULL)
1.29 + return 0;
1.30 + array->data = data;
1.31 + array->alloc = alloc;
1.32 + }
1.33 +
1.34 + p = array->data + array->size;
1.35 + array->size += size;
1.36 +
1.37 + return p;
1.38 +}
1.39 +
1.40 static int
1.41 write_to_fd(int fd, void *p, size_t size)
1.42 {
1.43 @@ -69,33 +102,21 @@
1.44 };
1.45
1.46 struct razor_set {
1.47 - unsigned long *buckets;
1.48 - int bucket_count, bucket_alloc;
1.49 - char *string_pool;
1.50 - int pool_size, pool_alloc;
1.51 + struct array buckets;
1.52 + struct array string_pool;
1.53 + struct array packages;
1.54 struct razor_set_header *header;
1.55 -
1.56 - struct razor_package *packages;
1.57 - int package_count, package_alloc;
1.58 };
1.59
1.60 struct razor_set *
1.61 razor_set_create(void)
1.62 {
1.63 struct razor_set *set;
1.64 + char *p;
1.65
1.66 - set = zalloc(sizeof *set);
1.67 - set->buckets = zalloc(4096 * sizeof *set->buckets);
1.68 - set->bucket_count = 0;
1.69 - set->bucket_alloc = 4096;
1.70 -
1.71 - set->string_pool = zalloc(4096);
1.72 - set->pool_size = 1;
1.73 - set->pool_alloc = 4096;
1.74 -
1.75 - set->packages = zalloc(4096 * sizeof *set->packages);
1.76 - set->package_count = 0;
1.77 - set->package_alloc = 4096;
1.78 + set = zalloc(sizeof(struct razor_set));
1.79 + p = array_add(&set->string_pool, 1);
1.80 + *p = '\0';
1.81
1.82 return set;
1.83 }
1.84 @@ -124,19 +145,19 @@
1.85
1.86 switch (set->header->sections[i].type) {
1.87 case RAZOR_BUCKETS:
1.88 - set->buckets = (void *) set->header + offset;
1.89 - set->bucket_count = size / sizeof *set->buckets;
1.90 - set->bucket_alloc = set->bucket_count;
1.91 + set->buckets.data = (void *) set->header + offset;
1.92 + set->buckets.size = size;
1.93 + set->buckets.alloc = size;
1.94 break;
1.95 case RAZOR_STRINGS:
1.96 - set->string_pool = (void *) set->header + offset;
1.97 - set->pool_size = size;
1.98 - set->pool_alloc = size;
1.99 + set->string_pool.data = (void *) set->header + offset;
1.100 + set->string_pool.size = size;
1.101 + set->string_pool.alloc = size;
1.102 break;
1.103 case RAZOR_PACKAGES:
1.104 - set->packages = (void *) set->header + offset;
1.105 - set->package_count = size / sizeof *set->packages;
1.106 - set->package_alloc = size / sizeof *set->packages;
1.107 + set->packages.data = (void *) set->header + offset;
1.108 + set->packages.size = size;
1.109 + set->packages.size = size;
1.110 break;
1.111 }
1.112 }
1.113 @@ -157,8 +178,9 @@
1.114 size = set->header->sections[i].type;
1.115 munmap(set->header, size);
1.116 } else {
1.117 - free(set->buckets);
1.118 - free(set->string_pool);
1.119 + free(set->buckets.data);
1.120 + free(set->string_pool.data);
1.121 + free(set->packages.data);
1.122 }
1.123
1.124 free(set);
1.125 @@ -169,12 +191,11 @@
1.126 {
1.127 char data[4096];
1.128 struct razor_set_header *header = (struct razor_set_header *) data;
1.129 - int fd, pool_size, package_size;
1.130 + int fd, pool_size, packages_size;
1.131
1.132 /* Align these to pages sizes */
1.133 - pool_size = (set->pool_size + 4095) & ~4095;
1.134 - package_size =
1.135 - (set->package_alloc * sizeof *set->packages + 4095) & ~4095;
1.136 + pool_size = (set->string_pool.size + 4095) & ~4095;
1.137 + packages_size = (set->packages.size + 4095) & ~4095;
1.138
1.139 memset(data, 0, sizeof data);
1.140 header->magic = RAZOR_MAGIC;
1.141 @@ -184,23 +205,25 @@
1.142 header->sections[0].offset = sizeof data;
1.143
1.144 header->sections[1].type = RAZOR_STRINGS;
1.145 - header->sections[1].offset = header->sections[0].offset +
1.146 - set->bucket_alloc * sizeof *set->buckets;
1.147 + header->sections[1].offset =
1.148 + header->sections[0].offset + set->buckets.alloc;
1.149
1.150 header->sections[2].type = RAZOR_PACKAGES;
1.151 - header->sections[2].offset = header->sections[1].offset + pool_size;
1.152 + header->sections[2].offset =
1.153 + header->sections[1].offset + pool_size;
1.154
1.155 header->sections[3].type = 0;
1.156 - header->sections[3].offset = header->sections[2].offset + package_size;
1.157 + header->sections[3].offset =
1.158 + header->sections[2].offset + packages_size;
1.159
1.160 fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, 0666);
1.161 if (fd < 0)
1.162 return -1;
1.163
1.164 write_to_fd(fd, data, sizeof data);
1.165 - write_to_fd(fd, set->buckets, set->bucket_alloc * sizeof *set->buckets);
1.166 - write_to_fd(fd, set->string_pool, pool_size);
1.167 - write_to_fd(fd, set->packages, package_size);
1.168 + write_to_fd(fd, set->buckets.data, set->buckets.alloc);
1.169 + write_to_fd(fd, set->string_pool.data, pool_size);
1.170 + write_to_fd(fd, set->packages.data, packages_size);
1.171
1.172 return 0;
1.173 }
1.174 @@ -220,25 +243,23 @@
1.175 unsigned long
1.176 razor_set_lookup(struct razor_set *set, const char *key)
1.177 {
1.178 - unsigned int start;
1.179 - unsigned int mask;
1.180 - unsigned long value;
1.181 - int i;
1.182 + unsigned int mask, start, i;
1.183 + unsigned long *b;
1.184 + char *pool;
1.185
1.186 - mask = set->bucket_alloc - 1;
1.187 - start = hash_string(key) & mask;
1.188 - i = start;
1.189 - do {
1.190 - value = set->buckets[i];
1.191 + pool = set->string_pool.data;
1.192 + mask = set->buckets.alloc - 1;
1.193 + start = hash_string(key) * sizeof(unsigned long);
1.194
1.195 - if (value == 0)
1.196 + for (i = 0; i < set->buckets.alloc; i += sizeof *b) {
1.197 + b = set->buckets.data + ((start + i) & mask);
1.198 +
1.199 + if (*b == 0)
1.200 return 0;
1.201
1.202 - if (strcmp(key, &set->string_pool[value]) == 0)
1.203 - return value;
1.204 -
1.205 - i = (i + 1) & mask;
1.206 - } while (i != start);
1.207 + if (strcmp(key, &pool[*b]) == 0)
1.208 + return *b;
1.209 + }
1.210
1.211 return 0;
1.212 }
1.213 @@ -246,79 +267,58 @@
1.214 static unsigned long
1.215 add_to_string_pool(struct razor_set *set, const char *key)
1.216 {
1.217 - int len, alloc;
1.218 - char *pool;
1.219 - unsigned long value;
1.220 + int len;
1.221 + char *p;
1.222
1.223 len = strlen(key) + 1;
1.224 - alloc = set->pool_alloc;
1.225 - while (alloc < set->pool_size + len)
1.226 - alloc *= 2;
1.227 - if (set->pool_alloc < alloc) {
1.228 - pool = realloc(set->string_pool, alloc);
1.229 - if (pool == NULL)
1.230 - return 0;
1.231 - set->string_pool = pool;
1.232 - set->pool_alloc = alloc;
1.233 - }
1.234 + p = array_add(&set->string_pool, len);
1.235 + memcpy(p, key, len);
1.236
1.237 - memcpy(set->string_pool + set->pool_size, key, len);
1.238 - value = set->pool_size;
1.239 - set->pool_size += len;
1.240 -
1.241 - return value;
1.242 + return p - (char *) set->string_pool.data;
1.243 }
1.244
1.245 static void
1.246 do_insert(struct razor_set *set, unsigned long value)
1.247 {
1.248 - unsigned int mask;
1.249 + unsigned int mask, start, i;
1.250 + unsigned long *b;
1.251 const char *key;
1.252 - int i, start;
1.253
1.254 - key = &set->string_pool[value];
1.255 - mask = set->bucket_alloc - 1;
1.256 - start = hash_string(key) & mask;
1.257 - i = start;
1.258 - do {
1.259 - if (set->buckets[i] == 0) {
1.260 - set->buckets[i] = value;
1.261 + key = (char *) set->string_pool.data + value;
1.262 + mask = set->buckets.alloc - 1;
1.263 + start = hash_string(key) * sizeof(unsigned long);
1.264 +
1.265 + for (i = 0; i < set->buckets.alloc; i += sizeof *b) {
1.266 + b = set->buckets.data + ((start + i) & mask);
1.267 + if (*b == 0) {
1.268 + *b = value;
1.269 break;
1.270 }
1.271 - i = (i + 1) & mask;
1.272 - } while (i != start);
1.273 + }
1.274 }
1.275
1.276 unsigned long
1.277 razor_set_insert(struct razor_set *set, const char *key)
1.278 {
1.279 - unsigned long value, *buckets, *old_buckets;
1.280 - int i, alloc, old_alloc;
1.281 + unsigned long value, *buckets, *b, *end;
1.282 + int alloc;
1.283
1.284 - alloc = set->bucket_alloc;
1.285 - while (alloc < 4 * set->bucket_count)
1.286 - alloc *= 2;
1.287 -
1.288 - if (alloc != set->bucket_alloc) {
1.289 - buckets = zalloc(alloc * sizeof *set->buckets);
1.290 - if (buckets == NULL)
1.291 - return 0;
1.292 - old_buckets = set->buckets;
1.293 - set->buckets = buckets;
1.294 - old_alloc = set->bucket_alloc;
1.295 - set->bucket_alloc = alloc;
1.296 -
1.297 - for (i = 0; i < old_alloc; i++) {
1.298 - value = old_buckets[i];
1.299 - if (value != 0)
1.300 + alloc = set->buckets.alloc;
1.301 + array_add(&set->buckets, 4 * sizeof *buckets);
1.302 + if (alloc != set->buckets.alloc) {
1.303 + end = set->buckets.data + alloc;
1.304 + memset(end, 0, set->buckets.alloc - alloc);
1.305 + for (b = set->buckets.data; b < end; b++) {
1.306 + value = *b;
1.307 + if (value != 0) {
1.308 + *b = 0;
1.309 do_insert(set, value);
1.310 + }
1.311 }
1.312 - free(old_buckets);
1.313 }
1.314
1.315 value = add_to_string_pool(set, key);
1.316 do_insert (set, value);
1.317 - set->bucket_count++;
1.318
1.319 return value;
1.320 }
1.321 @@ -327,25 +327,14 @@
1.322 razor_set_add_package(struct razor_set *set,
1.323 unsigned long name, unsigned long version)
1.324 {
1.325 - struct razor_package *packages;
1.326 - int alloc;
1.327 + struct razor_package *p;
1.328
1.329 - /* FIXME: make 0 an illegal pkgs number. */
1.330 - alloc = set->package_alloc;
1.331 - while (alloc < set->package_count + 1)
1.332 - alloc *= 2;
1.333 - if (set->package_alloc < alloc) {
1.334 - packages = realloc(set->packages, alloc * sizeof set->packages);
1.335 - if (packages == NULL)
1.336 - return 0;
1.337 - set->packages = packages;
1.338 - set->package_alloc = alloc;
1.339 - }
1.340 + p = array_add(&set->packages, sizeof *p);
1.341
1.342 - set->packages[set->package_count].name = name;
1.343 - set->packages[set->package_count].version = version;
1.344 + p->name = name;
1.345 + p->version = version;
1.346
1.347 - return set->package_count++;
1.348 + return p - (struct razor_package *) set->packages.data;
1.349 }
1.350
1.351 unsigned long
1.352 @@ -366,17 +355,18 @@
1.353 compare_packages(const void *p1, const void *p2)
1.354 {
1.355 const struct razor_package *pkg1 = p1, *pkg2 = p2;
1.356 + char *pool = qsort_set->string_pool.data;
1.357
1.358 - return strcmp(&qsort_set->string_pool[pkg1->name],
1.359 - &qsort_set->string_pool[pkg2->name]);
1.360 + return strcmp(&pool[pkg1->name], &pool[pkg2->name]);
1.361 }
1.362
1.363 static void
1.364 razor_set_sort(struct razor_set *set)
1.365 {
1.366 qsort_set = set;
1.367 - qsort(set->packages, set->package_count, sizeof *set->packages,
1.368 - compare_packages);
1.369 + qsort(set->packages.data,
1.370 + set->packages.size / sizeof(struct razor_package),
1.371 + sizeof(struct razor_package), compare_packages);
1.372 }
1.373
1.374 struct parsing_context {
1.375 @@ -500,15 +490,13 @@
1.376 void
1.377 razor_set_list(struct razor_set *set)
1.378 {
1.379 - int i;
1.380 - struct razor_package *p;
1.381 + struct razor_package *p, *end;
1.382 + char *pool;
1.383
1.384 - p = set->packages;
1.385 - for (i = 0; i < set->package_count && p->name; i++, p++) {
1.386 - printf("%s %s\n",
1.387 - &set->string_pool[p->name],
1.388 - &set->string_pool[p->version]);
1.389 - }
1.390 + pool = set->string_pool.data;
1.391 + end = set->packages.data + set->packages.size;
1.392 + for (p = set->packages.data; p < end && p->name; p++)
1.393 + printf("%s %s\n", &pool[p->name], &pool[p->version]);
1.394 }
1.395
1.396 void
1.397 @@ -571,12 +559,14 @@
1.398
1.399 razor_set_sort(set);
1.400
1.401 - printf("number of buckets: %d\n",
1.402 - set->bucket_count);
1.403 - printf("bucket allocation: %d\n",
1.404 - set->bucket_alloc);
1.405 - printf("pool size: %d\n", set->pool_size);
1.406 - printf("pool allocation: %d\n", set->pool_alloc);
1.407 + /* FIXME: We add a sentinel package here, but we
1.408 + * should probably just have a size field in the
1.409 + * header section. */
1.410 + razor_set_add_package(set, 0, 0);
1.411 +
1.412 + printf("bucket allocation: %d\n", set->buckets.alloc);
1.413 + printf("pool size: %d\n", set->string_pool.size);
1.414 + printf("pool allocation: %d\n", set->string_pool.alloc);
1.415
1.416 razor_set_write(set, repo_filename);
1.417