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.
145 lines
3.6 KiB
145 lines
3.6 KiB
#ifndef HASH_H
|
|
#define HASH_H
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <assert.h>
|
|
#include <pthread.h>
|
|
#define TABLE_SIZE 32 // the size of hash table
|
|
#define MAX_KEY_LENGTH 32 // the maximum length of key
|
|
typedef struct {
|
|
char key[MAX_KEY_LENGTH];
|
|
void *value;
|
|
int is_deleted; // Flag to mark items as deleted
|
|
} HashItem;
|
|
|
|
typedef struct {
|
|
HashItem **items;
|
|
pthread_mutex_t lock;
|
|
} HashTable;
|
|
|
|
static inline unsigned long
|
|
hash_function(const char *str) {
|
|
unsigned long i = 0;
|
|
for (int j = 0; str[j]; j++)
|
|
i += str[j];
|
|
return i % TABLE_SIZE;
|
|
}
|
|
|
|
static inline HashTable
|
|
*create_table() {
|
|
HashTable *table = (HashTable *)malloc(sizeof(HashTable));
|
|
if (!table) {
|
|
fprintf(stderr, "Failed to allocate memory for hash table struct.\n");
|
|
return NULL;
|
|
}
|
|
|
|
table->items = (HashItem **)malloc(sizeof(HashItem*) * TABLE_SIZE);
|
|
if (!table->items) {
|
|
fprintf(stderr, "Failed to allocate memory for items.\n");
|
|
free(table); // Free the table if item allocation fails
|
|
return NULL;
|
|
}
|
|
|
|
pthread_mutex_init(&table->lock, NULL);
|
|
|
|
for (int i = 0; i < TABLE_SIZE; i++) {
|
|
table->items[i] = NULL;
|
|
}
|
|
return table;
|
|
}
|
|
|
|
static inline void
|
|
add_item(HashTable *table, const char *key, void *value) {
|
|
assert(table != NULL);
|
|
assert(key != NULL);
|
|
assert(value != NULL);
|
|
|
|
pthread_mutex_lock(&table->lock);
|
|
|
|
unsigned long index = hash_function(key);
|
|
HashItem *item = malloc(sizeof(HashItem));
|
|
if (!item) {
|
|
fprintf(stderr, "Failed to allocate memory for a new item.\n");
|
|
pthread_mutex_unlock(&table->lock);
|
|
return;
|
|
}
|
|
strcpy(item->key, key);
|
|
item->value = value;
|
|
item->is_deleted = 0;
|
|
|
|
while (table->items[index] != NULL && !table->items[index]->is_deleted && strcmp(table->items[index]->key, key) != 0) {
|
|
index = (index + 1) % TABLE_SIZE;
|
|
}
|
|
|
|
free(table->items[index]); // Free the existing item if overwriting
|
|
table->items[index] = item;
|
|
|
|
pthread_mutex_unlock(&table->lock);
|
|
}
|
|
|
|
static inline void
|
|
remove_item(HashTable *table, const char *key) {
|
|
assert(table != NULL);
|
|
assert(key != NULL);
|
|
|
|
pthread_mutex_lock(&table->lock);
|
|
|
|
unsigned long index = hash_function(key);
|
|
while (table->items[index] != NULL && strcmp(table->items[index]->key, key) != 0) {
|
|
index = (index + 1) % TABLE_SIZE;
|
|
}
|
|
|
|
if (table->items[index] != NULL) {
|
|
table->items[index]->is_deleted = 1; // Mark as deleted
|
|
}
|
|
|
|
pthread_mutex_unlock(&table->lock);
|
|
}
|
|
|
|
static inline void
|
|
*find_value(HashTable *table, const char *key) {
|
|
assert(table != NULL);
|
|
assert(key != NULL);
|
|
|
|
pthread_mutex_lock(&table->lock);
|
|
|
|
unsigned long index = hash_function(key);
|
|
int count = 0;
|
|
while (table->items[index] != NULL && count < TABLE_SIZE && (table->items[index]->is_deleted || strcmp(table->items[index]->key, key) != 0)) {
|
|
index = (index + 1) % TABLE_SIZE;
|
|
count++;
|
|
}
|
|
|
|
if (table->items[index] == NULL || table->items[index]->is_deleted)
|
|
{
|
|
pthread_mutex_unlock(&table->lock);
|
|
return NULL;
|
|
}
|
|
else {
|
|
pthread_mutex_unlock(&table->lock);
|
|
return table->items[index]->value;
|
|
}
|
|
}
|
|
|
|
static inline void
|
|
free_table(HashTable *table) {
|
|
assert(table != NULL);
|
|
|
|
pthread_mutex_lock(&table->lock);
|
|
|
|
for (int i = 0; i < TABLE_SIZE; i++) {
|
|
if (table->items[i] != NULL) {
|
|
free(table->items[i]); // Free each item
|
|
}
|
|
}
|
|
free(table->items);
|
|
free(table);
|
|
|
|
pthread_mutex_unlock(&table->lock);
|
|
pthread_mutex_destroy(&table->lock);
|
|
}
|
|
|
|
#endif
|