hope it helps someone. but will serve as a quick access for me.
hope it helps someone. but will serve as a quick access for me.
read_line & read_lines from a FILE *
Code:/* * FIXME * Fails for stdin. * There may be bugs. Please report them. */ char *read_line(FILE *in) { char *line; int line_size = 0, ch; while ((ch = fgetc(in)) != EOF) { line_size++; if (ch == '\n' || ch == '\r') break; } line_size++; line = malloc(line_size); fseek(in, -line_size, SEEK_CUR); fgets(line, line_size, in); return line; } char **read_lines(FILE *in, int *count) { char **lines; int lines_count = 0, index, ch = 0; while ((ch = fgetc(in)) != EOF) { lines_count += (ch == '\n'); } lines = malloc(sizeof(char*) * lines_count + 1); fseek(in, 0, SEEK_SET); for (index = 0; index < lines_count; index++) { lines[index] = read_line(in); } lines[index] = 0; *count = lines_count; return lines; }
Code:/* * FIXME * Fails for stdin. * There may be bugs. Please report them. */ char *read_line(FILE *in) { char *line; int line_size = 0, ch; while ((ch = fgetc(in)) != EOF) { line_size++; if (ch == '\n' || ch == '\r') break; } line_size++; line = malloc(line_size); if (!line) return NULL ; fseek(in, -line_size, SEEK_CUR); fgets(line, line_size, in); return line; } char **read_lines(FILE *in, int *count) { char **lines; int lines_count = 0, index, ch = 0; while ((ch = fgetc(in)) != EOF) { lines_count += (ch == '\n'); } lines = malloc(sizeof(char*) * lines_count + 1); if (!lines) return NULL ; fseek(in, 0, SEEK_SET); for (index = 0; index < lines_count; index++) { lines[index] = read_line(in); } lines[index] = 0; *count = lines_count; return lines; }
Mainframe assembler programmer by trade. C coder when I can.
Well it definitely needs to be made to work with stdin.
Perhaps internal to the functions, store a line as a linked list of fixed-length records.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I agree with Salem - one of the most important places to safely read variable length lines is from stdin - either directly or as a redirect from some file or a pipe from another application. Since stdin (and other character devices) or pipes do not support seeking - only block-devices support seeking - the method of "read it first, then read it again" is not particularly good.
If you don't want to have a fixed size buffer like Salem suggests, use a "double each time it runs out" realloc statement [starting with something reasonable, like 16 or 32 chars]. It's not likely that you will have so many HUGE long input that it makes much difference that you have on average 25% extra space allocated (worst case just under 50%).
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
thanks for all the feedback.
i had thought that to make it work for stdin, i can read all the input and save it to a file, so that the above method works.
otherwise my approach would be:
read a char, add to my buffer, if no EOL yet and buffer is full, resize buffer and just continue.
now i have an array of char*, each char* will/can/may be resized, plus i had to resize the full char* array. too inefficient i thought!
i could not read lines as linked list because, i wanted to run stdlib::qsort() on the lines, so i needed a char* array.
any suggestions?
The overhead of reallocating the buffer is probably smaller than the overhead of reading it twice from a file - those are pretty costly operations overall. As long as you don't get too many re-allocations (and if you start with a 16 character buffer using my suggestion of doubling the buffer each time, then you will have to resize at 32, 64, 128, 256, 512, 1024, 2048, etc. So after 7 times of resizing, you are looking to call fgets on a 1025-2048 character buffer - that is pretty expensive.
Each line is resized indvidually. You may then have to resize the array holding each line, but that's a different matter altogether.
Of course, you could always use insertion sort in a linked list. But quickset method is most likely qsort.
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
thanks Mats, i will post a modified version later.
arithmetic expression parser.
Code:/* * This is an infix expression parser. The parser disregards the precendence of operators. * For example 3 + 4 * 2 = 14 and NOT 11 * * FIXME * There may be bugs. Please report them */ static void arith_err_die(char *p, int offset, char *msg) { printf("%s\n", p); while (offset--) printf(" "); printf("^\n%s\n", msg); exit(1); } static double arith_apply(char op, double a, double b) { double t = 0.0; if (op == '+') { t = a + b; } else if (op == '-') { t = a - b; } else if (op == 'x') { t = a * b; } else if (op == '/') { t = a / b; } else if (op == '^') { t = pow(a, b); } return t; } double arith(char *p) { double a, b; int is_a = 0, is_op = 0; int offset = 0; char *e = p, op; while (*e) { if ((*e == '-' && isdigit(e[1])) || isdigit(*e)) { if (is_a) { if (is_op) { b = atof(e); a = arith_apply(op, a, b); is_op = 0; } else { arith_err_die(p, offset, "bad expression"); } } else { a = atof(e); is_a = 1; } while (isdigit(*e) || *e == 'e' || *e == '+' || *e == '-' || *e == '.') { e++; offset++; } } else if (strchr("+-x/^", *e)) { op = *e; is_op = 1; e++; offset++; } else if (isspace(*e)) { e++; offset++; } else if (*e) { arith_err_die(p, offset, "bad token"); } } if (! is_a) { arith_err_die(p, offset, "bad expression"); } return a; }
Last edited by manav-II; 08-25-2008 at 11:31 PM. Reason: Parsing blooper! :P
postfix expression parser.
Code:/* * FIXME * There may be bugs. Especially with the stack. Please report them. */ static void postfix_err_die(char *p, int offset, char *msg) { printf("%s\n", p); while (offset--) printf(" "); printf("^\n%s\n", msg); exit(1); } static double postfix_apply(char op, double a, double b) { double t; if (op == '+') { t = a + b; } else if (op == '-') { t = a - b; } else if (op == 'x') { t = a * b; } else if (op == '/') { t = a / b; } else if (op == '^') { t = pow(a, b); } return t; } double postfix(char *p) { double *stack, *top; double a, b; int offset, p_size; char *e = p, *t; p_size = strlen(p); stack = malloc(sizeof(double) * p_size); top = stack + p_size; offset = 0; while (*e) { if (*e == '-' && isdigit(e[1]) || isdigit(*e)) { t = e; while (isdigit(*t) || *t == 'e' || *t == '+' || *t == '-' || *t == '.') { t++; offset++; } --top; *top = atof(e); e = t; } else if (strchr("+-x/^", *e)) { if ((&stack[p_size] - top) >= 2){ b = *top; top++; a = *top; top++; --top; *top = postfix_apply(*e, a, b); offset++; e++; } else { postfix_err_die(p, offset, "bad expression"); } } else if (isspace(*e)) { e++; offset++; } else if (*e) { postfix_err_die(p, offset, "bad token"); } else { break; } } if (&stack[p_size] - top > 1) { postfix_err_die(p, offset, "operator expected"); } a = *top; free(stack); return a; }
linked list data structure and utility functions.
Code:/* Bugs? Please report :) */ struct node { int item; struct node *next; struct node *prev; }; struct linked_list { int node_count; struct node *first, *last; }; struct linked_list *ll_new() { struct linked_list *tmp = malloc(sizeof(*tmp)); tmp->first = tmp->last = 0; tmp->node_count = 0; return tmp; } struct node *ll_new_node(int item) { struct node *tmp = malloc(sizeof(*tmp)); tmp->next = tmp->prev = 0; tmp->item = item; return tmp; } void ll_put_first(struct linked_list **this, int item) { struct node *tmp = ll_new_node(item); if (! *this) { *this = ll_new(); } if (! (*this)->first) { (*this)->first = (*this)->last = tmp; } else { tmp->next = (*this)->first; (*this)->first->prev = tmp; (*this)->first = tmp; } (*this)->node_count++; } void ll_put_last(struct linked_list **this, int item) { struct node *tmp = ll_new_node(item); if (! *this) { *this = ll_new(); } if (! (*this)->first) { (*this)->first = (*this)->last = tmp; } else { (*this)->last->next = tmp; tmp->prev = (*this)->last; (*this)->last = tmp; } (*this)->node_count++; } int ll_get_first(struct linked_list **this) { int item; struct node *tmp; if (! *this) { return 0; } tmp = (*this)->first; if ((*this)->first == (*this)->last) { /* Only one node in the list. */ (*this)->first = (*this)->last = 0; } else { (*this)->first = (*this)->first->next; (*this)->first->prev = 0; } item = tmp->item; free(tmp); (*this)->node_count--; return item; } int ll_get_last(struct linked_list **this) { int item; struct node *tmp; if (! *this) { return 0; } tmp = (*this)->last; if ((*this)->first == (*this)->last) { /* Only one node in the list. */ (*this)->first = (*this)->last = 0; } else { (*this)->last = (*this)->last->prev; (*this)->last->next = 0; } item = tmp->item; free(tmp); (*this)->node_count--; return item; } void ll_free(struct linked_list **this) { if (! *this) return; while ((*this)->node_count) { ll_get_first(this); } free(*this); *this = 0; } void ll_print(struct linked_list **this) { struct node *n; if (! *this) { printf("Empty list.\n"); return; } for (n = (*this)->first; n; n = n->next) { printf("[%d] ", n->item); } printf("\n"); }
Last edited by manav-II; 08-25-2008 at 02:57 PM.
Are you even compiling (never mind testing) before you post?Code:intll_new_item(void *data, int n) { inttmp = 0; tmp = malloc(sizeof(*tmp)); tmp->data = malloc(n); memcpy(tmp->data, data, n); return tmp; }
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.