From 5d3e9c659fa12bf78a6432504ffbc07f8f01d7b8 Mon Sep 17 00:00:00 2001 From: Dan Winship Date: Thu, 7 Feb 2008 09:58:48 -0500 Subject: [PATCH] split array and hashtable code out into a new file --- Makefile | 5 +- razor.c | 174 +------------------------------------------------------------- types.c | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ types.h | 27 ++++++++++ 4 files changed, 199 insertions(+), 175 deletions(-) create mode 100644 types.c create mode 100644 types.h diff --git a/Makefile b/Makefile index b7e4e38..39555f0 100644 --- a/Makefile +++ b/Makefile @@ -3,11 +3,12 @@ LDLIBS = -lexpat -lz -g -lrpm -lcurl all : razor test-driver -razor : razor.o yum.o main.o rpm.o util.o +razor : razor.o yum.o main.o rpm.o types.o util.o *.o : razor.h razor-internal.h +razor.o : types.h -test-driver : razor.o util.o test-driver.o +test-driver : razor.o types.o util.o test-driver.o test : test-driver ./test-driver test.xml diff --git a/razor.c b/razor.c index 0825d1b..d86a5b7 100644 --- a/razor.c +++ b/razor.c @@ -16,11 +16,7 @@ #include "razor.h" #include "razor-internal.h" - -struct array { - void *data; - int size, alloc; -}; +#include "types.h" struct razor_set_section { uint32_t type; @@ -92,11 +88,6 @@ struct import_directory { struct import_directory *last; }; -struct hashtable { - struct array buckets; - struct array *pool; -}; - struct razor_importer { struct razor_set *set; struct hashtable table; @@ -105,46 +96,6 @@ struct razor_importer { struct array files; }; -static void -array_init(struct array *array) -{ - memset(array, 0, sizeof *array); -} - -static void -array_release(struct array *array) -{ - free(array->data); -} - -static void * -array_add(struct array *array, int size) -{ - int alloc; - void *data, *p; - - if (array->alloc > 0) - alloc = array->alloc; - else - alloc = 16; - - while (alloc < array->size + size) - alloc *= 2; - - if (array->alloc < alloc) { - data = realloc(array->data, alloc); - if (data == NULL) - return 0; - array->data = data; - array->alloc = alloc; - } - - p = array->data + array->size; - array->size += size; - - return p; -} - static void * zalloc(size_t size) { @@ -275,55 +226,6 @@ razor_set_write(struct razor_set *set, const char *filename) return 0; } -static unsigned int -hash_string(const char *key) -{ - const char *p; - unsigned int hash = 0; - - for (p = key; *p; p++) - hash = (hash * 617) ^ *p; - - return hash; -} - -static uint32_t -hashtable_lookup(struct hashtable *table, const char *key) -{ - unsigned int mask, start, i; - uint32_t *b; - char *pool; - - pool = table->pool->data; - mask = table->buckets.alloc - 1; - start = hash_string(key) * sizeof(uint32_t); - - for (i = 0; i < table->buckets.alloc; i += sizeof *b) { - b = table->buckets.data + ((start + i) & mask); - - if (*b == 0) - return 0; - - if (strcmp(key, &pool[*b]) == 0) - return *b; - } - - return 0; -} - -static uint32_t -add_to_string_pool(struct hashtable *table, const char *key) -{ - int len; - char *p; - - len = strlen(key) + 1; - p = array_add(table->pool, len); - memcpy(p, key, len); - - return p - (char *) table->pool->data; -} - static uint32_t add_to_property_pool(struct array *pool, struct array *properties) { @@ -341,80 +243,6 @@ add_to_property_pool(struct array *pool, struct array *properties) return p - (uint32_t *) pool->data; } -static void -do_insert(struct hashtable *table, uint32_t value) -{ - unsigned int mask, start, i; - uint32_t *b; - const char *key; - - key = (char *) table->pool->data + value; - mask = table->buckets.alloc - 1; - start = hash_string(key) * sizeof(uint32_t); - - for (i = 0; i < table->buckets.alloc; i += sizeof *b) { - b = table->buckets.data + ((start + i) & mask); - if (*b == 0) { - *b = value; - break; - } - } -} - -static uint32_t -hashtable_insert(struct hashtable *table, const char *key) -{ - uint32_t value, *buckets, *b, *end; - int alloc; - - alloc = table->buckets.alloc; - array_add(&table->buckets, 4 * sizeof *buckets); - if (alloc != table->buckets.alloc) { - end = table->buckets.data + alloc; - memset(end, 0, table->buckets.alloc - alloc); - for (b = table->buckets.data; b < end; b++) { - value = *b; - if (value != 0) { - *b = 0; - do_insert(table, value); - } - } - } - - value = add_to_string_pool(table, key); - do_insert (table, value); - - return value; -} - -static void -hashtable_init(struct hashtable *table, struct array *pool) -{ - array_init(&table->buckets); - table->pool = pool; -} - -static void -hashtable_release(struct hashtable *table) -{ - array_release(&table->buckets); -} - -static uint32_t -hashtable_tokenize(struct hashtable *table, const char *string) -{ - uint32_t token; - - if (string == NULL) - string = ""; - - token = hashtable_lookup(table, string); - if (token != 0) - return token; - - return hashtable_insert(table, string); -} - void razor_importer_begin_package(struct razor_importer *importer, const char *name, const char *version) diff --git a/types.c b/types.c new file mode 100644 index 0000000..53ef654 --- /dev/null +++ b/types.c @@ -0,0 +1,168 @@ +#include +#include + +#include "types.h" + +void +array_init(struct array *array) +{ + memset(array, 0, sizeof *array); +} + +void +array_release(struct array *array) +{ + free(array->data); +} + +void * +array_add(struct array *array, int size) +{ + int alloc; + void *data, *p; + + if (array->alloc > 0) + alloc = array->alloc; + else + alloc = 16; + + while (alloc < array->size + size) + alloc *= 2; + + if (array->alloc < alloc) { + data = realloc(array->data, alloc); + if (data == NULL) + return 0; + array->data = data; + array->alloc = alloc; + } + + p = array->data + array->size; + array->size += size; + + return p; +} + + +void +hashtable_init(struct hashtable *table, struct array *pool) +{ + array_init(&table->buckets); + table->pool = pool; +} + +void +hashtable_release(struct hashtable *table) +{ + array_release(&table->buckets); +} + +static unsigned int +hash_string(const char *key) +{ + const char *p; + unsigned int hash = 0; + + for (p = key; *p; p++) + hash = (hash * 617) ^ *p; + + return hash; +} + +uint32_t +hashtable_lookup(struct hashtable *table, const char *key) +{ + unsigned int mask, start, i; + uint32_t *b; + char *pool; + + pool = table->pool->data; + mask = table->buckets.alloc - 1; + start = hash_string(key) * sizeof(uint32_t); + + for (i = 0; i < table->buckets.alloc; i += sizeof *b) { + b = table->buckets.data + ((start + i) & mask); + + if (*b == 0) + return 0; + + if (strcmp(key, &pool[*b]) == 0) + return *b; + } + + return 0; +} + +static void +do_insert(struct hashtable *table, uint32_t value) +{ + unsigned int mask, start, i; + uint32_t *b; + const char *key; + + key = (char *) table->pool->data + value; + mask = table->buckets.alloc - 1; + start = hash_string(key) * sizeof(uint32_t); + + for (i = 0; i < table->buckets.alloc; i += sizeof *b) { + b = table->buckets.data + ((start + i) & mask); + if (*b == 0) { + *b = value; + break; + } + } +} + +static uint32_t +add_to_string_pool(struct hashtable *table, const char *key) +{ + int len; + char *p; + + len = strlen(key) + 1; + p = array_add(table->pool, len); + memcpy(p, key, len); + + return p - (char *) table->pool->data; +} + +uint32_t +hashtable_insert(struct hashtable *table, const char *key) +{ + uint32_t value, *buckets, *b, *end; + int alloc; + + alloc = table->buckets.alloc; + array_add(&table->buckets, 4 * sizeof *buckets); + if (alloc != table->buckets.alloc) { + end = table->buckets.data + alloc; + memset(end, 0, table->buckets.alloc - alloc); + for (b = table->buckets.data; b < end; b++) { + value = *b; + if (value != 0) { + *b = 0; + do_insert(table, value); + } + } + } + + value = add_to_string_pool(table, key); + do_insert (table, value); + + return value; +} + +uint32_t +hashtable_tokenize(struct hashtable *table, const char *string) +{ + uint32_t token; + + if (string == NULL) + string = ""; + + token = hashtable_lookup(table, string); + if (token != 0) + return token; + + return hashtable_insert(table, string); +} diff --git a/types.h b/types.h new file mode 100644 index 0000000..6c21323 --- /dev/null +++ b/types.h @@ -0,0 +1,27 @@ +#ifndef _RAZOR_TYPES_H_ +#define _RAZOR_TYPES_H_ + +#include + +struct array { + void *data; + int size, alloc; +}; + +void array_init(struct array *array); +void array_release(struct array *array); +void *array_add(struct array *array, int size); + + +struct hashtable { + struct array buckets; + struct array *pool; +}; + +void hashtable_init(struct hashtable *table, struct array *pool); +void hashtable_release(struct hashtable *table); +uint32_t hashtable_insert(struct hashtable *table, const char *key); +uint32_t hashtable_lookup(struct hashtable *table, const char *key); +uint32_t hashtable_tokenize(struct hashtable *table, const char *string); + +#endif /* _RAZOR_TYPES_H_ */ -- 1.7.1