Java-like ArrayList in C

Al salamo Alykom,

Last week I had the change to have a look at the implementation of the java.util.ArrayList class in Java.

I decided to write a similar one in C, and hence it is fully depended on System.arraycopy, so I wrote arrayCopyutility function in C to use it.

The implementation of ArrayList we going to see here is depending on code wrote under the post of ArrayCopy.

I tried to include many of the functions of the java.util.ArrayList, and also missed many :).

Here's the header file:

/*
 * ArrayList
 */
#ifndef ARRAYLIST_H
#define ARRAYLIST_H

typedef struct
{
    int data;
}Element;

typedef struct
{
    int current;
    int size;
    int increment_rate;
    Element *elements;
}ArrayList;

typedef enum
{
    RIFHT, LEFT
} Shift;

// public functions:
void        init           (ArrayList*const);
void        initWithSize   (ArrayList*const, int);
void        initWithSizeAndIncRate    (ArrayList*const, int, int);
void        clean          (ArrayList*);
int         add            (ArrayList*const, Element);
int         insert         (ArrayList*const, Element, int);
Element*    removeAt       (ArrayList*const, int);
void        clear          (ArrayList*const);
int         set            (ArrayList*const, Element, int);
Element*    get            (ArrayList*const, int);
void        print          (const ArrayList*const);
int         lastIndexOf    (const ArrayList*const, Element);
int         indexOf        (const ArrayList*const, Element);
int         isEmpty        (const ArrayList*const);
// TODO
int        hashCode        (const ArrayList*const);


// static (private) utility functions:

/* Abstracting the print method of the element by delegating it to the element itself (OOP-like feature) */
static void    printElement(const Element*const);
static void    shift(ArrayList *const list, int index, int rooms, Shift dir);
static void    wide(ArrayList* const);

#endif // ARRAYLIST_H

And here's the implementation file:

#include <stdio.h>
#include <stdlib.h>

#include <array_list_impl/ArrayList.h>
#include <arrays/ArrayUtil.h>

void init (ArrayList *const list)
{
    initWithSize(list, 100);
}
void initWithSize(ArrayList *const list, int size)
{
    initWithSizeAndIncRate(list, size, 50);
}

void initWithSizeAndIncRate(ArrayList *const list, int size, int rate)
{
    list->size = size;
    list->increment_rate = rate;
    list->elements = (Element*) calloc(sizeof(Element), list->size);
    list->current = -1;
}

void clear (ArrayList *const list)
{
    while (list->current>=0)
    {
    list->elements[list->current] = (Element){0};
    list->current--;
    }
}

int set (ArrayList *const list, Element e, int index)
{
    if (index <= list->current)
    {
    list->elements[index] = e;
    }
    return 0;
}

Element* get (ArrayList *const list, int index)
{
    if (index <= list->current)
    {
    Element *e = &list->elements[index];
    return e;
    }
    return NULL;
}

int add (ArrayList *const list, Element e)
{
    if (++list->current < list->size)
    {
    list->elements[list->current] = e;
    return 1;
    }else
    {
    wide(list);
    list->elements[list->current] = e;
    return 1;
    }
    return 0;
}
static void wide(ArrayList* const list)
{
    list->size += list->increment_rate;
    Element *newArr = (Element*) calloc(sizeof(Element), list->size) ;
    arraryCopy(newArr, 0, list->elements, 0, list->current, list->size, sizeof(Element));
    free(list->elements);
    list->elements = newArr;
}

int insert (ArrayList *const list, Element e, int index)
{
    if (index <= list->current && ++list->current < list->size)
    {
    shift(list, index, 1, RIFHT);
    list->elements[index] = e;
    return 1;
    }
    return 0;
}

int lastIndexOf (const ArrayList *const list, Element e)
{
    int index = list->current;
    while (index >-1)
    {
    if (e.data == list->elements[index].data) return (list->current-index);
    index--;
    }
    return 0;
}

int indexOf (const ArrayList *const list, Element e)
{
    int index = 0;
    while (index <= list->current)
    {
    if (e.data == list->elements[index].data) return index;
    index++;
    }
    return 0;
}

int isEmpty (const ArrayList *const list)
{
    return list->current == -1;
}

Element    *removeAt(ArrayList *const list, int index)
{
    if (list->current >= index)
    {
    Element *e = &list->elements[index];
    shift(list, index, 1, LEFT);
    list->current--;    
    return e;
    }
    return NULL;
}

void print (const ArrayList *const list)
{
    int i;
    for (i=0; i<=list->current; i++)
    {
    Element e = list->elements[i];
    printElement(&e);
    }
    printf("\n");
}

void clean(ArrayList *list)
{
    free(list->elements);
}

static void printElement(const Element *const e)
{
    printf("%i ", e->data);
}

static void shift(ArrayList *const list, int index, int rooms, Shift dir)
{
    if (dir == RIFHT)
    {
    arraryCopy(list->elements, index+1, list->elements, index, rooms, list->current, sizeof(Element));
    }else //SHIFT
    {
    arraryCopy(list->elements, index, list->elements, index+1, rooms, list->current, sizeof(Element));
    }
}

And here's a test program:

#include <stdio.h>
#include <array_list_impl/ArrayList.h>

int main(void)
{
    
    ArrayList list;
    init(&list);
    add(&list, (Element){10});
    add(&list, (Element){30});
    add(&list, (Element){40});
    add(&list, (Element){50});
    add(&list, (Element){60});
    add(&list, (Element){30});
    add(&list, (Element){80});
    print(&list);
    
    insert(&list, (Element){20}, 1);
    insert(&list, (Element){15}, 1);
    insert(&list, (Element){3}, 0);
    print(&list);
    
    printf("Removeing element at index 5\n");
    removeAt(&list, 5);
    print(&list);
    
    Element *e = get(&list, 5);
    printf("element at 5th index:\n %i\n", (e!=NULL? e->data:-1));
    
    int i  = indexOf(&list, (Element){30});
    printf("Index of 30:\n %i\n", i);
    
    i  = lastIndexOf(&list, (Element){30});
    printf("Last index of 30:\n %i\n", i);
    
    printf("Clear...\n");
    clear(&list);
    print(&list);
    
    for (i=0; i<180; i++)
    {
    add(&list, (Element){i});
    }
    
    print(&list);
    clean(&list);
    
    return 0;
}

That's all folks.
Just make sure to test the above code well before using it.

arrayCopy

Hi folks,

While looking at the usage of the method System.arraycopy
in Java, I found it very useful function.
for example, in java.util.ArrayList it is doing may useful shifting operations.

So, I decide to try to write a similar function, but instead of using the pattern "func (src, dest)" of java, I used instead the pattern "func(dest, src)" of C.

The Header file:

#ifndef ARRAYUTIL_H
#define ARRAYUTIL_H

#include <stddef.h>

/**
 * dest    destination array
 * dIndex    index to which we will start copying
 * src        source array
 * sIndex    index from which we will start copying
 * len        number of elements that will be copied from source array
 * destArrLen    the length of the destination array (hence C doesn't know any length info about passed arrays)
 * size    the size of the type of the array (ex: if the array of type long, put in this parameter sizeof(long))
 */
void arraryCopy(void *dest, int dIndex, const void* src, int sIndex, int len, int destArrLen, size_t size);

#endif // ARRAYUTIL_H

The impl file:

#include <string.h>
#include <stdint.h>
#include <stdlib.h>

#include <arrays/ArrayUtil.h>

void arraryCopy(void *dest, int dIndex, const void* src, int sIndex, int len, int destLen, size_t size)
{
   uint8_t *udest = (uint8_t*) dest;
   uint8_t *usrc = (uint8_t*) src;
   dIndex  *= size;
   sIndex  *= size;
   len     *= size;
   destLen *= size;
  
   if (src != dest)
   {
   memcpy(&udest[dIndex], &usrc[sIndex], len);
   }else
   {
   if (dIndex > sIndex)
   {
       uint8_t *tmp = (uint8_t*) calloc(destLen, size);
       memcpy(tmp, &udest[dIndex], (destLen-dIndex));
       memcpy(&udest[dIndex], &usrc[sIndex], len);
       memcpy(&udest[dIndex+len], tmp, (destLen-dIndex));
       free(tmp);
   }else if (sIndex > dIndex)
   {
       memcpy(&udest[dIndex], &usrc[sIndex], (destLen-sIndex)+1);
   }else
       return;
   }
}

And, testing it:

#include <stdio.h>
#include <arrays/ArrayUtil.h>

int main(void)
{
   int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  
   arraryCopy(arr, 1, arr, 2, 1, 10, sizeof(int));
  
   int i;
   for (i=0; i<9; i++)        // the len became 9 here because we do shift left by 1
   printf("%i ", arr[i]);
  
   return 0;
}

Array Literals in C

#include <stdio.h>

void take_array(int[]);

int main(void)
{
    take_array((int[]){1, 2, 3});  // here's the point, we must do cast here!

    return 0;
}

void take_array(int arr[])
{
    printf("IN:  take_array(int[])\n");
}