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 code 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, this 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.
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;
}
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.