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.
71 lines
2.7 KiB
71 lines
2.7 KiB
// 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 <pthread.h>
|
|
|
|
// 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);
|
|
|
|
// 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
|
|
|