Daniel Daniel - 1 month ago 10
C Question

Segfault in simple hash table

I am trying to write a simple hash table in C and I am getting a very strange segfault when testing it with the code shown my

main()
.

The Design: I have a hash table with an underlying array of size 10,000. I hold a double pointer to the start of an array of
struct node_t
(or
node
) pointers. When I want to
put()
something into the hash table, I check if the
node
element at the appropriate location is
NULL
. If it is, I create a new node to fill the spot, otherwise, if there are collisions, I build a linked list off of the colliding node.

The Scenario: In
main()
, I am trying to
put()
the number 3328 into the hash table. Instead, the program segfaults. This makes no sense to me as the previous
put()
works fine and you can clearly see that I set all the initial pointers to NULL. As far as I know, the pointer that refers to hash table location 3328 is not getting set to NULL because when I dereference it in the
put()
function, that's when it segfaults. My main function looks like it should set all the pointers to NULL just fine though...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int TABLE_SIZE = 10000;

typedef struct node_t {
int key;
int value;
struct node_t* next;
} node;

node** table;

inline node** get_node_address(int key) {
key = (key > -key ? key : -key) % TABLE_SIZE;
return (node**) (table + key * sizeof(node*));
}

inline node* new_node(int key, int value) {
node* n = malloc(sizeof(node));
n->key = key;
n->value = value;
n->next = NULL;
return n;
}

void put(int key, int value) {
node** n = (node**) get_node_address(key);
node* iterator = (node*) *n;

if (*n == NULL) {
*n = new_node(key, value);
} else {
while (iterator->next != NULL)
iterator = iterator->next;

iterator->next = new_node(key, value);
}
}

int* get(int key) {
node* iterator = (node*) *get_node_address(key);

while (iterator != NULL && iterator->key != key) {
iterator = iterator->next;
}

if (iterator == NULL)
return NULL;
else
return &(iterator->value);
}

int main() {
printf("Starting..\n");

int i;
table = malloc(sizeof(node*) * TABLE_SIZE);
memset(table, 0, sizeof(node*) * TABLE_SIZE);

for (i = 0; i < TABLE_SIZE; i++) {
table[i] = NULL;
printf("setting %x\n", &table[i]);
}

printf("before bad: %x\n", *get_node_address(3327));
printf("bad address: %x\n", *get_node_address(3328));
printf("last address: %x\n", table + sizeof(node*) * TABLE_SIZE);

printf("Hashing...\n");

put(3328, 3338);
printf("%d", *get(3328));

return 0;
}

Answer

There's at least one problem:

inline node** get_node_address(int key) {
      key = (key > -key ? key : -key) % TABLE_SIZE;
      return (node**) (table + key * sizeof(node*)); /* <---- */
}

You mustn't multiply key. Because of the way pointer arithmetic works in C, table + key yields the key-th element.