From 19287a5a058ceea0804a448d0a6fe80347a383cd Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Tue, 14 Jun 2022 18:37:05 +1000 Subject: [PATCH 1/1] added --- htable/Makefile | 18 +++++ htable/example-htable.c | 73 ++++++++++++++++++++ htable/htable.c | 146 ++++++++++++++++++++++++++++++++++++++++ htable/htable.h | 74 ++++++++++++++++++++ 4 files changed, 311 insertions(+) create mode 100644 htable/Makefile create mode 100644 htable/example-htable.c create mode 100644 htable/htable.c create mode 100644 htable/htable.h diff --git a/htable/Makefile b/htable/Makefile new file mode 100644 index 0000000..236afb8 --- /dev/null +++ b/htable/Makefile @@ -0,0 +1,18 @@ +default: libhtable.a + +.INTERMEDIATE: htable.o +htable.o: CFLAGS = -Wall +htable.o: htable.c + +libhtable.a: htable.o + $(AR) r $@ $^ +CLEANRM += libhtable.a + +.INTERMEDIATE: example-htable.o +example-htable: CFLAGS = -Wall -g +example-htable: LDLIBS = libhtable.a +example-htable: example-htable.o libhtable.a +CLEANRM += example-htable + +clean: + rm -f $(CLEANRM) diff --git a/htable/example-htable.c b/htable/example-htable.c new file mode 100644 index 0000000..b3f387d --- /dev/null +++ b/htable/example-htable.c @@ -0,0 +1,73 @@ +/** + * This is an example of using htable. + */ +#include +#include +#include +#include +#include "htable.h" + +/** + * This is a table item, which is keyed on a 16-byte value. + */ +struct Counter { + int value; + char key[16]; + void *unused; +}; + +/** + * Hash function for the Counter keys. Note that this is an + * illsutration example only and there is no analysis of it being + * useful. + */ +static int Counter_hashcode( struct _htable *table, unsigned char *key ) { + int value = 0; + int i = 16; + unsigned char *end = key + 16; + unsigned char *p = key; + while ( p != end ) { + value += *(p++) + (i--); + } + return value; +} + +/** + * A hash table of Counter records using Counter_hashcode + */ +static htable counters = HTABLEINIT( struct Counter, key, Counter_hashcode ); + +#define MIN( a, b ) ({ int ax = a, bx = b; ( ax < bx )? ax : bx; }) + +/** + * setup a temporary struct Counter, and return a usefully cast + * pointer. + */ +static struct Counter *Counter_create(char *key) { + struct Counter *counter = (struct Counter *) + calloc( 1, sizeof( struct Counter ) ); + memcpy( counter->key, key, MIN( strlen( key ), sizeof( counter->key ) ) ); + return counter; +} + +static void Counter_dumpitem(int i,unsigned char *itemp) { + struct Counter *item = (struct Counter *) itemp; + fprintf(stdout, "[%03d] %16s %d %p\n", + i, item->key, item->value, item->unused ); +} + +int main(int argc,char **argv) { + static char *keys[] = { + "something", "intro", "foo bar", "hexadecimal", "burp", 0 }; + + int i; + for ( i = 0; keys[ i ]; i++ ) { + struct Counter *item = Counter_create( keys[ i ] ); + item->unused = item; + item->value = i; + htadd( &counters, (unsigned char *)item ); + } + fprintf( stdout, "table size = %d\n", counters.size ); + htdump( &counters, Counter_dumpitem ); + return 0; +} diff --git a/htable/htable.c b/htable/htable.c new file mode 100644 index 0000000..c35355d --- /dev/null +++ b/htable/htable.c @@ -0,0 +1,146 @@ +#include +#include +#include "htable.h" + +#define HOLE ((unsigned char *)1) + +//// 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 == HOLE ) { + 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 != HOLE ) { + 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 ] = HOLE; + table->holes += 1; + if ( table->holes > table->fill / 2 ) { + htrehash( table, table->size ); + } + } + pthread_mutex_unlock( &table->lock ); +} + +void htdump(htable *table,void (*dumpitem)(int i,unsigned char *p)) { + int i; + for ( i = 0 ; i < table->size; i++ ) { + if ( table->data[ i ] && table->data[ i ] != HOLE ) { + dumpitem( i, table->data[ i ] ); + } + } +} diff --git a/htable/htable.h b/htable/htable.h new file mode 100644 index 0000000..e0233b2 --- /dev/null +++ b/htable/htable.h @@ -0,0 +1,74 @@ +// A hashtable implementation with vectorized hashcode function. +// +// A hashtable is array of pointers, or the values 0 and 1, which mark +// unused and cleared slots respectively. +// +// Hash collision is handled by using the next usused or cleared slot +// by increasing, cycled indexing. An addition when the fill exceeds +// half the size causes a rehash into a new, double size table, +// without any cleared slots (i.e., the fill might be reduced after +// rehash, due to cleared slots). +// +// The fill count includes cleared entries, which counts deleted +// entries. A deletion that makes the number of cleared slots to +// exceed half the fill also causes a rehash into a new, same size +// table, without any cleared clots. +// +// The data elements have a key part, which is a contiguous portion of +// bytes at a given offset. The offset and size of the key are the +// same for all elements. +// +#ifndef HTABLE_H +#define HTABLE_H + +#define __USE_GNU 1 +#include + +// The hashtable head data structure: htable +typedef struct _htable { + unsigned char **data; // array of entries + unsigned int size; // total array size + unsigned int offset; // offset into elements for the key part + unsigned int esize; // byte size of the key part + unsigned int fill; // number of added elements + unsigned int holes; // number of deleted + int (*hashcode)(struct _htable *table,unsigned char *key); + pthread_mutex_t lock; +} htable; + +// 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. +//int htindex(htable *table,unsigned char *key); + +// 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); + +// Add the given element. +void htadd(htable *table,unsigned char *p); + +// 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. +//unsigned char *htnext(htable *table,int *i); + +// Delete the given element. +void htdelete(htable *table,unsigned char *p); + +// Dump the table with user-defined item dumper +void htdump(htable *table,void (*dumpitem)(int i,unsigned char *p)); + +// Special macro for htable initialization giving the record type, the +// key field and hashcode funtion. +// type = (base) data type for the elements +// member = the key field +// hashcodefn = function computing hashcode for a key +// assigns .compare = memcmp +#define HTABLEINIT(type,member,hashcodefn) \ + { .data = 0, .size = 0, .fill = 0, \ + .holes = 0, .offset = offsetof( type, member ), \ + .esize = sizeof( ((type *)0)->member ), .hashcode = hashcodefn, \ + .lock = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP } + +#endif // HTABLE_H -- 2.39.2