arraylist.c

[jacob navia]

#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 ErrorFunction SetErrorFunction(ArrayList *l,ErrorFunction fn);
static ArrayListInterface lpVtblAL = {
GetCount, IsReadOnly, SetReadOnly, Add, AddRange, Clear, Contains,
CopyTo, IndexOf, Insert, InsertAt, IndexAt, Remove, RemoveAt,
Finalize, GetCapacity, SetCapacity,
Apply, Push,
Pop,
ReplaceAt,
SetErrorFunction,
};
#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,const char *functionName)
{
void *result;
if (size == 0)
return str;
if (str == NULL) {
ContainerRaiseError(functionName,CONTAINER_ERROR_BADARG);
return NULL;
}
result = MALLOC(size);
if (result == NULL) {
ContainerRaiseError(functionName,CONTAINER_ERROR_NOMEMORY);
return NULL;
}
else memcpy(result,str,size);
return result;
}

#define AL_READONLY 1
#define AL_IGNORECASE 2
#define CHUNKSIZE 20
static int DefaultArrayListCompareFunction(void *left,void *right,void *ExtraArgs)
{
int siz=((ArrayList *)ExtraArgs)->ElementSize;
return memcmp(left,right,siz);
}

ArrayList *newArrayList(size_t elementsize,int startsize)
{
ArrayList *result;
size_t es;

/* This detects BOGUS sizes arising from passing a negative value */
if ((int)elementsize < 0) {
ContainerRaiseError("newArrayList",CONTAINER_ERROR_BADARG);
return NULL;
}
/* Allocate space for the array list header structure */
result = MALLOC(sizeof(*result));
if (result == NULL)
return NULL;
memset(result,0,sizeof(*result));
if (startsize <= 0)
startsize = DEFAULT_START_SIZE;
es = startsize * sizeof(void *);
result->contents = MALLOC(es);
if (result->contents == NULL) {
ContainerRaiseError("newArrayList",CONTAINER_ERROR_NOMEMORY);
FREE(result);
result = NULL;
}
else {
memset(result->contents,0,es);
result->capacity = startsize;
result->lpVtbl = &lpVtblAL;
result->ElementSize = elementsize;
result->CompareFn = DefaultArrayListCompareFunction;
result->RaiseError = ContainerRaiseError;
}
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)
{
/* Other implementations could copy the list into virtual memory pages
marked as read only, and add the OS read-only mechanisms as an additional
layer of protection.
*/
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) {
AL->RaiseError("Resize",CONTAINER_ERROR_NOMEMORY);
AL->contents = oldcontents;
return CONTAINER_ERROR_NOMEMORY;
}
memset(AL->contents,0,sizeof(void *)*newcapacity);
memcpy(AL->contents,oldcontents,AL->count*sizeof(void *));
AL->capacity = newcapacity;
FREE(oldcontents);
return 1;
}

/*------------------------------------------------------------------------
Procedure: Add ID:1
Purpose: Adds an item at the end of the arraylist
Input: The arraylist and the item to be added
Output: The number of items in the arraylist or negative if
error
Errors:
------------------------------------------------------------------------*/
static int Add(ArrayList *AL,void *newval)
{
if (AL->Flags & AL_READONLY)
return CONTAINER_ERROR_READONLY;
if (newval == NULL) {
AL->RaiseError("Add",CONTAINER_ERROR_BADARG);
return CONTAINER_ERROR_BADARG;
}
if (AL->count >= AL->capacity) {
int r = Resize(AL);
if (r <= 0)
return r;
}

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

/*------------------------------------------------------------------------
Procedure: AddRange ID:1
Purpose: Adds a range of data at the end of an existing
arrraylist. If for some reason this process is
interrupted in the middle, not all items will be
added.
Input: The arraylist and the data to be added
Output: The number of items added or negative error code
Errors: Arraylist must be writable and data must be
different of NULL
------------------------------------------------------------------------*/
static int AddRange(ArrayList * AL,void **data)
{
int i = 0;
if (AL->Flags & AL_READONLY)
return CONTAINER_ERROR_READONLY;
if (data == NULL) {
AL->RaiseError("AddRange",CONTAINER_ERROR_BADARG);
return CONTAINER_ERROR_BADARG;
}
while (data != NULL) {
int r = Add(AL,data);
if (r < 0) {
return r;
}
i++;
}
return i;
}

/*------------------------------------------------------------------------
Procedure: Clear ID:1
Purpose: Frees all memory from an array list object without
freeing the object itself
Input: The array list to be cleared
Output: The number of objects that were in the array list
Errors: The array list must be writable
------------------------------------------------------------------------*/
static int Clear(ArrayList *AL)
{
int oldval = AL->count,i;
if (AL->Flags & AL_READONLY)
return 0;
for (i=0; i<AL->count;i++) {
FREE(AL->contents);
AL->contents = NULL;
}
AL->count = 0;
return oldval;
}

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

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

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

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

if (str == NULL)
return CONTAINER_ERROR_BADARG;
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) {
AL->RaiseError("IndexAt",CONTAINER_ERROR_BADARG);
return NULL;
}
return AL->contents[idx];
}

/*------------------------------------------------------------------------
Procedure: InsertAt ID:1
Purpose: Inserts data at the given position, that should be
between zero and the number of items in the array
list. If the index is equal to the count of items in
the array the item will be inserted at the end. Any
insertion in the middle or at the beginning provokes
a move of all items between the index and the end of
the array list
Input: The array list, the index and the new data to be
inserted
Output: Error code less than zero if error, or positive
number bigger than zero otherwise
Errors: The index must be correct and the array list must be
writable
------------------------------------------------------------------------*/
static int InsertAt(ArrayList *AL,int idx,void *newval)
{
if (AL->Flags & AL_READONLY)
return CONTAINER_ERROR_READONLY;
if (idx < 0 || idx > AL->count) {
AL->RaiseError("InsertAt",CONTAINER_ERROR_INDEX);
return CONTAINER_ERROR_INDEX;
}
if (AL->count >= (AL->capacity-1)) {
int r = Resize(AL);
if (r <= 0)
return r;
}
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;
}
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)
return CONTAINER_ERROR_INDEX;
if (AL->Flags & AL_READONLY)
return CONTAINER_ERROR_READONLY;
FREE(AL->contents[idx]);
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)
{
return InsertAt(AL,AL->count,str);
}

/*------------------------------------------------------------------------
Procedure: Pop ID:1
Purpose: Removes the last item of the list and returns its
data to the caller. It is the responsability of the
caller to free this memory. This is almost the same as
the "Remove" function, with the only difference that the
data is NOT freed but returned to the caller.
Input: The array list to be popped
Output: a pointer to the last item's data
Errors: If the list is read-only or empty returns NULL
------------------------------------------------------------------------*/
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;
}

/*------------------------------------------------------------------------
Procedure: Finalize ID:1
Purpose: Releases all memory associated with an arraylist,
including the arraylist structure itself
Input: The arraylist to be destroyed
Output: The number of items that the arraylist contained or
zero if error
Errors: Input must be writable
------------------------------------------------------------------------*/
static int Finalize(ArrayList *AL)
{
int result = Clear(AL);
FREE(AL);
return result;
}

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

static bool SetCapacity(ArrayList *AL,int newCapacity)
{
if (AL->count != 0)
return 0;
FREE(AL->contents);
AL->contents = MALLOC(newCapacity*sizeof(void *));
if (AL->contents == NULL) {
AL->RaiseError("SetCapacity",CONTAINER_ERROR_NOMEMORY);
return 0;
}
memset(AL->contents,0,sizeof(void *)*newCapacity);
AL->capacity = newCapacity;
return 1;
}

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

/*------------------------------------------------------------------------
Procedure: ReplaceAt ID:1
Purpose: Replace the data at the given position with new
data.
Input: The list and the new data
Output: Returns the new data if OK, NULL if error.
Errors: Index error or read only errors are caught
------------------------------------------------------------------------*/
static void *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] = DuplicateElement(newval,AL->ElementSize,"Add");
return AL->contents[idx];
}

static ErrorFunction SetErrorFunction(ArrayList *AL,ErrorFunction fn)
{
ErrorFunction old;
old = AL->RaiseError;
AL->RaiseError = (fn) ? fn : EmptyErrorFunction;
return old;
}

 

[Ike Naar]

static int RemoveAt(ArrayList *AL,int idx)
{
if (idx >= AL->count || idx < 0)
return CONTAINER_ERROR_INDEX;
if (AL->Flags & AL_READONLY)
return CONTAINER_ERROR_READONLY;
FREE(AL->contents[idx]);

Here you free AL->contents[idx] for the first time.

if (AL->count == 0)
return -2;
FREE(AL->contents[idx]);

Here you free the same AL->contents[idx] for the second time.

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;
}

 

[jacob navia]

Ike Naar a écrit :

static int RemoveAt(ArrayList *AL,int idx)
{
if (idx >= AL->count || idx < 0)
return CONTAINER_ERROR_INDEX;
if (AL->Flags & AL_READONLY)
return CONTAINER_ERROR_READONLY;
FREE(AL->contents[idx]);

Here you free AL->contents[idx] for the first time.

if (AL->count == 0)
return -2;
FREE(AL->contents[idx]);

Here you free the same AL->contents[idx] for the second time.

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;
}

Sh....!!!!

I added that line twice dam!

The first one is the bug since I test if the list is empty afterwards!
Thanks a lot. I use always the GC, so that part is not well tested.

Sorry.

 

[Ben Bacarisse]

Ike Naar a écrit :

static int RemoveAt(ArrayList *AL,int idx)
{
if (idx >= AL->count || idx < 0)
return CONTAINER_ERROR_INDEX;
if (AL->Flags & AL_READONLY)
return CONTAINER_ERROR_READONLY;
FREE(AL->contents[idx]);

Here you free AL->contents[idx] for the first time.

if (AL->count == 0)
return -2;
FREE(AL->contents[idx]);

Here you free the same AL->contents[idx] for the second time.

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;
}

Sh....!!!!

I added that line twice dam!

The first one is the bug since I test if the list is empty afterwards!
Thanks a lot. I use always the GC, so that part is not well tested.

I suspect it's not tested at all. The second one is a bug as well.
If I follow the code correctly you are trying to free a non-malloc'd
string.