A container library in C. Part 2: String collection implementation

Discussion in 'C Programming' started by jacob navia, Sep 28, 2009.

  1. jacob navia

    jacob navia Guest

    This is the implementation part of the string collection container

    ------------------------------------------------------------------

    #include <string.h>
    #include "strcollection.h"

    #ifndef MALLOC
    #include <stdlib.h>
    #define MALLOC(s) malloc(s)
    #define FREE(p) free(p)
    #endif

    // Forward definitions
    static int GetCount(StringCollection *SC);
    static int IsReadOnly(StringCollection *SC);
    static int SetReadOnly(StringCollection *SC, int newval);
    static int Add(StringCollection *SC, const char *newval);
    static int AddRange(StringCollection *SC, const char * const *newvalues);
    static int Clear(StringCollection *SC);
    static int Contains(StringCollection *SC, const char *str);
    static char **CopyTo(StringCollection *SC);
    static int IndexOf(StringCollection *SC, const char *SearchedString);
    static int Insert(StringCollection *SC, const char *str);
    static int InsertAt(StringCollection *SC, int idx, const char *newval);
    static char *IndexAt(StringCollection *SC, int idx);
    static int Remove(StringCollection *SC, const char *str);
    static int RemoveAt(StringCollection *SC, int idx);
    static int Finalize(StringCollection *SC);
    static int GetCapacity(StringCollection *SC);
    static int SetCapacity(StringCollection *SC, int newCapacity);
    static void Apply(StringCollection *SC,
    int(*Applyfn)(char *str, void *arg), void *arg);
    static int *Map(StringCollection *SC, int (*Applyfn)(char *str));
    static int Push(StringCollection *SC, const char *str);
    static char *Pop(StringCollection *SC);
    static char *ReplaceAt(StringCollection *SC, int idx, const char *str);
    static StringCollectionFunctions lpVtableSC = {
    GetCount, IsReadOnly, SetReadOnly, Add, AddRange,
    Clear, Contains, CopyTo, IndexOf, Insert,
    InsertAt, IndexAt, Remove, RemoveAt,
    Finalize, GetCapacity, SetCapacity, Apply,
    Map, Push, Pop, ReplaceAt,
    };

    static char *DuplicateString(const char *str)
    {
    char *result;

    if (str == NULL)
    return NULL;
    result = MALLOC(strlen(str) + 1);
    if (result == NULL)
    return NULL;
    return strcpy(result, str);
    }

    #define SC_READONLY 1
    #define CHUNKSIZE 20
    #define DEFAULT_START_SIZE 0

    StringCollection *newStringCollection(int startsize)
    {
    StringCollection *SC = MALLOC(sizeof(*SC));

    if (SC == NULL)
    return NULL;

    SC->lpVtbl = &lpVtableSC;
    SC->count = 0;
    SC->contents = NULL;
    SC->capacity = 0;
    SC->flags = 0;

    if (startsize == 0)
    startsize = DEFAULT_START_SIZE;
    if (startsize) {
    SC->capacity = startsize;
    SC->contents = MALLOC(startsize * sizeof(*SC->contents));
    if (SC->contents == NULL) {
    FREE(SC);
    return NULL;
    }
    // useless, for cleanliness only
    memset(SC->contents, 0, startsize * sizeof(*SC->contents));
    }
    return SC;
    }

    static int GetCount(StringCollection *SC)
    {
    return SC->count;
    }

    static int IsReadOnly(StringCollection *SC)
    {
    return (SC->flags & SC_READONLY) ? 1 : 0;
    }

    static int SetReadOnly(StringCollection *SC, int newval)
    {
    int oldval = (SC->flags & SC_READONLY) ? 1 : 0;

    if (newval)
    SC->flags |= SC_READONLY;
    else
    SC->flags &= ~SC_READONLY;
    return oldval;
    }

    static int Resize(StringCollection *SC)
    {
    int newcapacity = SC->capacity + CHUNKSIZE;
    char **newcontents;

    newcontents = MALLOC(newcapacity * sizeof(*newcontents));
    if (newcontents == NULL)
    return 0;
    memcpy(newcontents, SC->contents, SC->count * sizeof(*newcontents));
    // useless, for cleanliness only
    memset(newcontents + SC->count * sizeof(*newcontents),
    0, (newcapacity - SC->count) * sizeof(*newcontents));
    FREE(SC->contents);
    SC->contents = newcontents;
    SC->capacity = newcapacity;
    return 1;
    }

    static int Add(StringCollection *SC, const char *str)
    {
    char *newval = NULL;

    if (SC->flags & SC_READONLY)
    return -1;
    if (SC->count >= SC->capacity) {
    if (!Resize(SC))
    return 0;
    }
    if (str) {
    newval = DuplicateString(str);
    if (newval == NULL)
    return 0;
    }
    SC->contents[SC->count] = newval;
    return ++SC->count;
    }

    static int AddRange(StringCollection *SC, const char * const *data)
    {
    int i;

    if (SC->flags & SC_READONLY)
    return 0;
    for (i = 0; data != NULL; i++) {
    int r = Add(SC, data);
    if (r <= 0)
    return r;
    }
    return SC->count;
    }

    static int Clear(StringCollection *SC)
    {
    int oldval = SC->count, i;

    if (SC->flags & SC_READONLY)
    return 0;
    for (i = 0; i < SC->count; i++) {
    FREE(SC->contents);
    SC->contents = NULL;
    }
    SC->count = 0;
    return oldval;
    }

    static int Contains(StringCollection *SC, const char *str)
    {
    return (IndexOf(SC, str) >= 0);
    }

    static char **CopyTo(StringCollection *SC)
    {
    char **result = MALLOC((SC->count + 1) * sizeof(*result));
    int i;

    if (result == NULL)
    return NULL;
    for (i = 0; i < SC->count; i++) {
    // XXX: MALLOC failure ignored
    result = DuplicateString(SC->contents);
    }
    result = NULL;
    return result;
    }

    #ifdef __LCC__
    /* The lcc-win compiler allows operator overloading, and allows using
    this abstract data type with the more natural [ ] operators */
    char * __declspec(naked) operator[](StringCollection *SC, int idx)
    {
    }
    #endif

    static int IndexOf(StringCollection *SC, const char *str)
    {
    int c, i;

    if (str == NULL) {
    for (i = 0; i < SC->count; i++) {
    if (SC->contents == NULL)
    return i;
    }
    return -1;
    } else {
    c = *str;
    for (i = 0; i < SC->count; i++) {
    if (SC->contents == NULL)
    continue;
    if (c == SC->contents[0] && !strcmp(SC->contents, str))
    return i;
    }
    return -1;
    }
    }

    static char *IndexAt(StringCollection *SC, int idx)
    {
    if (idx < 0 || idx >= SC->count)
    return NULL;
    return SC->contents[idx];
    }

    static int InsertAt(StringCollection *SC, int idx, const char *str)
    {
    char *newval = NULL;

    if (SC->flags & SC_READONLY)
    return 0;
    if (idx < 0 || idx > SC->count)
    return -1;
    if (SC->count >= SC->capacity) {
    if (!Resize(SC))
    return 0;
    }
    if (str) {
    newval = DuplicateString(str);
    if (newval == NULL)
    return 0;
    }
    if (idx < SC->count) {
    memmove(SC->contents + idx + 1, SC->contents + idx,
    (SC->count - idx) * sizeof(*SC->contents));
    }
    SC->contents[idx] = newval;
    return ++SC->count;
    }

    static int Insert(StringCollection *SC, const char *str)
    {
    return InsertAt(SC, 0, str);
    }

    static int RemoveAt(StringCollection *SC, int idx)
    {
    if (idx < 0 || idx >= SC->count)
    return -1;
    FREE(SC->contents[idx]);
    memmove(SC->contents + idx, SC->contents + idx + 1,
    (SC->count - idx - 1) * sizeof(*SC->contents));
    SC->contents[--SC->count] = NULL;
    return SC->count;
    }

    static int Remove(StringCollection *SC, const char *str)
    {
    int idx = IndexOf(SC, str);
    if (idx < 0)
    return idx;
    return RemoveAt(SC, idx);
    }

    static int Push(StringCollection *SC, const char *str)
    {
    char *newval = NULL;

    if (SC->flags & SC_READONLY)
    return 0;
    if (SC->count >= SC->capacity) {
    if (!Resize(SC))
    return 0;
    }
    if (str) {
    newval = DuplicateString(str);
    if (newval == NULL)
    return 0;
    }
    SC->contents[SC->count++] = newval;
    return SC->count;
    }

    static char * Pop(StringCollection *SC)
    {
    char *result;

    if ((SC->flags & SC_READONLY) || SC->count == 0)
    return NULL;
    SC->count--;
    result = SC->contents[SC->count];
    SC->contents[SC->count] = NULL;
    return result;
    }

    static int Finalize(StringCollection *SC)
    {
    int result = SC->count, i;

    for (i = 0; i < SC->count; i++) {
    FREE(SC->contents);
    }
    FREE(SC->contents);
    FREE(SC);
    return result;
    }

    static int GetCapacity(StringCollection *SC)
    {
    return SC->capacity;
    }

    static int SetCapacity(StringCollection *SC, int newcapacity)
    {
    char **newcontents;

    if (newcapacity < 0)
    return 0;

    newcontents = MALLOC(newcapacity * sizeof(*newcontents));
    if (newcontents == NULL)
    return 0;

    while (SC->count > newcapacity) {
    FREE(SC->contents[--SC->count]);
    }
    memcpy(newcontents, SC->contents, SC->count * sizeof(*newcontents));
    // useless, for cleanliness only
    memset(newcontents + SC->count * sizeof(*newcontents),
    0, (newcapacity - SC->count) * sizeof(*newcontents));
    FREE(SC->contents);
    SC->contents = newcontents;
    SC->capacity = newcapacity;
    return 1;
    }

    static void Apply(StringCollection *SC,
    int (*Applyfn)(char *str, void *arg), void *arg)
    {
    int i;

    for (i = 0; i < SC->count; i++) {
    Applyfn(SC->contents, arg);
    }
    }

    static int *Map(StringCollection *SC, int (*Applyfn)(char *str))
    {
    int *result = MALLOC(SC->count * sizeof(*result));
    int i;

    if (result == NULL)
    return NULL;
    for (i = 0; i < SC->count; i++) {
    result = Applyfn(SC->contents);
    }
    return result;
    }

    #ifdef __LCC__
    /* The lcc-win compiler allows operator overloading, and allows using
    this abstract data type with the more natural [ ]= operators */
    char * __declspec(naked) operator[]=(StringCollection *SC,
    int idx, char *newval)
    {
    }
    #endif

    static char *ReplaceAt(StringCollection *SC, int idx, const char *str)
    {
    char *newval = NULL;

    if (SC->flags & SC_READONLY)
    return NULL;
    if (idx < 0 || idx > SC->count)
    return NULL;
    if (idx == SC->count) {
    if (!Add(SC, str))
    return NULL;
    } else {
    if (str) {
    newval = DuplicateString(str);
    if (newval == NULL)
    return NULL;
    }
    FREE(SC->contents[idx]);
    SC->contents[idx] = newval;
    }
    return SC->contents[idx];
    }

    #ifdef TEST

    #include <stdio.h>

    static void PrintStringCollection(StringCollection *SC)
    {
    int i;

    printf("Count %d, Capacity %d {\n",
    SC->count, SC->capacity);
    for (i = 0; i < SC->count; i++) {
    printf(" \"%s\",\n", SC->lpVtbl->IndexAt(SC, i));
    }
    printf("}\n");
    }

    int main(void)
    {
    StringCollection *SC;
    int count;
    char *p;

    SC = newStringCollection(0);
    printf("newStringCollection(%d)\n", 0);
    PrintStringCollection(SC);
    SC->lpVtbl->Finalize(SC);

    SC = newStringCollection(10);
    printf("newStringCollection(%d)\n", 10);
    PrintStringCollection(SC);
    printf("Add \"%s\"\n", "Martin");
    SC->lpVtbl->Add(SC, "Martin");
    printf("Insert \"%s\"\n", "Jacob");
    SC->lpVtbl->Insert(SC, "Jakob");
    count = SC->lpVtbl->GetCount(SC);
    if (count != 2)
    printf("Count should be 2, is %d\n", count);
    PrintStringCollection(SC);
    printf("Insert at %d \"%s\"\n", 1, "Position 1");
    SC->lpVtbl->InsertAt(SC, 1, "Position 1");
    printf("Insert at %d \"%s\"\n", 2, "Position 2");
    SC->lpVtbl->InsertAt(SC, 2, "Position 2");
    PrintStringCollection(SC);
    printf("Remove \"%s\"\n", "Jacob");
    SC->lpVtbl->Remove(SC, "Jakob");
    PrintStringCollection(SC);
    printf("Push \"%s\"\n", "pushed");
    SC->lpVtbl->Push(SC, "pushed");
    PrintStringCollection(SC);
    p = SC->lpVtbl->Pop(SC);
    FREE(p);
    printf("Pop -> \"%s\"\n", p);
    PrintStringCollection(SC);
    p = SC->lpVtbl->IndexAt(SC, 1);
    printf("IndexAt %d -> \"%s\"\n", 1, p);
    PrintStringCollection(SC);
    SC->lpVtbl->Finalize(SC);

    return 0;
    }
    #endif
    jacob navia, Sep 28, 2009
    #1
    1. Advertising

  2. On Mon, 28 Sep 2009 12:07:30 +0200, jacob navia <>
    wrote:

    >This is the implementation part of the string collection container
    >
    >------------------------------------------------------------------
    >
    >#include <string.h>
    >#include "strcollection.h"
    >
    >#ifndef MALLOC
    >#include <stdlib.h>
    >#define MALLOC(s) malloc(s)
    >#define FREE(p) free(p)
    >#endif

    snip

    >#define SC_READONLY 1
    >#define CHUNKSIZE 20
    >#define DEFAULT_START_SIZE 0
    >
    >StringCollection *newStringCollection(int startsize)
    >{
    > StringCollection *SC = MALLOC(sizeof(*SC));
    >
    > if (SC == NULL)
    > return NULL;
    >
    > SC->lpVtbl = &lpVtableSC;
    > SC->count = 0;
    > SC->contents = NULL;
    > SC->capacity = 0;
    > SC->flags = 0;
    >
    > if (startsize == 0)
    > startsize = DEFAULT_START_SIZE;
    > if (startsize) {


    If the function was called with an argument of 0, startsize is still 0
    and this block is not executed. SC->contents is still NULL.

    > SC->capacity = startsize;
    > SC->contents = MALLOC(startsize * sizeof(*SC->contents));
    > if (SC->contents == NULL) {
    > FREE(SC);
    > return NULL;
    > }
    > // useless, for cleanliness only
    > memset(SC->contents, 0, startsize * sizeof(*SC->contents));


    And this invokes undefined behavior when SC->contents is NULL.

    > }
    > return SC;
    >}


    --
    Remove del for email
    Barry Schwarz, Sep 28, 2009
    #2
    1. Advertising

  3. On Mon, 28 Sep 2009 09:27:01 -0700, Barry Schwarz <>
    wrote:

    >On Mon, 28 Sep 2009 12:07:30 +0200, jacob navia <>
    >wrote:
    >
    >>This is the implementation part of the string collection container
    >>
    >>------------------------------------------------------------------
    >>
    >>#include <string.h>
    >>#include "strcollection.h"
    >>
    >>#ifndef MALLOC
    >>#include <stdlib.h>
    >>#define MALLOC(s) malloc(s)
    >>#define FREE(p) free(p)
    >>#endif

    >snip
    >
    >>#define SC_READONLY 1
    >>#define CHUNKSIZE 20
    >>#define DEFAULT_START_SIZE 0
    >>
    >>StringCollection *newStringCollection(int startsize)
    >>{
    >> StringCollection *SC = MALLOC(sizeof(*SC));
    >>
    >> if (SC == NULL)
    >> return NULL;
    >>
    >> SC->lpVtbl = &lpVtableSC;
    >> SC->count = 0;
    >> SC->contents = NULL;
    >> SC->capacity = 0;
    >> SC->flags = 0;
    >>
    >> if (startsize == 0)
    >> startsize = DEFAULT_START_SIZE;
    >> if (startsize) {

    >
    >If the function was called with an argument of 0, startsize is still 0
    >and this block is not executed. SC->contents is still NULL.
    >
    >> SC->capacity = startsize;
    >> SC->contents = MALLOC(startsize * sizeof(*SC->contents));
    >> if (SC->contents == NULL) {
    >> FREE(SC);
    >> return NULL;
    >> }
    >> // useless, for cleanliness only
    >> memset(SC->contents, 0, startsize * sizeof(*SC->contents));

    >
    >And this invokes undefined behavior when SC->contents is NULL.


    Except of course that it never gets invoked and I should learn to
    count braces more carefully.

    >
    >> }
    >> return SC;
    >>}


    --
    Remove del for email
    Barry Schwarz, Sep 29, 2009
    #3
  4. jacob navia

    jacob navia Guest

    Barry Schwarz a critics :
    >> And this invokes undefined behavior when SC->contents is NULL.

    >
    > Except of course that it never gets invoked and I should learn to
    > count braces more carefully.


    To err is human... The catastrophe with my failed release should
    prove that
    :)

    Thanks for reading my code.

    jacob
    jacob navia, Sep 29, 2009
    #4
    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. Øyvind Isaksen
    Replies:
    1
    Views:
    964
    Øyvind Isaksen
    May 18, 2007
  2. jacob navia

    A container library in C. Part 1: Header file

    jacob navia, Sep 28, 2009, in forum: C Programming
    Replies:
    14
    Views:
    674
    Tech07
    Oct 3, 2009
  3. jacob navia
    Replies:
    5
    Views:
    500
    jacob navia
    Sep 28, 2009
  4. jacob navia
    Replies:
    10
    Views:
    641
    jacob navia
    Oct 1, 2009
  5. Alan Curry

    review of the "container library", part 1/?

    Alan Curry, Mar 1, 2011, in forum: C Programming
    Replies:
    18
    Views:
    653
    jacob navia
    Mar 11, 2011
Loading...

Share This Page