malloc to allocate memory for a List

Question

I have a custom struct

typedef struct node
{

   struct node *next;
   int vertex;
}node;

typedef struct {

    int numberOfNodes;  
    int *visited; 
    int numberOfEdges ;

    node **ppLists;
} adjacencyList;

I am trying to allocate memory for a adjacency list with the following code with numberOfNodes as 1000.

adjacencyList *createAdjList(int numberOfNodes)
{
    int i;
    adjacencyList *newList;

    //Allocate memory for list and the array of nodes

    newList=(adjacencyList *)malloc(sizeof(adjacencyList));
    newList->numberOfNodes=numberOfNodes;
    newList->ppLists=(node**)malloc(numberOfNodes*sizeof(node));


    for (i = 0; i < newList->numberOfNodes; i++) {
      newList->ppLists[i] = (node*)malloc(sizeof(node)*newList->numberOfNodes);
    }

    return newList;
}

The code complies successfully, however i get a segmentation fault during run time. I used the gdb and this is the back trace.

#0  0x00007ffff7a51425 in __GI_raise (sig=<optimized out>) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1  0x00007ffff7a54b8b in __GI_abort () at abort.c:91
#2  0x00007ffff7a9915d in __malloc_assert (assertion=<optimized out>, file=<optimized out>, line=<optimized out>, function=<optimized out>) at malloc.c:300
#3  0x00007ffff7a9c674 in sYSMALLOc (av=0x7ffff7dd3720, nb=16016) at malloc.c:2448
#4  _int_malloc (av=0x7ffff7dd3720, bytes=16000) at malloc.c:3903
#5  0x00007ffff7a9dfc5 in __GI___libc_malloc (bytes=16000) at malloc.c:2924
#6  0x0000000000401c08 in createAdjList (numberOfNodes=1000) at /home/merlyn/projects/soft/AdjacencyList.c:25
#7  0x0000000000401155 in createAdjListFromMatrix (pAdjMatrix=0x605010) at /home/merlyn/projects/soft/tools.c:86
#8  0x0000000000401017 in main (argc=2, argv=0x7fffffffdf18) at /home/merlyn/projects/soft/main.c:22

valgrind

==6328== Memcheck, a memory error detector
==6328== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==6328== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==6328== Command: ./exercise
==6328== 
==6328== Invalid write of size 4
==6328==    at 0x4E8892D: _IO_vfscanf (vfscanf.c:1857)
==6328==    by 0x4E903EA: __isoc99_fscanf (isoc99_fscanf.c:35)
==6328==    by 0x401A15: readAdjMatrixFromFile (AdjacencyMatrix.c:138)
==6328==    by 0x400FF5: main (main.c:14)
==6328==  Address 0x51f3675 is 997 bytes inside a block of size 1,000 alloc'd
==6328==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6328==    by 0x4019AA: readAdjMatrixFromFile (AdjacencyMatrix.c:126)
==6328==    by 0x400FF5: main (main.c:14)
==6328== 
1000 
==6328== Conditional jump or move depends on uninitialised value(s)
==6328==    at 0x401D68: addEdgeToAdjList (AdjacencyList.c:75)
==6328==    by 0x4011A5: createAdjListFromMatrix (tools.c:77)
==6328==    by 0x401016: main (main.c:22)
==6328== 
==6328== 
==6328== HEAP SUMMARY:
==6328==     in use at exit: 17,098,448 bytes in 7,154 blocks
==6328==   total heap usage: 7,156 allocs, 2 frees, 17,099,584 bytes allocated
==6328== 
==6328== LEAK SUMMARY:
==6328==    definitely lost: 48 bytes in 2 blocks
==6328==    indirectly lost: 17,098,400 bytes in 7,152 blocks
==6328==      possibly lost: 0 bytes in 0 blocks
==6328==    still reachable: 0 bytes in 0 blocks
==6328==         suppressed: 0 bytes in 0 blocks
==6328== Rerun with --leak-check=full to see details of leaked memory
==6328== 
==6328== For counts of detected and suppressed errors, rerun with: -v
==6328== Use --track-origins=yes to see where uninitialised values come from
==6328== ERROR SUMMARY: 3994 errors from 2 contexts (suppressed: 2 from 2

main .c

#include "AdjacencyList.h"
#include "AdjacencyMatrix.h"
#include "tools.h"

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


int main(int argc, char* argv[])
{

    // load the matrix 

    adjacencyMatrix *newAdjMatrix=readAdjMatrixFromFile(argv[1]) ;

    // A test to check if the matrix has actually been loaded

    writeAdjMatrixToFile(newAdjMatrix, "123.txt");

    // covert matrix to list

    adjacencyList *newAdjList = createAdjListFromMatrix(newAdjMatrix);

    // perform reachablity for matrix

    //checkReachabilityMatrix(newAdjMatrix,0) ;

    // perform reachability for list

   return 0;
}

adjacencyMatrix *readAdjMatrixFromFile(char *pFilename)
{

    adjacencyMatrix *newAdjMatrix;
    newAdjMatrix = (adjacencyMatrix *) malloc(sizeof(adjacencyMatrix));
    FILE *pFile;
    pFile = fopen("/home/merlyn/projects/soft/Graph.txt", "r");
    char ch;

    if(pFile==NULL)
    {
        printf("Cannot open File");

    }
    //First Character will have number of nodes
    int i,j;
    //fgetc(
    fscanf(pFile, "%d",&i);

    //newAdjMatrix->numberOfNodes=((int)fgetc(pFile));

    newAdjMatrix->numberOfNodes = i;
    newAdjMatrix->ppMatrix = (bool**) malloc(sizeof(bool*)*newAdjMatrix->numberOfNodes);

    int idx;
    for (idx = 0; idx < newAdjMatrix->numberOfNodes; idx++) 
        newAdjMatrix->ppMatrix[idx] = (bool*) malloc(sizeof(bool)*newAdjMatrix->numberOfNodes);

    i=0;//rows
    j=0;//columns
    //iterate over entire file
    for(i=0;i<newAdjMatrix->numberOfNodes;i++)
    {
      for(j=0;j<newAdjMatrix->numberOfNodes;j++)

        //keep adding elements to the column for ith row
          fscanf(pFile, "%d",&newAdjMatrix->ppMatrix[i][j]);

    }

    fclose(pFile);
    return newAdjMatrix;
}

typedef struct
{

    int numberOfNodes;

    bool **ppMatrix;
} adjacencyMatrix;

tools.c

adjacencyList *createAdjListFromMatrix(adjacencyMatrix *pAdjMatrix)
{
    //create a adjacencyList with the same number of nodes as adjacencyMatrix

    adjacencyList *pNewadjacencyList=createAdjList(pAdjMatrix->numberOfNodes);

    // now we move from row to row and create a list for every 1
    int i,j;

    for( i=0;i<pAdjMatrix->numberOfNodes;i++)
    {
        for( j=0;j<pAdjMatrix->numberOfNodes;j++)
        {
            //If an edge is found then create a node
            if(pAdjMatrix->ppMatrix[i][j]==1)
            {
                addEdgeToAdjList(pNewadjacencyList, i, j);

            }

        }
    }
    return pNewadjacencyList;
}

Not the problem, but [do **not** cast the return value of `malloc()`.](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858#605858) — , Jul 06 '13 at 12:27
but what about custom types ? does it still hold. and the other thing is i used malloc to create a adjmatrix for which it worked — Whereismywall, Jul 06 '13 at 12:43

Th30n · Answer 1 · 2013-07-06T12:43:19.477

This line here:

newList->ppLists=(node**)malloc(numberOfNodes*sizeof(node));

Should be changed to:

newList->ppLists = malloc(numberOfNodes*sizeof(node*));

The reason is, you have an array of pointers to node. So the real type of this array is a pointer to node (node*). That is the type for which you want to allocate memory. After the malloc has allocated memory it will return a pointer to that type, so you will get a pointer to pointer = node**

In C you don't have to cast void * returned by malloc unlike c++

Nobilis · Answer 2 · 2013-07-06T12:54:08.770

0

Here:

newList->ppLists=(node**)malloc(numberOfNodes*sizeof(node));

You are asking malloc to return a pointer to some nodes. But since you have a declaration that is of pointer to pointer for ppLists you want malloc in the following way (taking into account H2CO3's recommendation not to cast the result):

newList->ppLists = malloc(numberOfNodes * sizeof *newList->ppLists);

This is asking malloc to give you back an array of pointers to structs of type node rather than an array of said structs.

edited Jul 06 '13 at 12:54

answered Jul 06 '13 at 12:34

Nobilis

7,310
1
33
67

1

Alternately, you can use `newList->ppLists = malloc( numberOfNodes * sizeof *newList->ppLists );` - since the type of `newList->ppLists` is `node **`, the expression `*newList->ppLists` has type `node *`, which is the type you want. I prefer this method since it means I don't have to worry about keeping the type synced with the expression. – John Bode Jul 06 '13 at 12:49
@Whereismywall Do you have access to `valgrind`, have you tried running your app with it? From the code you've posted this as far as I can infer. – Nobilis Jul 06 '13 at 12:50
@JohnBode Thanks for the suggestion! I agree it does read better, I'll edit my posting to reflect it. – Nobilis Jul 06 '13 at 12:54
@Whereismywall can you post the code lines and methods referred to in `valgrind`'s report? It makes reference to some lines in `main` and `tools`. Perhaps it might be too much code but do please try to provide as much as it's relevant. – Nobilis Jul 06 '13 at 12:56
@Whereismywall I cannot spot some obvious ones but is it possible that the `fscanf` calls fail to read the file properly and then write to the variables supplied? Problems of this sort are mentioned in the `valgrind` report. And you don't seem to be doing anything with `pFilename`. Finally, if you compile with the `-Wall` and `-Wextra` flags are you able to get something obvious and useful? – Nobilis Jul 06 '13 at 13:18
I know this is a bit trouble some. 1 i dont thing there is a problem with the reading matrix from file, as i write this matrix after reading it to check if everything is ok . 2 when i run debugger with kdevelop i can see all the specified fields(while debugger is running ) 3 i am using the new haswell cpu, could this be the problem? – Whereismywall Jul 06 '13 at 13:29
@Whereismywall I think you got me there :) But anyway as a final suggestion try setting up some break points right after you read from a file or allocate memory and see if the calls have been successful and the variables initialised. – Nobilis Jul 06 '13 at 13:39

malloc to allocate memory for a List

2 Answers2