For context, I'm a new programmer to C and I wanted to make a toy implementation of a dictionary/map from a 'Person' struct to an integer. I'm using separate chaining, so I have a hash table of linked list pointers.
So far, I've been able to add one value to the linked list just fine, but when I call the function to get the value for the Person key I'm using, the memory at one of my nodes seems to get overwritten.
More info if it's helpful, using a singly linked list with one sentinel node at the head and a tail reference.
New to StackOverflow, so I can't actually embed the image, but pictured on left is the HashTable at the beginning of the function call, when nothing has been changed. The relevant stuff is the expanded part of the Variables menu, which shows that at position 58 is a pointer to 0x61f8e0, the linked list. The linked list has a head pointer to 0x61f760, which is the sentinel value, and a tail pointer to 0x61f864, currently pointing to a Node with the value (3) for a Person named Robert who's 36 years old. The tail pointer's next field points to 0x0 (not pictured), like intended. The picture follows: https://i.stack.imgur.com/F9EJ9.png
This is what happens as soon as the first statement (which hashes the Person pointer very naively) is executed: https://i.stack.imgur.com/UJvGy.png. As you'll see, the value is now some random long number, the intrinsic age is now 1 instead of 36, the saved name is now gibberish, and worst of all the next pointer now points somewhere completely random (0x61fb10).
The function in question follows.
int tableGet(HashTable t, Person key) {
int position = hash(&key) % 100;
List* listLoc = t.table[position];
if ((int) listLoc == 0) {
return -1;
}
Node curr = *(listLoc -> head);
while (curr.next != NULL) {
if (curr.savedAge == key.age && curr.savedName == key.name) {
return curr.val;
}
curr = *curr.next;
}
return -1;
}
Here is the hash function, in case that's what's causing the problems.
int hash(Person* p) {
int sum;
Person person = *p;
int i = 0;
char nameChar = person.name[i];
while (nameChar != '\0'){
sum += (int) nameChar;
i += 1;
nameChar = person.name[i];
}
return (int) (person.age + sum);
}
And just because why not, here's all of the short amount of code I've written for this.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
typedef struct Node {
int val;
int savedAge;
char savedName[100];
struct Node* next;
} Node;
typedef struct {
int age;
char name[100];
} Person;
typedef struct {
Node* head;
Node* tail;
} List;
typedef struct {
List* table[100];
} HashTable;
int hash(Person*);
Person person(int age, char name[]) {
Person p;
p.age = age;
strcpy(p.name, name);
return p;
}
Node node(int val, Person p, Node* next) {
Node n;
n.val = val;
strcpy(n.savedName, p.name);
n.savedAge = p.age;
n.next = next;
return n;
}
List list() {
List l;
Node head = node(-1, person(0, "SENTINEL"), NULL);
l.head = &head;
l.tail = l.head;
return l;
}
void listAdd(List* l, Node n) {
Node* newTailPtr = &n;
l -> tail -> next = newTailPtr;
l -> tail = newTailPtr;
}
HashTable table() {
int table[100] = {0};
HashTable t;
memcpy(t.table, table, sizeof table);
return t;
}
HashTable tableAdd(HashTable t, Person key, int val) {
int num = hash(&key) % 100;
List* loc = t.table[num];
if ((int) loc == 0) {
List newList = list();
t.table[num] = &newList;
}
listAdd((List*) t.table[num], node(val, key, NULL));
return t;
}
int tableGet(HashTable t, Person key) {
int position = hash(&key) % 100;
List* listLoc = t.table[position];
if ((int) listLoc == 0) {
return -1;
}
Node curr = *(listLoc -> head);
while (curr.next != NULL) {
if (curr.savedAge == key.age && curr.savedName == key.name) {
return curr.val;
}
curr = *curr.next;
}
return -1;
}
int hash(Person* p) {
int sum;
Person person = *p;
int i = 0;
char nameChar = person.name[i];
while (nameChar != '\0'){
sum += (int) nameChar;
i += 1;
nameChar = person.name[i];
}
return (int) (person.age + sum);
}
int main() {
Person bob = person(36, "Robert");
printf(bob.name);
printf("\n");
HashTable tab = table();
tab = tableAdd(tab, bob, 3);
printf("Added Robert to table as 3\n");
int val = tableGet(tab, bob);
if (val == 3) {
printf("Success!\n");
} else {
printf("Failure, val is %d\n", val);
}
return 0;
}