Dynamic lists of strings in C

Discussion in 'C Programming' started by hlubenow, Mar 31, 2007.

  1. hlubenow

    hlubenow Guest

    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: ), (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;
    }
    /********************************************************************/
    hlubenow, Mar 31, 2007
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. robin
    Replies:
    10
    Views:
    530
    Dave Hansen
    Apr 12, 2006
  2. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    384
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  3. Ben

    Strings, Strings and Damned Strings

    Ben, Jun 22, 2006, in forum: C Programming
    Replies:
    14
    Views:
    733
    Malcolm
    Jun 24, 2006
  4. hlubenow

    Dynamic lists of strings in C

    hlubenow, Mar 31, 2007, in forum: C Programming
    Replies:
    28
    Views:
    666
    Default User
    Apr 11, 2007
  5. hlubenow

    Dynamic lists of strings in C

    hlubenow, Mar 31, 2007, in forum: C Programming
    Replies:
    1
    Views:
    388
    Jens Thoms Toerring
    Mar 31, 2007
Loading...

Share This Page