2

When removing an element from a hashtable, I need to traverse through linked-lists for elements that collide. I am using pointer operations to do this, and my linked list is in the form of bucket_t. The problem I am facing is that when I try to save the location of the first ht->bucket[I], that value changes along with the others, so at the end of the function, my head is right at the spot of next and results in a segmentation fault. I am new to working with pointers like this in c, and I apologize if my explanation is bad, but I think the code is fairly simple for you guys to see what I am trying to achieve:

void  ht_del(hashtable_t *ht, char *key) {
bucket_t *last=NULL, *next=NULL, *head=NULL;
unsigned long i;
for(i = 0; i < ht->size; i++){
  head = ht->buckets[i];
  next = ht->buckets[i];
  while(next && next->key && strcmp(next->key,key)!=0){
    last = next;
    next = next->next;
    printf("\nvisiting next\n");
    printf("key = %s\n", head->key);
  }
  if(next && next->key && strcmp(next->key,key)==0){
    printf("key found, removing key = %s, val = %s:", next->key, next->val);
    free(next->key);
    free(next->val);
    if(next->next){
      last->next = next->next;
      printf("Last->next ->key = %s\n", last->next->key);
    }
    else{
      free(next->next);
      printf("end of the line\n");
    }
    free(next);
    printf("head key = %s", head->key);
  }
 }
}

Additionally, to help understand the structs im using:

typedef struct hashtable hashtable_t;
typedef struct bucket bucket_t;

struct bucket {
  char *key;
  void *val;
  bucket_t *next;
};

struct hashtable{
  unsigned long size;
  bucket_t **buckets;
};
Lucas Trestka
  • 81
  • 8
  • Why repeatedly print the `head` key with `printf("key = %s\n", head->key);` in the `while()` loop? – chux - Reinstate Monica Jan 30 '18 at 20:43
  • I just did that to see if it was changing as I traversed through the linked list. – Lucas Trestka Jan 30 '18 at 20:44
  • Hmm, say that `while(... && strcmp(next->key,key)!=0)` fails the first time because the strings compare equal. `if(... && strcmp(next->key,key)==0)` will pass and later code does `if(next->next){`. If that is true, then code does `NULL->next = ...` and that is a problem. – chux - Reinstate Monica Jan 30 '18 at 20:50
  • I don't see a [mcve]. It very well might be that the problem is in other code. – Antti Haapala -- Слава Україні Jan 30 '18 at 20:58
  • Hmm, good point. I made a quick fix for that but that didn't stop the problem. The problem I'm facing is that when I move last and next, it also moves ht->buckets[I]. So regardless of using different variables, my head keeps moving, and is ultimately deleted. – Lucas Trestka Jan 30 '18 at 21:00
  • I'm still having trouble understanding your logic here. For `ht->buckets[i]`, the `key` member of all the nodes in the linked list shouldn't have the same key because they hold the values that collide with each other? – Pablo Jan 30 '18 at 21:05
  • @Pablo Collision is usually due to `Hash(key) == Hash(ht->buckets[i]->key)` and the later nodes of the linked list. As presented, OP's problem is how to remove a node from a linked list. The _hash_ part of this hash table code is missing. – chux - Reinstate Monica Jan 30 '18 at 21:18
  • @chux of course, for some reason I interpreted the `key` as already been hashed, that's why it didn't make sense to me. – Pablo Jan 30 '18 at 22:11

2 Answers2

4

How can I get the address of a pointer for my linked list such that I can properly set it in a hashtable after removing an item... ?

To remove a node from a linked list, keep track of the previous node.

for(i = 0; i < ht->size; i++){
  bucket_t before_head = { .next = ht->buckets[i] };  // Only next member used.
  bucket_t *previous = &before_head;
  while (previous->next && strcmp(previous->next->key,key) != 0) {
    previous = previous->next;
  }
  if (previous->next) { // match was found
    // delete previous->next and its members allocations
    bucket_t *node_after_match = previous->next->next;
    free(previous->next->key);
    free(previous->next->val);
    free(previous->next);
    // link previous to node after deletion.
    previous->next = node_after_match; 

    // assign a potential new head of the list
    ht->buckets[i] = before_head.next;
    break; // exit for loop  
  }
}

As hinted by @Pablo, I'd expect a hash function instead of a for() loop to rapidly find the hash table index. Something like:

// for(i = 0; i < ht->size; i++){
i = hash(key)%ht->size;
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
0
void  ht_del(hashtable_t *ht, char *key) {
    unsigned long i;
    i = hash(key)%ht->size;
    bucket_t before_head = { .next = ht->buckets[i]};
    bucket_t *previous = &before_head;
    while(previous->next && strcmp(previous->next->key,key)!=0) {
      previous = previous->next;
    }
    if(previous->next ) {
      bucket_t *next = previous->next->next;
      bucket_t *b = previous->next;
      free(previous->next->key);
      free(previous->next->val);
      previous->next = next;
      free(b);
      ht->buckets[i] = previous->next;
    }
}
Pablo
  • 13,271
  • 4
  • 39
  • 59
Lucas Trestka
  • 81
  • 8