Dynamic lists of strings in C

[hlubenow]

Hello,

I really like Perl and Python for their flexible lists like @a (Perl) and
a[] (Python), where you can easily store lots of strings or even a whole
text-file.

Now I'm not a C-professional, just a hobby-programmer trying to teach it
myself. I found C rather difficult without those lists (and corresponding
string-functions).
Slowly getting into C-strings, I thought, what if I take a C-string and
treat it as a list, with the elements separated by '\n' ? After all it's
just data stored byte by byte in memory with a closing '\0'. So these
strings could become very long.
Then I wrote some functions based on this idea. They worked, but I had to
realloc() memory for the whole list every list-operation. So this could be
done faster. Someone told me, I could try it with a "linked list".
I read about that and rewrote the functions. To my surprise with structs
this was easier to do than the string-version.
Anyway, below I post an example of what I did (I promise, if code get's any
longer than this, I'll put it up as a file for download). It just defines
one or two list and prints some results, demonstrating the list-functions.

Please take a look at main(). With the comments there, it should give you an
idea of what I'm after.

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

But why for example has this never made its way to the C standard library
like std::vector has to STL in C++ ?

See you

H.

/***********************************************************************/
/*
list.c: Provides linked lists of strings.

Compile with:
gcc -W -Wall -pedantic -ansi -o listexample list.c

Written by hlubenow (Email: (e-mail address removed)), (C) 2007. License: LGPL.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU Library General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with this program; if not, write to the
Free Software Foundation, Inc.,
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/

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

struct list
{
char *content;
struct list *next;
};

char *strMalloc(unsigned int s);
char *strRealloc(char *a, unsigned int s);
struct list *listMalloc(unsigned int s);
struct list *newList(void);
struct list *listUnshift(struct list *head, char *b);
struct list *listAssign(struct list *head, int pos, char *b);
struct list *listAppend(struct list *head, char *b);
struct list *listInsert(struct list *head, int pos, char *b);
int countList(struct list *head);
char *getElement(struct list *head, int pos);
struct list *deleteElement(struct list *head, int pos);
struct list *deleteElements(struct list *head, int start, int end);
struct list *strToList(char *a, char *b);
char *listToStr(struct list *head, char *joinstr);
int printList(struct list *head);
struct list *clearList(struct list *head);


int main(void)
{
struct list *a;
struct list *s;
int count;
char *elem;
char *j;
char *x;
int i;

/* Ok, let's go: */

/* Create a list */
a = newList();

/* Fill it */
a = listAppend(a, "apple");
a = listAppend(a, "banana");
a = listAppend(a, "cherry");
a = listAppend(a, "strawberry");

/* Count it */
count = countList(a);

printf("\nThe list has %d elements now:\n", count);

/* Get single elements from it */
for (i = 0; i < count; i++)
{
elem = getElement(a, i);
printf("%d: %s\n", i, elem);
free(elem);
}

/* Directly define elements */
a = listAssign(a, 1, "pear");

puts("\nList changed:");
printList(a);

/* Even beyond the borders of the list */
a = listAssign(a, 5, "lemon");

puts("\nList changed again:");
printList(a);

count = countList(a);
printf("The list has %d elements now.\n\n", count);

/* You also can insert (listInsert()) and delete elements
(deleteElements()) from the list */

/* Furthermore strings can be split and returned as a list: */

s = strToList("Split me into parts", " ");

count = countList(s);
for (i = 0; i < count; i++)
{
elem = getElement(s, i);
printf("%d: %s\n", i, elem);
free(elem);
}

s = clearList(s);

/* And lists can be joined to a string: */
a = listAssign(a, 4, "mango");
j = listToStr(a, " ");

printf("\nA string: %s\n", j);

free(x);
free(j);

/* Please call this, if you don't need the list anymore: */
a = clearList(a);

return 0;
}


char *strMalloc(unsigned int s)
{
/* Allocates memory for a string, testing if allocation has
been successfull. */

char *a;
if ((a = (char *) malloc(s * sizeof(char))) == NULL)
{
puts("Error allocating memory.");
exit(1);
}

return a;
}


char *strRealloc(char *a, unsigned int s)
{
/* Reallocates memory of a string, testing if reallocation has
been successfull. */

if ((a = (char *) realloc(a, s * sizeof(char))) == NULL)
{
puts("Error reallocating memory.");
exit(1);
}

return a;
}


struct list *listMalloc(unsigned int s)
{
/* Allocates memory for a list, testing if allocation has
been successfull. */

struct list *a;
if ((a = (struct list *) malloc(s * sizeof(struct list))) == NULL)
{
puts("Error allocating list-memory.");
exit(1);
}

return a;
}


/* List functions. */

struct list *newList(void)
{
return NULL;
}

struct list *listUnshift(struct list *head, char *b)
{
/* Inserts an element at the beginning of the list, like
Perl's "unshift()". The first element has to be put into
the list this way. listAppend() and listAssign() take care
of this automatically. */

struct list *c = listMalloc(1);
c->content = strMalloc(strlen(b) + 1);
strcpy(c->content, b);
c->next = head;
return c;
}


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 (head == NULL)
{
head = listUnshift(head, b);
return head;
}

listlen = countList(head);

if (pos >= listlen)
{
for (i = 0; i < pos - listlen; i++)
{
head = listAppend(head, "");
}

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);
return head;
}


struct list *listAppend(struct list *head, char *b)
{
struct list *a;
struct list *c;

if (head == NULL)
{
head = listUnshift(head, b);
return head;
}

c = listMalloc(1);
c->content = strMalloc(strlen(b) + 1);
strcpy(c->content, b);

a = head;

while(a->next)
{
a = a->next;
}
a->next = c;
c->next = NULL;
return head;
}


struct list *listInsert(struct list *head, int pos, char *b)
{
/* Inserts a new element into the list extending the list. */

int listlen;
int i;
struct list *a;
struct list *c;

if (head == NULL || pos == 0)
{
head = listUnshift(head, b);
return head;
}

listlen = countList(head);

if (pos >= listlen)
{
puts ("List index out of range.");
exit(1);
}

c = listMalloc(1);
c->content = strMalloc(strlen(b) + 1);
strcpy(c->content, b);

a = head;

for (i=0; i < pos - 1; i++)
{
a = a->next;
}

c->next = a->next;
a->next = c;
return head;
}


int countList(struct list *head)
{
/* Returns the number of elements of the list.
Also used internally. */

int x = 0;

if (head == NULL)
{
return x;
}

while(head->next)
{
x ++;
head = head->next;
}
x ++;
return x;
}


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);
}

for (i=0; i < pos; i++)
{
head = head->next;
}

a = strMalloc(strlen(head->content) + 1);
strcpy(a, head->content);
return a;
}


struct list *deleteElement(struct list *head, int pos)
{
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);
}

return NULL;
}

a = head;
b = a->next;

if (length == 2)
{
a->next = NULL;
free(b);
return head;
}

for (i=0; i < pos - 1; i++)
{
a = a->next;
}

b = a->next;
c = b->next;

a->next = c;
free(b);

return head;
}


struct list *deleteElements(struct list *head, int start, int end)
{
/* Deletes elements starting from position "start" to position
"end" from the list.

If -1 is passed as "end", the list is deleted
from position "start" to its end. */

int i;
int length = countList(head);

if (start >= length || end >= length
|| start < 0 || end < -1)
{
puts ("List index out of range.");
exit(1);
}

if (start > end)
{
puts ("Invalid values.");
exit(1);
}

if (end == -1)
{
end = length - 1;
}

for (i=start; i <= end; i++)
{
head = deleteElement(head, start);
}

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). */

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);

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);
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);
return b;
}


int printList(struct list *head)
{
while(head->next != NULL)
{
if(*(head->content + strlen(head->content) - 1) != '\n')
{
puts(head->content);
}
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;
}


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);
}

a = head;

for (i=0; i < listlen; i++)
{
b = a;
a = a->next;
}

for (i=listlen - 1; i == 0; i--)
{
if (i > 0)
{
b[i - 1]->next = NULL;
}
free(b);
}

free(b);

return NULL;
}
/***********************************************************************/

 

[Richard Heathfield]

hlubenow said:

Well, what do you think of it (besides me casting malloc() ),

Since you evidently are aware that casting malloc is considered to be a
bad idea here, and yet do it anyway, I don't see any gain to be had in
pointing out other bad ideas in your code.

 

[Bill Pursell]

char *strMalloc(unsigned int s);
char *strRealloc(char *a, unsigned int s);
struct list *listMalloc(unsigned int s);

The above parameters should be of type size_t,
not unsigned.

/* Please call this, if you don't need the list anymore: */
a = clearList(a);

Perhaps clearList is misnamed. Does this free the memory
associated with a? Given the name, I would expect it
not to, but you are using it as if it does.

char *strMalloc(unsigned int s)
{
/* Allocates memory for a string, testing if allocation has
been successfull. */

char *a;
if ((a = (char *) malloc(s * sizeof(char))) == NULL)
{
puts("Error allocating memory.");
exit(1);
}

1) Error messages should go to stderr, not stdout.
2) If you exit, you should exit with EXIT_FAILURE,
but you shouldn't exit here. You should
instead return an error value. (eg NULL).
3) Sizeof(char) is always 1. It makes sense to call
"malloc( s * sizeof *a)", but it pointless to call it
with sizeof(char).

 

[Malcolm McLean]

hlubenow said:



Since you evidently are aware that casting malloc is considered to be a
bad idea here, and yet do it anyway, I don't see any gain to be had in
pointing out other bad ideas in your code.

If you cast malloc() the code might compile under C++. That's legitimate,
even if you happen to disagree. On the other hand exit(1) is non-portable.
No dispute that it should be exit(EXIT_FAILURE).

 

[santosh]

hlubenow wrote:

Anyway, below I post an example of what I did (I promise, if code get's any
longer than this, I'll put it up as a file for download). It just defines
one or two list and prints some results, demonstrating the list-functions.

Please take a look at main(). With the comments there, it should give you an
idea of what I'm after.

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 ?

<snip>

When compiling try using a high optimisation level. The optimiser
often does a lot of analysis of your code and may show more suspicious
constructs. This what I get when I compile your code with the -O3
switch in addition to yours, (gcc.)

$ gcc -Wall -Wextra -ansi -pedantic -O3 -o 01 01.c
01.c: In function 'listToStr':
01.c:524: warning: 'size' may be used uninitialized in this function
01.c: In function 'main':
01.c:126: warning: 'x' is used uninitialized in this function
$

Also try using a static code checking tool like splint. A run here
seems to indicate memory leaks in your code. No offense, but it's too
long for me to check manually.

 

[Richard Heathfield]

Malcolm McLean said:

If you cast malloc() the code might compile under C++.

If that's the only change needed to make the code compile in C++,
there's no point in compiling the code in C++.

 

[hlubenow]

When compiling try using a high optimisation level. The optimiser
often does a lot of analysis of your code and may show more suspicious
constructs. This what I get when I compile your code with the -O3
switch in addition to yours, (gcc.)

$ gcc -Wall -Wextra -ansi -pedantic -O3 -o 01 01.c
01.c: In function 'listToStr':
01.c:524: warning: 'size' may be used uninitialized in this function
01.c: In function 'main':
01.c:126: warning: 'x' is used uninitialized in this function
$

Yes, you're right. I sometimes compile with -O3, but seem to have forgotten
it this time:
At line 524 you can just initialize size as 0 (size = 0, before entering
the while-loop.
In main(), variable x is just not needed in this example (I usually (tried
to) use the functions as a library, so main() was written quite fast to
make the example run as a single file). You can just delete the lines with
"x" in main(), that should be about line 61 and 126.

Also try using a static code checking tool like splint. A run here
seems to indicate memory leaks in your code. No offense, but it's too
long for me to check manually.

That's really one thing I should learn to do. A memory leak - that's bad.
I tried to avoid it, but it happened. So I'll really have do some more
bug-hunting.

I got so much more hints above, especially from Jens Thoms Toerring, I fear,
it will take some time to fix it all - sigh -.

I even think about going back to Python again ...

But thank you very much for your support.

H.

 

[hlubenow]

Also try using a static code checking tool like splint. A run here
seems to indicate memory leaks in your code.

Jens Thoms Toerring mentioned, I didn't do 'free(b->content);' in
function clearList(). That may be the reason for the memory leak.

H.

 

[Peter Nilsson]

hlubenow said:

Since you evidently are aware that casting malloc is considered to
be a bad idea here, and yet do it anyway, I don't see any gain to
be had in pointing out other bad ideas in your code.

From what I've read, redundantly initialising automatic objects is

considered a bad idea here too, but you do it anyway. You have your
reasons, and I'm sure the OP has theirs.

What _you_ gain is up to you. But if WinProcs are okay, why on
earth should perfectly well defined and extremely common ISO C
be out of the question?

 

[Richard Heathfield]

Peter Nilsson said:

considered a bad idea here too, but you do it anyway.

1) I don't agree it's redundant;
2) I don't agree that everyone here apart from me considers it a bad
idea;
3) there are good solid arguments for blanket initialisation.

You have your
reasons, and I'm sure the OP has theirs.

Let's hear it from the OP, then. If those reasons are good ones, we'll
all learn something, right?

What _you_ gain is up to you. But if WinProcs are okay,

Which bit of them did you think wasn't okay?

why on
earth should perfectly well defined and extremely common ISO C
be out of the question?

What makes you think the code is perfectly well-defined? (It isn't.)

 

[Peter Nilsson]

Peter Nilsson said:

1) I don't agree it's redundant;
2) I don't agree that everyone here apart from me considers it a
bad idea;
3) there are good solid arguments for blanket initialisation.


Let's hear it from the OP, then. If those reasons are good ones,
we'll all learn something, right?

Has Plauger failed to supply good reasons, or are you saying you've
learnt nothing from Plauger? Or, have you indeed learnt from Plauger,
but decided that Plauger doesn't count in terms of 'everyone here'?

 

[Richard Heathfield]

Peter Nilsson said:

Has Plauger failed to supply good reasons, or are you saying you've
learnt nothing from Plauger?

P J Plauger is effectively in the same position as an implementor, and
implementors need to, and are able to, do all kinds of stuff that would
not be appropriate for user-programmers. Most people are not in the
position of being an implementor.

Or, have you indeed learnt from Plauger,
but decided that Plauger doesn't count in terms of 'everyone here'?

Whilst I have every respect for him, I think he would be the first to
agree that he is not everyone here.

 

[Peter Nilsson]

Peter Nilsson said:

P J Plauger is effectively in the same position as an implementor,
and implementors need to, and are able to, do all kinds of stuff
that would not be appropriate for user-programmers. Most people are
not in the position of being an implementor.

Which part of the following argument is exclusive to implementors?

Actually, I want to compile our C code with *all* significant C and
C++ compilers.

For one thing, the C++ Standard is intentionally silent (thanks to
me) on whether the C library has "C" or "C++" linkage. We have some
OEM customers who want the C names mangled, to provide link-time
argument type checking, and we have many others who want C names
to look like, well, C names.

For another thing, C++ is indeed in some ways a "better C", as
Stroustrup has been asserting for the past decade and a half. We
find bugs in hoary C code quite often when compiling it as C. So
it's just part of our shop discipline to make sure all our C code
compiles as C++ too.

I agree that you have to write more casts in C++ than in C, and
I agree that casts can sometimes disguise other problems. But it's
been my experience over the past ten years that casts tend to hide
stupid bugs, which are relatively easy to find, while compiling as
C++ tends to find subtler bugs, which are not. The tradeoff has
been well worth it for us.

Whilst I have every respect for him, I think he would be the first
to agree that he is not everyone here.

I'm sure he would. But you introduced the term 'everyone here' in the
sense that one exception (to everyone) is sufficient to refute the
claim that blanket initialisation is 'not a good idea here'. If
Plauger is not a similar exception to your claim that malloc casting
is 'not a good idea here', then what is he?

 

[Richard Heathfield]

Peter Nilsson said:

Which part of the following argument is exclusive to implementors?

Actually, I want to compile our C code with *all* significant C and
C++ compilers.

Most people don't need to do this. I can see why an implementor might
see the need to do it, however. Note that what he calls "C code" cannot
be regarded as C code when being compiled by a C++ compiler. The C++
compiler will deal with it under C++ rules, not C rules.

For one thing, the C++ Standard is intentionally silent (thanks to
me) on whether the C library has "C" or "C++" linkage. We have some
OEM customers who want the C names mangled, to provide link-time
argument type checking, and we have many others who want C names
to look like, well, C names.

Here we see that Mr Plauger himself is directly responsible for one of
the reasons that he has a need to write his code to satisfy two
different language grammars at the same time. This part of the argument
is not just specific to implementors - it is actually specific to Mr
Plauger himself.

For another thing, C++ is indeed in some ways a "better C",

And here Mr Plauger is simply wrong.

 

[Ian Collins]

For another thing, C++ is indeed in some ways a "better C", as
Stroustrup has been asserting for the past decade and a half. We
find bugs in hoary C code quite often when compiling it as C. So
it's just part of our shop discipline to make sure all our C code
compiles as C++ too.

Assuming you intended to write "We find bugs in hoary C code quite often
when compiling it as C++", I agree. The first time I went down this
path, it was with some dodgy C code that had some very unsavoury bugs
caused by type abuse not spotted by the C compiler. I probably wouldn't
have as may issues today, with better C compliers and lint. But some,
inappropriate assignment to enums being the worst, may remain.

I agree that you have to write more casts in C++ than in C, and
I agree that casts can sometimes disguise other problems. But it's
been my experience over the past ten years that casts tend to hide
stupid bugs, which are relatively easy to find, while compiling as
C++ tends to find subtler bugs, which are not. The tradeoff has
been well worth it for us.

The most common bug a cast in C will hide (missing prototypes) can't
happen in C++.
Your signature is missing the space after the --.

 

[Ian Collins]

Peter Nilsson said:


And here Mr Plauger is simply wrong.

Considering C++ extends C, it is a better C if those extensions make the
programmer's job for a particular task easier. If they don't, it isn't.
So some ways is an appropriate qualifier.

 

[Richard Heathfield]

Ian Collins said:

Considering C++ extends C, it is a better C if those extensions
make the programmer's job for a particular task easier. If they
don't, it isn't. So some ways is an appropriate qualifier.

C++ isn't C. It therefore cannot be a "better C". It can't even be a
"different C", except perhaps in the same way that a camel is a
different horse.

One might reasonably claim that C++ is *better than* C, but that doesn't
really mean anything until one defines what one means by "better", and
one must still be prepared for the fact that others might not concur
with that definition.

 

[Richard Bos]

Which part of the following argument is exclusive to implementors?

Actually, I want to compile our C code with *all* significant C and
C++ compilers.
This...

For one thing, the C++ Standard is intentionally silent (thanks to
me) on whether the C library has "C" or "C++" linkage. We have some
OEM customers

....and this.

Richard

 

[Mark McIntyre]

Ian Collins said:


C++ isn't C. It therefore cannot be a "better C".

I think you're being needlessly pendantic here. Clearly the remark was
meant in the same sense that one might call a steam excavator a
better shovel.

doesn't really mean anything until one defines what one means by "better", and
one must still be prepared for the fact that others might not concur
with that definition.

Agreed. The (completely unknown) context was probably relevant
however.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Al Balmer]

We
find bugs in hoary C code quite often when compiling it as C.

(I assume you meant to write C++.) I find bugs in hoary C code quite
often while making it ISO compliant and compiling on a modern C
compiler.

I agree that you have to write more casts in C++ than in C, and
I agree that casts can sometimes disguise other problems. But it's
been my experience over the past ten years that casts tend to hide
stupid bugs, which are relatively easy to find, while compiling as
C++ tends to find subtler bugs, which are not. The tradeoff has
been well worth it for us.

I can't think of any reason that a C++ compiler should be inherently
better at finding bugs in C code. If your C compiler has insufficient
diagnostics, there's always the lint family of products.