This is an automated email from the git hooks/post-receive script. satta pushed a commit to branch upstream in repository libhat-trie.
commit 3c6fb6e692924f64bafa359f857fb54a307bb8c9 Author: Sascha Steinbiss <sascha.steinb...@dcso.de> Date: Tue Apr 25 10:27:10 2017 +0200 New upstream version 0.1.1 --- configure.ac | 4 +- src/ahtable.c | 83 ++++++++++++++++++++++++++++++++++++ src/ahtable.h | 4 ++ src/hat-trie.h | 1 - src/portable_endian.h | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++ test/check_ahtable.c | 51 ++++++++++++++++++++++ 6 files changed, 256 insertions(+), 3 deletions(-) diff --git a/configure.ac b/configure.ac index 870b786..8acc767 100644 --- a/configure.ac +++ b/configure.ac @@ -1,10 +1,10 @@ -AC_INIT([hat-trie], [0.1.0], [dcjo...@cs.washington.edu]) +AC_INIT([hat-trie], [0.1.1], [dcjo...@cs.washington.edu]) AM_INIT_AUTOMAKE([foreign]) m4_ifdef([AM_SILENT_RULES],[AM_SILENT_RULES([yes])]) AC_CONFIG_MACRO_DIR([m4]) -base_CFLAGS="-std=c99 -Wall -Wextra -pedantic" +base_CFLAGS="-std=gnu99 -Wall -Wextra -pedantic" opt_CFLAGS="${base_CFLAGS} -O3" dbg_CFLAGS="${base_CFLAGS} -g -O0" diff --git a/src/ahtable.c b/src/ahtable.c index c0f6fb3..8f9c23d 100644 --- a/src/ahtable.c +++ b/src/ahtable.c @@ -10,6 +10,7 @@ #include "ahtable.h" #include "misc.h" #include "murmurhash3.h" +#include "portable_endian.h" #include <assert.h> #include <string.h> @@ -50,6 +51,83 @@ ahtable_t* ahtable_create_n(size_t n) return table; } +void ahtable_save(const ahtable_t* table, FILE* fd) +{ + if (table == NULL) return; + + /* Store table metadata as 64-bit network-ordered (big-endian) values so + * that architectures with larger capacity can take advantage of size. + */ + uint64_t n = htobe64(table->n); + fwrite(&n, sizeof(uint64_t), 1, fd); + + uint64_t m = htobe64(table->m); + fwrite(&m, sizeof(uint64_t), 1, fd); + + uint64_t max_m = htobe64(table->max_m); + fwrite(&max_m, sizeof(uint64_t), 1, fd); + + fwrite(&table->flag, sizeof(uint8_t), 1, fd); + + fwrite(&table->c0, sizeof(unsigned char), 1, fd); + fwrite(&table->c1, sizeof(unsigned char), 1, fd); + + size_t i; + uint32_t slot_size; + for (i = 0; i < table->n; ++i) { + slot_size = htobe32(table->slot_sizes[i]); + fwrite(&slot_size, sizeof(uint32_t), 1, fd); + if(table->slot_sizes[i] > 0) { + fwrite(table->slots[i], sizeof(unsigned char), table->slot_sizes[i], fd); + } + } +} + +/* Loads a 64-bit value from disk and casts it into a size_t, which may or may + * not be 64-bit. As long as the loaded value fits inside size_t, we're good. + * Returns 0 if the value didn't fit, 1 otherwise. + */ +static uint8_t read_u64bit_to_size_t(size_t* dest, FILE* fd) +{ + uint64_t value; + fread(&value, sizeof(uint64_t), 1, fd); + if (value > (size_t)-1) { + printf("Unable to load 64-bit data from file\n"); + return 0; + } else { + *dest = (size_t)be64toh(value); + return 1; + } +} + +ahtable_t* ahtable_load(FILE* fd) +{ + size_t n; + if (!read_u64bit_to_size_t(&n, fd)) return NULL; + ahtable_t* table = ahtable_create_n(n); + + if (!read_u64bit_to_size_t(&table->m, fd)) return NULL; + + if (!read_u64bit_to_size_t(&table->max_m, fd)) return NULL; + + fread(&table->flag, sizeof(uint8_t), 1, fd); + + fread(&table->c0, sizeof(unsigned char), 1, fd); + fread(&table->c1, sizeof(unsigned char), 1, fd); + + size_t i; + uint32_t slot_size; + for (i = 0; i < table->n; ++i) { + fread(&slot_size, sizeof(uint32_t), 1, fd); + table->slot_sizes[i] = be32toh(slot_size); + if(table->slot_sizes[i] > 0) { + table->slots[i] = malloc_or_die(table->slot_sizes[i]); + fread(table->slots[i], sizeof(unsigned char), table->slot_sizes[i], fd); + } + } + + return table; +} void ahtable_free(ahtable_t* table) { @@ -259,6 +337,11 @@ static value_t* get_key(ahtable_t* table, const char* key, size_t len, bool inse value_t* ahtable_get(ahtable_t* table, const char* key, size_t len) { + if (len > 32767) { + fprintf(stderr, "HAT-trie/AH-table cannot store keys longer than 32768\n"); + exit(EXIT_FAILURE); + } + return get_key(table, key, len, true); } diff --git a/src/ahtable.h b/src/ahtable.h index 15e8e21..c267d6c 100644 --- a/src/ahtable.h +++ b/src/ahtable.h @@ -47,6 +47,7 @@ extern "C" { #include <stdlib.h> #include <stdbool.h> +#include <stdio.h> #include "pstdint.h" #include "common.h" @@ -74,6 +75,9 @@ ahtable_t* ahtable_create (void); // Create an empty hash table. ahtable_t* ahtable_create_n (size_t n); // Create an empty hash table, with // n slots reserved. +ahtable_t* ahtable_load (FILE* fd); // Load a hash table from a file handle. +void ahtable_save (const ahtable_t* T, FILE* fd); // Save a hash table to a file handle. + void ahtable_free (ahtable_t*); // Free all memory used by a table. void ahtable_clear (ahtable_t*); // Remove all entries. size_t ahtable_size (const ahtable_t*); // Number of stored keys. diff --git a/src/hat-trie.h b/src/hat-trie.h index b6b0653..a646c94 100644 --- a/src/hat-trie.h +++ b/src/hat-trie.h @@ -30,7 +30,6 @@ typedef struct hattrie_t_ hattrie_t; hattrie_t* hattrie_create (void); // Create an empty hat-trie. void hattrie_free (hattrie_t*); // Free all memory used by a trie. -hattrie_t* hattrie_dup (const hattrie_t*); // Duplicate an existing trie. void hattrie_clear (hattrie_t*); // Remove all entries. size_t hattrie_size (const hattrie_t*); // Number of stored keys. size_t hattrie_sizeof (const hattrie_t*); // Memory used in structure in bytes. diff --git a/src/portable_endian.h b/src/portable_endian.h new file mode 100644 index 0000000..edf2978 --- /dev/null +++ b/src/portable_endian.h @@ -0,0 +1,116 @@ +// "License": Public Domain +// I, Mathias Panzenböck, place this file hereby into the public domain. Use it at your own risk for whatever you like. + +#ifndef PORTABLE_ENDIAN_H__ +#define PORTABLE_ENDIAN_H__ + +#if (defined(_WIN16) || defined(_WIN32) || defined(_WIN64)) && !defined(__WINDOWS__) + +# define __WINDOWS__ + +#endif + +#if defined(__linux__) || defined(__CYGWIN__) + +# define __USE_BSD +# include <endian.h> + +#elif defined(__APPLE__) + +# include <libkern/OSByteOrder.h> + +# define htobe16(x) OSSwapHostToBigInt16(x) +# define htole16(x) OSSwapHostToLittleInt16(x) +# define be16toh(x) OSSwapBigToHostInt16(x) +# define le16toh(x) OSSwapLittleToHostInt16(x) + +# define htobe32(x) OSSwapHostToBigInt32(x) +# define htole32(x) OSSwapHostToLittleInt32(x) +# define be32toh(x) OSSwapBigToHostInt32(x) +# define le32toh(x) OSSwapLittleToHostInt32(x) + +# define htobe64(x) OSSwapHostToBigInt64(x) +# define htole64(x) OSSwapHostToLittleInt64(x) +# define be64toh(x) OSSwapBigToHostInt64(x) +# define le64toh(x) OSSwapLittleToHostInt64(x) + +# define __BYTE_ORDER BYTE_ORDER +# define __BIG_ENDIAN BIG_ENDIAN +# define __LITTLE_ENDIAN LITTLE_ENDIAN +# define __PDP_ENDIAN PDP_ENDIAN + +#elif defined(__OpenBSD__) + +# include <sys/endian.h> + +#elif defined(__NetBSD__) || defined(__FreeBSD__) || defined(__DragonFly__) + +# include <sys/endian.h> + +# define be16toh(x) betoh16(x) +# define le16toh(x) letoh16(x) + +# define be32toh(x) betoh32(x) +# define le32toh(x) letoh32(x) + +# define be64toh(x) betoh64(x) +# define le64toh(x) letoh64(x) + +#elif defined(__WINDOWS__) + +# include <winsock2.h> +# include <sys/param.h> + +# if BYTE_ORDER == LITTLE_ENDIAN + +# define htobe16(x) htons(x) +# define htole16(x) (x) +# define be16toh(x) ntohs(x) +# define le16toh(x) (x) + +# define htobe32(x) htonl(x) +# define htole32(x) (x) +# define be32toh(x) ntohl(x) +# define le32toh(x) (x) + +# define htobe64(x) htonll(x) +# define htole64(x) (x) +# define be64toh(x) ntohll(x) +# define le64toh(x) (x) + +# elif BYTE_ORDER == BIG_ENDIAN + + /* that would be xbox 360 */ +# define htobe16(x) (x) +# define htole16(x) __builtin_bswap16(x) +# define be16toh(x) (x) +# define le16toh(x) __builtin_bswap16(x) + +# define htobe32(x) (x) +# define htole32(x) __builtin_bswap32(x) +# define be32toh(x) (x) +# define le32toh(x) __builtin_bswap32(x) + +# define htobe64(x) (x) +# define htole64(x) __builtin_bswap64(x) +# define be64toh(x) (x) +# define le64toh(x) __builtin_bswap64(x) + +# else + +# error byte order not supported + +# endif + +# define __BYTE_ORDER BYTE_ORDER +# define __BIG_ENDIAN BIG_ENDIAN +# define __LITTLE_ENDIAN LITTLE_ENDIAN +# define __PDP_ENDIAN PDP_ENDIAN + +#else + +# error platform not supported + +#endif + +#endif diff --git a/test/check_ahtable.c b/test/check_ahtable.c index f61132b..63439cd 100644 --- a/test/check_ahtable.c +++ b/test/check_ahtable.c @@ -205,6 +205,52 @@ void test_ahtable_sorted_iteration() fprintf(stderr, "done.\n"); } +void test_ahtable_save_load() +{ + fprintf(stderr, "saving ahtable ... \n"); + + FILE* fd_w = fopen("test.aht", "w"); + ahtable_save(T, fd_w); + fclose(fd_w); + + fprintf(stderr, "loading ahtable ... \n"); + + FILE* fd_r = fopen("test.aht", "r"); + ahtable_t* U = ahtable_load(fd_r); + fclose(fd_r); + + fprintf(stderr, "comparing ahtable ... \n"); + + ahtable_iter_t* i = ahtable_iter_begin(T, false); + ahtable_iter_t* j = ahtable_iter_begin(U, false); + const char *k1 = NULL; + const char *k2 = NULL; + value_t* v1; + value_t* v2; + size_t len1 = 0; + size_t len2 = 0; + while (!ahtable_iter_finished(i) && !ahtable_iter_finished(j)) { + k1 = ahtable_iter_key(i, &len1); + v1 = ahtable_iter_val(i); + + k2 = ahtable_iter_key(j, &len2); + v2 = ahtable_iter_val(j); + + if(len1 != len2) { + fprintf(stderr, "[error] key lengths don't match (%lu, %lu)\n", len1, len2); + } + + if(*v1 != *v2) { + fprintf(stderr, "[error] values don't match (%lu, %lu)\n", *v1, *v2); + } + + ahtable_iter_next(i); + ahtable_iter_next(j); + } + ahtable_iter_free(i); + ahtable_iter_free(j); +} + int main() { @@ -218,5 +264,10 @@ int main() test_ahtable_sorted_iteration(); teardown(); + setup(); + test_ahtable_insert(); + test_ahtable_save_load(); + teardown(); + return 0; } -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/debian-med/libhat-trie.git _______________________________________________ debian-med-commit mailing list debian-med-commit@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/debian-med-commit