dynamic_array.c

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

#define START_SIZE 10
#define GROWTH_FACTOR 1.5

typedef struct {
  int size;   /* total available size */
  int count;  /* number of elements */
  int *items;
} DynArray;

/* -1 if malloc failed */
int DynArray_init(DynArray *ary) {
  ary->items = malloc(sizeof(int) * START_SIZE);
  ary->size = START_SIZE;
  ary->count = 0;
  return ary->items == NULL ? -1 : 0;
}

/* O(1). -1 if out of bounds */
int DynArray_get(DynArray *ary, int i) {
  return (i < ary->count) ? ary->items[i] : -1;
}

/* O(1). no-op if out of bounds */
void DynArray_set(DynArray *ary, int i, int n) {
  if (i < ary->count) {
    ary->items[i] = n;
  }
}

/* O(1) amortized */
int DynArray_push(DynArray *ary, int item) {
  int resize = 0;

  if (ary->count == ary->size) {
    int new_size = ary->size * GROWTH_FACTOR;
    int *new_items = malloc(sizeof(int) * new_size);

    if (new_items == NULL) {
      return -1;
    }

    int i;
    for (i = 0; i < ary->size; i++) {
      new_items[i] = ary->items[i];
    }
    free(ary->items);
    ary->items = new_items;
    ary->size = new_size;
    resize = 1;
  }

  ary->items[ary->count] = item;
  ary->count++;

  return resize;
}

/* Global test array */
DynArray ary;

void display() {
  int i;
  for (i = 0; i < ary.count; i++) {
    int n = DynArray_get(&ary, i);
    printf("%d ", n);
  }
  printf("\n");
}

void push(int i) {
  int old_size = ary.size;

  switch (DynArray_push(&ary, i)) {
    case 0:
      break;
    case 1:
      printf("Old size: %d, new size: %d\n", old_size, ary.size);
      break;
    default:
      printf("Failed to insert %d!\n", i);
  }
}

void init() {
  if (DynArray_init(&ary) < 0) {
    printf("Failed to initialize!\n");
  }
}

int get(int i) {
  return DynArray_get(&ary, i);
}

void cleanup() {
  free(ary.items);
}

int main(void) {
  int i, max = 20000;

  init();

  for (i = 0; i < max; i++) {
    push(i);
  }
  for (i = 0; i < max; i++) {
    assert(i == get(i));
  }

  cleanup();

  return 0;
}