Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
Hi guys,

I am implementing a singly linked list. The thing is whenever my str_temp goes above 12-15 elements, i get this error

malloc: *** error for object 0x1099008b8: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
Run Command: line 1: 7322 Abort trap: 6 ./"$2"

The error is happening in AppendNode method. Can you please tell me where I might be going wrong.
Code snippet is given below. Please let me know if you need more info.


Code:
class node{
    public:    
    int data;
    class node* next;
    
};

class IO{
    public:
    int numReq;
    class node *head;
    class node *tail;
    
    IO(int);
    void makeList(int*);
    void makeSorted(int*);    
    void printList();
    void SortedInsert(class node*&,int); 
    void InsertSort();
    void AppendNode(int);
       
};

void IO::makeList(int str_temp[]){
    int i;
    cout<<"NUMREQ "<<numReq<<endl;
    for (i=0;i<numReq;i++) {
    cout<<str_temp[i]<<endl;
        AppendNode(str_temp[i]);
    }
}


void IO::AppendNode(int num) {
   class node* current = head;
   class node* newNode;
   newNode = new node();
   newNode->data = num;
   newNode->next = NULL;

   // special case for length 0
   if (current == NULL) {
      head = newNode;
   }
   else {
      // Locate the last node
      while (current->next != NULL) {
         current = current->next;
      }
      current->next = newNode;
   }

}
 

jiminaus

macrumors 65816
Dec 16, 2010
1,449
1
Sydney
Assuming an IO constructor like:
Code:
IO::IO(int a)
: numReq(a), head(NULL), tail(NULL)
{
}

This code works for me. I can create list of any size. I've tried up to 10,000.

Anything beyond that is too slow because instead of maintaining and taking advantage of the tail member in AppendNode, you're walking through the list. So to add the 1,000,000th item, for example, your code needs to walk along the existing 999,999 items.


So the error is not were you think it is. How are you calling makeList?
 

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
I am using an app called code runner. I just press run in that to run the program.

----------

I tried using terminal just now. g++ filename. i still get the same error.

And yes, my constructor is the same as you have mentioned.
I am using this string - 89 92 201 128 10 1 2 3 4 5 6 6 7 7 23 and i get the error mentioned.

I am calling makelist like this -

Code:
int main(int argc, char *argv[]) {
int i;
FlagReader(argc,argv);
Init();
IO str(refStringLen);
str.makeList(refString);
str.printList();

//str.makeSorted(refString);
//str.printList();

return 0;    
}
 
Last edited:

jiminaus

macrumors 65816
Dec 16, 2010
1,449
1
Sydney
You passing a string containing the numbers separated by space?!

Your makeList member function is not expecting a string containing the numbers. It's expecting an array of integers. This is why your program is failing.

You need to get the numbers out of the string and convert them from text to integers.

For example, I called makeList with this code:
Code:
int main (int argc, const char * argv[])
{
    const int count = 10000;
    int *nums = new int[count];
    for (int i = 0; i < count; i++) {
        nums[i] = i;
    }
    
    IO io(count);    
    io.makeList(nums);
    
    delete[] nums;
    
    return 0;
}
 

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
I am tokenizing it and the reference string will have integers correctly.
Thats not the problem.

Code:
cout << "Please type the reference string and press Enter" <<endl; 
        getline(cin,str);

        temp= new char [str.size()+1];
        strcpy(temp,str.c_str());
        pch = strtok(temp," ");        
        refString =(int*)malloc(sizeof(str)*sizeof(int));
        
        while (pch != NULL)
        {
            refString[refStringLen]=atoi(pch);
            pch = strtok (NULL, " ");
            refStringLen++;
        }

The problem occurs whenever the control goes to AppendNode method, the line

class node* newNode;
newNode = new node();

Thats where the error occurs .
 

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
i tried using your main, and it works. But my main is not working/ I am clueless where i am going wrong.
 

chown33

Moderator
Staff member
Aug 9, 2009
10,706
8,346
A sea of green
I am tokenizing it and the reference string will have integers correctly.
Thats not the problem.

Code:
cout << "Please type the reference string and press Enter" <<endl; 
        getline(cin,str);

        temp= new char [str.size()+1];
        strcpy(temp,str.c_str());
        pch = strtok(temp," ");        
        refString =(int*)malloc(sizeof(str)*sizeof(int));
        
        while (pch != NULL)
        {
            refString[refStringLen]=atoi(pch);
            pch = strtok (NULL, " ");
            refStringLen++;
        }

The problem occurs whenever the control goes to AppendNode method, the line

class node* newNode;
newNode = new node();

Thats where the error occurs .
Post the complete code of your main(). You've only posted part of your code. We need to see it all. Pretend we want to compile and run it, just like you did with jiminaus's code.

For example, I'd like to know the starting value of refStringLen. If it's not 0, then think very carefully about what your while loop will do. Question to ask yourself: At what index are the first and second ints stored?

You should also think about what size you're passing to malloc(). Better still, think why you're using malloc() at all, if you could be using new int[someCount].
 
Last edited:

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
Here is all the code

Code:
#include<iostream>
#include<string>



using namespace std;

int numCylin=200;
char *inputFile;
int iFlag,FIFOFlag,SSTFFlag,CSCANFlag,LOOKFlag;
int *refString,refStringLen;


class node{
    public:    
    int data;
    class node* next;
    
};

class IO{
    public:
    int numReq;
    class node *head;
    class node *tail;
    
    IO(int);
    void makeList(int*);
    void makeSorted(int*);    
    void printList();
    void SortedInsert(class node*&,int); 
    void InsertSort();
    void AppendNode(int);
       
};

void IO::printList(){
    int i;
    class node *lnode=head;
    for (i=0;i<numReq;i++) {
        cout<<i<<" "<<lnode->data<<endl;
        lnode=lnode->next;
    }
}

void IO::makeList(int str_temp[]){
    int i;
    cout<<"NUMREQ "<<numReq<<endl;
    for (i=0;i<numReq;i++) {
    cout<<str_temp[i]<<endl;
        AppendNode(str_temp[i]);
    }
}


void IO::AppendNode(int num) {
    cout<<"-----"<<endl;
    node* current = head;
    cout<<"-----"<<endl;

    node* newNode = new node();
    cout<<"-----"<<endl;

   newNode->data = num;
   newNode->next = NULL;
    cout<<"-----"<<endl;
   // special case for length 0
   if (current == NULL) {
      head = newNode;
    cout<<"-----"<<endl;
   }
   else {
      // Locate the last node
      while (current->next != NULL) {
         current = current->next;
      }
      current->next = newNode;
   }

}

void IO::makeSorted(int *str_temp){
    int i;
    for (i=0;i<numReq;i++) {
        SortedInsert(head,str_temp[i]);
    }
}

void IO::SortedInsert(class node*& headRef,int num) {
    class node* newNode;
   newNode = new node();
   newNode->data = num;
   newNode->next = NULL;

   // Special case for the head end
   if (head == NULL || headRef->data >= newNode->data) {
      newNode->next = headRef;
      headRef = newNode;
   }
   else {
      // Locate the node before the point of insertion
      class node* current = headRef;
      while (current->next!=NULL && current->next->data<newNode->data) {
         current = current->next;
      }
      newNode->next = current->next;
      current->next = newNode;
   }
}


IO::IO(int num):numReq(num),head(NULL),tail(NULL){
    }

    
void PrintHelp(){
    cout << "-h                     : Print a usage summary with all options and exit." <<endl;
    exit(0);
}

void FlagReader(int argc, char** argv){
        int i;
        for(i=1;i<argc;i++){
            if(!strcmp(argv[i],"-h")){
                PrintHelp();
            }else
            if(!strcmp(argv[i],"-n")){
                i++;
                numCylin = atoi(argv[i]);
                continue;
            }else
            if(!strcmp(argv[i],"-d")){
                FIFOFlag=0;
                i++;
                if (!strcmp(argv[i],"SSTF")) {
                    SSTFFlag=1;    
                }
                if (!strcmp(argv[i],"FIFO")){
                    FIFOFlag=1;
                }
                if (!strcmp(argv[i],"C-SCAN")) {
                    CSCANFlag=1;    
                }
                if (!strcmp(argv[i],"LOOK")) {
                    LOOKFlag=1;    
                }
                continue;
            }else
            if(!strcmp(argv[i],"-i")){
                iFlag=1;
                i++;
                inputFile=(char*)malloc(sizeof(argv[i]));
                strcpy(inputFile,argv[i]);
                continue;
            }
                    }
                
}

int Init(){
    int i;
    
    if (iFlag==1) {
        
        FILE *file = NULL;
        unsigned long fileLen;
        char filenames[1000]="",f1[9000]="";
        file = fopen(inputFile,"rb");
        char *pch;
        int num=0;

        if(file==NULL){
            printf("cant open file\n");
            return 0;
        }
        //To find file length
        fseek(file, 0, SEEK_END);
        fileLen=ftell(file);
        fseek(file,0,SEEK_SET);
    
        //Read file contents into buffer
        fread(f1,fileLen, 1, file);
        fclose(file);
        
        refString =(int*)malloc(sizeof(f1));
        pch = strtok (f1," ");
        while (pch != NULL)
        {
            refString[refStringLen]=atoi(pch);
            pch = strtok (NULL, " ");
            refStringLen++;
        }
        
    }
    else
    {
        string str;
        char *temp;
        char *pch;
        cout << "Please type the reference string and press Enter" <<endl; 
        getline(cin,str);

        temp= new char [str.size()+1];
        strcpy(temp,str.c_str());
        pch = strtok(temp," ");        
        refString =(int*)malloc(sizeof(str)*sizeof(int));
        
        while (pch != NULL)
        {
            refString[refStringLen]=atoi(pch);
            pch = strtok (NULL, " ");
            refStringLen++;
        }
    }
}


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

FlagReader(argc,argv);
Init();

IO io(refStringLen);
io.makeList(refString);

io.printList();

//str.makeSorted(refString);
//str.printList();

//89 92 201 128 10 1 2 3 4 5 6 6 7 7 23
return 0;    
}
 

gnasher729

Suspended
Nov 25, 2005
17,980
5,565
What exactly does the sizeof operator return? For example, what is sizeof(argv) ? Hint: It's not what you think it is.

First rule of debugging: The bug is not where you think it is. So if you post the code where you think the bug is, you will not post the code containing the bug.
 

chown33

Moderator
Staff member
Aug 9, 2009
10,706
8,346
A sea of green
What have you done to test the components of this code?

Have you tested Init() and FlagReader() independently? Are you certain that they're known working? Building things from untested large components is risky.

What evidence do you have that they work? Evidence means things like debugger observation, log or console output, etc. If you haven't tested them, you need to break the problem down and do those tests. If you don't have evidence, you need to add printf's or cout's that produce such evidence.


What have you done to debug the components of this code?

Given that jiminaus's main() worked, and assuming you understand what his code does, what does that suggest about your non-working code?

To me, it suggests the real problem might not be where you think it is. Or it might not be what you think it is. For example, a bad value of refStringLen.


I guarantee that you have some serious buffer overflow bugs. Like this:
Code:
        //Read file contents into buffer
        fread(f1,fileLen, 1, file);
f1 is a local 9000-char buffer. fileLen can be anything. You haven't limited fileLen in any way, so if it's larger than 9000, you just overflowed a stack-resident buffer. Boom.
 
Last edited:

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
@chown33-
Before posting the code I have printed to find till where the code works .
I have printed the contents of RefStringLen and the refString just before it enters AppendNode(). The contents of refString is coming correctly.
I have tried printing the contents of str_temp too.It comes correctly.

Yea,error is happening in refString. i dont know how though.
I tried giviing this and it works

Code:
int refString[]={89,92,201,128,10,1,2,3,4,5,6,6,7,7,23};
int refStringLen = 15;

IO io(refStringLen);
io.makeList(refString);

io.printList();

What might be happening? When i print the contents of refString it comes correctly. 9000 is more than enough for f1.

@gnasher729
Ok will give it a look. But currently i am not facing any music from that end. But will give it a look and correct it.
 

gnasher729

Suspended
Nov 25, 2005
17,980
5,565
Yea,error is happening in refString. i dont know how though.

I told you how. If the user uses the -i option, then you ********* up the memory much much much much earlier. Remember the golden rule: The bug is not where you think it is.
 

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
I told you how. If the user uses the -i option, then you ********* up the memory much much much much earlier. Remember the golden rule: The bug is not where you think it is.

lets consider that i am not using -i flag. Still the error occurs. I will correct it though.
 

chown33

Moderator
Staff member
Aug 9, 2009
10,706
8,346
A sea of green
@chown33-
Before posting the code I have printed to find till where the code works .
I have printed the contents of RefStringLen and the refString just before it enters AppendNode(). The contents of refString is coming correctly.
I have tried printing the contents of str_temp too.It comes correctly.
Then post your log. We'd like to see your evidence. Frankly, I'd also like to see the code with the extra logging in it. Because that way we know where the evidence comes from. Because if you log the wrong thing, the logged data isn't worthwhile.


Consider this code:
Code:
        cout << "Please type the reference string and press Enter" <<endl; 
        getline(cin,str);

[COLOR="Red"]        fprintf( stderr, "str size: %d, sizeof: %d\n", str.size(), sizeof(str) );
[/COLOR]
        temp= new char [str.size()+1];
        strcpy(temp,str.c_str());
        pch = strtok(temp," ");        
[COLOR="Blue"]        refString =(int*)malloc(sizeof(str)*sizeof(int));
[/COLOR]
I added the one line in red.

Run it, enter this text:
Code:
12 34 56 78 90 11
Output from the newly added fprintf() is:
Code:
str size: 17, sizeof: 8
(You'll see a sizeof of 8 if you're running 64-bit code, 4 if running 32-bit code.)

Try running it again and typing in your input that causes a failure.

What does this say about the other uses of sizeof in your code? For example, the sizeof(str) in your call to malloc() as hilited in blue above?
 

RouterGuy

macrumors newbie
Jan 9, 2011
6
1
Why are you using malloc, this isn't C. Use a vector and the methods it provides to dynamically grow the array instead of tinkering around with memory allocation on your own would be my suggestion.
 

gnasher729

Suspended
Nov 25, 2005
17,980
5,565
lets consider that i am not using -i flag. Still the error occurs. I will correct it though.

In that case you run into exactly the same bug:

Code:
        string str;
        refString =(int*)malloc(sizeof(str)*sizeof(int));

Wouldn't it be common sense that after identifying one horrible bug you would check whether the same blunder has happened in another place?
 

neowin

macrumors newbie
Original poster
Jun 27, 2011
19
0
I got what was going wrong :D.
I was not allocating sufficient memory space in refString malloc.
I increased the memory and it works!

Any suggestion on how to calculate the exact number of integers to be allocate when read from the stdin?

Thanks for all your answers @chown33 , @gnasher729 and @jiminaus

Happy holidays!
 

chown33

Moderator
Staff member
Aug 9, 2009
10,706
8,346
A sea of green
Any suggestion on how to calculate the exact number of integers to be allocate when read from the stdin?

Think through what you're asking.

Your question is basically one of the following:
  1. How can I predict, with perfect accuracy, the number of integers that a user hasn't typed in yet?
  2. How can I accurately predict, without parsing or otherwise looking at the string typed in, exactly how many integers the string will be parsed into?

This question seems silly, because the code implements a linked list. One property of a linked list is that it's of arbitrary length (any number of nodes). Another property is that it can easily be grown or shrunk by adding or deleting nodes. So in a practical sense, one easy way to parse input of unpredictable length is to use a linked list in the proper way. That would be:
1. Read a number.
2. Create a node containing the number.
3. Add node to linked list.
4. Repeat until input is consumed.

If step 3 adds nodes at the head, then the list is in LIFO order. If it adds at the tail, it's in FIFO order. In any case, walk the list counting nodes. Make an array of that length. Remove node from list, storing number in array. Repeat until list is empty.

Or you could not use an array at all, and simply parse the numbers, appending to the linked list using, for example, IO::AppendNode(num).
 
Last edited:
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.