A container library in C Part 4. The arraylist container

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

  1. jacob navia

    jacob navia Guest

    This implements the ararylist container arraylist.c
    ----------------------------------------------------
    #include "containers.h"

    static int GetCount( ArrayList *AL);
    static int IsReadOnly( ArrayList *AL);
    static int SetReadOnly( ArrayList *AL,int newval);
    static int Add( ArrayList *AL,void *newval);
    static int AddRange( ArrayList *AL,void **newvalues);
    static int Clear( ArrayList *AL);
    static bool Contains( ArrayList *AL,void *str);
    static void **CopyTo( ArrayList *AL);
    static int IndexOf( ArrayList *AL,void *SearchedElement);
    static int Insert( ArrayList *AL,void *);
    static int InsertAt( ArrayList *AL,int idx,void *newval);
    static void *IndexAt( ArrayList *AL,int idx);
    static int Remove( ArrayList *AL,void *);
    static int RemoveAt( ArrayList *AL,int idx);
    static int Finalize( ArrayList *AL);
    static int GetCapacity( ArrayList *AL);
    static bool SetCapacity( ArrayList *AL,int newCapacity);
    static void Apply(ArrayList *AL,int(*Applyfn)(void *,void *),void *arg);
    static int Push(ArrayList *AL,void *str);
    static void *Pop(ArrayList *AL);
    static void *ReplaceAt(ArrayList *AL,int idx,void *newval);
    static int IsCaseSensitive(ArrayList *AL);
    static int SetCaseSensitive(ArrayList *AL,int newval);
    static ArrayListInterface lpVtableAL = {
    GetCount, IsReadOnly, SetReadOnly, Add, AddRange, Clear, Contains,
    CopyTo, IndexOf, Insert, InsertAt, IndexAt, Remove, RemoveAt,
    Finalize, GetCapacity, SetCapacity, Apply, Push, Pop, ReplaceAt,
    };
    #ifndef NO_GC
    #include <gc.h>
    #define MALLOC GC_malloc
    #define FREE(a)
    #else
    #include <stdlib.h>
    #define MALLOC malloc
    #define FREE free
    #endif

    #ifndef DEFAULT_START_SIZE
    #define DEFAULT_START_SIZE 20
    #endif

    static void *DuplicateElement(void *str,int size)
    {
    if (str == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    return NULL;
    }
    void *result = MALLOC(size);
    if (result == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_NOMEMORY);
    return NULL;
    }
    else memcpy(result,str,size);
    return result;
    }

    #define AL_READONLY 1
    #define AL_IGNORECASE 2
    #define CHUNKSIZE 20

    ArrayList newArrayList(size_t elementsize,int startsize)
    {
    ArrayList result;
    if ((elementsize &0x800000) || elementsize == 0)
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    memset(&result,0,sizeof(result));
    result.count = 0;
    if (startsize <= 0)
    startsize = DEFAULT_START_SIZE;
    result.contents = MALLOC(startsize*elementsize);
    if (result.contents == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_NOMEMORY);
    }
    else {
    memset(result.contents,0,elementsize*startsize);
    result.capacity = startsize;
    result.lpVtbl = &lpVtableAL;
    result.ElementSize = elementsize;
    }
    return result;
    }

    static int GetCount(ArrayList *AL)
    {
    return AL->count;
    }
    static int IsReadOnly(struct _ArrayList *AL)
    {
    return AL->flags & AL_READONLY ? 1 : 0;
    }
    static int SetReadOnly(struct _ArrayList *AL,int newval)
    {
    int oldval = AL->flags & AL_READONLY ? 1 : 0;
    if (newval)
    AL->flags |= AL_READONLY;
    else
    AL->flags &= ~AL_READONLY;
    return oldval;
    }


    static int Resize(ArrayList *AL)
    {
    int newcapacity = AL->capacity + CHUNKSIZE;
    void **oldcontents = AL->contents;
    AL->contents = MALLOC(newcapacity*sizeof(void *));
    if (AL->contents == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_NOMEMORY);
    AL->contents = oldcontents;
    return 0;
    }
    memset(AL->contents,0,sizeof(void *)*newcapacity);
    memcpy(AL->contents,oldcontents,AL->count*sizeof(void *));
    AL->capacity = newcapacity;
    FREE(oldcontents);
    return 1;
    }

    static int Add(ArrayList *AL,void *newval)
    {
    if (AL->flags & AL_READONLY)
    return -1;
    if (newval == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    return -2;
    }
    if (AL->count >= AL->capacity) {
    if (!Resize(AL))
    return 0;
    }

    AL->contents[AL->count] = DuplicateElement(newval,AL->ElementSize);
    if (AL->contents[AL->count] == NULL) {
    return 0;
    }
    AL->count++;
    return AL->count;
    }

    static int AddRange(struct _ArrayList * AL,void **data)
    {
    int i = 0,c;
    if (AL->flags & AL_READONLY)
    return 0;
    if (data == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    return -2;
    }
    c = AL->count;
    while (data != NULL) {
    int r = Add(AL,data);
    if (r <= 0) {
    while (AL->count > c) {
    Pop(AL);
    }
    return r;
    }
    i++;
    }
    return AL->count;
    }

    static int Clear(struct _ArrayList *AL)
    {
    int oldval = AL->count;
    if (AL->flags & AL_READONLY)
    return 0;
    for (int i=0; i<AL->count;i++) {
    FREE(AL->contents);
    AL->contents = NULL;
    }
    AL->count = 0;
    return oldval;
    }

    static bool Contains(ArrayList *AL,void *str)
    {
    if (str == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    return false;
    }
    for (int i = 0; i<AL->count;i++) {
    if (!memcmp(AL->contents,str,AL->ElementSize))
    return true;
    }
    return false;
    }

    static void **CopyTo(ArrayList *AL)
    {
    void **result = MALLOC(AL->count*sizeof(void *));
    int i;
    if (result == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_NOMEMORY);
    return NULL;
    }
    for (i=0; i<AL->count;i++) {
    result = DuplicateElement(AL->contents,AL->ElementSize);
    if (result == NULL) {
    return NULL;
    }
    }
    result = NULL;
    return result;
    }

    static int IndexOf(ArrayList *AL,void *str)
    {
    int i;

    if (str == NULL)
    return -1;
    for (i=0; i<AL->count;i++) {
    if (!memcmp(AL->contents,str,AL->ElementSize)) {
    return i;
    }
    }
    return -1;
    }

    static void *IndexAt(ArrayList *AL,int idx)
    {
    if (idx >=AL->count || idx < 0) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    return NULL;
    }
    return AL->contents[idx];
    }
    #if 0
    // Under lcc-win you can use the more natural [ ] syntax.
    void *operator[](ArrayList *AL,int idx)
    {
    return IndexAt(AL,idx);
    }
    #endif

    static int InsertAt(ArrayList *AL,int idx,void *newval)
    {
    if (AL->flags & AL_READONLY)
    return 0;
    if (idx < 0 || idx > AL->count) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_INDEX);
    return -1;
    }
    if (AL->count >= (AL->capacity-1)) {
    if (!Resize(AL))
    return 0;
    }
    if (idx == 0) {
    if (AL->count > 0)
    memmove(AL->contents+1,AL->contents,AL->count*sizeof(void *));
    AL->contents[0] = newval;
    }
    else if (idx == AL->count) {
    AL->contents[idx] = newval;
    }
    else if (idx < AL->count) {
    memmove(AL->contents+idx+1,AL->contents+idx,(AL->count-idx+1)*sizeof(void *));
    AL->contents[idx] = newval;
    }
    AL->count++;
    return AL->count;
    }

    static int Insert(ArrayList *AL,void *newval)
    {
    if (AL->flags & AL_READONLY)
    return 0;
    return InsertAt(AL,0,newval);
    }

    static int RemoveAt(ArrayList *AL,int idx)
    {
    if (idx >= AL->count || idx < 0 || (AL->flags & AL_READONLY))
    return -1;
    if (AL->count == 0)
    return -2;
    FREE(AL->contents[idx]);
    if (idx < (AL->count-1)) {
    memmove(AL->contents+idx,AL->contents+idx+1,
    (AL->count-idx)*sizeof(void *));
    }
    AL->contents[AL->count-1]=NULL;
    AL->count--;
    return AL->count;
    }

    static int Remove(ArrayList *AL,void *str)
    {
    int idx = IndexOf(AL,str);
    if (idx < 0)
    return idx;
    return RemoveAt(AL,idx);
    }

    static int Push(ArrayList *AL,void *str)
    {
    void *r;
    if (AL->flags&AL_READONLY)
    return 0;
    if (AL->count >= AL->capacity-1) {
    if (!Resize(AL))
    return 0;
    }
    r = DuplicateElement(str,AL->ElementSize);
    if (r == NULL)
    return 0;
    AL->contents[AL->count++] = r;
    return AL->count;
    }

    static void * Pop(ArrayList *AL)
    {
    void *result;
    if ((AL->flags&AL_READONLY) || AL->count == 0)
    return NULL;
    AL->count--;
    result = AL->contents[AL->count];
    AL->contents[AL->count] = NULL;
    return result;
    }

    static int Finalize(ArrayList *AL)
    {
    int result = AL->count;
    for (int i=0; i<AL->count;i++) {
    FREE(AL->contents);
    }
    FREE(AL->contents);
    FREE(&AL);
    return result;
    }

    static int GetCapacity(ArrayList *AL)
    {
    return AL->capacity;
    }

    static bool SetCapacity(struct _ArrayList *AL,int newCapacity)
    {
    if (AL->count != 0)
    return false;
    FREE(AL->contents);
    AL->contents = MALLOC(newCapacity*sizeof(void *));
    if (AL->contents == NULL) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_NOMEMORY);
    return false;
    }
    memset(AL->contents,0,sizeof(void *)*newCapacity);
    AL->capacity = newCapacity;
    return 1;
    }

    static void Apply(struct _ArrayList *AL,int (*Applyfn)(void *,void *),void *arg)
    {
    for (int i=0; i<AL->count;i++) {
    Applyfn(AL->contents,arg);
    }
    }

    #if 0
    // Under lcc-win you can use the more natural [ ] syntax
    void * __declspec(naked) operator[]=(ArrayList *AL,int idx,void *newval)
    {
    }
    #endif

    static int ReplaceAt(ArrayList *AL,int idx,void *newval)
    {
    if (AL->flags & AL_READONLY)
    return 0;
    if (idx < 0 || idx > AL->count)
    return 0;
    FREE(AL->contents[idx]);
    AL->contents[idx] = newval;
    return 1;
    }
    #if 0
    void *operator[]=(ArrayList AL,int idx,void *newval)
    {
    return ReplaceAt(AL,idx,newval);
    }
    #endif


    #ifdef TEST
    #include <stdio.h>
    static void PrintArrayList(ArrayList *AL)
    {
    printf("Count %d, Capacity %d\n",AL->count,AL->capacity);
    for (int i=0; i<AL->count;i++) {
    printf("%s\n",AL);
    }
    printf("\n");
    }
    int main(void)
    {
    ArrayList AL = newArrayList();
    char *p;
    AL.lpVtbl->Add(&AL,"Martin");
    AL.lpVtbl->Insert(&AL,"Jakob");
    if (!AL.lpVtbl->Contains(&AL,"Martin")) {
    printf("error, string not found!\n");
    }
    printf("Count should be 2, is %d\n",AL->GetCount());
    PrintArrayList(&AL);
    AL.lpVtbl->InsertAt(1,"Position 1");
    AL.lpVtbl->InsertAt(2,"Position 2");
    PrintArrayList(AL);
    AL.lpVtbl->Remove("Jakob");
    PrintArrayList(AL);
    AL.lpVtbl->Push("pushed");
    PrintArrayList(&AL);
    AL.lpVtbl->Pop();
    PrintArrayList(AL);
    p = AL[1];
    printf("Item position 1:%s\n",p);
    PrintArrayList(&AL);
    }
    #endif
     
    jacob navia, Sep 28, 2009
    #1
    1. Advertising

  2. jacob navia

    jacob navia Guest

    Sorry, an error in line 23:
    Should be:
    static int ReplaceAt(ArrayList *AL,int idx,void *newval);
     
    jacob navia, Sep 28, 2009
    #2
    1. Advertising

  3. "jacob navia" <> wrote in message
    news:h9q6ne$1l3$...
    > Sorry, an error in line 23:
    > Should be:
    > static int ReplaceAt(ArrayList *AL,int idx,void *newval);


    I am curious as to why you are using a signed type for the `idx' parameter?
    IVMHO, it would be "easier" to use `size_it's, or some other unsigned type
    because you don't have to always check to see if the index is less than
    zero.
     
    Chris M. Thomasson, Sep 29, 2009
    #3
  4. jacob navia

    jacob navia Guest

    christian.bau a écrit :
    > Just saying that the ability to change an object from being read-only
    > to being modifiable makes some very important optimisations (like very
    > fast copying) impossible. Read up on Apple's Core Foundation library
    > (which is in actual use by a significant number of users).



    How do you destroy a read-only object?

    You *must* change it to read/write!

    I do not see how you could initially add objects to a read only
    list. You *have* to get rid of the read-only flag when initializing
    and when destroying the object.
     
    jacob navia, Sep 29, 2009
    #4
  5. jacob navia

    jacob navia Guest

    Mark McIntyre a écrit :
    > jacob navia wrote:
    >> christian.bau a écrit :
    >>> Just saying that the ability to change an object from being read-only
    >>> to being modifiable makes some very important optimisations (like very
    >>> fast copying) impossible. Read up on Apple's Core Foundation library
    >>> (which is in actual use by a significant number of users).

    >>
    >>
    >> How do you destroy a read-only object?

    >
    > Read-only is not the same as indestructible. Consider that a programme
    > may create lots of readonly objects when it is initialised and delete
    > them all when it terminates.
    >
    > Also, what is the scope of something like
    >
    > void test()
    > {
    > {
    > const int i=5;
    > }
    > }
    >


    Sure, the storage of i goes away but no explicit destruction is done.
    For a list, you should free the storage when you destroy it and that
    needs a call to free(). Only writable lists can be destroyed, so it is
    not possible to destroy a read only list

    >> I do not see how you could initially add objects to a read only
    >> list.

    >
    > perhaps something like
    >
    > const int mylist[]={4,6,7,54};
    >


    That is an array, not a list. Arrays are supported by the language
    natively, and that is not the case for lists.
     
    jacob navia, Sep 29, 2009
    #5
  6. jacob navia <> writes:
    [...]
    > Sure, the storage of i goes away but no explicit destruction is done.
    > For a list, you should free the storage when you destroy it and that
    > needs a call to free(). Only writable lists can be destroyed, so it is
    > not possible to destroy a read only list

    [...]

    It depends on how your list is implemented. If a list object
    contains pointers to other data, that other data can be modified
    (destroyed, whatever) without modifying the list object itself.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Sep 30, 2009
    #6
  7. jacob navia

    Phil Carmody Guest

    Mark McIntyre <> writes:
    > jacob navia wrote:
    >> Mark McIntyre a écrit :
    >>> jacob navia wrote:
    >>>>
    >>>> How do you destroy a read-only object?
    >>>
    >>> Read-only is not the same as indestructible. Consider that a
    >>> programme may create lots of readonly objects when it is
    >>> initialised and delete them all when it terminates.
    >>>
    >>> Also, what is the scope of something like
    >>>
    >>> void test()
    >>> {
    >>> {
    >>> const int i=5;
    >>> }
    >>> }
    >>>

    >>
    >> Sure, the storage of i goes away but no explicit destruction is done.

    >
    > It is destroyed, and is thus an example of gow a read-only object is
    > destroyed. And from a purely pedantic point of view, I explicitly
    > caused it to be destroyed by typing the scope-ending brace.
    >
    >>>> I do not see how you could initially add objects to a read only
    >>>> list.
    >>>
    >>> perhaps something like
    >>>
    >>> const int mylist[]={4,6,7,54};

    >>
    >> That is an array, not a list. Arrays are supported by the language
    >> natively, and that is not the case for lists.

    >
    > I assume you don't understand the english phrase "something like".


    And an array can validly be considered a list. To me a (finite)
    list is a bijection between an initial subset of the natural numbers
    (the validity of 0 in that deliberately being left ambiguous) and
    a target set. An array satisfies that definition trivially, and if
    you're Bourbaki and programming C, you even get the indices to match.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
     
    Phil Carmody, Sep 30, 2009
    #7
  8. >>>>> "jn" == jacob navia <> writes:

    jn> christian.bau a écrit :

    >> Just saying that the ability to change an object from being
    >> read-only to being modifiable makes some very important
    >> optimisations (like very fast copying) impossible. Read up on
    >> Apple's Core Foundation library (which is in actual use by a
    >> significant number of users).


    jn> How do you destroy a read-only object?

    jn> You *must* change it to read/write!

    Actually, no. In CoreFoundation, you can create and destroy immutable
    objects -- you just can't change what they contain.

    jn> I do not see how you could initially add objects to a read only
    jn> list. You *have* to get rid of the read-only flag when
    jn> initializing and when destroying the object.

    You have a limited notion of "read-only" that is not shared by all
    library authors.

    Charlton


    --
    Charlton Wilbur
     
    Charlton Wilbur, Sep 30, 2009
    #8
  9. jacob navia

    jacob navia Guest

    Charlton Wilbur a écrit :
    >>>>>> "jn" == jacob navia <> writes:

    >
    > jn> christian.bau a écrit :
    >
    > >> Just saying that the ability to change an object from being
    > >> read-only to being modifiable makes some very important
    > >> optimisations (like very fast copying) impossible. Read up on
    > >> Apple's Core Foundation library (which is in actual use by a
    > >> significant number of users).

    >
    > jn> How do you destroy a read-only object?
    >
    > jn> You *must* change it to read/write!
    >
    > Actually, no. In CoreFoundation, you can create and destroy immutable
    > objects -- you just can't change what they contain.
    >
    > jn> I do not see how you could initially add objects to a read only
    > jn> list. You *have* to get rid of the read-only flag when
    > jn> initializing and when destroying the object.
    >
    > You have a limited notion of "read-only" that is not shared by all
    > library authors.
    >
    > Charlton
    >
    >

    The Apple libraries say that to create an immutable object (read only)
    you should initialize it with a C array. Then, obviously, you can't
    create any immutable object that contains an heterogeneous set of object
    that will never fit in a C array.

    Another limitation of the Apple design is that you can't change the immutable
    property after the container is created. In my design that is possible.
    (At least I did not find how, maybe I am wrong in this respect).

    It is pointless to argue about this or that characteristic of the sample
    implementation that I provide. It doesn't matter since you can create your
    own implementation (that could mimic Apple's design) at will. What I am
    proposing is an INTERFACE, and providing a sample implementation to
    demonstrate how an implementation *could* be done. The INTERFACE is the only
    fixed part of this stuff. I provide the sample implementation to make it
    easy to implement different "flavors" of the INTERFACE.

    But please do not consider the sample implementation as the only way to
    implement the interface.

    There will never be a single library that will satisfy ALL needs. What
    do you need is a common interface that allows you to switch from one
    implementation to another without changing a single line in your source
    code.
     
    jacob navia, Sep 30, 2009
    #9
  10. >>>>> "jn" == jacob navia <> writes:

    >> You have a limited notion of "read-only" that is not shared by
    >> all library authors.


    jn> The Apple libraries say that to create an immutable object (read
    jn> only) you should initialize it with a C array. Then, obviously,
    jn> you can't create any immutable object that contains an
    jn> heterogeneous set of object that will never fit in a C array.

    Except that, oddly enough, they do, because CoreFoundation provides
    containers for just such a purpose!

    jn> Another limitation of the Apple design is that you can't change
    jn> the immutable property after the container is created. In my
    jn> design that is possible. (At least I did not find how, maybe I
    jn> am wrong in this respect).

    Of course you can't change it - it's *immutable*. You get significant
    performance benefits from that. If you want to change it, you make a
    mutable copy of it.

    jn> But please do not consider the sample implementation as the only
    jn> way to implement the interface.

    I haven't even looked at your implementation. I was commenting on the
    way you seem to think your approach is the only correct one, and that
    you seem unwilling or unable to even attempt to understand other
    approaches.

    Charlton



    --
    Charlton Wilbur
     
    Charlton Wilbur, Oct 1, 2009
    #10
  11. jacob navia

    jacob navia Guest

    Charlton Wilbur a écrit :
    > I haven't even looked at your implementation.


    Sure sure. Then, you write the following sentence:

    > I was commenting on the
    > way you seem to think your approach is the only correct one, and that
    > you seem unwilling or unable to even attempt to understand other
    > approaches.
    >


    So, you do not even look at what I am proposing, then, you snip
    the paragraph where I say explicitly that the sample implementation
    is just ONE way of implementing the interface, designed to
    easy the customization and THEN

    of course you accuse me of ignoring other implementations...

    After you quoted my comments concerning Apple's implementation...

    OK.
     
    jacob navia, Oct 1, 2009
    #11
    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. Saravanan Rathinavelu

    Iterate through ArrayList using an another ArrayList

    Saravanan Rathinavelu, Aug 16, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    2,797
    Natty Gur
    Aug 19, 2003
  2. Kaidi
    Replies:
    4
    Views:
    2,492
    Kaidi
    Jan 3, 2004
  3. xz
    Replies:
    16
    Views:
    2,444
  4. Philipp
    Replies:
    6
    Views:
    977
    Arne Vajhøj
    May 28, 2008
  5. jacob navia
    Replies:
    5
    Views:
    528
    jacob navia
    Sep 28, 2009
Loading...

Share This Page