Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #11885 > unrolled thread

Analogue of ReadLine() in C

Back to article view | Back to comp.lang.c

Contents

  Analogue of ReadLine() in C Максим Фомин <maxim@maxim-fomin.ru> - 2011-10-19 12:26 -0700
    Re: Analogue of ReadLine() in C China Blue Corn Chips <chine.bleu@yahoo.com> - 2011-10-19 13:05 -0700
      Re: Analogue of ReadLine() in C China Blue Corn Chips <chine.bleu@yahoo.com> - 2011-10-19 20:50 -0700
        Re: Analogue of ReadLine() in C Seebs <usenet-nospam@seebs.net> - 2011-10-20 07:42 +0000
          Re: Analogue of ReadLine() in C China Blue Corn Chips <chine.bleu@yahoo.com> - 2011-10-20 02:51 -0700
            Re: Analogue of ReadLine() in C gazelle@shell.xmission.com (Kenny McCormack) - 2011-10-20 12:52 +0000
            Re: Analogue of ReadLine() in C "BartC" <bc@freeuk.com> - 2011-10-20 14:31 +0100
              Re: Analogue of ReadLine() in C Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-10-20 08:05 -0700
                Re: Analogue of ReadLine() in C gazelle@shell.xmission.com (Kenny McCormack) - 2011-10-20 15:15 +0000
                Re: Analogue of ReadLine() in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-10-20 16:50 +0100
                Re: Analogue of ReadLine() in C "BartC" <bc@freeuk.com> - 2011-10-20 23:23 +0100
                  Re: Analogue of ReadLine() in C Keith Thompson <kst-u@mib.org> - 2011-10-20 15:34 -0700
                    Re: Analogue of ReadLine() in C Ian Collins <ian-news@hotmail.com> - 2011-10-21 14:10 +1300
                    Re: Analogue of ReadLine() in C "BartC" <bc@freeuk.com> - 2011-10-21 10:30 +0100
                      Re: Analogue of ReadLine() in C Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-10-21 05:59 -0700
                      Re: Analogue of ReadLine() in C Keith Thompson <kst-u@mib.org> - 2011-10-21 10:58 -0700
                        Re: Analogue of ReadLine() in C "BartC" <bc@freeuk.com> - 2011-10-22 20:00 +0100
                          Re: Analogue of ReadLine() in C Ian Collins <ian-news@hotmail.com> - 2011-10-23 08:09 +1300
                          Re: Analogue of ReadLine() in C Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-10-22 23:55 -0700
              Re: Analogue of ReadLine() in C Ian Collins <ian-news@hotmail.com> - 2011-10-21 08:34 +1300
            Re: Analogue of ReadLine() in C Seebs <usenet-nospam@seebs.net> - 2011-10-20 17:57 +0000
            Re: Analogue of ReadLine() in C Markus Wichmann <nullplan@gmx.net> - 2011-10-23 23:03 +0200
              Re: Analogue of ReadLine() in C Acid Washed China Blue Jeans <chine.bleu@yahoo.com> - 2011-10-24 00:31 -0700
              Re: Analogue of ReadLine() in C Richard Damon <news.x.richarddamon@xoxy.net> - 2011-10-24 08:10 -0400
    Re: Analogue of ReadLine() in C 88888 Dihedral <dihedral88888@googlemail.com> - 2011-10-19 14:04 -0700
      Re: Analogue of ReadLine() in C Kaz Kylheku <kaz@kylheku.com> - 2011-10-19 21:52 +0000
    Re: Analogue of ReadLine() in C Ike Naar <ike@iceland.freeshell.org> - 2011-10-19 22:34 +0000
    Re: Analogue of ReadLine() in C pete <pfiland@mindspring.com> - 2011-10-19 19:02 -0400
      Re: Analogue of ReadLine() in C pete <pfiland@mindspring.com> - 2011-10-20 00:36 -0400
    Re: Analogue of ReadLine() in C Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-10-20 00:11 -0700
      Re: Analogue of ReadLine() in C Максим Фомин <maxim@maxim-fomin.ru> - 2011-10-20 01:59 -0700
    Re: Analogue of ReadLine() in C James Kuyper <jameskuyper@verizon.net> - 2011-10-20 06:57 -0400
    Re: Analogue of ReadLine() in C Markus Wichmann <nullplan@gmx.net> - 2011-10-20 18:40 +0200
      Re: Analogue of ReadLine() in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-10-20 18:20 +0100
        Re: Analogue of ReadLine() in C Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-10-21 08:58 +0000
          Re: Analogue of ReadLine() in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-10-21 19:12 +0100
          Re: Analogue of ReadLine() in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-10-21 19:35 +0100
            Re: Analogue of ReadLine() in C "io_x" <a@b.c.invalid> - 2011-10-22 18:58 +0200
          Re: Analogue of ReadLine() in C David Thompson <dave.thompson2@verizon.net> - 2011-10-28 01:34 -0400
    Re: Analogue of ReadLine() in C Michael Angelo Ravera <maravera@prodigy.net> - 2011-10-20 13:32 -0700
      Re: Analogue of ReadLine() in C James Kuyper <jameskuyper@verizon.net> - 2011-10-20 16:42 -0400
      Re: Analogue of ReadLine() in C "Morris Keesan" <mkeesan@post.harvard.edu> - 2011-10-20 16:47 -0400
    Re: Analogue of ReadLine() in C Shao Miller <sha0.miller@gmail.com> - 2012-01-07 14:37 -0500

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#11919

On 2011-10-20, China Blue Corn Chips <chine.bleu@yahoo.com> wrote:
> In article <slrnj9vjr9.2vs.usenet-nospam@guild.seebs.net>,
>  Seebs <usenet-nospam@seebs.net> wrote:
[all in reference to:]
>> >> >char *p = 0; int m = 0, n = 0, c;
>> >> >while (c=fgetc(file), c!='\n' && c!=EOF) {
>> >> >    if (n>=m) {m = 2*n+1; p = realloc(p, m);}
>> >> >    p[n++] = c;

>> >>   What if !realloc(p,m)?

>> > Buy a bigger swap disk.
 
>> This is crappy advice, because it's completely unrelated.  There are

> The maximum line size is the file size. If the VM that can map in the entire 
> file, it can allocate space for one line.

Except, as I pointed out, this isn't true.

> If you want to run on smaller 
> memories, adapt the code accordingly. I'm not interested in doing so.

That's fine.  But telling someone *else* to "buy a bigger swap disk" as
a solution to a problem that cannot be fixed by buying a bigger swap disk
remains crappy advice.

> The total time and space is O(n). Changing the multiplier leaves you with O(n). 
> Starting with size>0 reduces the time and space by O(k), however
> O(n)-O(k) = O(n).

Except that:
1.  The thing it optimizes is actually O(log(n)).
2.  k is, in this case, quite likely to be the entirety of the actual data.

> You're worrying about optimising at the wrong level which is a 
> waste of time unless you've done measurement showing this is a hot loop.

There's such a thing as premature optimization, but that doesn't mean we
should go out of our way to do things in obviously stupid ways.  On a real
system, with real data, your solution will take many times more real
execution time than one which changes nothing except starting with n=64.

And while it's a bad thing to go around making things fancier than you need
to for no measured benefit, it's not a bad thing to make reasonable choices
for starting values.

> Also 
> realloc(0,n) is the same as malloc(n) so one initial malloc is no different than 
> a realloc on the first loop; but it requires more code.

Right.  I didn't suggest a fancier algorithm; I suggested starting n at some
other value.

> I used to write code that had to fit in 65K bytes. I don't any more. You can if 
> you want.

This is a ridiculous bit of hyperbole.  I'm not talking about crazy or
unreasonable requirements; I'm talking about something which, for data sizes
most people deal with on a daily basis, would blow up on most consumer
machines today, when an even slightly cleverer algorithm wouldn't.

>> Depending, I'd say either start with a "likely" length or start with
>> something around a page size, and reallocate up a little more conservatively.

> If the resize doesn't increase geometrically, the run time switches to O(n^2). 
> Otherwise it is O(n) + whatever code complexity you want to pretend you can beat 
> O(n).

O(n) notation only gets you so far.  There is more to writing good code than
that.

I guess what offends me about this isn't that it's lazy, but that it's not
even lazy.  It wouldn't be any more effort to do this in a way that would
work dramatically better.  If it were *any* more effort, I could agree that
maybe it wasn't worth putting in that effort, but when it's *no effort at
all*, that's ridiculous.

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

[toc] | [prev] | [next] | [standalone]

#12012

On 20.10.2011 11:51, China Blue Corn Chips wrote:
> The total time and space is O(n). Changing the multiplier leaves you with O(n). 
> Starting with size>0 reduces the time and space by O(k), however
> O(n)-O(k) = O(n). You're worrying about optimising at the wrong level which is a 
> waste of time unless you've done measurement showing this is a hot loop. Also 
> realloc(0,n) is the same as malloc(n) so one initial malloc is no different than 
> a realloc on the first loop; but it requires more code.
> 
[...]
> 
> If the resize doesn't increase geometrically, the run time switches to O(n^2). 
> Otherwise it is O(n) + whatever code complexity you want to pretend you can beat 
> O(n).
> 

One of the problems with the O-notation is that it doesn't tell you one
bit if it stays the same. If I had an algorithm that would _always_ beat
your algorithm by 1/2 the runtime, the complexity would still stay the same.

O-notation is only meaningfull if it shows differences! Otherwise, more
insight is needed.

CYA,
Markus

[toc] | [prev] | [next] | [standalone]

#12015

In article <91cen8-hea.ln1@voyager.wichi.de.vu>,
 Markus Wichmann <nullplan@gmx.net> wrote:

> On 20.10.2011 11:51, China Blue Corn Chips wrote:
> > The total time and space is O(n). Changing the multiplier leaves you with 
> > O(n). 
> > Starting with size>0 reduces the time and space by O(k), however
> > O(n)-O(k) = O(n). You're worrying about optimising at the wrong level which 
> > is a 
> > waste of time unless you've done measurement showing this is a hot loop. 
> > Also 
> > realloc(0,n) is the same as malloc(n) so one initial malloc is no different 
> > than 
> > a realloc on the first loop; but it requires more code.
> > 
> [...]
> > 
> > If the resize doesn't increase geometrically, the run time switches to 
> > O(n^2). 
> > Otherwise it is O(n) + whatever code complexity you want to pretend you can 
> > beat 
> > O(n).
> > 
> 
> One of the problems with the O-notation is that it doesn't tell you one
> bit if it stays the same. If I had an algorithm that would _always_ beat
> your algorithm by 1/2 the runtime, the complexity would still stay the same.
> 
> O-notation is only meaningfull if it shows differences! Otherwise, more
> insight is needed.

And you waste even more time coding an O(n^2) algorithm down to almost assembly 
instead of realising you can use an O(n) algorithm.

-- 
Celle est une langue.     |           Faded, patched, secret so tight...
C'est francais           /|\              I'm whoever you want me to be.
et tres, tres sexuel.    \|/         Annoying Usenet one post at a time.
- China Azul              |            At least I can stay in character.

[toc] | [prev] | [next] | [standalone]

#12029

On 10/23/11 5:03 PM, Markus Wichmann wrote:
> On 20.10.2011 11:51, China Blue Corn Chips wrote:
>> The total time and space is O(n). Changing the multiplier leaves you with O(n).
>> Starting with size>0 reduces the time and space by O(k), however
>> O(n)-O(k) = O(n). You're worrying about optimising at the wrong level which is a
>> waste of time unless you've done measurement showing this is a hot loop. Also
>> realloc(0,n) is the same as malloc(n) so one initial malloc is no different than
>> a realloc on the first loop; but it requires more code.
>>
> [...]
>>
>> If the resize doesn't increase geometrically, the run time switches to O(n^2).
>> Otherwise it is O(n) + whatever code complexity you want to pretend you can beat
>> O(n).
>>
>
> One of the problems with the O-notation is that it doesn't tell you one
> bit if it stays the same. If I had an algorithm that would _always_ beat
> your algorithm by 1/2 the runtime, the complexity would still stay the same.
>
> O-notation is only meaningfull if it shows differences! Otherwise, more
> insight is needed.
>
> CYA,
> Markus

And O-notation is also only meaningful if n is going to get "large". If 
your problem domain inherently has just "small" n then using a simpler 
O(n^2) algorithm may be significantly better than O(n) one. It may have 
  a smaller constant, or may just be enough simpler, that the extra 
resources used aren't important (if what it is measuring isn't a 
significant bottleneck for this program).

[toc] | [prev] | [next] | [standalone]

#11890

If one has problems with dynamical allocations  of pointers in the   main memory, please use static buffer first to dump  buffer contents and define the DEBUG modes for all pointers!


======
It is bad in C/C++ to use  macros with nested operations in any argument!

Macros should not affect arguments' variables values unless desired in the macros! 

   

[toc] | [prev] | [next] | [standalone]

#11891

On 2011-10-19, 88888 Dihedral <dihedral88888@googlemail.com> wrote:
> If one has problems with dynamical allocations  of pointers in the   main memory, please use static buffer first to dump  buffer contents and define the DEBUG modes for all pointers!
>
>
>======
> It is bad in C/C++ to use  macros with nested operations in any argument!

ITYM, "side effects in any argument".

I do not agree. The obvious counterexample are properly designed macros which
are carefully designed to evaluate their arguments exactly once, and have a
proper sequence point after the evaluation of arguments.

Removing this requirement sometimes make it easier to design a macro, and then
the users of the macro have to be given a big warning.

> Macros should not affect arguments' variables values unless desired in the macros! 

When it is acceptable for a computer operation to have an effect on data,
such that the effect is not desired?

[toc] | [prev] | [next] | [standalone]

#11893

On 2011-10-19, ?????? ????? <maxim@maxim-fomin.ru> wrote:
> I need function similar to ReadLine() in any other language.
> The program below fails[1] when data more then LAG_SIZE is passed
>
> #include <stdio.h>
> #include <stdbool.h>
> #include <string.h>
> #include <stdlib.h>
>
> char * read_line(void)
> {
> 	bool read_more = true;
> 	enum { LAG_SIZE = 32 };
> 	char *return_buf = NULL;
> 	char *new_line_pos = NULL;
> 	char tmp_buf[LAG_SIZE] = {'\0'};
> 	size_t size = 0;
> 	while (read_more && fgets(tmp_buf, LAG_SIZE, stdin)){
> 		char *tmp_realloc;
> 		size += LAG_SIZE;
> 		tmp_realloc = realloc(return_buf, size);
> 		if (!tmp_realloc){
> 			free(return_buf);
> 			return_buf = NULL;
> 			break;
> 		}
> 		return_buf = tmp_realloc;
> 		memset(return_buf + size - LAG_SIZE, '\0', LAG_SIZE);
> 		new_line_pos = strchr(tmp_buf, '\n');
> 		if (new_line_pos){
> 			*new_line_pos = '\0';
> 			read_more = false;
> 		}
> 		strcat(return_buf, tmp_buf);
> 		memset(tmp_buf, '\0', LAG_SIZE);
> 	}
> 	return return_buf;
> }
>
> void loop(void)
> {
> 	bool repeat = true;
> 	while (repeat){
> 		char *command;
> 		printf("Enter> ");
> 		command = read_line();
> 		if (command && !strcmp(command, "exit"))

Is this really what you meant? This means that the program will
loop forever when no more input can be read (e.g. when EOF is
reached). I'd guess you want:

    if (command == NULL || !strcmp(command, "exit"))

instead.

> 			repeat = false;
> 		free(command);
> 	}
> }
>
> int main(void)
> {
> 	loop();
> 	return 0;
> }
>
> [1]: *** glibc detected *** ./a.out: realloc(): invalid next size:
> 0x0804b008 ***


-- 
ike@sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org

[toc] | [prev] | [next] | [standalone]

#11894

=?UTF-8?B?0JzQsNC60YHQuNC8INCk0L7QvNC40L0=?= wrote:
> 
> I need function similar to ReadLine() in any other language.
> The program below fails[1] when data more then LAG_SIZE is passed
> 
> #include <stdio.h>
> #include <stdbool.h>
> #include <string.h>
> #include <stdlib.h>
> 
> char * read_line(void)
> {
>         bool read_more = true;
>         enum { LAG_SIZE = 32 };
>         char *return_buf = NULL;
>         char *new_line_pos = NULL;
>         char tmp_buf[LAG_SIZE] = {'\0'};
>         size_t size = 0;
>         while (read_more && fgets(tmp_buf, LAG_SIZE, stdin)){
>                 char *tmp_realloc;
>                 size += LAG_SIZE;
>                 tmp_realloc = realloc(return_buf, size);
>                 if (!tmp_realloc){
>                         free(return_buf);
>                         return_buf = NULL;
>                         break;
>                 }
>                 return_buf = tmp_realloc;
>                 memset(return_buf + size - LAG_SIZE, '\0', LAG_SIZE);
>                 new_line_pos = strchr(tmp_buf, '\n');
>                 if (new_line_pos){
>                         *new_line_pos = '\0';
>                         read_more = false;
>                 }
>                 strcat(return_buf, tmp_buf);
>                 memset(tmp_buf, '\0', LAG_SIZE);
>         }
>         return return_buf;
> }
> 
> void loop(void)
> {
>         bool repeat = true;
>         while (repeat){
>                 char *command;
>                 printf("Enter> ");
>                 command = read_line();
>                 if (command && !strcmp(command, "exit"))
>                         repeat = false;
>                 free(command);
>         }
> }
> 
> int main(void)
> {
>         loop();
>         return 0;
> }
> 
> [1]: *** glibc detected *** ./a.out: realloc(): invalid next size:
> 0x0804b008 ***

/* BEGIN read_line_test.c */

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

void loop(void);

int read_line(char **lineptr, 
              size_t *n, 
              FILE *stream, 
              size_t *size);

int 
main(void)
{
    loop();
    return 0;
}

void 
loop(void)
{
    int rc;
    char *command = NULL;
    size_t n = 0;

    do {
        printf("Enter> ");
        rc = read_line(&command, &n, stdin, NULL);
    } while (rc > -1 && strcmp(command, "exit"));
    free(command);
}

int 
read_line(char **lineptr, size_t *n, FILE *stream, size_t *size)
{
    int rc;
    size_t count = 0;
    size_t min = 2;

    while ((rc = getc(stream)) != EOF 
        || !feof(stream) && !ferror(stream)) 
    {
        if (++count == (size_t)-2) {
            if (rc != '\n') {
                (*lineptr)[count - 1] = (char)rc;
                (*lineptr)[count++] = '\0';
            } else {
                (*lineptr)[count - 1] = '\0'; 
            }
            break;
        }
        if (++min > *n) {
            void *p;
            size_t max;
            size_t next;

            for (next = min ^ min - 1; min > next; ++next) {
                next *= 2;
            }
            do {
                max = next;
                next = (max - min) / 2 + min;
                p = realloc(*lineptr, max);
            } while (p == NULL && max != min);
            if (p == NULL) {
                if (*n > count) {
                    if (rc != '\n') {
                        (*lineptr)[count - 1] = (char)rc;
                        (*lineptr)[count++] = '\0';
                    } else {
                        (*lineptr)[count - 1] = '\0'; 
                    }
                } else {
                    ungetc(rc, stream);
                    --count;
                    if (*n != 0) {
                        (*lineptr)[count++] = '\0';
                    }
                }
                if (size != NULL) {
                    *size = count;
                }
                count = 0;
                break;
            } else {
                *lineptr = p;
                *n = max;
            }
        }
        if (rc != '\n') {
            (*lineptr)[count - 1] = (char)rc;
        } else {
            (*lineptr)[count - 1] = '\0'; 
            break;
        }
    }
    if (rc != EOF || !feof(stream) && !ferror(stream)) {
        rc = INT_MAX > count ? count : INT_MAX;
    } else {
        if (*n > count) {
            (*lineptr)[count++] = '\0';
        }
    }
    if (size != NULL && rc != 0) {
        *size = count;
    }
    return rc;
}

/* END read_line_test.c */

-- 
pete

[toc] | [prev] | [next] | [standalone]

#11897

pete wrote:
 
> void
> loop(void)
> {
>     int rc;
>     char *command = NULL;
>     size_t n = 0;
> 
>     do {
>         printf("Enter> ");
>         rc = read_line(&command, &n, stdin, NULL);
>     } while (rc > -1 && strcmp(command, "exit"));
>     free(command);
> }

/* 
** Instead, that should be: 
*/

void 
loop(void)
{
    int rc;
    char *command = NULL;
    size_t n = 0;

    do {
        printf("Enter> ");
        fflush(stdout);
        rc = read_line(&command, &n, stdin, NULL);
    } while (rc > 0 && strcmp(command, "exit"));
    free(command);
}

-- 
pete

[toc] | [prev] | [next] | [standalone]

#11901

On Oct 19, 8:26 pm, Максим Фомин <ma...@maxim-fomin.ru> wrote:

> I need function similar to ReadLine() in any other language.

*what* other language? It certinly isn't present in all other
langauges.

> The program below fails[1] when data more then LAG_SIZE is passed

so fix it

<snip>

[toc] | [prev] | [next] | [standalone]

#11903

On Oct 20, 11:11 am, Nick Keighley <nick_keighley_nos...@hotmail.com>
wrote:
> On Oct 19, 8:26 pm, Максим Фомин <ma...@maxim-fomin.ru> wrote:
>
> > I need function similar to ReadLine() in any other language.
>
> *what* other language? It certinly isn't present in all other
> langauges.

Yes, not all languages have. But many decent have.
However, it is not an issue.

>
> > The program below fails[1] when data more then LAG_SIZE is passed
>
> so fix it
>
> <snip>

I haven't not found any error in red_line() function (I consider calls
to malloc, realloc and free legitimate), in fact I doubt that there is
one.
That's why I asked the question.

[toc] | [prev] | [next] | [standalone]

#11905

On 10/19/2011 03:26 PM, Максим Фомин wrote:
> I need function similar to ReadLine() in any other language.
> The program below fails[1] when data more then LAG_SIZE is passed
...
> [1]: *** glibc detected *** ./a.out: realloc(): invalid next size:
> 0x0804b008 ***

I could not duplicate that symptom. Could you provide the exact command
line you used to compile the program, and exact input line that triggers
the failure?
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#11916

On 19.10.2011 21:26, Максим Фомин wrote:
> I need function similar to ReadLine() in any other language.
> The program below fails[1] when data more then LAG_SIZE is passed
> 

Reading linewise through a file is as simple as using fgets(). If the
last character in the returned string is newline character, you got a
whole line.

This makes it possible to adapt to use cases. In your case, I would
simply do something like:

#include <stdio.h>
#include <string.h>
static char buffer[256];

static void loop()
{
    do {
        if (fgets(buffer, sizeof buffer, stdin) < 0) {
            /* read error. Might be eof or real error. */
            if (ferror(stdin)) perror("read error");
            return;
        }
    } while (strncmp(buffer, "exit", sizeof "exit" - 1));
}

int main() { loop(); }

No dynamic allocation where it isn't necessary. It is not really
necessary in I/O, because there is never a buffer big enough for that,
so don't program as though there were!

HTH,
Markus

[toc] | [prev] | [next] | [standalone]

#11917

Markus Wichmann <nullplan@gmx.net> writes:

> On 19.10.2011 21:26, Максим Фомин wrote:
>> I need function similar to ReadLine() in any other language.
>> The program below fails[1] when data more then LAG_SIZE is passed
>> 
>
> Reading linewise through a file is as simple as using fgets(). If the
> last character in the returned string is newline character, you got a
> whole line.
>
> This makes it possible to adapt to use cases. In your case, I would
> simply do something like:
>
> #include <stdio.h>
> #include <string.h>
> static char buffer[256];
>
> static void loop()
> {
>     do {
>         if (fgets(buffer, sizeof buffer, stdin) < 0) {

I think you intended to write == 0 here.

>             /* read error. Might be eof or real error. */
>             if (ferror(stdin)) perror("read error");
>             return;
>         }
>     } while (strncmp(buffer, "exit", sizeof "exit" - 1));
> }
>
> int main() { loop(); }

I am not sure how you decided that this suits the OP's use case.  I
think the original posted code was just a cut down example, so it's not
obvious that silently splitting lines that are longer than 255
characters suits the OP.

> No dynamic allocation where it isn't necessary. It is not really
> necessary in I/O, because there is never a buffer big enough for that,
> so don't program as though there were!

I think you'd be annoyed if, say, awk behaved like this.  Given a big
enough buffer, your shell might get away with it, but I expect it
doesn't try.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#11935

On Thu, 2011-10-20, Ben Bacarisse wrote:
> Markus Wichmann <nullplan@gmx.net> writes:
...

> I am not sure how you decided that this suits the OP's use case.  I
> think the original posted code was just a cut down example, so it's not
> obvious that silently splitting lines that are longer than 255
> characters suits the OP.
>
>> No dynamic allocation where it isn't necessary. It is not really
>> necessary in I/O, because there is never a buffer big enough for that,
>> so don't program as though there were!
>
> I think you'd be annoyed if, say, awk behaved like this.  Given a big
> enough buffer, your shell might get away with it, but I expect it
> doesn't try.

I'm too lazy to look for the context, but I assume you are talking
about varying input line lengths here.

I think it's a bit more complicated than that. Assuming some
line-oriented input format:

- It's usually wrong to set a limit (say, 8192 bytes) and pretend
  anything longer is two or more lines.

- It's usually wrong to accept *any* length by using malloc()/realloc(),
  and then start swapping and crashing when someone feeds you a
  10GB line.

  I assume a decent awk sets some limit (far higher than any reasonable
  input) and exits gracefully with an error message when it gets
  anything larger.

- Many file/data formats put a limit to the line length anyway.
  NNTP, SMTP. IIRC also the C language says a compiler is allowed
  to bail out on lines longer than N characters.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#11945

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> Jorgen Grahn <grahn+nntp@snipabacken.se> writes:
>>- It's usually wrong to set a limit (say, 8192 bytes) and pretend
>>  anything longer is two or more lines.
>
>   Untested:
>
> int readline
> ( FILE * const source, 
>   int( * const target )( int ch, void * obj ),
>   void * const object )
> { int c; int result = 1; while( result == 1 )
>   { c = fgetc( source ); result =
>     c == EOF           ? 2 :
>     ferror( source    )? 3 :
>     c == '\n'          ? 0 :
>     target( c, object )? 4 : result; }
>   return result; }

Unread.  :-)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#11946

Jorgen Grahn <grahn+nntp@snipabacken.se> writes:

> On Thu, 2011-10-20, Ben Bacarisse wrote:
>> Markus Wichmann <nullplan@gmx.net> writes:
> ...
>
>> I am not sure how you decided that this suits the OP's use case.  I
>> think the original posted code was just a cut down example, so it's not
>> obvious that silently splitting lines that are longer than 255
>> characters suits the OP.
>>
>>> No dynamic allocation where it isn't necessary. It is not really
>>> necessary in I/O, because there is never a buffer big enough for that,
>>> so don't program as though there were!
>>
>> I think you'd be annoyed if, say, awk behaved like this.  Given a big
>> enough buffer, your shell might get away with it, but I expect it
>> doesn't try.
>
> I'm too lazy to look for the context, but I assume you are talking
> about varying input line lengths here.

I was talking about the remark I quoted -- that dynamic allocation is
not a good idea because no buffer is big enough.

> I think it's a bit more complicated than that. Assuming some
> line-oriented input format:
>
> - It's usually wrong to set a limit (say, 8192 bytes) and pretend
>   anything longer is two or more lines.
>
> - It's usually wrong to accept *any* length by using malloc()/realloc(),
>   and then start swapping and crashing when someone feeds you a
>   10GB line.
>
>   I assume a decent awk sets some limit (far higher than any reasonable
>   input) and exits gracefully with an error message when it gets
>   anything larger.

With a general purpose program like awk, I think there are only two good
strategies:

(a) Just keep allocating because the system does something helpful when
the process gets too large.

(b) Limit the total memory allocation, without limiting any one kind
(like line length).

The trouble is that there are systems that don't do (a) and
implementations that don't (or can't) do (b).  I don't think limiting
the line length is really the right solution.

> - Many file/data formats put a limit to the line length anyway.
>   NNTP, SMTP. IIRC also the C language says a compiler is allowed
>   to bail out on lines longer than N characters.

If a sane upper limit can be picked then there is no problem.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#11957

"Ben Bacarisse" <ben.usenet@bsb.me.uk> ha scritto nel messaggio 
news:0.024f7a917e9abfe6741b.20111021193525BST.87r526i45u.fsf@bsb.me.uk...
> Jorgen Grahn <grahn+nntp@snipabacken.se> writes:
> If a sane upper limit can be picked then there is no problem.

i agree
it is not possible for one program has +oo [+ or -]input
the sys goes to hang

[toc] | [prev] | [next] | [standalone]

#12164

On 21 Oct 2011 08:58:55 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
wrote:
<snip>
> I think it's a bit more complicated than that. Assuming some
> line-oriented input format:
> 
> - It's usually wrong to set a limit (say, 8192 bytes) and pretend
>   anything longer is two or more lines.
> 
I'd say always wrong, or very nearly always.

> - It's usually wrong to accept *any* length by using malloc()/realloc(),
>   and then start swapping and crashing when someone feeds you a
>   10GB line.
> 
>   I assume a decent awk sets some limit (far higher than any reasonable
>   input) and exits gracefully with an error message when it gets
>   anything larger.
> 
I recently had occasion to do some testing on this.

gawk on Linux died around 1G with an error message clearly indicating
that reallocation failed (as expected for a 2G-ish address space).
gawk on mingw failed somewhere in the millions, which on experiment
was confirmed to be very nearly the same size as a program that just
realloc'ed one buffer upward; presumably this has to do with Windows
address space as seen by mingw and I didn't investigate in detail.

Other awks on several Solarises*, HPUX, and an elderly AIX, all died
in the thousands, except that Solaris most-ancient 'oawk' did the very
bad thing of *breaking* lines over some length IIRC about 500.

(* I think the plural should actually be Solares IIRC my high-school
Latin, but I doubt anybody cares.)

> - Many file/data formats put a limit to the line length anyway.
>   NNTP, SMTP. IIRC also the C language says a compiler is allowed
>   to bail out on lines longer than N characters.
> 
Although NNTP and SMTP, at least, limit line lengths 'on the wire'
after encoding. From early on there were lots of attempts at encodings
allowing 'real' lines to be longer than the transmitted ones, although
none really successful until MIME's QP and B64.

A C implementation is not required to support more than 4095 chars
(509 in C89) in a 'logical' source line (after backslash splicing) nor
more than 254 per line in *text* files at runtime. The basic source
charset doesn't include newline, but some end-of-line 'indicator' is
"treat[ed] ... as if ... newline", so it's not clear if the 4095
includes that. The basic execution charset includes newline, which
terminates lines in text files, and is included in the 254.

In the 70s and into the 80s when C was developed (and most of the
major Internet protocols also) there were lots of important systems
and especially filesystems that had definite limits on the sizes of
records, which conventionally mapped to lines of text (although a C
implementor could break that mapping if they had to). 

The Tanpaqard NonStop defined a rather odd format for text files
(officially EDIT format, commonly called code-101 because that's how
it is identified in the directory) which compresses runs of spaces and
can handle actual line lengths from about 239 with no spaces to over
3000 with many spaces. This was created before C existed, and when
Tandem implemented C (belatedly, right around '88) they added
'C-format' files (bag-o-bytes with NL) as code-180, and explicitly
noted in their manual that reading EDIT files, although supported as
an extension (and extremely useful to sites with lots of those files)
was not quite exactly conforming.

[toc] | [prev] | [next] | [standalone]

#11922

You will see some petty squabling.

The reason that you code fails is that you can't generally realloc what you haven't [m|c|0]alloc'd.

I agree with others that you should first allocate something like the longest common line (whatever you deem that to be). I might pick 256 or 512 or 409 or 86 or 133. If wastage for multiple consecutive lines is a big problem, you will want to do some sort of your own memory management for your "Lines". 

You could allocate something extremely large and then copy it into a buffer that is just barely big enough. 

Most libraries do not allocate exactly what you tell them to. If you know about the memory management method, you can allocate something reasonable initially and avoid doing the copy when you know (or believe) that it won't really give back any of the memory.

So, if your libraries always allocate in multiples of 16, you could make your initial allocation be something like 48 or 80 or 128. 

It would, of course, be nice to have your function learn how big your lines were likely to be by keeping internal statistics or by an argument as a hint.

Ironically, any function that returns an allocated buffer will likely be least efficient in space use with small lines and least efficient in computational speed with large ones. If you don't care about running out of memory at 3% of your nominal capacity when you are processing a file with a bunch of short lines nor in taking 4 times as long as nominal when you have a very few very large lines the one-size-fits-all approach for a library would work fine.

If you can't make your function smart, you can create two or three differnt variations so as to optimize whatever metric you'd like. Having one function that reads chat room squawks (which are typically less than 32 characters), another that reads C code (which have an average around 40 or 50 characters and a max that is defined), and another that reads paragraphs from a novel (where dialogue paragraphs might be short, but descriptions [especially in Russian] can go on for several pages) with different optimization criteria would seem like a good idea.

For the ReadNovelLine function, it would seem reasonable to have an I/O argument that indicated what kind of a thing was expected and what you actually got. If you wanted to get cute, you could even have a secret circular array of the last so many line lengths. Do you want to do it or to do it inteligently?

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web