147 lines
4.1 KiB
C
147 lines
4.1 KiB
C
/***************************************************************************
|
|
* Copyright (C) 07/2007 by Olaf Rempel *
|
|
* razzor@kopf-tisch.de *
|
|
* *
|
|
* 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; version 2 of the License *
|
|
* *
|
|
* 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., *
|
|
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
|
|
***************************************************************************/
|
|
#include <stdlib.h>
|
|
#include <inttypes.h>
|
|
#include <pthread.h>
|
|
|
|
#include "hashtable.h"
|
|
|
|
/* see linux/include/linux/jhash.h for details */
|
|
#define JHASH_GOLDEN_RATIO 0x9e3779b9
|
|
#define __jhash_mix(a, b, c) \
|
|
{ \
|
|
a -= b; a -= c; a ^= (c>>13); \
|
|
b -= c; b -= a; b ^= (a<<8); \
|
|
c -= a; c -= b; c ^= (b>>13); \
|
|
a -= b; a -= c; a ^= (c>>12); \
|
|
b -= c; b -= a; b ^= (a<<16); \
|
|
c -= a; c -= b; c ^= (b>>5); \
|
|
a -= b; a -= c; a ^= (c>>3); \
|
|
b -= c; b -= a; b ^= (a<<10); \
|
|
c -= a; c -= b; c ^= (b>>15); \
|
|
}
|
|
|
|
struct hash_table * create_hash(uint32_t buckets)
|
|
{
|
|
struct hash_table *table;
|
|
uint32_t i;
|
|
|
|
table = malloc(sizeof(struct hash_table) +
|
|
(sizeof(struct hash_entry *) * buckets));
|
|
|
|
if (table == NULL)
|
|
return NULL;
|
|
|
|
for (i = 0; i < buckets; i++)
|
|
table->bucket[i] = NULL;
|
|
|
|
table->buckets = buckets;
|
|
table->hash_rnd = time(NULL);
|
|
|
|
pthread_mutex_init(&table->mutex, NULL);
|
|
return table;
|
|
}
|
|
|
|
void purge_hash(struct hash_table *table,
|
|
void (*callback)(const struct hash_entry *entry, void *privdata),
|
|
void *privdata)
|
|
{
|
|
uint32_t i;
|
|
pthread_mutex_lock(&table->mutex);
|
|
|
|
for (i = 0; i < table->buckets; i++) {
|
|
struct hash_entry *entry = table->bucket[i];
|
|
while (entry != NULL) {
|
|
struct hash_entry *tmp = entry;
|
|
|
|
if (callback != NULL)
|
|
callback(entry, privdata);
|
|
|
|
entry = entry->next;
|
|
free(tmp);
|
|
}
|
|
table->bucket[i] = NULL;
|
|
}
|
|
|
|
table->hash_rnd = time(NULL);
|
|
pthread_mutex_unlock(&table->mutex);
|
|
}
|
|
|
|
void destroy_hash(struct hash_table *table)
|
|
{
|
|
purge_hash(table, NULL, NULL);
|
|
pthread_mutex_destroy(&table->mutex);
|
|
free(table);
|
|
}
|
|
|
|
static uint32_t calc_hashkey(const struct hash_entry *entry, uint32_t initval)
|
|
{
|
|
uint32_t a = entry->src_ip;
|
|
uint32_t b = (entry->flags << 8) | entry->protonum;
|
|
uint32_t c = entry->dst_port;
|
|
|
|
a += JHASH_GOLDEN_RATIO;
|
|
b += JHASH_GOLDEN_RATIO;
|
|
c += initval;
|
|
|
|
__jhash_mix(a, b, c);
|
|
|
|
return c;
|
|
}
|
|
|
|
static int cmp_entry(const struct hash_entry *a, const struct hash_entry *b)
|
|
{
|
|
return (a->src_ip ^ b->src_ip) |
|
|
(a->protonum ^ b->protonum) |
|
|
(a->dst_port ^ b->dst_port) |
|
|
(a->flags ^ b->flags);
|
|
}
|
|
|
|
void hash_add(struct hash_table *table, struct hash_entry *entry)
|
|
{
|
|
uint32_t key = calc_hashkey(entry, table->hash_rnd) % table->buckets;
|
|
|
|
pthread_mutex_lock(&table->mutex);
|
|
|
|
struct hash_entry *search = table->bucket[key];
|
|
/* search collision-list */
|
|
while (search != NULL) {
|
|
if (cmp_entry(entry, search) == 0) {
|
|
/* add values */
|
|
search->src_bytes += entry->src_bytes;
|
|
search->dst_bytes += entry->dst_bytes;
|
|
search->count++;
|
|
|
|
pthread_mutex_unlock(&table->mutex);
|
|
|
|
/* free entry */
|
|
free(entry);
|
|
return;
|
|
}
|
|
search = search->next;
|
|
}
|
|
|
|
/* insert new bucket */
|
|
entry->count = 1;
|
|
entry->next = table->bucket[key];
|
|
table->bucket[key] = entry;
|
|
|
|
pthread_mutex_unlock(&table->mutex);
|
|
}
|