rrqnet/htable.c

#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 ) {
	    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 );
}