From 6b6a025488f289f749498a7e6cc1994be19f53e8 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Wed, 5 Sep 2012 12:44:41 +0200 Subject: [PATCH] Add a simple hash table implementation. --- src/Makefile.am | 4 +- src/hash.c | 103 ++++++++++++++++++++++++++++++++++++++++++++++++ src/hash.h | 41 +++++++++++++++++++ 3 files changed, 146 insertions(+), 2 deletions(-) create mode 100644 src/hash.c create mode 100644 src/hash.h diff --git a/src/Makefile.am b/src/Makefile.am index f0a24e0e..89ff2d89 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -5,7 +5,7 @@ sbin_PROGRAMS = tincd tincctl sptps_test EXTRA_DIST = linux bsd solaris cygwin mingw openssl gcrypt tincd_SOURCES = \ - utils.c getopt.c getopt1.c list.c splay_tree.c dropin.c fake-getaddrinfo.c fake-getnameinfo.c \ + utils.c getopt.c getopt1.c list.c splay_tree.c dropin.c fake-getaddrinfo.c fake-getnameinfo.c hash.c \ buffer.c conf.c connection.c control.c edge.c graph.c logger.c meta.c net.c net_packet.c net_setup.c \ net_socket.c netutl.c node.c process.c protocol.c protocol_auth.c protocol_edge.c protocol_misc.c \ protocol_key.c protocol_subnet.c route.c sptps.c subnet.c subnet_parse.c tincd.c \ @@ -46,7 +46,7 @@ INCLUDES = @INCLUDES@ -I$(top_builddir) noinst_HEADERS = \ xalloc.h utils.h getopt.h list.h splay_tree.h dropin.h fake-getaddrinfo.h fake-getnameinfo.h fake-gai-errnos.h ipv6.h ipv4.h ethernet.h \ buffer.h conf.h connection.h control.h control_common.h device.h edge.h graph.h info.h logger.h meta.h net.h netutl.h node.h process.h \ - protocol.h route.h subnet.h sptps.h tincctl.h top.h bsd/tunemu.h + protocol.h route.h subnet.h sptps.h tincctl.h top.h bsd/tunemu.h hash.h nodist_noinst_HEADERS = \ cipher.h crypto.h ecdh.h ecdsa.h digest.h prf.h rsa.h ecdsagen.h rsagen.h diff --git a/src/hash.c b/src/hash.c new file mode 100644 index 00000000..e5f2e007 --- /dev/null +++ b/src/hash.c @@ -0,0 +1,103 @@ +/* + hash.c -- hash table management + Copyright (C) 2012 Guus Sliepen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +*/ + +#include "system.h" + +#include "hash.h" +#include "xalloc.h" + +/* Generic hash function */ + +static uint32_t hash_function(const void *p, size_t len) { + const uint8_t *q = p; + uint32_t hash = 0; + while(len > 0) { + for(int i = len > 4 ? 4 : len; --i;) + hash += q[i] << (8 * i); + hash *= 0x9e370001UL; // Golden ratio prime. + len -= 4; + } + return hash; +} + +/* Map 32 bits int onto 0..n-1, without throwing away too many bits if n is 2^8 or 2^16 */ + +static uint32_t modulo(uint32_t hash, size_t n) { + if(n == 0x100) + return (hash >> 24) ^ ((hash >> 16) & 0xff) ^ ((hash >> 8) & 0xff) ^ (hash & 0xff); + else if(n == 0x10000) + return (hash >> 16) ^ (hash & 0xffff); + else + return hash % n; +} + +/* (De)allocation */ + +hash_t *hash_alloc(size_t n, size_t size) { + hash_t *hash = xmalloc_and_zero(sizeof *hash); + hash->n = n; + hash->size = size; + hash->keys = xmalloc(hash->n * hash->size); + hash->values = xmalloc_and_zero(hash->n * sizeof *hash->values); + return hash; +} + +void hash_free(hash_t *hash) { + free(hash->keys); + free(hash->values); + free(hash); +} + +/* Searching and inserting */ + +void hash_insert(hash_t *hash, const void *key, const void *value) { + uint32_t i = modulo(hash_function(key, hash->size), hash->n); + memcpy(hash->keys + i * hash->size, key, hash->size); + hash->values[i] = value; +} + +void *hash_search(const hash_t *hash, const void *key) { + uint32_t i = modulo(hash_function(key, hash->size), hash->n); + if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) { + return (void *)hash->values[i]; + } + return NULL; +} + +void *hash_search_or_insert(hash_t *hash, const void *key, const void *value) { + uint32_t i = modulo(hash_function(key, hash->size), hash->n); + if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) + return (void *)hash->values[i]; + memcpy(hash->keys + i * hash->size, key, hash->size); + hash->values[i] = value; + return NULL; +} + +/* Utility functions */ + +void hash_clear(hash_t *hash) { + memset(hash->values, 0, hash->n * sizeof *hash->values); +} + +void hash_resize(hash_t *hash, size_t n) { + hash->keys = xrealloc(hash->keys, n * hash->size); + hash->values = xrealloc(hash->values, n * sizeof *hash->values); + if(n > hash->n) + memset(hash->values + hash->n, 0, (n - hash->n) * sizeof *hash->values); +} diff --git a/src/hash.h b/src/hash.h new file mode 100644 index 00000000..c26e7acd --- /dev/null +++ b/src/hash.h @@ -0,0 +1,41 @@ +/* + hash.h -- header file for hash.c + Copyright (C) 2012 Guus Sliepen + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along + with this program; if not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. +*/ + +#ifndef __TINC_HASH_H__ +#define __TINC_HASH_H__ + +typedef struct hash_t { + size_t n; + size_t size; + char *keys; + const void **values; +} hash_t; + +extern hash_t *hash_alloc(size_t n, size_t size) __attribute__ ((__malloc__)); +extern void hash_free(hash_t *); + +extern void hash_insert(hash_t *, const void *key, const void *value); + +extern void *hash_search(const hash_t *, const void *key); +extern void *hash_search_or_insert(hash_t *, const void *key, const void *value); + +extern void hash_clear(hash_t *); +extern void hash_resize(hash_t *, size_t n); + +#endif /* __TINC_HASH_H__ */ -- 2.20.1