CS 245 Homework 3

Due Date

4:00 pm Wednesday September 30

Assignment Name

stack

File Names

alist.c alist.h

Below is an implementation of an arraylist where the item type is void *. It can actually store any kind of (pointers to) data structures. For example, it can store strings since their type is char *. It can also store streams since their type if FILE *. I have implemented some of the functions defined in the header file. You will implement the rest. The comments in the header file explain what each function is supposed to do.

Use memcpy or memmove whenever you need to move a block of items in the array rather than stepping through the array and doing assignments.

Turnin will compile your programs together with a test program, but you should write your own test program. To compile it, you can use:

          cc -Wall -o testalist testalist.c alist.c

alist.h

#ifndef ALIST_H
#define ALIST_H

// An alist functions as a dynamically allocated resizeable
// array. The item type is void * so it can store pointers
// to items of any type.

typedef struct alist alist;

#define INITIAL_CAPACITY 5

// Creates a new alist of size 5.
// If memory allocation fails, returns NULL.
alist *alist_new();

// Frees the memory for at. Does not free any dynamically
// allocated memory for the items in a.
void alist_free(alist *a);

// Returns the length of a.
size_t alist_length(alist *a);

// Returns the item in a in position index which
// must be less than the length of a.
void *alist_get(alist *a, size_t index);

// Sets the value of the item in a in position
// index which must be less than the length of a.
void alist_put(alist *a, size_t index, void *value);

// Appends a new item to the end of a. Returns a. If
// memory allocation fails, leaves a unchanged and
// returns NULL.
alist *alist_append(alist *a, void *value);

// Removes the item from a in position index
// which must be less than the length of a. Items
// to the right of position index are shifted left.
void alist_remove(alist *a, size_t index);

// Inserts an item into a at position index which
// must be less than or equal to the length of a.
// Items from position index to the right are shifted right.
alist *alist_insert(alist *a, size_t index, void *value);

// Returns a dynamically allocated array containing
// (the pointers to) the items in a.
void **alist_to_array(alist *a);

// Returns an alist containing (the pointers to) the items
// in array of size n.
alist *alist_new_from_array(int n, void *array[n]);

// Iterates over the items in a calling func on each item in a.
void alist_iterate(alist *a, void (*func)(void *)); 

alist.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "alist.h"

#define INITIAL_CAPACITY 5

struct alist {
  size_t capacity;
  size_t length;
  void **contents;
};

alist *alist_new() {
  alist *a = malloc(sizeof(struct alist));
  if (a == NULL) return NULL;
  a->capacity = INITIAL_CAPACITY;
  a->length = 0;
  a->contents = calloc(INITIAL_CAPACITY, sizeof(void *));
  if (a->contents == NULL) {
    free(a);
    return NULL;
  }
  return a;
}

void alist_free(alist *a) {
  assert(a != NULL);
  free(a->contents);
  free(a);
}

size_t alist_length(alist *a) {
  assert(a != NULL);
  return a->length;
}

static alist *resize(alist *a) {
  assert(a != NULL);
  size_t new_capacity = a->capacity * 2;
  void **new_contents = realloc(a->contents, new_capacity * sizeof(void *));
  if (new_contents == NULL) return NULL;
  else {
    a->capacity = new_capacity;
    a->contents = new_contents;
    return a;
  } 
}

alist *alist_append(alist *a, void *value) {
  assert(a != NULL);
  if (a->length == a->capacity) {
    if (resize(a) == NULL) return NULL;
  }
  a->contents[a->length] = value;
  a->length++;
  return a;
}

void *alist_get(alist *a, size_t index) {
  assert(a != NULL);
  assert(index >= 0 && index < a->length);
  return a->contents[index];
}

void alist_put(alist *a, size_t index, void *value) {
  assert(a != NULL);
  assert(index >= 0 && index < a->length);
  a->contents[index] = value;
}

alist *alist_insert(alist *a, size_t index, void *value) {
  assert(a != NULL);
  assert(index >= 0 && index <= a->length);
  if (a->length == a->capacity) {
    if (resize(a) == NULL) return NULL;
  }
  if (index != a->length) {
    memmove(&(a->contents[index + 1]), &(a->contents[index]),
           (a->length - index) * sizeof(void *));
  }
  a->contents[index] = value;
  a->length++;
  return a;
}