Задание № 1477

Студент

Бочарников Андрей

Задача

Хэш-таблица

Состояние

Открыто

Дедлайн
21 февраля 2019
Назначено

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;
}

Действия