Mercurialrazor / file revision
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | revisions | annotate | diff | raw
razor.c
author Kristian H?gsberg <krh@redhat.com>
Mon Sep 03 23:31:32 2007 -0400 (2007-09-03)
changeset 4 c8e9dbcfaf02
parent 3 917677cdceb3
child 6 4eeed5fbe6b7
permissions -rw-r--r--
Cleanup and renaming: hashtable and razor_context combined into razor_set.

It's no longer just a hashtable, it's really a set of packages. 
     1 #include <stdlib.h>

     2 #include <stdio.h>

     3 #include <string.h>

     4 #include <sys/types.h>

     5 #include <sys/stat.h>

     6 #include <sys/mman.h>

     7 #include <unistd.h>

     8 #include <fcntl.h>

     9 

    10 #include <expat.h>

    11 #include "sha1.h"

    12 

    13 static int

    14 write_to_fd(int fd, void *p, size_t size)

    15 {

    16 	int rest, len;

    17 

    18 	rest = size;

    19 	while (rest > 0) {

    20 		len = write(fd, p, rest);

    21 		if (len < 0)

    22 			return -1;

    23 		rest -= len;

    24 	}

    25 

    26 	return 0;

    27 }

    28 

    29 static int

    30 write_to_file(const char *filename, void *p, size_t size)

    31 {

    32 	int fd, err;

    33 

    34 	fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, 0666);

    35 	if (fd < 0)

    36 		return -1;

    37 	err = write_to_fd(fd, p, size);

    38 	close(fd);

    39 

    40 	return err;

    41 }

    42 

    43 static void *

    44 zalloc(size_t size)

    45 {

    46 	void *p;

    47 

    48 	p = malloc(size);

    49 	memset(p, 0, size);

    50 

    51 	return p;

    52 }

    53 

    54 struct razor_set_header {

    55 	unsigned int magic;

    56 	unsigned int version;

    57 	struct { unsigned int type, offset; } sections[0];

    58 };

    59 

    60 #define RAZOR_MAGIC 0x7a7a7a7a

    61 #define RAZOR_VERSION 1

    62 #define RAZOR_BUCKETS 1

    63 #define RAZOR_STRINGS 2

    64 #define RAZOR_PACKAGES 3

    65 

    66 struct razor_package {

    67 	unsigned long name;

    68 	unsigned long version;

    69 };

    70 

    71 struct razor_set {

    72 	unsigned long *buckets;

    73 	int bucket_count, bucket_alloc;

    74 	char *string_pool;

    75 	int pool_size, pool_alloc;

    76 	struct razor_set_header *header;

    77 

    78 	struct razor_package *packages;

    79 	int package_count, package_alloc;

    80 };

    81 

    82 struct razor_set *

    83 razor_set_create(void)

    84 {

    85 	struct razor_set *set;

    86 

    87 	set = zalloc(sizeof *set);

    88 	set->buckets = zalloc(4096 * sizeof *set->buckets);

    89 	set->bucket_count = 0;

    90 	set->bucket_alloc = 4096;

    91 

    92 	set->string_pool = zalloc(4096);

    93 	set->pool_size = 1;

    94 	set->pool_alloc = 4096;

    95 

    96 	set->packages = zalloc(4096 * sizeof *set->packages);

    97 	set->package_count = 0;

    98 	set->package_alloc = 4096;

    99 

   100 	return set;

   101 }

   102 

   103 struct razor_set *

   104 razor_set_open(const char *filename)

   105 {

   106 	struct razor_set *set;

   107 	struct stat stat;

   108 	unsigned int size, offset;

   109 	int fd, i;

   110 

   111 	set = zalloc(sizeof *set);

   112 	fd = open(filename, O_RDONLY);

   113 	if (fstat(fd, &stat) < 0)

   114 		return NULL;

   115 	set->header = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);

   116 	if (set->header == MAP_FAILED) {

   117 		free(set);

   118 		return NULL;

   119 	}

   120 

   121 	for (i = 0; i < set->header->sections[i].type; i++) {

   122 		offset = set->header->sections[i].offset;

   123 		size = set->header->sections[i + 1].offset - offset;

   124 

   125 		switch (set->header->sections[i].type) {

   126 		case RAZOR_BUCKETS:

   127 			set->buckets = (void *) set->header + offset;

   128 			set->bucket_count = size / sizeof *set->buckets;

   129 			set->bucket_alloc = set->bucket_count;

   130 			break;

   131 		case RAZOR_STRINGS:

   132 			set->string_pool = (void *) set->header + offset;

   133 			set->pool_size = size;

   134 			set->pool_alloc = size;

   135 			break;

   136 		case RAZOR_PACKAGES:

   137 			set->packages = (void *) set->header + offset;

   138 			set->package_count = size / sizeof *set->packages;

   139 			set->package_alloc = size / sizeof *set->packages;

   140 			break;

   141 		}

   142 	}

   143 	close(fd);

   144 

   145 	return set;

   146 }

   147 

   148 void

   149 razor_set_destroy(struct razor_set *set)

   150 {

   151 	unsigned int size;

   152 	int i;

   153 

   154 	if (set->header) {

   155 		for (i = 0; set->header->sections[i].type; i++)

   156 			;

   157 		size = set->header->sections[i].type;

   158 		munmap(set->header, size);

   159 	} else {

   160 		free(set->buckets);

   161 		free(set->string_pool);

   162 	}

   163 

   164 	free(set);

   165 }

   166 

   167 static int

   168 razor_set_write(struct razor_set *set, const char *filename)

   169 {

   170 	char data[4096];

   171 	struct razor_set_header *header = (struct razor_set_header *) data;

   172 	int fd, pool_size, package_size;

   173 

   174 	/* Align these to pages sizes */

   175 	pool_size = (set->pool_size + 4095) & ~4095;

   176 	package_size =

   177 		(set->package_alloc * sizeof *set->packages + 4095) & ~4095;

   178 

   179 	memset(data, 0, sizeof data);

   180 	header->magic = RAZOR_MAGIC;

   181 	header->version = RAZOR_VERSION;

   182 

   183 	header->sections[0].type = RAZOR_BUCKETS;

   184 	header->sections[0].offset = sizeof data;

   185 

   186 	header->sections[1].type = RAZOR_STRINGS;

   187 	header->sections[1].offset = header->sections[0].offset +

   188 		set->bucket_alloc * sizeof *set->buckets;

   189 

   190 	header->sections[2].type = RAZOR_PACKAGES;

   191 	header->sections[2].offset = header->sections[1].offset + pool_size;

   192 

   193 	header->sections[3].type = 0;

   194 	header->sections[3].offset = header->sections[2].offset + package_size;

   195 

   196 	fd = open(filename, O_CREAT | O_WRONLY | O_TRUNC, 0666);

   197 	if (fd < 0)

   198 		return -1;

   199 

   200 	write_to_fd(fd, data, sizeof data);

   201 	write_to_fd(fd, set->buckets, set->bucket_alloc * sizeof *set->buckets);

   202 	write_to_fd(fd, set->string_pool, pool_size);

   203 	write_to_fd(fd, set->packages, package_size);

   204 

   205 	return 0;

   206 }

   207 

   208 static unsigned int

   209 hash_string(const char *key)

   210 {

   211 	const char *p;

   212 	unsigned int hash = 0;

   213 

   214 	for (p = key; *p; p++)

   215 		hash = (hash << 2) ^ *p;

   216 

   217 	return hash;

   218 }

   219 

   220 unsigned long

   221 razor_set_lookup(struct razor_set *set, const char *key)

   222 {

   223 	unsigned int start;

   224 	unsigned int mask;

   225 	unsigned long value;

   226 	int i;

   227 

   228 	mask = set->bucket_alloc - 1;

   229 	start = hash_string(key) & mask;

   230 	i = start;

   231 	do {

   232 		value = set->buckets[i];

   233 

   234 		if (value == 0)

   235 			return 0;

   236 

   237 		if (strcmp(key, &set->string_pool[value]) == 0)

   238 			return value;

   239 

   240 		i = (i + 1) & mask;

   241 	} while (i != start);

   242 

   243 	return 0;

   244 }

   245 

   246 static unsigned long

   247 add_to_string_pool(struct razor_set *set, const char *key)

   248 {

   249 	int len, alloc;

   250 	char *pool;

   251 	unsigned long value;

   252 

   253 	len = strlen(key) + 1;

   254 	alloc = set->pool_alloc;

   255 	while (alloc < set->pool_size + len)

   256 		alloc *= 2;

   257 	if (set->pool_alloc < alloc) {

   258 		pool = realloc(set->string_pool, alloc);

   259 		if (pool == NULL)

   260 			return 0;

   261 		set->string_pool = pool;

   262 		set->pool_alloc = alloc;

   263 	}

   264 

   265 	memcpy(set->string_pool + set->pool_size, key, len);

   266 	value = set->pool_size;

   267 	set->pool_size += len;

   268 

   269 	return value;

   270 }

   271 

   272 static void

   273 do_insert(struct razor_set *set, unsigned long value)

   274 {

   275 	unsigned int mask;

   276 	const char *key;

   277 	int i, start;

   278 

   279 	key = &set->string_pool[value];

   280 	mask = set->bucket_alloc - 1;

   281 	start = hash_string(key) & mask;

   282 	i = start;

   283 	do {

   284 		if (set->buckets[i] == 0) {

   285 			set->buckets[i] = value;

   286 			break;

   287 		}

   288 		i = (i + 1) & mask;

   289 	} while (i != start);

   290 }

   291 

   292 unsigned long

   293 razor_set_insert(struct razor_set *set, const char *key)

   294 {

   295 	unsigned long value, *buckets, *old_buckets;

   296 	int i, alloc, old_alloc;

   297 

   298 	alloc = set->bucket_alloc;

   299 	while (alloc < 4 * set->bucket_count)

   300 		alloc *= 2;

   301 

   302 	if (alloc != set->bucket_alloc) {

   303 		buckets = zalloc(alloc * sizeof *set->buckets);

   304 		if (buckets == NULL)

   305 			return 0;

   306 		old_buckets = set->buckets;

   307 		set->buckets = buckets;

   308 		old_alloc = set->bucket_alloc;

   309 		set->bucket_alloc = alloc;

   310 		

   311 		for (i = 0; i < old_alloc; i++) {

   312 			value = old_buckets[i];

   313 			if (value != 0)

   314 				do_insert(set, value);

   315 		}

   316 		free(old_buckets);

   317 	}

   318 

   319 	value = add_to_string_pool(set, key);

   320 	do_insert (set, value);

   321 	set->bucket_count++;

   322 

   323 	return value;

   324 }

   325 

   326 static unsigned long

   327 razor_set_add_package(struct razor_set *set,

   328 		      unsigned long name, unsigned long version)

   329 {

   330 	struct razor_package *packages;

   331 	int alloc;

   332 

   333 	/* FIXME: make 0 an illegal pkgs number. */

   334 	alloc = set->package_alloc;

   335 	while (alloc < set->package_count + 1)

   336 		alloc *= 2;

   337 	if (set->package_alloc < alloc) {

   338 		packages = realloc(set->packages, alloc * sizeof set->packages);

   339 		if (packages == NULL)

   340 			return 0;

   341 		set->packages = packages;

   342 		set->package_alloc = alloc;

   343 	}

   344 

   345 	set->packages[set->package_count].name = name;

   346 	set->packages[set->package_count].version = version;

   347 

   348 	return set->package_count++;

   349 }

   350 

   351 unsigned long

   352 razor_set_tokenize(struct razor_set *set, const char *string)

   353 {

   354 	unsigned long token;

   355 

   356 	token = razor_set_lookup(set, string);

   357 	if (token != 0)

   358 		return token;

   359 

   360 	return razor_set_insert(set, string);

   361 }

   362 

   363 static struct razor_set *qsort_set;

   364 

   365 static int

   366 compare_packages(const void *p1, const void *p2)

   367 {

   368 	const struct razor_package *pkg1 = p1, *pkg2 = p2;

   369 

   370 	return strcmp(&qsort_set->string_pool[pkg1->name],

   371 		      &qsort_set->string_pool[pkg2->name]);

   372 }

   373 

   374 static void

   375 razor_set_sort(struct razor_set *set)

   376 {

   377 	qsort_set = set;

   378 	qsort(set->packages, set->package_count, sizeof *set->packages,

   379 	      compare_packages);

   380 }

   381 

   382 struct parsing_context {

   383 	struct razor_set *set;

   384 	int pkg_id;

   385 };

   386 

   387 static void

   388 parse_package(struct parsing_context *ctx, const char **atts)

   389 {

   390 	unsigned long name, version;

   391 	int i;

   392 

   393 	for (i = 0; atts[i]; i += 2) {

   394 		if (strcmp(atts[i], "name") == 0)

   395 			name = razor_set_tokenize(ctx->set, atts[i + 1]);

   396 		else if (strcmp(atts[i], "version") == 0)

   397 			version = razor_set_tokenize(ctx->set, atts[i + 1]);

   398 	}

   399 

   400 	if (name == 0 || version == 0) {

   401 		fprintf(stderr, "invalid package tag, "

   402 			"missing name or version attributes\n");

   403 		return;

   404 	}

   405 

   406 	ctx->pkg_id = razor_set_add_package(ctx->set, name, version);

   407 

   408 	return;

   409 }

   410 

   411 static void

   412 start_element(void *data, const char *name, const char **atts)

   413 {

   414 	struct parsing_context *ctx = data;

   415 	int i;

   416 

   417 	if (strcmp(name, "package") == 0)

   418 		parse_package(ctx, atts);

   419 

   420 	for (i = 0; atts[i]; i += 2)

   421 		razor_set_tokenize(ctx->set, atts[i + 1]);

   422 }

   423 

   424 static void

   425 end_element (void *data, const char *name)

   426 {

   427 	struct parsing_context *ctx = data;

   428 

   429 	if (strcmp(name, "package") == 0)

   430 		ctx->pkg_id = 0;

   431 }

   432 

   433 static char *

   434 sha1_to_hex(const unsigned char *sha1)

   435 {

   436 	static int bufno;

   437 	static char hexbuffer[4][50];

   438 	static const char hex[] = "0123456789abcdef";

   439 	char *buffer = hexbuffer[3 & ++bufno], *buf = buffer;

   440 	int i;

   441 

   442 	for (i = 0; i < 20; i++) {

   443 		unsigned int val = *sha1++;

   444 		*buf++ = hex[val >> 4];

   445 		*buf++ = hex[val & 0xf];

   446 	}

   447 	*buf = '\0';

   448 

   449 	return buffer;

   450 }

   451 

   452 static int

   453 razor_set_import(struct razor_set *set, const char *filename)

   454 {

   455 	SHA_CTX sha1;

   456 	XML_Parser parser;

   457 	struct parsing_context ctx;

   458 	int fd;

   459 	void *p;

   460 	struct stat stat;

   461 	char buf[128];

   462 	unsigned char hash[20];

   463 

   464 	fd = open(filename, O_RDONLY);

   465 	if (fstat(fd, &stat) < 0)

   466 		return -1;

   467 	p = mmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);

   468 	if (p == MAP_FAILED)

   469 		return -1;

   470 

   471 	parser = XML_ParserCreate(NULL);

   472 	ctx.set = set;

   473 	XML_SetUserData(parser, &ctx);

   474 	XML_SetElementHandler(parser, start_element, end_element);

   475 	if (XML_Parse(parser, p, stat.st_size, 1) == XML_STATUS_ERROR) {

   476 		fprintf(stderr,

   477 			"%s at line %d, %s\n",

   478 			XML_ErrorString(XML_GetErrorCode(parser)),

   479 			XML_GetCurrentLineNumber(parser),

   480 			filename);

   481 		return 1;

   482 	}

   483 

   484 	XML_ParserFree(parser);

   485 

   486 	SHA1_Init(&sha1);

   487 	SHA1_Update(&sha1, p, stat.st_size);

   488 	SHA1_Final(hash, &sha1);

   489 

   490 	close(fd);

   491 

   492 	snprintf(buf, sizeof buf, "set/%s", sha1_to_hex(hash));

   493 	if (write_to_file(buf, p, stat.st_size) < 0)

   494 		return -1;

   495 	munmap(p, stat.st_size);

   496 

   497 	return 0;

   498 }

   499 

   500 void

   501 razor_set_list(struct razor_set *set)

   502 {

   503 	int i;

   504 	struct razor_package *p;

   505 

   506 	p = set->packages;

   507 	for (i = 0; i < set->package_count && p->name; i++, p++) {

   508 		printf("%s %s\n",

   509 		       &set->string_pool[p->name],

   510 		       &set->string_pool[p->version]);

   511 	}

   512 }

   513 

   514 void

   515 razor_set_info(struct razor_set *set)

   516 {

   517 	unsigned int offset, size;

   518 	int i;

   519 

   520 	for (i = 0; i < set->header->sections[i].type; i++) {

   521 		offset = set->header->sections[i].offset;

   522 		size = set->header->sections[i + 1].offset - offset;

   523 

   524 		switch (set->header->sections[i].type) {

   525 		case RAZOR_BUCKETS:

   526 			printf("bucket section:\t\t%dkb\n", size / 1024);

   527 			break;

   528 		case RAZOR_STRINGS:

   529 			printf("string pool:\t\t%dkb\n", size / 1024);

   530 			break;

   531 		case RAZOR_PACKAGES:

   532 			printf("package section:\t%dkb\n", size / 1024);

   533 			break;

   534 		}

   535 	}

   536 }

   537 

   538 static int

   539 usage(void)

   540 {

   541 	printf("usage: razor [ import FILES | lookup <key> | list | info ]\n");

   542 	exit(1);

   543 }

   544 

   545 static const char repo_filename[] = "system.repo";

   546 

   547 int

   548 main(int argc, char *argv[])

   549 {

   550 	int i;

   551 	struct razor_set *set;

   552 	struct stat statbuf;

   553 

   554 	if (argc < 2) {

   555 		usage();

   556 	} else if (strcmp(argv[1], "import") == 0) {

   557 		if (stat("set", &statbuf) && mkdir("set", 0777)) {

   558 			fprintf(stderr, "could not create directory 'set'\n");

   559 			exit(-1);

   560 		}

   561 			

   562 		set = razor_set_create();

   563 

   564 		for (i = 2; i < argc; i++) {

   565 			if (razor_set_import(set, argv[i]) < 0) {

   566 				fprintf(stderr, "failed to import %s\n",

   567 					argv[i]);

   568 				exit(-1);

   569 			}

   570 		}

   571 

   572 		razor_set_sort(set);

   573 

   574 		printf("number of buckets: %d\n",

   575 		       set->bucket_count);

   576 		printf("bucket allocation: %d\n",

   577 		       set->bucket_alloc);

   578 		printf("pool size: %d\n", set->pool_size);

   579 		printf("pool allocation: %d\n", set->pool_alloc);

   580 

   581 		razor_set_write(set, repo_filename);

   582 

   583 		razor_set_destroy(set);

   584 	} else if (strcmp(argv[1], "lookup") == 0) {

   585 		set = razor_set_open(repo_filename);

   586 		printf("%s is %lu\n", argv[2],

   587 		       razor_set_lookup(set, argv[2]));

   588 		razor_set_destroy(set);

   589 	} else if (strcmp(argv[1], "list") == 0) {

   590 		set = razor_set_open(repo_filename);

   591 		razor_set_list(set);

   592 		razor_set_destroy(set);

   593 	} else if (strcmp(argv[1], "info") == 0) {

   594 		set = razor_set_open(repo_filename);

   595 		razor_set_info(set);

   596 		razor_set_destroy(set);

   597 	} else {

   598 		usage();

   599 	}

   600 

   601 	return 0;

   602 }
razor