SE250:lab-3:jham005:arraylist.c

/*
  File:    arraylist.c
  Date:    18 March 2008
  Author:  John Hamer
  Purpose: resizable array-based list data structure
*/

#include <stdio.h>		/* for printf */
#include <stdlib.h>		/* for malloc, realloc, free */
#include <string.h>		/* for memmove */
#include <assert.h>		/* for assert */

#include "arraylist.h"

int    ARRAYLIST_MIN_ALLOC     = 16;
double ARRAYLIST_GROWTH_FACTOR = 2.0;
int    ARRAYLIST_GROWTH_INCR   = 0;
int    ARRAYLIST_ALWAYS_MALLOC = 0;

void arraylist_init( ArrayList *alist ) {
  alist->arr = 0;
  alist->length = 0;
  alist->capacity = 0;
}


void arraylist_clear( ArrayList *alist ) {
  if( alist->arr )
    free( alist->arr );
  arraylist_init( alist );
}


int arraylist_size( ArrayList *alist ) {
  return alist->length;
}


void ensure_capacity( ArrayList *alist, int required_capacity ) {
  if( required_capacity > alist->capacity ) {
    if( ARRAYLIST_ALWAYS_MALLOC ) {
      element_t* newarr = malloc( required_capacity * sizeof( element_t ) );
      assert( newarr != (element_t*)0 );
      memmove( newarr, alist->arr, alist->length * sizeof(element_t) );
      free( alist->arr );
      alist->arr = newarr;
    } else {
      /* This is the "right thing to do", but it messes up the timings.
	 In our benchmarks, nothing else allocates memory and so realloc
	 may end up with very little work to do.  In a real program,
	 many data structures compete for memory, and realloc will
	 usually need to perform the steps in the #ifdef above.
      */
      alist->arr = realloc( alist->arr, required_capacity * sizeof(element_t) );
      assert( alist->arr != (element_t*)0 );
    }
    alist->capacity = required_capacity;
  }
}


void arraylist_put( ArrayList *alist, element_t elt, int index ) {
  assert( index >= 0 && index <= alist->length );
  if( alist->length == alist->capacity ) {
    int expand;
    if( expand < ARRAYLIST_MIN_ALLOC )
      expand = ARRAYLIST_MIN_ALLOC;
    else
      expand = (int)(alist->capacity * ARRAYLIST_GROWTH_FACTOR + ARRAYLIST_GROWTH_INCR );

    if( expand < alist->capacity + 1 )
      expand = alist->capacity + 1;

    ensure_capacity( alist, expand );
  }
  memmove( &alist->arr[ index + 1 ], &alist->arr[ index ], 
	   (alist->length - index) * sizeof( element_t ) );
  alist->arr[ index ] = elt;
  alist->length++;
}


void arraylist_push( ArrayList *alist, element_t elt ) {
  arraylist_put( alist, elt, alist->length );
}


element_t arraylist_get( ArrayList *alist, int index ) {
  assert( index >= 0 && index < alist->length );
  return alist->arr[ index ];
}


element_t arraylist_pop( ArrayList *alist ) {
  assert( alist->length > 0 );
  return alist->arr[ --alist->length ];
}