A container library in C Part 4. The arraylist container

[jacob navia]

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]

Sorry, an error in line 23:
Should be:
static int ReplaceAt(ArrayList *AL,int idx,void *newval);

 

[Chris M. Thomasson]

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.

 

[jacob navia]

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]

Mark McIntyre a écrit :

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.

 

[Keith Thompson]

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.

 

[Phil Carmody]

Mark McIntyre a écrit :

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

 

[Charlton Wilbur]

jn> christian.bau a écrit :

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

 

[jacob navia]

Charlton Wilbur a écrit :

jn> christian.bau a écrit :


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.

 

[Charlton Wilbur]

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

 

[jacob navia]

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.