marekweb / datastructs-c Goto Github PK

As arraylist_remove is written, it reads memory from one position where it might not be readable.

The code is:

void* value = l->body[index];
arraylist_memshift(l->body + index + 1, -1, l->size - index);
l->size--;
return value;

Let say I have this body: {0, 1, 2, 3, 4}, with size = capacity = 5.
if I do arraylist_remove(l, 2), it will try to do:
arraylist_memshift(l->body + 3, -1, 3)
That will try to copy body[3] into body[2], body[4] into body[3], and body[5] into body[4].
But we can't access body[5], because capacity < 6.
This might not throw an error, but it's not correct.

Also, it could just be me misunderstanding the code

If you remove an entry using hashtable_remove, you set its key = NULL. But if you then call hashtable_find_slot, and it linearly probes to the site of the deleted entry, seeing key = NULL will make the routine think this is the end of the linear probing chain, and the routine will falsely return the claim that the key was not found, instead of continuing to search past the removed entry.

A quick fix is to set a removed entry's key to some arbitrary value, say "XYZZY" or "\0", and to ban both NULL and "\0" from being permissible keys in the hashtable.