9

I am C novice but been a programmer for some years, so I am trying to learn C by following along Stanford's course from 2008 and doing Assignment 3 on Vectors in C.

It's just a generic array basically, so the data is held inside a struct as a void *. The compiler flag -Wpointer-arith is turned on so I can't do arithmetic (and I understand the reasons why).

The struct around the data must not know what type the data is, so that it is generic for the caller.

To simplify things I am trying out the following code:

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

typedef struct {
    void *data;
    int aindex;
    int elemSize;
} trial;

void init(trial *vector, int elemSize)
{
    vector->aindex = 0;
    vector->elemSize = elemSize;
    vector->data = malloc(10 * elemSize);
}

void add(trial *vector, const void *elemAddr)
{
    if (vector->aindex != 0)
        vector->data = (char *)vector->data + vector->elemSize;

    vector->aindex++;
    memcpy(vector->data, elemAddr, sizeof(int));

}

int main()
{
    trial vector;
    init(&vector, sizeof(int));

    for (int i = 0; i < 8; i++)
        {add(&vector, &i);}

    vector.data = (char *)vector.data - ( 5 * vector.elemSize);
    printf("%d\n", *(int *)vector.data);
    printf("%s\n", "done..");

    free(vector.data);
    return 0;
}

However I get an error at free with free(): invalid pointer. So I ran valgrind on it and received the following:

==21006==  Address 0x51f0048 is 8 bytes inside a block of size 40 alloc'd
==21006==    at 0x4C2CEDF: malloc (vg_replace_malloc.c:299)
==21006==    by 0x1087AA: init (pointer_arithm.c:13)
==21006==    by 0x108826: main (pointer_arithm.c:29)

At this point my guess is I am either not doing the char* correctly, or maybe using memcpy incorrectly

Sam Hammamy
  • 10,819
  • 10
  • 56
  • 94
  • 2
    `vector->data = (char *)vector->data + sizeof(int);` changes the pointer, so when you go to `free` it, you are using the wrong address. – 001 May 23 '18 at 13:50
  • I thought this cast would be temporary? – Sam Hammamy May 23 '18 at 13:51
  • 4
    Johnny Mopp has nothing to do with the cast. The problem is that you are reassigning the pointer. It no longer points at the memory allocated with `malloc()`. – Code-Apprentice May 23 '18 at 13:58
  • Just noticed: `vector.data = (char *)vector.data - ( 5 * vector.elemSize);` looks like you try to reset it back to the original value before the `free()` but you use `5` instead of `8`. – 001 May 23 '18 at 14:00
  • 1
    I suggest that you read https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ for some tips to debug your code. Pointers are a little bit more complex to debug but the concepts from Eric Lippert's blog can be modified to debug these kinds of programs. – Code-Apprentice May 23 '18 at 14:05

3 Answers3

10

This happens because you add eight elements to the vector, and then "roll back" the pointer by only five steps before attempting a free. You can easily fix that by using vector->aindex to decide by how much the index is to be unrolled.

The root cause of the problem, however, is that you modify vector->data. You should avoid modifying it in the first place, relying on a temporary pointer inside of your add function instead:

void add(trial *vector, const void *elemAddr, size_t sz) {
    char *base = vector->data;
    memcpy(base + vector->aindex*sz, elemAddr, sz);
    vector->aindex++;
}

Note the use of sz, you need to pass sizeof(int) to it.

Another problem in your code is when you print by casting vector.data to int*. This would probably work, but a better approach would be to write a similar read function to extract the data.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Thanks @dasblinklight that's what I needed to understand! I also changed my print call to `printf("%d\n", *(int *)vector.data + 5);` – Sam Hammamy May 23 '18 at 14:07
4

Your code is somewhat confusing, there's probably a mis-understanding or two hiding in there.

A few observations:

  1. You can't change a pointer returned by malloc() and then pass the new value to free(). Every value passed to free() must be the exact same value returned by one of the allocation functions.
  2. As you've guessed, the copying is best done by memcpy() and you have to cast to char * for the arithmetic.

The function to append a value could be:

void add(trial *vector, const void *element)
{
  memcpy((char *) vector->data + vector->aindex * vector->elemSize, element);
  ++vector->aindex;
}

Of course this doesn't handle overflowing the vector, since the length is not stored (I didn't want to assume it was hard-coded at 10).

Changing the data value in vector for each object is very odd, and makes things more confusing. Just add the required offset when you need to access the element, that's super-cheap and very straight forward.

unwind
  • 391,730
  • 64
  • 469
  • 606
4

If you don't know the array's data type beforehand, you must assume a certain amount of memory when you first initialize it, for example, 32 bytes or 100 bytes. Then if you run out of memory, you can expand using realloc and copying over your previous data to the new slot. The C++ vector IIRC follows either a x2 or x2.2 ratio to reallocate, not sure.

Next up is your free. There's a big thing you must know here. What if the user were to send you a memory allocated object of their own? For example a char* that they allocated previously? If you simply delete the data member of your vector, that won't be enough. You need to ask for a function pointer in case the data type is something that requires special attention as your input to add.

Lastly you are doing a big mistake at this line here:

if (vector->aindex != 0)
    vector->data = (char *)vector->data + vector->elemSize;

You are modifiyng your pointer address!!! Your initial address is lost here! You must never do this. Use a temporary char* to hold your initial data address and manipulate it instead.

SenselessCoder
  • 1,139
  • 12
  • 27