Well guys, this bug sucked. Let's play a game. Can you spot the error in the following code?
void vector_erase_index(struct vector_t* vector, intptr_t index)
{
intptr_t offset;
intptr_t total_size;
if(index >= vector->capacity)
return;
/* shift memory right after the specified element down by one element */
offset = vector->element_size * index; /* offset to the element being erased in bytes */
total_size = vector->element_size * vector->count; /* total current size in bytes */
memcpy(vector->data + offset, /* target is to overwrite the element specified by index */
vector->data + offset + vector->element_size, /* copy beginning from one element ahead of element to be erased */
total_size - offset - vector->element_size); /* copying number of elements after element to be erased */
--vector->count;
}
It removes an element from a contiguous section of memory by shifting all proceeding elements down by one. The following is a dump of the vector's content before, during, and after erasing the element. In this case element 1 is being erased. It can be observed that there are numerous duplicates after erasure.
allocating at 605180 size 18
location 605010, size 18
location 605030, size 58
location 605090, size 18
location 60d240, size 110
location 605100, size 18
location 60d360, size 120
location 6051b0, size 18
location 60d490, size f0
location 60d590, size 18
location 605120, size 50
====> adding to vector (11)
freeing at 605030
location 605010, size 18
location 605030, size 58 <---- index 1 being erased from vector
location 605090, size 18
location 60d240, size 110
location 605100, size 18
location 60d360, size 120
location 6051b0, size 18
location 60d490, size f0
location 60d590, size 18
location 605120, size 50
location 605180, size 18
====> removing from vector (10)
allocating at 605200 size 110
location 605010, size 18
location 605090, size 18
location 60d240, size 110
location 605100, size 18
location 60d360, size 120
location 605180, size 18 <---- what is this
location 605180, size 18 <---- what is that
location 605180, size 18 <---- what the
location 605180, size 18 <---- duplicates everywhere
location 605180, size 18 <---- nuuuuuu
Solution:
memcpy() is being used on two overlapping memory sections.
The result is that it is reading from the same place it is writing to,
causing undefined behaviour and corrupting the memory.
Solution is to use memmove() instead.
I like offending people. People who get offended should be offended. --
Linus Torvalds