Arraylist in C.

Question

HELLO WORLD, GUYS!!!

I am currently writing a program to implement an arraylist (or dynamic array) in C. Hmm... I think I have 70 - 80% done with it, however, I found a serious problem with my codes when testing them on a couple of machines.

Briefly, I inserted a group of strings( char* ) into my arraylist, and tried to get and display them after couples of operations. However, there is what I got:

CHECK: 1
CHECK: 2
CHECK: ܗ¿èۗ¿
CHECK: EàEàHAÿE؉Ⱥ
CHECK: 5
CHECK: 6

Unfortunately, I still cannot figure out where the problem is in my codes, even though I have reviewed my codes twice. Thus, I write to ask for help from you guys.

arraylist.h

#ifndef _ARRAYLIST_H
#define _ARRAYLIST_H

#include <stdio.h>

typedef char* value_type;

struct arraylist {
  int size;
  value_type* data;
};

extern void arraylist_initial(struct arraylist *list);
extern int arraylist_get_size(const struct arraylist list);
extern value_type* arraylist_get_data_collection(const struct arraylist list);
extern void arraylist_set_data_collection(struct arraylist *list, value_type* data);
extern void arraylist_add(struct arraylist *list, value_type value);
extern value_type arraylist_get(const struct arraylist list, int index);
extern int arraylist_indexof(const struct arraylist list, value_type value);

#endif

arraylist.c

#include "arraylist.h"

void arraylist_initial(struct arraylist *list) {
  list->size = 0;
  list->data = NULL;
}

int arraylist_get_size(const struct arraylist list) {
  return list.size;
}

value_type* arraylist_get_data_collection(const struct arraylist list) {
  return list.data;
}

void arraylist_set_data_collection(struct arraylist *list, value_type* data) {
  list->data = data;
}

void arraylist_add(struct arraylist *list, value_type value) {
  int size = arraylist_get_size(*list);
  value_type new_data[size + 1];

  int index = 0;
  for(; index != size; ++index) {
    new_data[index] = arraylist_get(*list, index);
  }
  new_data[index] = value;

  arraylist_set_data_collection(list, new_data);

  ++list->size;
}

value_type arraylist_get(const struct arraylist list, int index) {
  if(index < arraylist_get_size(list)) {
    return list.data[index];
  }
  else {
    return NULL;
  }
}

int arraylist_indexof(const struct arraylist list, value_type value) {
  int index = 0;
  for(; index != arraylist_get_size(list); ++index) {
    if(strcmp(list.data[index], value) == 0) {
      return index;
    }
  }

  return -1;
}

int main(void){
  struct arraylist list;

  arraylist_initial(&list);

  arraylist_add(&list, "1");
  arraylist_add(&list, "2");
  arraylist_add(&list, "3");
  arraylist_add(&list, "4");
  arraylist_add(&list, "5");
  arraylist_add(&list, "6");

  int index = 0;
  for(; index != 6; ++index) {
    printf("CHECK: %s\n", arraylist_get(list, index));
  }

  return 0;
}

Waiting for your reply.

Thanks a ton.

Answer 1

In the arraylist_add method you are storing the address of a local variable new_data in to the list. This variable will destroyed as soon as the control comes out of the function. Hence you have invalid pointers which when derefrenced invoke undefined behavior. To fix this problem, you need to allocate memory for the string from heap using malloc i.e. you need to do something like value_type* new_data = (value_type*)malloc( (size + 1) * sizeof(value_type));. Also remember that you have to deallocate this memory yourself using free.

Answer 2

At first glance: in arraylist_add you declare new_data as a local variable. When you pass that to arraylist_set_data_collection, it passes the pointer to this data. However, once arraylist_add returns to main, new_data is out of scope, and is therefore no longer valid.

Consider doing a deep copy and handling the memory manually with malloc and free.

Answer 3

The root of your problem is here:

void arraylist_add(struct arraylist *list, value_type value) {
  int size = arraylist_get_size(*list);
  value_type new_data[size + 1];
  ...
  arraylist_set_data_collection(list, new_data);
  ...
  ++list->size;
}

new_data is declared on the stack. It's no longer safe to use that memory after the call returns. You need to allocate space for the data with malloc, e.g.

Edit: Oh, and HELLO WORLD to you too!

Answer 4

As others have noted, the problem is in the arraylist_add() function, which needs to dynamically allocate memory. This problem is actually perfectly suited for realloc(), which will expand the dynamically allocated array (meaning you don't have to do the copying loop):

void arraylist_add(struct arraylist *list, value_type value) {
  int size = arraylist_get_size(*list);
  value_type *new_data;

  new_data = realloc(list->data, (size + 1) * sizeof new_data[0]);

  if (new_data)
  {
      new_data[size] = value;
      arraylist_set_data_collection(list, new_data);
      ++list->size;
  }
}

This will even work for the first allocation, since realloc() works like malloc() if you pass it a NULL.

PS:

To make the implementation more efficient, you shouldn't expand the array by one entry each time - instead, keep track of the number of allocated blocks separately from the number of entries.