Packet tunneling over UDP, multiple channels
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

136 lines
3.3 KiB

2 years ago
#include <stdlib.h>
#include <string.h>
#include "htable.h"
//// Generic hash table implementation
// Determine the index for a key. On match, it returns the index into
// the table. On mismatch it returns -i-1 for the first free spot
// where the keyed element would fit.
static int htindex(htable *table,unsigned char *key) {
if ( table->data == 0 ) {
table->data = calloc( 256, sizeof( unsigned char* ) );
table->size = 256;
}
unsigned int hash = (*table->hashcode)( table, key ) % table->size;
unsigned int i = hash;
int hole = -1;
for ( ;; ) {
unsigned char *x = table->data[ i++ ];
if ( x == 0 ) {
return ( hole >= 0 )? -hole : - (int) i;
}
if ( x == (unsigned char *)1 ) {
if ( hole < 0 ) {
hole = i;
}
} else if ( memcmp( x + table->offset, key, table->esize ) == 0 ) {
return i-1;
}
if ( i >= table->size ) {
i = 0;
}
if ( i == hash ) {
break;
}
}
return -1;
}
// Find the keyed element, and assign the x pointer, or assign 0.
// Returns 1 if element is found and 0 otherwise.
int htfind(htable *table,void *key,unsigned char **x) {
pthread_mutex_lock( &table->lock );
int i = htindex( table, key );
if ( i < 0 ) {
*x = 0;
pthread_mutex_unlock( &table->lock );
return 0;
}
*x = table->data[ i ];
pthread_mutex_unlock( &table->lock );
return 1;
}
// Forward
static void htgrow(htable *table);
// Add the given element.
void htadd(htable *table,unsigned char *p) {
pthread_mutex_lock( &table->lock );
if ( table->fill >= table->size / 2 ) {
htgrow( table );
}
int i = htindex( table, p + table->offset );
if ( i < 0 ) {
i = -i - 1;
if ( table->data[ i ] != 0 ) {
table->holes--;
} else {
table->fill++;
}
} else {
// There is a match already what to do?
}
table->data[ i ] = p;
pthread_mutex_unlock( &table->lock );
}
// Return the next element starting at i, or 0 if there are no more.
// Also increment the index to be of the element + 1, or -1 if there
// are no more elements.
static unsigned char *htnext(htable *table,int *i) {
if ( *i < 0 ) {
return 0;
}
unsigned char **p = table->data + *i;
unsigned char **e = table->data + table->size;
for ( ; p < e; p++ ) {
(*i) += 1;
if ( *p != 0 && *p != (unsigned char*)1 ) {
2 years ago
return *p;
}
}
(*i) = -1;
return 0;
}
static void htrehash(htable *table,unsigned int size) {
htable old = *table;
table->data = calloc( size, sizeof( unsigned char * ) );
table->size = size;
table->fill = 0;
table->holes = 0;
int i = 0;
unsigned char *p;
while ( ( p = htnext( &old, &i ) ) != 0 ) {
htadd( table, p );
}
free( old.data );
}
static void htgrow(htable *table) {
if ( table->data == 0 ) {
table->data = calloc( 256, sizeof( unsigned char * ) );
table->size = 256;
table->fill = 0;
table->holes = 0;
return;
}
htrehash( table, table->size << 8 );
}
// Delete the given element.
void htdelete(htable *table,unsigned char *p) {
pthread_mutex_lock( &table->lock );
int i = htindex( table, p + table->offset );
if ( i >= 0 ) {
table->data[ i ] = (unsigned char *)1;
table->holes += 1;
if ( table->holes > table->fill / 2 ) {
htrehash( table, table->size );
}
}
pthread_mutex_unlock( &table->lock );
}