LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 11-12-2022, 09:51 AM   #1
AlinaC
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Rep: Reputation: 0
C program: memory leak/ segmentation fault/ memory limit exceeded


Hi all,

thank you for all constructive feedback.

Sorry about "annoying" thing. Haven't remarked it was still there before posting. This was a joke from the university, as our professor told us we could write both input[n]=x or n[input]=x but the latter was annoying .

I have replaced "realloc" with "malloc", so this piece works (I hope).

But now I see the other line where error appears and it looks like the real issue.
[CODE]long int * frequency = (long int*) malloc(2 * MAX * MAX * sizeof(long int));[CODE]

This is the part where I need to go through my array (where I've saved sums of all pairs on the previous step) and find which numbers/sums are repeating and how many times. I've done it easy but ineffectively and need to change.
As of now, I check an array item, and if it contains the number X, I add +1 to the item X in a frequency array, eg frequency[x]+=1.

I've read some articles on Internet and it looks like dictionary can be a better structure to use for this purpose. (I need to check every item in an array and create a list of unique numbers/sums that are present in this array; each number/sum to be associated with the frequency).

Do you think dictionary will be a good choice for that? I basically need to store pairs int->int, specifically sum(a number stored in an array item) -> frequency (how many times this sum was contained in different array items).

Thanks
Alina

------the task ----------------
The problem is to develop a program to analyze input sequence.

Assume a sequence of numbers. We may choose a contiguous range from the input sequence, for instance, we may choose the range between the 5-th number and the 10-th number. A range must contain at least two numbers. The sum of the numbers may be computed for such range. We choose all possible ranges from the input sequence and we compute the sum for each of them. We are interested how many different ranges exist in the input sequence such that these ranges have the same sum.

For instance, the input sequence may be:
1 5 2 4 2 2 2
there is a total of 21 contiguous ranges of length ≥ 2, in particular:
0..1: 1 5 sum=6
0..2: 1 5 2 sum=8
0..3: 1 5 2 4 sum=12
0..4: 1 5 2 4 2 sum=14
0..5: 1 5 2 4 2 2 sum=16
0..6: 1 5 2 4 2 2 2 sum=18
1..2: 5 2 sum=7
1..3: 5 2 4 sum=11
1..4: 5 2 4 2 sum=13
1..5: 5 2 4 2 2 sum=15
1..6: 5 2 4 2 2 2 sum=17
2..3: 2 4 sum=6
2..4: 2 4 2 sum=8
2..5: 2 4 2 2 sum=10
2..6: 2 4 2 2 2 sum=12
3..4: 4 2 sum=6
3..5: 4 2 2 sum=8
3..6: 4 2 2 2 sum=10
4..5: 2 2 sum=4
4..6: 2 2 2 sum=6
5..6: 2 2 sum=4
Of these 21 ranges, there are 12 pairs such that the ranges in the pair have the same sum:
0..1 ~ 2..3 sum=6
0..1 ~ 3..4 sum=6
0..1 ~ 4..6 sum=6
0..2 ~ 2..4 sum=8
0..2 ~ 3..5 sum=8
0..3 ~ 2..6 sum=12
2..3 ~ 3..4 sum=6
2..3 ~ 4..6 sum=6
2..4 ~ 3..5 sum=8
2..5 ~ 3..6 sum=10
3..4 ~ 4..6 sum=6
4..5 ~ 5..6 sum=4
The input of the program is a sequence of integers (positive, zero, and negative values). The reading of the input sequence is terminated when EOF is reached. The input sequence is at most 2000 numbers long.

The output of the program is the total number of pairs of ranges such that the sums of the ranges are the same.

---------whole code of program [updated] ---------
Code:
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000

//Take in the list of numbers
//As the list is input, loop within the j-arrays
//Loop through the result & get data into frequency array 
//Loop through the frequency array to get the result


int choose(int n, int k){
    if (k == 0) return 1;
    return (n * choose(n - 1, k - 1)) / k;
}


int main(){
	

//***************************
//takes input into the array
int * input = (int *) malloc (MAX * sizeof(int));

int n = 0, x;
printf("Input sequence:\n");

while ( scanf ( "%d", & x ) == 1 ) {
		if (n > MAX){
				free ( input );
				printf ( "Invalid input.\n" );
				return EXIT_FAILURE;
			}

		input [n] = x;
		++n;
	}
if ( ! feof ( stdin ) ) {
		printf ( "Invalid input.\n" );
		free ( input );
		return EXIT_FAILURE;
	}
	
if ( n == 0 ) {
		printf ( "Invalid input.\n" );
		free ( input );
		return EXIT_FAILURE;
	}
	
//****************************
//Finding sums
long int * pointer  = (long int*) malloc(((n-1) * (n-1)) * sizeof(long int));


for (int i = 0; i < n-1; i ++){
	//i is the column now
	//i + 2 is the N of elements in the sum
	for (int j = 0; j< n-1-i; j ++){ 
		//Add jth, ..., j+i+1 th element
		for (int k = j; k <= j+i+1; k++){ 
		*(pointer + (n-1)*i + j)  += input[k];
	}
	}
}

free(input);

//*******************************
//getting frequency
long int * frequency  = (long int*) malloc(2 * MAX * MAX  * sizeof(long int));


for (int i = 0; i < n-1; i ++){
	for (int j = 0; j < n-1-i; j ++){
		*(frequency + MAX + *(pointer + (n-1) * i + j)) += 1;
	}}


//*****************************
//Finding the max N of pairs
free(pointer);

int pairs = 0;

for (int i = 0; i < 2 * MAX * MAX; i++){
	if (i[frequency] == 2){
		pairs += 1;
	}
	else if (i[frequency] > 2){
		pairs += choose(i[frequency], 2);
} }





//******************************
//Printing whatever i need to print

free (frequency);

printf("Total pairs: %d\n", pairs);

return 0;}

//Maybe, it just wasn't meant to be


/*
 for (int i = 0; i < n-1; i ++){
	for (int j = 0; j < n-1-i; j ++){
	printf("%ld ", *(pointer + (n-1)*i + j));
	}
	printf("\n");}
 */

Last edited by AlinaC; 11-13-2022 at 08:04 AM. Reason: Found the real issue, code updated
 
Old 11-12-2022, 11:18 AM   #2
rtmistler
Moderator
 
Registered: Mar 2011
Location: USA
Distribution: MINT Debian, Angstrom, SUSE, Ubuntu, Debian
Posts: 9,736
Blog Entries: 13

Rep: Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784Reputation: 4784
I've written blogs about how to debug core dumps and use the debugger.

Please see the link in my signature.
 
1 members found this post helpful.
Old 11-12-2022, 11:43 AM   #3
dugan
LQ Guru
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 10,701

Rep: Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062Reputation: 5062
Quote:
Originally Posted by AlinaC View Post
Debugging has shown that it relates to the following line of code:

Code:
input = (int * ) realloc ( input, sizeof ( * input) * max );
I'm going to shove a rubber duck in your face. Explain to that duck what that line is supposed to do.

Last edited by dugan; 11-12-2022 at 12:23 PM.
 
Old 11-12-2022, 01:25 PM   #4
pan64
LQ Addict
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 19,250

Rep: Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525
you need to check the return value of malloc, realloc and in general any function. Just to know if they failed or not.
you can use valgrind to check memory related issues
you did not provide enough info, for example what did you exactly entered/tried when it failed.
you need also explain how did you compile/build this code (including the versions and also the OS).

Oh yes, what is this good for?
Code:
 n [ input ] = x;

Last edited by pan64; 11-12-2022 at 01:26 PM.
 
Old 11-12-2022, 02:03 PM   #5
GazL
LQ Veteran
 
Registered: May 2008
Distribution: CRUX 3.7
Posts: 6,568

Rep: Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668Reputation: 4668
Quote:
Originally Posted by pan64 View Post
Oh yes, what is this good for?
Code:
 n [ input ] = x;
Yeah, I'm surprised that didn't throw a warning.
 
Old 11-12-2022, 07:39 PM   #6
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,659

Rep: Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998Reputation: 1998
Quote:
Originally Posted by pan64 View Post
Oh yes, what is this good for?
Code:
 n [ input ] = x;
As clearly explained by the comment on the previous line, it's good for annoying people.

(see also https://c-faq.com/aryptr/joke.html)
 
1 members found this post helpful.
Old 11-13-2022, 01:53 AM   #7
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,389
Blog Entries: 1

Rep: Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665
Code:
if (n >= max) {
    max += max/2 + 10;
    input = (int * ) realloc (input, sizeof (*input) * max);
}
This wouldn't work in generic case (where n can be greater than max+(max/2)+10) but here n is incremented by one in every step, so 'n<=max' should be true before this part and 'n<max' after it.
Just to be sure, these checks could be added:
Code:
if (n > max) exit (60);
if (n == max) {
    max += max/2 + 10;
    input = (int * ) realloc (input, sizeof (*input) * max);
    if (input==NULL) exit (61);
}

Last edited by NevemTeve; 11-13-2022 at 01:55 AM.
 
Old 11-13-2022, 03:15 AM   #8
pan64
LQ Addict
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 19,250

Rep: Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525Reputation: 6525
Quote:
Originally Posted by ntubski View Post
As clearly explained by the comment on the previous line, it's good for annoying people.

(see also https://c-faq.com/aryptr/joke.html)
That clearly will not annoy me. It has definitely different consequences.
 
Old 11-13-2022, 08:05 AM   #9
AlinaC
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Quote:
Originally Posted by rtmistler View Post
I've written blogs about how to debug core dumps and use the debugger.

Please see the link in my signature.
Thank you for reference, will read it to learn more about debugging
 
Old 11-13-2022, 08:07 AM   #10
AlinaC
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Question

Quote:
Originally Posted by dugan View Post
I'm going to shove a rubber duck in your face. Explain to that duck what that line is supposed to do.
I didn't get what you intended to say with this phrase. Was it intentionally rude - or you just was asking to explain what this line of code was intended to do?
 
Old 11-13-2022, 08:16 AM   #11
AlinaC
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Quote:
Originally Posted by pan64 View Post
you need to check the return value of malloc, realloc and in general any function. Just to know if they failed or not.
you can use valgrind to check memory related issues
you did not provide enough info, for example what did you exactly entered/tried when it failed.
you need also explain how did you compile/build this code (including the versions and also the OS).

Oh yes, what is this good for?
Code:
 n [ input ] = x;
Thank you for your questions and advice, this was the most constructive answer!
I've used valgrind, it doesn't find anything.

First I compiled the code with g++ v11.3.0 in Ubuntu, no error. When I tried uploading my code to the university environment, the error appeared. I've tested then this code in Vs Code and then Visual Studio in Windows and got error messages with more info about where the problem could be.

I've tried with 2 examples from below, both failed with the same error
Example program output:
Input sequence:
1 5 2 4
Total pairs: 1

Input sequence:
1 5 2 4 2 2 2
Total pairs: 12
 
Old 11-13-2022, 08:18 AM   #12
AlinaC
LQ Newbie
 
Registered: Nov 2022
Posts: 6

Original Poster
Rep: Reputation: 0
Quote:
Originally Posted by NevemTeve View Post
Code:
if (n >= max) {
    max += max/2 + 10;
    input = (int * ) realloc (input, sizeof (*input) * max);
}
This wouldn't work in generic case (where n can be greater than max+(max/2)+10) but here n is incremented by one in every step, so 'n<=max' should be true before this part and 'n<max' after it.
Just to be sure, these checks could be added:
Code:
if (n > max) exit (60);
if (n == max) {
    max += max/2 + 10;
    input = (int * ) realloc (input, sizeof (*input) * max);
    if (input==NULL) exit (61);
}
Thank you for advice. After reading more about malloc/realloc, I've decided malloc should work better for my case and changed the code. Now debugging shows an error on another line: long int * frequency = (long int*) malloc(2 * MAX * MAX * sizeof(long int));
I've written about it in the updated text of my question.
 
Old 11-13-2022, 08:35 AM   #13
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,389
Blog Entries: 1

Rep: Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665
At that point, realloc is perfectly valid, as it keeps the already filled values. It's the later malloc-s where 'n' should be used instead of 'MAX'

Anyways, I tried the latest state of your program with valgrind; it showed that 'frequency' is uninitialized: 'malloc' allocates memory, but doesn't clear it; 'calloc' does that:
Code:
- long int * frequency  = (long int*) malloc(2 * MAX * MAX  * sizeof(long int));
+ long int * frequency  = (long int*) calloc(2 * n * n, sizeof(long int));

Last edited by NevemTeve; 11-13-2022 at 08:47 AM.
 
1 members found this post helpful.
Old 11-13-2022, 08:55 AM   #14
boughtonp
Senior Member
 
Registered: Feb 2007
Location: UK
Distribution: Debian
Posts: 2,985

Rep: Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120Reputation: 2120
Quote:
Originally Posted by AlinaC View Post
I didn't get what you intended to say with this phrase. Was it intentionally rude - or you just was asking to explain what this line of code was intended to do?
It's a reference to a common debugging technique - instead of asking a colleague for help, you first describe the issue to a rubber duck and imagine it responding with questions as that co-worker might, which you then answer.

Frequently, the action of describing a problem and considering common questions is enough to resolve an issue, but even when it's not it means you've done some basic diagnostic steps that allow you to rule certain things out before taking the issue to someone who isn't a duck.

 
1 members found this post helpful.
Old 11-13-2022, 09:05 AM   #15
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 4,389
Blog Entries: 1

Rep: Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665Reputation: 1665
A note: I'd start with ensuring that all elements are positive: if the minimum of all elements is not positive, then add 1-minimum to every elements.

After that we have n-1 series of nested intervals (only the sum of the elements is relevant; as the elements are positive, these sum-series are increasing).
Code:
input:    1 2 4  3  5  7  1 (n=7)
series#1:   3 7 10 15 22 23
series#2:     6  9 14 21 22
series#3:        7 12 19 20
series#4:           8 15 16
series#5:             12 13
series#6:                 8
Now we only have to find the common elements in these list.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
why different signals send to programs that exceeded memory limit set by setrlimit()? lonelycorn Programming 2 09-02-2010 10:03 PM
Simple C++ Program: Program Compiles But Won't Run (Segmentation Fault) violagirl23 Programming 3 01-09-2008 01:09 AM
yast segmentation fault, system freezing - nvidia driver at fault? BaltikaTroika SUSE / openSUSE 2 12-02-2005 10:34 AM
Memory Leak when using memory debugging C program on SuSE SLES8 babalina Linux - Distributions 0 10-06-2003 10:39 AM
child pid xxxxx exit signal File size limit exceeded (25)" problem. bisbane Linux - General 1 10-31-2002 05:35 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 08:22 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration