I've a problem with memory allocation for an hash table with linked list (for avoid collisions) in C.

I think that the problem is on allocation of an item. I've made two scruct, one for the single item and one for the table. The first have two pointer to next and prev item. Please help me. I stay on this code until 3 days. The code :

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define CAPACITY 50000 

unsigned long hash(char *str) { 
    unsigned long int stringsum = 0; 
    for(; *str != '\0'; str  ) { 
        stringsum  = *str; 
    } 
    return stringsum % CAPACITY; 
    
} 


typedef struct item  { 
    char *value; 
    char *key; 
    struct item *next; 
    struct item *prev; 
} ht_item; 

typedef struct hashtable { 
    ht_item **items; 
    int dim; 
    int count; 
} HashTable; 

HashTable* create_table(int size); HashTable* create_item(HashTable *table, char *value, char *key); 
void print_table(HashTable* table, int dim); 


int main(void) { 
    HashTable *table = create_table(CAPACITY); 
    table = create_item(table, "Giuseppe", "Nome"); 
    print_table(table, CAPACITY); 
    return 0; 
    
} 


HashTable* create_item(HashTable *table, char *value, char *key) { 
    unsigned long index = hash(key);
    printf("%u", index); 
    ht_item *_iterator; ht_item *prev;
    for(_iterator = table->items[index], prev = NULL; _iterator != NULL; prev = _iterator, _iterator = _iterator->next);
     _iterator = (ht_item*)malloc(sizeof(ht_item));
     _iterator->key = (char*)malloc(200);
     _iterator->value = (char*)malloc(200); 
     strcpy(_iterator->key, key);
     strcpy(_iterator->value, value);
     _iterator->next = NULL;
     _iterator->prev = prev; 
    return table; 
} 


HashTable* create_table(int size)
{ 
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    table->dim = size; 
    table->items = (ht_item**)calloc(size, sizeof(ht_item*)); 
    for(int i = 0; i < size; i  ){ 
        table->items[i] = NULL; 
    } 
    
    return table; 
} 


void print_table(HashTable* table, int dim) { 
    for(int i = 0; i < CAPACITY; i  )
     { 
        if(table->items[i] != NULL)
         { ht_item *_iterator = (ht_item*)malloc(sizeof(ht_item));
             for(_iterator = table->items[i]; _iterator != NULL;
             _iterator = _iterator->next)
             { 
                printf("Key: %s\tValue: %s\n", _iterator->key, _iterator->value); 
                } free(_iterator); 
            } 
        } 
}

CodePudding user response：

Made some changes in your code. Please read through the blocks containing // CHANGE HERE comment.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define CAPACITY 50000

// CHANGE HERE - additional parameter, value to be used for modulo
unsigned long hash(char *str, unsigned int mod_value) { 
    unsigned long int stringsum = 0; 
    for(; *str != '\0'; str  ) { 
        stringsum  = *str; 
    }
    // CHANGE HERE - use mod_value instead of CAPACITY
    return stringsum % mod_value; 
    
} 


typedef struct item  { 
    char *value; 
    char *key; 
    struct item *next; 
    struct item *prev; 
} ht_item; 

typedef struct hashtable { 
    ht_item **items; 
    int dim; 
    int count; 
} HashTable; 

HashTable* create_table(int size); HashTable* create_item(HashTable *table, char *value, char *key); 
void print_table(HashTable* table, int dim); 


int main(void) { 
    HashTable *table = create_table(CAPACITY); 
    table = create_item(table, "Giuseppe", "Nome"); 
    print_table(table); 
    return 0; 
} 


HashTable* create_item(HashTable *table, char *value, char *key) {
    // CHANGE HERE - function arguments validation
    if (table == NULL)
    {
        return table;
    }
    if (value == NULL || key == NULL)
    {
        printf("Key or value is null\n");
        return table;
    }

    // CHANGE HERE - pass table->dim to hash
    unsigned long index = hash(key, table->dim);
    printf("Index: %lu\n", index);
    
    // CHANGE HERE - simplified the code a bit
    ht_item* new_node = malloc(sizeof(ht_item));
    new_node->key = malloc(200 * sizeof(char));
    strncpy(new_node->key, key, 200);
    new_node->value = malloc(200 * sizeof(char));
    strncpy(new_node->value, value, 200);
    
    // CHANGE HERE - if first node in index
    if (table->items[index] == NULL)
    {
        table->items[index] = new_node;
        return table;
    }
    
    ht_item *cur, *prev = NULL;
    for(cur = table->items[index]; cur != NULL; prev = cur, cur = cur->next);
    
    prev->next = new_node;  // CHANGE HERE - it seems this line was missing
    new_node->prev = prev;
    new_node->next = NULL;
    
    return table; 
} 


HashTable* create_table(int size)
{ 
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    table->dim = size; 
    table->items = (ht_item**)calloc(size, sizeof(ht_item*)); 
    for(int i = 0; i < size; i  ){ 
        table->items[i] = NULL; 
    } 
    
    return table; 
} 


void print_table(HashTable* table) {
    // CHANGE HERE - function arguments validation
    if (table == NULL)
    {
        printf("Table is null\n");
        return;
    }
    // CHANGE HERE - change CAPACITY to dim
    for(int i = 0; i < table->dim; i  )
    {
        //printf("i = %d [%d]\n", i, table->items[i] == NULL);
        if(table->items[i] != NULL)
        {
            // CHANGE HERE - removed unnecessary malloc
            ht_item *_iterator = NULL;
            for(_iterator = table->items[i]; _iterator != NULL; _iterator = _iterator->next)
            { 
                printf("Key: %s\tValue: %s\n", _iterator->key, _iterator->value);
            }
        } 
    } 
}

CodePudding user response：

The create_item function can and should be simplified. I have put some comments inline.

HashTable* create_item(HashTable *table, char *value, char *key) { 
    // use modulo operator here, not in the hash function
    unsigned long index = hash(key) % table->dim;

    // nicer way of allocating
    ht_item *insert = malloc(sizeof *insert);

    // use strdup to avoid wasted memory and buffer overflows
    insert->key = strdup(key);
    insert->value = strdup(value);

    // head insert rather than tail
    insert->next = table->items[index];
    table->items[index] = insert;        

    return table; 
}

I dropped the use of the prev member. If you need that somewhere it's an exercise for you to add it. I don't think it's necessary for a simple hash table.