Re: Dynamic lists of strings in C
- From: jt@xxxxxxxxxxx (Jens Thoms Toerring)
- Date: 31 Mar 2007 18:54:03 GMT
hlubenow <hlubenow2@xxxxxxx> wrote:
Well, what do you think of it (besides me casting malloc() :) ), that is
what do you think of my code, but also of the idea in general ?
I know, other people have tried something similar before:
http://jengelh.hopto.org/f/libHX/
http://mij.oltrelinux.com/devel/simclist/
https://sourceforge.net/project/showfiles.php?group_id=97342
http://www.pronix.de/comment/site-1038/open-1406/site-1.html
I guess if you have a closer look you will find a lot more of
such examples, I am using something similar (but not restricted
to strings) in one of my programs since quite some time.
But why for example has this never made its way to the C standard library
like std::vector has to STL in C++ ?
Probably because it's rarely needed and there's too much memory
allocation behind the scenes - it looks like for that kind of
reasons not even strdup() was included (a function you could
have used here very well).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list
{
char *content;
struct list *next;
};
That's not a list, that's a list element. And why not store the
length of what content points to, that would safe a lot of un-
necessary strlen() calls. And you probably could avoid of lot
of repeated calculation if you would store the number of elements
somewhere instead of calling countList() over and over again.
And, while you're still at it, you probably should also store
a pointer to the end if the list, so you don't have to loop
over the whole list when you want to append to the end.
char *strMalloc(unsigned int s)
It's much better to always use size_t instead of unsigned int,
since a size_t is always large enough while you can't be sure
with unsigned int and also malloc() etc. expects a variable of
this type as the size argument.
{
/* Allocates memory for a string, testing if allocation has
been successfull. */
char *a;
if ((a = (char *) malloc(s * sizeof(char))) == NULL)
Why, oh why, not
a = malloc( s * sizeof *a )
What do you get from the cast and the sizeof(char), which is
always 1?
{
puts("Error allocating memory.");
exit(1);
With this your code already has become useless for inclusion into
any larger project. If I run out of memory I need to be notified
about the problem and the program can't suddenly die on me. But
if you insist on exit() return EXIT_FAILURE instead of 1 (and
print error messages to stderr).
}
return a;
}
struct list *listAssign(struct list *head, int pos, char *b)
{
/* Lets you define or redefine list-elements.
If pos is greater than the list, the list is extended and the new
element is appended. */
int listlen;
int i;
struct list *a;
if (pos < 0)
{
puts ("List index out of range.");
exit(1);
}
If you test the arguments (laudable) you also should check 'b'
isn't a NULL pointer.
if (head == NULL)
{
head = listUnshift(head, b);
return head;
}
listlen = countList(head);
if (pos >= listlen)
{
for (i = 0; i < pos - listlen; i++)
{
head = listAppend(head, "");
Why assign an empty string to the "undefined" elements in between
instead of having a NULL pointer for those?
}
head = listAppend(head, b);
return head;
}
a = head;
for (i=0; i < pos; i++)
{
a = a->next;
}
a->content = strRealloc(a->content, strlen(b) + 1);
strcpy(a->content, b);
Why not doing the copy also in strMalloc() (making that a
strdup() function) or strRealloc()?
return head;
}
char *getElement(struct list *head, int pos)
{
/* Returns the element at position pos of the list. */
int i;
char *a;
int listlen = countList(head);
if (pos >= listlen)
{
puts ("List index out of range.");
exit(1);
}
So it's ok if 'pos' is negative or 'head' a NULL pointer?
for (i=0; i < pos; i++)
{
head = head->next;
}
Is it a good idea to return an empty string for elements that are
"undefined", i.e. that where created when the user created a
new element with an index larger than the length of the array?
The empty string can very well be also a "legal" entry in the
list.
And you definitely have to document clearly that the user has
to deallocate the memory the return value of this function
points to when (s)he's done with that string.
a = strMalloc(strlen(head->content) + 1);
strcpy(a, head->content);
return a;
}
struct list *deleteElement(struct list *head, int pos)
Since you seem to allow "undefined" elements in between wouldn't
it make a lot more sense to "undefine" the element instead of
removing the element of the list, especially since then all the
indices for strings later in the list get garbled? You at least
should give the user the choice of either a Perl-like delete
(that doesn't remove the element but marks it as undefined) and
a Perl-like splice (that actually removes parts of the array).
{
struct list *a;
struct list *b;
struct list *c;
int i;
int length = countList(head);
if (pos >= length || pos < 0)
{
puts ("List index out of range.");
exit(1);
}
if (length <= 1)
{
if (length == 1)
{
free(head);
Wouldn't you also need to free the string pointed to by that element?
}
return NULL;
}
a = head;
b = a->next;
if (length == 2)
{
a->next = NULL;
free(b);
Same problem here.
return head;
}
for (i=0; i < pos - 1; i++)
{
a = a->next;
}
b = a->next;
c = b->next;
a->next = c;
free(b);
And another time.
return head;
}
struct list *strToList(char *a, char *b)
{
/* Splits a string at "b" and converts the result
into a list. "listUnshift()" instead of "listAppend()" is
used for speed reasons (tricky). */
My guess is that this is just an example of premature optimization...
struct list *head;
char *c;
int lenc;
int lenb;
int i;
int u;
int x;
if (strstr(a, b) == NULL)
{
puts("Splitpart not in string to split !");
return NULL;
}
head = NULL;
c = strMalloc(strlen(a) + 1);
strcpy(c, a);
The following is one of the instances where strtok() could be
used instead - would probably make the code a bit easier to read.
lenc = strlen(c);
lenb = strlen(b);
for(i = lenc - 1; i >= 0; i--)
{
x = 0;
if(i >= lenb - 1 && *(c + i) == *(b + lenb - 1))
{
for(u = 0; u < lenb; u++)
{
if(*(c + i - lenb + 1 + u) == *(b + u))
{
x++;
}
else
{
break;
}
}
if(x == lenb)
{
*(c + i - lenb + 1) = '\0';
if(i != lenc - 1)
{
head = listUnshift(head, c + i + 1);
}
}
}
}
head = listUnshift(head, c);
free(c);
return head;
}
char *listToStr(struct list *head, char *joinstr)
{
/* Join a list to a single string, connecting the
list-elements with "joinstr". */
int size;
char *b;
struct list *a = head;
while(a->next != NULL)
{
size += strlen(a->content);
size += strlen(joinstr);
a = a->next;
}
size += strlen(a->content);
Why not make that
size_t join_len = strlen( joinstr );
for ( a = head; a != NULL; a = a->next )
size += strlen( a->context ) + join_len;
Looks a bit clearer to me. And calling strlen() on 'joinstr' for
each element is a waste of CPU cycles. BTW, you should test if
'joinstr' isn't a NULL pointer.
size ++;
b = strMalloc(size);
strcpy(b, "");
a = head;
while(a->next != NULL)
{
strcat(b, a->content);
strcat(b, joinstr);
a = a->next;
}
strcat(b, a->content);
You better use 'b' as a pointer to the current position in the
string here - strcat() has to over the whole string each time.
What about e.g.
char *p;
sptr = b = strMalloc(size);
for ( a = head; a->next != NULL; a = a->next ) {
strcpy( sptr, a->content;
sptr += strlen( a->content );
strcpy( sptr, joinstr );
sptr += join_len;
}
strcpy( sptr, a->content );
Of course, having the lengths of the strings stored together with
the pointer to the string would avoid lots of calls of strlen().
return b;
}
int printList(struct list *head)
{
while(head->next != NULL)
{
if(*(head->content + strlen(head->content) - 1) != '\n')
{
puts(head->content);
Why would you like to output a '\n' if there's none at the end of
the string?
}
else
{
printf("%s", head->content);
}
head = head->next;
}
if(*(head->content + strlen(head->content) - 1) != '\n')
{
puts(head->content);
}
else
{
printf("%s", head->content);
}
return 0;
}
Why not make that just
int printList( struct list *head )
for ( ; head != NULL; head = head->next )
if ( head->content[ strlen( head->content ) - 1 ] != '\n' )
puts(head->content);
else
printf( "%s", head->content );
return 0;
}
struct list *clearList(struct list *head)
{
/* If you don't need your list any more, you're supposed to call
this to free the memory of each element's struct instance. */
struct list *a;
struct list **b;
int listlen;
int i;
listlen = countList(head);
/* Create "listlen" pointers to each element (structure) of the list. */
if ((b = (struct list **) malloc(listlen * sizeof(struct list *))) ==
NULL)
{
puts("Error allocating memory.");
exit(1);
}
What is that necessary for? And I would be annoyed a lot if my
program would die due to memory exhaustion in a function that
is supposed to free memory.
a = head;
for (i=0; i < listlen; i++)
{
b[i] = a;
a = a->next;
}
for (i=listlen - 1; i == 0; i--)
Is there any reason why you would free the list starting at the end?
And the loop will normally do nothing since the condition for the
end of the loop probably should be 'i >= 0' instead of 'i == 0'.
{
if (i > 0)
{
b[i - 1]->next = NULL;
}
That is absolutely useless.
free(b[i]);
You never free 'b[i]->content'.
}
free(b);
return NULL;Regards, Jens
}
--
\ Jens Thoms Toerring ___ jt@xxxxxxxxxxx
\__________________________ http://toerring.de
.
- References:
- Dynamic lists of strings in C
- From: hlubenow
- Dynamic lists of strings in C
- Prev by Date: Re: C ethics question
- Next by Date: Re: Confused Newbie
- Previous by thread: Dynamic lists of strings in C
- Next by thread: Computer Training Videos "now online"
- Index(es):
Relevant Pages
|
