Открыто
11.02.2019, 08:49
Реализовать на языке C модуль для работы с хэш-таблицей.
Строго заданный интерфейс:
#include <stdbool.h> // bool
#include <stddef.h> // size_t
static const size_t INVALID = ~((size_t)0);
typedef
struct HTableItem
{
const void * key;
void * value;
}
HTableItem;
void * htable_create(
size_t keySize, size_t valueSize,
size_t hash(const void *),
bool(*equals)( const void *, const void * )
);
void htable_destroy(void * htable, void(*destroy)( void * ));
void * htable_init(
void * htable,
size_t keySize, size_t valueSize,
size_t hash(const void *),
bool(*equals)( const void *, const void * ),
void(*destroy)(void*)
);
void htable_clear(void * htable, void(*destroy)( void * ));
size_t htable_count(const void * htable);
void * htable_item(const void * htable, const void * key);
void * htable_insert(void * htable, const void * key, bool * createFlag);
void htable_remove(void * htable, const void * key, void(*destroy)( void * ));
size_t htable_first(const void * htable);
size_t htable_last(const void * htable);
size_t htable_next(const void * htable, size_t item_id);
size_t htable_prev(const void * htable, size_t item_id);
size_t htable_stop(const void * htable);
void * htable_current(const void * htable, size_t item_id);
void htable_erase(void * htable, size_t item_id, void(*destroy)( void * ));
INVALID -- код ошибки для невалидных ситуаций.struct HTableItem -- элемент хэш-таблицы, содержащий в себе указатели на ключ и значение.htable_create -- Создать новую пустую хэш-таблицу. Размер ключа -- keySize, размер значения элемента -- valueSize, для обработки элементов по ключу использовать функцию хеширования hash, и функцию проверки на равенство equals.htable_destroy -- Удалить существующую хэш-таблицу. Если указана функция destroy, то вызвать её для каждого удаляемого элемента htableItem.htable_init -- Инициализировать хэш-таблицу новыми параметрами.
Если htable содержит элементы, то сначала удалить все элементы, потом инициализировать хэш-таблицу с учетом новых параметров.
Размер ключа -- keySize, размер значения элемента -- valueSize,
для обработки элементов по ключу использовать функцию хеширования hash, и функцию проверки на равенство equals.
Если указана функция destroy, то вызвать её для каждого удаляемого элемента htableItem.htable_clear -- Удалить все элементы из хэш-таблицы. Если указана функция destroy, то вызвать её для каждого удаляемого элемента htableItem.htable_count -- Возвращает количество элементов в хэш-таблице. В случае, если htable равен NULL, возвращает INVALID константу. htable_item -- Получить значение по заданному ключу. В случае наличия искомого ключа в хэш-таблице, функция возвращает указатель на значение связанное с этим ключом, иначе -- NULL.htable_insert -- Добавить значение по заданному ключу.
В случае успеха, функция возвращает указатель на связанное с искомым ключом значение, иначе -- NULL.
Указатель createFlag не может быть равен NULL.
При создании нового элемента хэш-таблицы этот флаг будет установлен в true,
при доступе к значению уже существовавшего элемента -- в false.htable_remove -- Найти по ключу и удалить элемент из хэш-таблицы. Если указана функция destroy, то вызвать её для удаляемого элемента htableItem.htable_first -- Идентификатор для первого элемента хэш-таблицы. Идентификатор может стать невалидным при модификации таблицы.htable_last -- Идентификатор для последнего элемента хэш-таблицы. Идентификатор может стать невалидным при модификации таблицы.htable_next -- По идентификатору текущего элемента получить идентификатор следующего элемента таблицы.htable_prev -- По идентификатору текущего элемента получить идентификатор предыдущего элемента таблицы.htable_stop -- Идентификатор, получаемый при попытке обратиться к элементу за пределами таблицы.htable_current -- Получить элемент htableItem по его идентификатору.htable_erase -- Удаление элемента хэш-таблицы по его идентификатору. Если указана функция destroy, то вызвать её для удаляемого элемента htableItem. После удаления элемента, идентификаторы любых элементов из этой хэш-таблицы могут стать невалидным.//Пример использования
#include <string.h>
#include <assert.h>
#include <math.h>
#include "htable.h"
typedef struct{
int array[8];
float d_variable;
} Value;
typedef struct {
char name[10];
} Key;
static size_t hash(const void* ptr) {
const int p = 31;
const int m = 1e9 + 9;
size_t hash_value = 0;
size_t p_pow = 1;
const Key* key = (const Key*)ptr;
for(size_t i = 0; i < 10; ++i){
const char c = key->name[i];
hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
p_pow = (p_pow * p) % m;
}
return hash_value;
}
static bool equals(const void* lhsp, const void* rhsp){
const Key* lhs = (const Key*)lhsp;
const Key* rhs = (const Key*)rhsp;
return 0 == strcmp(lhs->name, rhs->name);
}
int main(int argc, char * argv[])
{
//Создаем хэш-таблицу: ключ - тип Key; значение - тип Value;
void* htable = htable_create(sizeof(Key), sizeof(Value), hash, equals);
assert(0 == htable_count(htable));
assert(htable_stop(htable) == htable_first(htable));
//Создаем ключ и значение для хэш-таблицы
Key key = { "New key" };
Value value = { {1, 2, 3, 4, 5, 6, 7, 8}, 0.f };
bool isCreated = false;
//Добавляем по ключу значение
Value* insertedValue = (Value*)htable_insert(htable, &key, &isCreated);
assert(true == isCreated);
*insertedValue = value;
//Проверяем, что по добавленному ключу получим соответствующее значение
Value* item = (Value*)htable_item(htable, &key);
for(size_t i = 0; 8 > i; ++i){
assert(item->array[i] == value.array[i]);
}
assert(fabsf(item->d_variable - value.d_variable) < 1e-10f);
assert(htable_last(htable) == htable_first(htable));
assert(htable_next(htable, htable_first(htable)) == htable_stop(htable));
htable_destroy(htable, NULL);
return 0;
}