24-timed-sorting-4/array_backed_list.c

/*----------------------------------------------------------
 *				HTBLA-Leonding / Class: 2IHIF
 * ---------------------------------------------------------
 * Exercise Number: S07
 * Title:			Array backed List implementation
 * Author:			Marc Tismonar
 * ----------------------------------------------------------
 * Description:
 * Implementation of an array backed list.
 * ----------------------------------------------------------
 */

/*
  Implementation notes:

  1) The 'ListData' struct of this linked list SHALL have
     - a buffer for the payload data (array of integer), 
     - the capacity of the buffer (length of the array)
     - and the size of the list (number actual element in the list)
    as members!

  2) List allocation: 
     Use functions `mem_alloc(…)` and `mem_free(…)`
     declared in `allocator.h`. DO NOT use `malloc(…)` and `free(…)` directly
     as unit tests will fail.

    Note:
     a) `list_obtain` shall allocate only the list data, but NOT the payload buffer
     b) The payload buffer shall be allocated when a value is inserted the first time.
        The payload buffer shall be increased if an additional item shall be inserted 
        (via one of the insert functions) no capacity is left. All  values contained in the list
        shall be copied into the increased buffer.
        Initial allocation of the payload buffer and increasing the payload buffer is actually
        the same case, because the initial capacity is 0 and therefore no capacity is left.
        The payload buffer shall be increased by `CAPACITY_INCREMENT` (`config.h`) items.        
     c) `list_clear` shall NOT free the payload buffer. Setting the size to 0 is sufficient.
     d) `list_release` shall free the payload buffer, if it was allocated.

  3) Use 'limits.h' to get maximum and minimum values for numeric types, if needed.

*/

#include "array_backed_list.h"

/* add includes as needed */

#include "config.h"
#include "allocator.h"


/** The implementation of list data: payload-buffer, capacity, size */
struct IntListData {
   int* buffer;
   int capacity;
   int size;
};

/* ===================================================================== */
/* private list functions */

/** 
 * Enlarges the backing array by the given amount of items. 
 * Hint: memcpy may be used to copy all bytes(!) from the existing to the new buffer
 */
static void increase_buffer(IntList list, unsigned int additional_capacity) {
   if (list->buffer == 0) {
      list->buffer = alloc_mem(sizeof(int) * additional_capacity);
      if (list->buffer != 0) {
         list->capacity = additional_capacity;
      }
   } else {
      int* new_buffer = alloc_mem(sizeof(int) * (list->capacity + additional_capacity));
      if (new_buffer != 0) {
         for (int i = 0; i < list->size; i++) {
            new_buffer[i] = list->buffer[i];
         }
         
         free_mem(list->buffer);
         list->buffer = new_buffer;
         list->capacity += additional_capacity;
      }
   }
}

/* ===================================================================== */

/**
 * Obtains ('creates') and provides a 'new' list instance.
 * Any list obtained via this function MUST be released using
 * function `release_list()`.
 * 
 * Note: This function does not make any assumptions 
 * about how list components, esp. nodes, are allocated.
 * 
 * @return The list instance or 0, if no list could by instantiated.
 */
IntList list_obtain() {
   IntList list = alloc_mem(sizeof(struct IntListData));
   if (list != 0) {
      list->buffer = 0;
      list->capacity = 0;
      list->size = 0;
   }

   return list;
}

/**
 * Releases a list that was obtained earlier via function `obtain_list`.
 * Released lists MUST NOT be used anymore.
 * 
 * Note: The implementation of this function does not make any assumptions
 * about the allocation method of list elements, but MUST match the implementation
 * of function `obtain_list` as its inverse function.
 * 
 * @param p_list The pointer to the list to release. The value of the pointer
 * is set to 0, if the list was successfully released, otherwise it is left untouched.
 */
void list_release(IntList* p_list) {
   if (p_list != 0 && *p_list != 0) {
      IntList list = *p_list;
      if (list->buffer != 0) {
         free_mem(list->buffer);
      }

      free_mem(list);
      *p_list = 0;
   }
}

/**
 * Determines whether or not the given list is valid.
 * 
 * @param list The list to evaluate.
 * @return `True` if the list is valid, false otherwise.
 */
bool list_is_valid(IntList list) {
   return list != 0;
}

/**
 * Determines whether or not the list contains at least one item.
 * 
 * @param list The list to evaluate.
 * @return `False` if the list contains one or more items, `true` otherwise.
 */
bool list_is_empty(IntList list) {
   return !list_is_valid(list) || list->size == 0;
}

/**
 * Provides the number of values stored in the list.
 * 
 * @param list The list to evaluate.
 * @return The number of values the list contains.
 */
int list_get_size(IntList list) {
   return list_is_valid(list) ? list->size : 0;
}

/**
 * Determines whether or not the list given list contains the queried value
 * at least once.
 * 
 * @param list The list to query.
 * @param value The value.
 * @return `True` if the list contains at least one instance of the value, 
 * `false ` otherwise.
 */
bool list_contains(IntList list, int value) {
   if (list_is_valid(list)) {
      for (int i = 0; i < list->size; i++) {
         if (list->buffer[i] == value) {
            return true;
         }
      }
   }

   return false;
}

/**
 * Provides the value stored in the list at the given position.
 * 
 * @param list The list from which the value shall be retrieved.
 * @param index The zero-based position index of the value to retrieve.
 * @return The value stored at the given position or 0, if the position
 * is not available.
 */
int list_get_at(IntList list, unsigned int index) {
   if (list_is_valid(list) && index < list->size) {
      return list->buffer[index];
   }

   return 0;
}

/**
 * Inserts the given value at the end of the given list.
 * 
 * @param list The list to which the value shall be appended.
 * @param value The value to append to the list.
 */
void list_insert(IntList list, int value) {
   if (list_is_valid(list)) {
      if (list->size >= list->capacity) {
         increase_buffer(list, CAPACITY_INCREMENT);
      }

      list->buffer[list->size] = value;
      list->size++;
   }
}

/**
 * Inserts the given value at the indexed position in a way the 
 * the inserted value is on that position. The index is
 * - similar to arrays - zero-based. If the the list is shorter
 * than the indexed position, the value is inserted at the end
 * of the list.
 * 
 * @param list The list into which the value shall be appended.
 * @param index The position index of the value to insert.
 * @param value  The value to insert.
 */
void list_insert_at(IntList list, unsigned int index, int value) {
   if (list_is_valid(list)) {
      if (index >= list->size) {
         list_insert(list, value);
      } else {
         if (list->size >= list->capacity) {
            increase_buffer(list, CAPACITY_INCREMENT);
         }

         for (int i = list->size; i > index; i--) {
            list->buffer[i] = list->buffer[i - 1];
         }

         list->buffer[index] = value;
         list->size++;
      }
   }
}

/**
 * Appends the `list_to_append` at the end of the given `list`.
 * The appended list is empty afterwards, because all nodes of that list
 * have been transferred to `list`.
 * 
 * @param list The list that receives the other list.
 * @param list_to_append The list that is appended to `list`.
 */
/* This function is not required in this assignment. */
/* void list_append(IntList list, IntList list_to_append); */

/**
 * Removes the first occurrance of `value` from the given list.
 * If the list does not contain that value, the list shall not
 * be modified.
 * 
 * @param list The list from which the given value shall be removed.
 * @param value The value to remove from the list.
 */
void list_remove(IntList list, int value) {
   if (list_is_valid(list)) {
      for (int i = 0; i < list->size; i++) {
         if (list->buffer[i] == value) {
            for (int j = i; j < list->size - 1; j++) {
               list->buffer[j] = list->buffer[j + 1];
            }

            list->size--;
            return;
         }
      }
   }
}

/**
 * Removes all occurrances of `value` from the list.
 * If the list does not contain that value, the list shall not
 * be modified.
 * 
 * @param list The list from which all occurrances of `value` shall be removed.
 * @param value The `value` to remove throughout the list.
 */
void list_remove_all(IntList list, int value) {
   if (list_is_valid(list)) {
      for (int i = 0; i < list->size; i++) {
         if (list->buffer[i] == value) {
            for (int j = i; j < list->size - 1; j++) {
               list->buffer[j] = list->buffer[j + 1];
            }

            list->size--;
            i--;
         }
      }
   }
}

/**
 * Removes the value at the indexed position from the given list
 * and provides that value. If the list does not have a value
 * at that position, the list remains unmodified.
 * 
 * @param list The list from which the value at the given index shall be returned.
 * @param index The zero-based index of the value to return.
 * @return The removed value or 0 in case of errors.
 */
int list_remove_at(IntList list, unsigned int index) {
   if (list_is_valid(list) && index < list->size) {
      int value = list->buffer[index];
      for (int i = index; i < list->size - 1; i++) {
         list->buffer[i] = list->buffer[i + 1];
      }

      list->size--;
      return value;
   }
   
   return 0;
}

/**
 * Swaps the values at the given indexes, so that value at fst_idx becomes
 * the value at snd_idx and vice versa. The invocation is ignored, if the 
 * list is invalid or at least one of the given indexes is out of range.
 * 
 * @param list The list to manipulate
 * @param fst_idx The index of the first item to swap.
 * @param snd_idx The index of the second item to swap.
 */
void list_swap(IntList list, unsigned int fst_idx, unsigned int snd_idx) {
   if (list_is_valid(list) && fst_idx < list->size && snd_idx < list->size) {
      int temp = list->buffer[fst_idx];
      list->buffer[fst_idx] = list->buffer[snd_idx];
      list->buffer[snd_idx] = temp;
   }
}

/**
 * Clears the given list by removing all values from the list.
 * 
 * @param list The list to clear.
 */
void list_clear(IntList list) {
   if (list_is_valid(list)) {
      list->size = 0;
   }
}

/**
 * Appends the `list_to_append` at the end of the given `list`.
 * The appended list is empty afterwards, because all nodes of that list
 * have been transferred to `list`.
 * 
 * @param list The list that receives the other list.
 * @param list_to_append The list that is appended to `list`.
 */
void list_append(IntList list, IntList list_to_append) {
   if (list_is_valid(list) && list_is_valid(list_to_append)) {
      for (int i = 0; i < list_to_append->size; i++) {
         list_insert(list, list_to_append->buffer[i]);
      }
      list_to_append->size = 0;
   }
}

/**
 * Splits the given `list` into a `left` and `right` part at the given `split_idx`.
 * The `left` list contains the items of `list` from head to `split_idx - 1` rendering
 * the size of the left part equal to `split_idx`. The `right` list contains
 * the items of `list` from originally `split_idx` to tail.
 * 
 * If `split_idx` is larger than the size of `list`, all items of `list` 
 * are moved to `left`, leaving the `right` list empty.
 * 
 * If a target list (`left`, `right`) is not empty, the nodes that are received from
 * `list` are appended.
 * 
 * If any of the given lists is invalid, the invocation is ignored.
 * 
 * @param list The list to split.
 * @param left The left part of the original list.
 * @param right The right part of the original list.
 * @param split_idx The index of the node of `list` that becomes the head of `right` list.
 */
void list_split(IntList list, IntList left, IntList right, unsigned int split_idx) {
   if (list_is_valid(list) && list_is_valid(left) && list_is_valid(right)) {
      if (split_idx >= list->size) {
         split_idx = list->size;
      }

      for (int i = 0; i < split_idx; i++) {
         list_insert(left, list->buffer[i]);
      }

      for (int i = split_idx; i < list->size; i++) {
         list_insert(right, list->buffer[i]);
      }

      list_clear(list);
   }
}

/**
 * Transfers the first node (the 'head') of the given `list` as last node ('tail') 
 * of the target list.
 * 
 * If any of the given lists is invalid or the source list is empty, the invocation is ignored.
 * 
 * @param list The list from which the `head` is transferred to `target_list`.
 * @param target_list The list that receives the head of `list`.
 */
void list_transfer_head(IntList list, IntList target_list) {
   if (list_is_valid(list) && list_is_valid(target_list) && !list_is_empty(list)) {
      int value = list->buffer[0];
      list_remove_at(list, 0);
      list_insert(target_list, value);
   }
}