Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Dynamic lists of strings in C

Reply
Thread Tools

Dynamic lists of strings in C

 
 
hlubenow
Guest
Posts: n/a
 
      03-31-2007
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/show...group_id=97342
http://www.pronix.de/comment/site-10...06/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: http://www.velocityreviews.com/forums/(E-Mail 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[i] = a;
a = a->next;
}

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

free(b);

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

 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      03-31-2007
hlubenow said:

<snip>

> 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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
 
Reply With Quote
 
 
 
 
Bill Pursell
Guest
Posts: n/a
 
      03-31-2007
On 31 Mar, 15:54, hlubenow <(E-Mail Removed)> wrote:

> 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.

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


--
Bill Pursell


 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      04-01-2007
"Richard Heathfield" <(E-Mail Removed)> wrote in message
> hlubenow said:
>
> <snip>
>
>> 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.
>

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

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      04-01-2007
hlubenow wrote:

<snip>

> 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.

 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      04-01-2007
Malcolm McLean said:

> "Richard Heathfield" <(E-Mail Removed)> wrote in message
>> hlubenow said:
>>
>> <snip>
>>
>>> 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.
>>

> 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++.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
 
Reply With Quote
 
hlubenow
Guest
Posts: n/a
 
      04-01-2007
santosh wrote:

> 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.
 
Reply With Quote
 
hlubenow
Guest
Posts: n/a
 
      04-01-2007
santosh wrote:

> 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[i]->content);' in
function clearList(). That may be the reason for the memory leak.

H.
 
Reply With Quote
 
Peter Nilsson
Guest
Posts: n/a
 
      04-03-2007
Richard Heathfield <(E-Mail Removed)> wrote:
> hlubenow said:
> > Well, what do you think of it (besides me castingmalloc() ),

>
> 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?

--
Peter

 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      04-03-2007
Peter Nilsson said:

> Richard Heathfield <(E-Mail Removed)> wrote:
>> hlubenow said:
>> > Well, what do you think of it (besides me castingmalloc() ),

>>
>> 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.


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

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Dynamic lists of strings in C hlubenow C Programming 1 03-31-2007 06:54 PM
Dynamic lists of strings in C hlubenow C Programming 0 03-31-2007 03:01 PM
Strings, Strings and Damned Strings Ben C Programming 14 06-24-2006 05:09 AM
List of lists of lists of lists... =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==?= Python 5 05-15-2006 11:47 AM
converting lists to strings to lists robin Python 10 04-12-2006 04:58 PM



Advertisments