Mark: 1 revision(s)

2008-11-03T05:19:20Z

1 revision(s)

New page

/*
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 ];
}

SE250:lab-3:jham005:arraylist.c - Revision history

Mark: 1 revision(s)