Cant determine correct algorithm to allocate memory

Question

I have this code where i am programming a dynamic array in C. So basically the major problem here is that lets say you add the value 1 to the array and then later you decide to add the value 5. Well in my case, when you try to print the index 0 which is suppose to be 1, it gives me a seg fault. But when you print the index 1, it gives me 5, which is correct value. It for some reason forgets all of the previous added values execept the one current. I have done a valgrind check, and i will show results after i show the files:

Vertex.h:

#ifndef _VERTEX_AM_H_LB
#define _VERTEX_AM_H_LB 1
#pragma once
#include<stdint.h>
/**
 * Vertex Library C
 *
 * GCC C99 <Vertex.h>
 *
 * @author Amanuel Bogale
 * @copyright 2016 Amanuel Bogale
 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
 *
 */

//@union for storing
//data types supported
//for vertex
typedef union
    {
        char ch; //1 byte
        unsigned char uch;//1 byte
        signed char sch;// 1 byte
        int in;//2 or 4bytes
        unsigned int uin;//2 or 4bytes
        long ln;// 4byte
        unsigned long uln; //4byte
        long long lnln; //8byte
        short sh;// 2byte
        unsigned short ush; //2bytes
        float fl;//4byte
        double db; //8byte
        long double ldb; //10byte
}type;

/*
 * @struct for defining
 * vertex. Initalize First
 */
struct vertex_am
{
    size_t current_size;
    type type;
    long long size_contents;
    void **contents; //Array Of Void Pointers
    //Add to the end of array
    void (*add)(struct vertex_am *self,void*val);
};

typedef struct vertex_am vertex_am;



vertex_am* init_vertex(size_t size, vertex_am* vertex);
void end_vertex(vertex_am* vertex);
long long get_elements_num(vertex_am vert);
void add_end(vertex_am *vert, void* val);
void* get_val(vertex_am vert,long long index);
int get_first_index(vertex_am vert, void*key);
int get_last_index(vertex_am vert, void*key);
#endif

Vertex.c:

#include<stdlib.h>
#include<stdio.h>
#include<stdint.h>
#include "../includes/Vertex.h"

/**
 * Vertex Library C
 *
 * GCC C99 <Vertex.c>
 *
 * @author Amanuel Bogale
 * @copyright 2016 Amanuel Bogale
 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
 *
 */

vertex_am* init_vertex(size_t size, vertex_am* vertex)
{
    vertex = malloc(size);
    vertex->current_size = size;
    vertex->size_contents = 0;
    return vertex;
}

long long get_elements_num(vertex_am vert)
{
    return(vert.size_contents);
}

void add_end(vertex_am *vert, void* val)
{
    vert->contents = (void **)malloc(sizeof(vert->contents) + (sizeof(val)) );
//  vert->contents = (void **)malloc(sizeof(void)*(vert->size_contents+1));
    vert->contents[vert->size_contents] = val;
    vert->size_contents++;
}

void* get_val(vertex_am vert,long long index)
{
    return (vert.contents[index]);
}

int get_first_index(vertex_am vert, void*key)
{
    int returner;
    for(int i=0; i<=(vert.size_contents); i++)
    {
        if(vert.contents[i] == key)
        {
            returner=i;
            break;
        }
    }
    return (returner);
}

int get_last_index(vertex_am vert, void*key)
{
    int returner;
    for(int i=0; i<=(vert.size_contents); i++)
        {
            if(vert.contents[i] == key)
            {
                returner=i;
            }
        }
    return (returner);
}


void end_vertex(vertex_am* vertex)
{
    free(vertex);
}

main.c:

#include<stdlib.h>
#include<stdio.h>
#include<stdint.h>
#include "includes/Vertex.h"

int main()
{
    int n = 34;
    int x = 33;
    int y = 44;
    vertex_am *vert = NULL;


    vert = init_vertex(sizeof(*vert), vert);
    add_end(vert,&n);
    add_end(vert,&x);
    add_end(vert,&y);


//  int *anwser = (int*) get_val(*vert, 2);
//  printf("Val : %d \n",*anwser);

    int *check = (int*)vert->contents[2];
    printf("%d" , *check);


    int first_index_anwser = get_first_index(*vert,&n);// &n same as 34. So find first 34 in dyn_array
    printf("First Index : %d \n",first_index_anwser);

    int last_index_anwser = get_last_index(*vert,&n);// &n same as 34. So find Last 34 dyn_array
    printf("Last Index : %d \n",last_index_anwser);

    end_vertex(vert);
    return 0;
}


/*
 * TODO POP:
 * pop_beg
 * pop_last
 * pop_index
 *
 * TODO add:
 * add_beg
 * add_index
 *
 * TODO index:
 * by_index instead of first last
 */

The problem here as you can see here i am printing the current index in main.c:

int *check = (int*)vert->contents[2];
        printf("%d" , *check);

Because there are three added items as you can see in main.c... and second index is latest. well if i try to print index 1 or 0, it will give a segmentation fault, for some reason... And like i said i have done a valgrind check for this and i got this:

==37900== Memcheck, a memory error detector
==37900== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==37900== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==37900== Command: ./main
==37900== 
==37900== Invalid write of size 8
==37900==    at 0x4008A1: add_end (Vertex.c:34)
==37900==    by 0x400747: main (main.c:17)
==37900==  Address 0x5420170 is 0 bytes after a block of size 16 alloc'd
==37900==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==37900==    by 0x40087A: add_end (Vertex.c:32)
==37900==    by 0x400747: main (main.c:17)
==37900== 
==37900== Invalid read of size 8
==37900==    at 0x400750: main (main.c:23)
==37900==  Address 0x5420170 is 0 bytes after a block of size 16 alloc'd
==37900==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==37900==    by 0x40087A: add_end (Vertex.c:32)
==37900==    by 0x400747: main (main.c:17)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x400900: get_first_index (Vertex.c:48)
==37900==    by 0x400795: main (main.c:27)
==37900== 
==37900== Invalid read of size 8
==37900==    at 0x4008F9: get_first_index (Vertex.c:48)
==37900==    by 0x400795: main (main.c:27)
==37900==  Address 0x5420170 is 0 bytes after a block of size 16 alloc'd
==37900==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==37900==    by 0x40087A: add_end (Vertex.c:32)
==37900==    by 0x400747: main (main.c:17)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4B43: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
==37900== Use of uninitialised value of size 8
==37900==    at 0x50A172B: _itoa_word (_itoa.c:179)
==37900==    by 0x50A50EC: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A1735: _itoa_word (_itoa.c:179)
==37900==    by 0x50A50EC: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A516F: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4C19: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A53DA: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4C6B: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4CA2: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007B0: main (main.c:28)
==37900== 
44First Index : 44 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x40094B: get_last_index (Vertex.c:62)
==37900==    by 0x4007D7: main (main.c:30)
==37900== 
==37900== Invalid read of size 8
==37900==    at 0x400944: get_last_index (Vertex.c:62)
==37900==    by 0x4007D7: main (main.c:30)
==37900==  Address 0x5420170 is 0 bytes after a block of size 16 alloc'd
==37900==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==37900==    by 0x40087A: add_end (Vertex.c:32)
==37900==    by 0x400747: main (main.c:17)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4B43: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
==37900== Use of uninitialised value of size 8
==37900==    at 0x50A172B: _itoa_word (_itoa.c:179)
==37900==    by 0x50A50EC: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A1735: _itoa_word (_itoa.c:179)
==37900==    by 0x50A50EC: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A516F: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4C19: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A53DA: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4C6B: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
==37900== Conditional jump or move depends on uninitialised value(s)
==37900==    at 0x50A4CA2: vfprintf (vfprintf.c:1631)
==37900==    by 0x50AC848: printf (printf.c:33)
==37900==    by 0x4007F2: main (main.c:31)
==37900== 
Last Index : 44 
==37900== 
==37900== HEAP SUMMARY:
==37900==     in use at exit: 48 bytes in 3 blocks
==37900==   total heap usage: 5 allocs, 2 frees, 1,136 bytes allocated
==37900== 
==37900== LEAK SUMMARY:
==37900==    definitely lost: 48 bytes in 3 blocks
==37900==    indirectly lost: 0 bytes in 0 blocks
==37900==      possibly lost: 0 bytes in 0 blocks
==37900==    still reachable: 0 bytes in 0 blocks
==37900==         suppressed: 0 bytes in 0 blocks
==37900== Rerun with --leak-check=full to see details of leaked memory
==37900== 
==37900== For counts of detected and suppressed errors, rerun with: -v
==37900== Use --track-origins=yes to see where uninitialised values come from
==37900== ERROR SUMMARY: 30 errors from 22 contexts (suppressed: 0 from 0)
amanuel@ubuntu:~/Code/E-Workspace/CustLibs$

Many invalid writes targeting the add function in Vertex.c:

void add_end(vertex_am *vert, void* val)
{
    vert->contents = (void **)malloc(sizeof(vert->contents) + (sizeof(val)) );
//  vert->contents = (void **)malloc(sizeof(void)*(vert->size_contents+1));
    vert->contents[vert->size_contents] = val;
    vert->size_contents++;
}

. This is as much info about this problem i have now, any help as usual would be greatly appreciated.

You probably want to `realloc`() `vert->contents` with `vert->size_contents + 1` size before the assignment `vert->contents[vert->size_contents] = val`. — pah, Jul 05 '16 at 00:35

Some programmer dude · Accepted Answer · 2016-07-05T00:53:30.303

3

The expression sizeof(vert->contents) + (sizeof(val)) that you use in your call to malloc will not work as you expect it to. It will allocate space for two pointers, and that's it. No matter how many entries you want to allocate memory for, you will only get 8 or 16 bytes (depending on if you're on a 32 or 64 bit platform).

My guess is that you should allocate sizeof(*vert->contents) * (vert->size_contents+1) bytes.

There's also another problem: Each time you call add_end you will allocate a new chunk of memory, completely disregarding the old memory, and will with that have a memory leak, as well as a lot of uninitialized memory after you make the change above.

If you want to reallocate memory you should be using realloc instead. You can even use it for your initial allocation if you properly initialize the pointer to NULL.

So the code should instead be something like

void **temp = realloc(vert->contents, sizeof(*vert->contents) * (vert->size_contents+1));
if (temp == NULL)
{
    // TODO: Handle error
}
else
{
    vert->contents = temp;
    // Rest of your code...
}

It's important that vert->contents is initialized to NULL before the first call to realloc, or you will have undefined behavior.

edited Jul 05 '16 at 00:53

answered Jul 05 '16 at 00:32

Some programmer dude

400,186
35
402
621

1

@Dsafds No I don't, the asterisk (the "star") should be there. It will give the same result as `sizeof(void*)` (note the asterisk there too) but is safer if you ever change the type of `vert->contents`. – Some programmer dude Jul 05 '16 at 00:40
After changing it to `vert->contents = (void **)realloc(vert,sizeof(*vert->contents) * (vert->size_contents+1));` like you sugessted. I got a lot less errors in valgrind (11) . But now a seg fault appears even to the latest index .(Didnt mean to delete commet sorry.. Didnt see you responding) . My code basically is same as before except that change i listed above, you sugested – amanuel2 Jul 05 '16 at 00:43
1

@Dsafds *Almost* right, but the pointer you're (re)allocating is `vert->contents`, not `vert`. And remember that `vert->contents` **must** be a null pointer for the first call. Also, don't reassign back to the pointer you are reallocating, what if `realloc` returns `NULL`? You then will lose the original pointer and have a memory leak. – Some programmer dude Jul 05 '16 at 00:45
Thanks a lot Joachim!!!(sorry for the wait, had to get something to eat) Just one question, that is not really related to the orrignal(sorry). you can see that whenever i have to call the function add_end() to add at the end.. But is there a way so i can call it by the instance of the struct? like do, vertex_am vert; .. and then later vert.add_end() ? – amanuel2 Jul 05 '16 at 00:55
@Dsafds If you add a member to the structure that is a pointer to a function, and initialize it to make it point to the real `add_end` function, then yes it's possible, but not otherwise. Maybe you want to [look into C++](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list)? – Some programmer dude Jul 05 '16 at 00:57
Hmm..... ahh i wish i can do C++ Joachim, but C++ Is risky for making kernels and OS. So i guess i will have to live with this :( . Question regarding your edit there, your saying if temp == NULL make a error statement? At the beggining its set to NULL, so it will have an error call when i start add_end? or am i suppose to check if it is NULL, and if it is use malloc, and if it isnt use realloc? – amanuel2 Jul 05 '16 at 01:02
@Dsafds The check is to make sure that `realloc` doesn't fail. The `realloc` function will return `NULL` if it fails, not otherwise. – Some programmer dude Jul 05 '16 at 01:06
Ok Valgrind has one more error, um that is i lost 24 bytes(because i have 3 allocated array ), and its pointing me to this line(btw i understood what you meant above comment and changed code to your way): `vert->contents = (void **)realloc(vert->contents,sizeof(*vert->contents) * (vert->size_contents+1));` – amanuel2 Jul 05 '16 at 01:17

Cant determine correct algorithm to allocate memory

1 Answers1