открытой адресации разрешения коллизий

Question

я столкнулась с трудностями при реализации открытой адресации хэш-таблицу на языке программирования C:

#ifndef COMDS_OPENADDR_HASH_TABLE 
#define COMDS_OPENADDR_HASH_TABLE 

#define COMDS_KEY_EXIST 1 
#define COMDS_REALLOC_FAIL 2 

struct kv_pairs { 
    void *key; 
    void *value; 
}; 

typedef struct openaddr_hash_table { 
    size_t buckets; 
    size_t used; 
    size_t (*hash)(void *data); 
    struct kv_pairs *table; 
    int (*key_equal)(void *fkey, void *skey); 
    int (*value_equal)(void *fvalue, void *svalue); 
}OpenAddrHashTable; 
#endif 

Так вот я использую массив структур kv_pairs, чтобы держать мои ключи и значения, проблема что у меня должно быть 3 специальных значения: DELETED, USED, СВОБОДНЫЙ, чтобы указать, что местоположение удалено/использовано/бесплатно, я не знаю, как кодировать эти значения?

Я попытался установить STRUCT kv_pairs состоянии и установить бесплатно 0x0 УДАЛИТЬ 0x1 и ИСПОЛЬЗУЕМЫЕ 0x2 и делает сравнение, как этот

table[i] == FREE || table[i] == (struct kv*)DELETED 

Answer 1

Вопрос немного сбивает с толку, и я предположив, что вы не пытаетесь получить доступ к уже освобожденной памяти (что ваш вопрос заставляет меня думать, что вы есть). Добавления перечислимого тега на структуру kv_pair будет простым решением

struct kv_pair { 
    enum { KV_PAIR_FREE, KV_PAIR_DELETED, KV_PAIR_USED } tag; 
    void *key; 
    void *value; 
}; 

Или вы могли бы добавить отдельный массив (возможно, выделенные вместе) тегов на структуру openaddr_hash_table

enum tag { KV_PAIR_FREE, KV_PAIR_DELETED, KV_PAIR_USED}; 
struct openaddr_hash_table { 
    size_t buckets; 
    size_t used; 
    size_t (*hash)(void *data); 
    struct kv_pairs *table; 
    enum tag *tags; 
    int (*key_equal)(void *fkey, void *skey); 
    int (*value_equal)(void *fvalue, void *svalue); 
}; 

Тот выбрать, будет зависеть на шаблоне доступа к общей памяти, но оба увеличат использование памяти в структуре данных. Третье решение без увеличения памяти (что, кажется, что вы хотите) может быть следующим:

#include <stdint.h> 
#define FREE 0 
#define DELETED 1 

struct kv_pair { 
    void *key; 
    union { 
     void *value; 
     uintptr_t tag; 
    } value; 
}; 

Вы бы проверить тег, только если ключ NULL, а если нет, то в использовании.