C++

Forum

 
Sorting program

pacman169 (374)
My program is supposed to rearrange input lines in alphabetical order. It is written in C. However currently it is not working as expected.



Input: dcba
Output: error: input too big to sort

I have used the array buf for storing the input lines. Here is the code, any help to fix it is appreciated:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 

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


#define MAXLINES 5000     /* max #lines to be sorted */
#define MAXSIZE 10000     /* maximum storage for input lines */


char *lineptr[MAXLINES];     /* pointers to  text lines */
char buf[MAXSIZE];        

int readlines(char *lineptr[], char buf[], int nlines);
void writelines(char *lineptr[], int nlines);


void myqsort(char *lineptr[], int left, int right);

/* sort input lines */

int main()
{
	
	int nlines;     /* number of input lines read */
	
	
	if ((nlines = readlines(lineptr, buf, MAXLINES)) >= 0) {
		myqsort(lineptr, 0, nlines-1);
		writelines(lineptr, nlines);
		return 0;
	}   else {
		printf("error: input too big to sort\n");
		return 1;
		
	}
}
	
#define MAXLEN 1000 /* max length of any input line */
int mygetline(char *, int);
char *alloc(int);

  /* readlines: read input lines */
int readlines(char *lineptr[], char buf[], int maxlines)
{
	int len, nlines;
	char *p = &buf[0]; 
	char line[MAXLEN];
	
	nlines = 0;
	while ((len = mygetline(line, MAXLEN)) > 0)
		if (nlines >= maxlines || buf + MAXSIZE - p > MAXSIZE )
			return -1;
	    else {
	    	line[len-1] = '\0'; /*delete newline */
			p+=len;
			strcpy(p, line);
			lineptr[nlines++] = p;
	    }
	
		return nlines;
 }
	
	
/* writelines: write output lines */

void writelines(char *lineptr[], int nlines)
{
	int i;
	
	
	for (i = 0; i < nlines; i++)
		printf("%s\n", lineptr[i]);
	
}
	
	
	
void myqsort(char *v[], int left, int right)

{
   
   int i, last;
   void swap(char *v[], int i, int j);
   
   if (left >= right)                    /* do nothing if array contains */
   return;                               

    swap(v, left, (left + right)/2);
	last = left;
	for (i = left+1; i<= right; i++)
	     if (strcmp(v[i], v[left]) < 0)
		 swap(v, ++last, i);
    swap(v, left, last);
	myqsort(v, left, last-1);
	myqsort(v, last+1, right);

}



void swap(char *v[], int i, int j)
{
	char *temp;
	
	temp = v[i];
	v[i] = v[j];
	v[j] = temp;
}




int mygetline (char s[], int lim)
	
{
	int c, i;
	
	for (i = 0; i<lim-1 && (c=getchar()) != EOF && c!= '\n'; ++i)	
		s[i] = c;
	if (c == '\n') {
		s[i] = c;
		++i;
	}
	s[i] = '\0';
	return i;
}


I did not show the implementations of getline or qsort.
Last edited on
ne555 (10692)
¿and why not? It would be a lot easier if we can simply run your program.


`p' seems to be used uninitialized in line 50
Last edited on
pacman169 (374)
`p' seems to be used uninitialized in line 50



Thank you. I edited my post, and when I compile it (GCC) It appears to work in my system.

Do you agree it is working?

Some results on my system:

 efg
abcd
defghi
abcd
defghi
efg
Last edited on
MiiNiPaa (8886)
In readlines move line 55 after line 57.
pacman169 (374)
Why should I do that? The program stops working if I do that. I'm still not sure if I did it correctly anyway.
MiiNiPaa (8886)
It should work fine
http://coliru.stacked-crooked.com/a/86c58860db8034be
Why should I do that?
Because else you are firs incrementing pointer leaving empty space at the beginning of the bffer, then do some operations
pacman169 (374)
Wouldn't it be easier to just read input lines into a buffer instead of having to use strcpy()?

I'm not very experienced in C so it would be difficult to implement.
MiiNiPaa (8886)
Wouldn't it be easier to just read input lines into a buffer instead of having to use strcpy()?
It was your choice, but yes, you can read lines directly into buffer.
pacman169 (374)
And how am I supposed to do it?

Is this correct?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 

 /* readlines: read input lines */
int readlines(char *lineptr[], char buf[], int maxlines)
{
	int len, nlines;
	size_t result;
	nlines = 0;
	FILE *fp;
	
	while(1) {
		
	char source[MAXLEN];
	
	if (nlines >= maxlines)
		break;
	
	if (len > MAXLEN)
		break;
	
	
    result = fread(source, sizeof(char), MAXLEN, fp);
	lineptr[nlines++] = source;
	source += len;
	
	if (result == NULL)
		break;
	
	
	//terminate
	
	fclose(fp);
	return 0;
	
   }

 }
MiiNiPaa (8886)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
//Assuming get_line function which takes a stream, buffer and buffer size, 
//reads null-terminated string in buffer
//returns amount of characters written (including terminating 0)
//returns 0 on failure (end of file reached or buf_size == 0)
size_t get_line(FILE* stream, char* buf, size_t buf_size);

int read_lines(FILE* source, char* lineptr[], size_t max_lines, char* buf, size_t buf_size)
{
    size_t line_size = 0;
    size_t lines = 0;
    while(lines < max_lines && (line_size = get_line(source, buf, buf_size) > 0) {
        lineptr[lines++] = buf;
        buf += line_size;
        buf_size -= line_size;
    }
    return lines;
}
pacman169 (374)
Here is my solution slightly modified :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 

  /* readlines: read input lines */
int readlines(FILE *source, char *lineptr[], char *buf, int maxlines)
{
	size_t linesize, nlines; 
	size_t bufsize = 1000;
	nlines = 0;
	
	
 for(;;) 
 
 {
		
	linesize = getline (&buf, &bufsize, source);
		
	if (linesize == 0)
		break;
	
	if (nlines >= maxlines)
		break;
	
	if (linesize > bufsize)
		break;
	
	 
	lineptr[nlines++] = buf;
	buf += linesize;
	bufsize -= linesize;

 }
 
 return nlines;

}


I wonder if the implementation is correct, getting strange results when trying to compile. The get line function is declared in stdio.h
MiiNiPaa (8886)
I was assuming you will be using your own mygetline implementation with minimal changes.

If you want to use Linux-specific getline, then you will need to make changes to conform its behaviour.
pacman169 (374)
I use the function get line declared here:

http://www.gnu.org/software/libc/manual/html_node/Line-Input.html


Why won't my code work?

http://coliru.stacked-crooked.com
MiiNiPaa (8886)
MiiNiPaa wrote:
1
2
3
 
//Assuming get_line function which takes a stream, buffer and buffer size, 
//reads null-terminated string in buffer
//returns amount of characters written (including terminating 0)
getline wrote:
When getline is successful, it returns the number of characters read (including the newline, but not including the terminating null).
I wrote about expected behavior of get_line for a reason. In your case you should add 1 to linesize

Additionally if buffer is not large enough to hold all values, everything will break loudly: your code does not handle automatic reallocation gracefully.
pacman169 (374)
Then it would be something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 

  /* readlines: read input lines */
int readlines(FILE *source, char *lineptr[], char *buf, int maxlines)
{
	size_t linesize, nlines; 
	size_t bufsize = 1000;
	nlines = 0;
	
	
 for(;;) 
 
 {
	
	buf = (char *) malloc (bufsize + 1);
	linesize = getline (&buf, &bufsize, source);
		
	if (linesize == 0)
		break;
	
	if (nlines >= maxlines)
		break;
	
	if (linesize > bufsize)
		break;
	
	 
	lineptr[nlines++] = buf;
	buf += linesize;
	bufsize -= linesize;

 }
 
 return nlines;

}
MiiNiPaa (8886)
NOtice that caller will not see change to buf, therefore that parameter is useless, and you can even omit it.
pacman169 (374)
Some results with GCC:

defghi
abc
efg
abc

defghi

efg


Link to current code: http://coliru.stacked-crooked.com
Last edited on
Topic archived. No new replies allowed.