projects
/
tinc
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Fix a few memory leaks at exit time.
[tinc]
/
src
/
hash.c
diff --git
a/src/hash.c
b/src/hash.c
index
36b510c
..
63b8f54
100644
(file)
--- a/
src/hash.c
+++ b/
src/hash.c
@@
-1,6
+1,6
@@
/*
hash.c -- hash table management
/*
hash.c -- hash table management
- Copyright (C) 2012 Guus Sliepen <guus@tinc-vpn.org>
+ Copyright (C) 2012
-2013
Guus Sliepen <guus@tinc-vpn.org>
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
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
@@
-27,36
+27,44
@@
static uint32_t hash_function(const void *p, size_t len) {
const uint8_t *q = p;
uint32_t hash = 0;
static uint32_t hash_function(const void *p, size_t len) {
const uint8_t *q = p;
uint32_t hash = 0;
+
while(true) {
while(true) {
- for(int i = len > 4 ? 4 : len; --i;)
- hash += q[i] << (8 * i);
+ for(int i = len > 4 ? 4 : len; --i;) {
+ hash += (uint32_t)q[len - i] << (8 * i);
+ }
+
hash *= 0x9e370001UL; // Golden ratio prime.
hash *= 0x9e370001UL; // Golden ratio prime.
- if(len <= 4)
+
+ if(len <= 4) {
break;
break;
+ }
+
len -= 4;
}
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) {
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)
+ if(n == 0x100)
{
return (hash >> 24) ^ ((hash >> 16) & 0xff) ^ ((hash >> 8) & 0xff) ^ (hash & 0xff);
return (hash >> 24) ^ ((hash >> 16) & 0xff) ^ ((hash >> 8) & 0xff) ^ (hash & 0xff);
- else if(n == 0x10000)
+ } else if(n == 0x10000) {
return (hash >> 16) ^ (hash & 0xffff);
return (hash >> 16) ^ (hash & 0xffff);
- else
+ } else {
return hash % n;
return hash % n;
+ }
}
/* (De)allocation */
hash_t *hash_alloc(size_t n, size_t size) {
}
/* (De)allocation */
hash_t *hash_alloc(size_t n, size_t size) {
- hash_t *hash = xzalloc(sizeof
*hash
);
+ hash_t *hash = xzalloc(sizeof
(*hash)
);
hash->n = n;
hash->size = size;
hash->keys = xzalloc(hash->n * hash->size);
hash->n = n;
hash->size = size;
hash->keys = xzalloc(hash->n * hash->size);
- hash->values = xzalloc(hash->n * sizeof
*hash->values
);
+ hash->values = xzalloc(hash->n * sizeof
(*hash->values)
);
return hash;
}
return hash;
}
@@
-76,32
+84,45
@@
void hash_insert(hash_t *hash, const void *key, const void *value) {
void *hash_search(const hash_t *hash, const void *key) {
uint32_t i = modulo(hash_function(key, hash->size), hash->n);
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];
}
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);
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))
+
+ if(hash->values[i] && !memcmp(key, hash->keys + i * hash->size, hash->size)) {
return (void *)hash->values[i];
return (void *)hash->values[i];
+ }
+
memcpy(hash->keys + i * hash->size, key, hash->size);
hash->values[i] = value;
return NULL;
}
memcpy(hash->keys + i * hash->size, key, hash->size);
hash->values[i] = value;
return NULL;
}
+/* Deleting */
+
+void hash_delete(hash_t *hash, const void *key) {
+ uint32_t i = modulo(hash_function(key, hash->size), hash->n);
+ hash->values[i] = NULL;
+}
+
/* Utility functions */
void hash_clear(hash_t *hash) {
/* Utility functions */
void hash_clear(hash_t *hash) {
- memset(hash->values, 0, hash->n * sizeof
*hash->values
);
+ 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);
}
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);
+ hash->values = xrealloc(hash->values, n * sizeof(*hash->values));
+
if(n > hash->n) {
memset(hash->keys + hash->n * hash->size, 0, (n - hash->n) * hash->size);
if(n > hash->n) {
memset(hash->keys + hash->n * hash->size, 0, (n - hash->n) * hash->size);
- memset(hash->values + hash->n, 0, (n - hash->n) * sizeof
*hash->values
);
+ memset(hash->values + hash->n, 0, (n - hash->n) * sizeof
(*hash->values)
);
}
}
}
}