C_lib/vector/vector.c

/*
* C_lib Copyright (C) 2021 Wael Karram.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 3 of the License.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program.  If not, see <https://www.gnu.org/licenses/>.
*/

/* This file contains the function implementations for a vector. */
/* Include guard + includes. */
#ifndef VECTOR_C
#define VECTOR_C
#include "vector.h"
#endif /* VECTOR_C */

/* Function implementations. */

/* This function initializes a new empty vector, returns NULL on failure. */
static inline vector_t* initialize_vector() {
	/* Local variables. */
	vector_t *vector;

	/* Attempt to allocate. */
	vector = (vector_t*) malloc(sizeof(vector_t));
	/* Check the allocation. */
	if (vector == NULL)
		return NULL;

	/* Set the initial values. */
	vector->power = INITIAL_POWER_VECTOR_C;
	vector->length = powl(GROWTH_CONSTANT_VECTOR_C, INITIAL_POWER_VECTOR_C);
	vector->element_size = sizeof(void*); /* For better portability. */
	vector->last_element = (size_t) LAST_ELEMENT_EMPTY_INDEX_VECTOR_C;
	vector->empty = (char) TRUE;

	/* Attempt to allocate the array. */
	vector->array = (void_ptr*) malloc(vector->length * sizeof(void*));
	/* Check the allocation. */
	if (vector->array == NULL) {
		free(vector);
		return NULL;
	}

	/* Return the pointer. */
	return vector;
}

/* This function appends a value to a vector, user should verify that size of data is compatible! */
/* Note that if a failure code is returned, then the original vector wasn't changed whatsoever. */
/* Returns SUCCESS_CODE_VECTOR_C on success and FAILURE_CODE_VECTOR_C on failure. */
/* Undefined behavior for NULL vectors. */
static inline int append_to_vector(vector_t* vector, void* const data) {
	/* Sanity check. */
	assert(vector);

	/* Check if the vector has enough space. */
	if (check_vector_grow(vector, THRESHOLD_GROW_VECTOR_C)) {
		/* Grow the vector. */
		if (!grow_vector(vector))
			return FAILURE_CODE_VECTOR_C;
	}

	/* Add the value to the end. */
	*(vector->array + (((vector->empty) ? 0 : vector->last_element) * vector->element_size)) = data;
	/* Set the vector to be non-empty and set the index correctly if needed. */
	if (vector->empty) {
		vector->empty = (char) FALSE;
		vector->last_element = 0L;
	} else {
		/* Increment the internal index. */
		vector->last_element = vector->last_element + 1L;
	}

	/* Return success. */
	return SUCCESS_CODE_VECTOR_C;
}

/* This function prepends a value to a vector, user should verify that size of data is compatible! */
/* Note that if a failure code is returned, then the original vector wasn't changed whatsoever. */
/* Returns SUCCESS_CODE_VECTOR_C on success and FAILURE_CODE_VECTOR_C on failure. */
/* Undefined behavior for NULL vectors. */
static inline int prepend_to_vector(vector_t* const vector, void* const data) {
	/* Sanity check. */
	assert(vector);

	/* Check if the vector has enough space. */
	if (check_vector_grow(vector, THRESHOLD_GROW_VECTOR_C)) {
		/* Grow the vector. */
		if (!grow_vector(vector))
			return FAILURE_CODE_VECTOR_C;
	}

	/* Check if the vector is empty. */
	if (vector->empty)
		return append_to_vector(vector, data);

	/* Push the vector by 1. */
	push_vector(vector, 1L);

	/* Prepend. */
	*(vector->array) = data;
	/* Increment the internal index. */
	vector->last_element = vector->last_element + 1L;

	/* Return success. */
	return SUCCESS_CODE_VECTOR_C;
}

/* This function reads from the vector at the given index. */
/* Returns NULL on error. */
/* NULL can also be a perfectly fine value to store and retrieve. */
/* Undefined behavior for NULL vectors. */
static inline void* read_from_vector(const vector_t* const vector, const size_t index) {
	/* Sanity check. */
	assert(vector && vector->last_element >= index && !(vector->empty));

	/* Read and return the pointer. */
	return *(vector->array + (index * vector->element_size));
}

/* This function reads from the vector at the given index. */
/* Returns NULL on error and sets error to the error code. */
/* NULL can also be a perfectly fine value to store and retrieve. */
/* Undefined behavior for NULL vectors. */
/* Disallows writes beyond last_index + 1. */
static inline int write_to_vector(vector_t* const vector, const size_t index, void* const data) {
	/* Sanity check. */
	assert(vector && vector->length > index && (vector->last_element + 1L) > index);

	/* Check if the vector is empty. */
	if (vector->empty)
		return append_to_vector(vector, data);

	/* Check if the write is over-writing or not. */
	/* Check for an append call. */
	if (index == (vector->last_element + 1L))
		return append_to_vector(vector, data);
	/* Overwriting call! */
	*(vector->array + (index * vector->element_size)) = data;
	vector->last_element = vector->last_element + 1L;

	/* Check if the vector needs to be grown. */
	if (check_vector_grow(vector, THRESHOLD_GROW_VECTOR_C))
		return (grow_vector(vector)) ? SUCCESS_CODE_VECTOR_C : WRITE_SUCCESS_VECTOR_GROW_FAIL_VECTOR_C;

	/* Done. */
	return SUCCESS_CODE_VECTOR_C;
}

/* This function deletes from the vector at the given index. */
/* Undefined behavior for NULL vectors. */
/* Disallows deletes out of bounds. */
/* free_function mustn't be NULL. */
/* Silently fails when index is out of bounds. */
static inline void delete_from_vector(vector_t* const vector, const size_t index, void (*free_function)(const void*)) {
	/* Sanity checks. */
	assert(vector && (vector->array) && !((vector->length <= index) || ((vector->last_element + 1L) < index)));

	/* Check if the vector is empty. */
	if (vector->empty)
		return;

	/* Local variables. */
	void_ptr pointer = vector->array;
	size_t i, j;

	/* Free the internal data. */
	if (free_function)
		free_function((vector->array + (index * vector->element_size)));
	else
		free((vector->array + (index * vector->element_size)));
	*(vector->array + (index * vector->element_size)) = NULL;

	/* Compact the vector manually and return the result accordingly. */
	/* This can be done in O(n-k) instead of compact_vector's O(n^2). */
	for (j = index; j < vector->length - 1; j++) {
			/* Current pointer is NULL, swap with the next one. */
			swap_void_ptr(pointer + (j * vector->element_size), pointer + (j *(vector->element_size + 1)), vector->element_size);
	}

	/* Move back the last element by 1. */
	vector->last_element -= 1L;

	/* Check if the vector should be shrunk. */
	if (check_vector_shrink(vector, THRESHOLD_SHRINK_VECTOR_C))
		shrink_vector(vector);
}

/* This function serializes a vector into a copy array. */
/* Returns NULL on allocation failure. */
/* Will exhibit undefined behavior if the vector is NULL or is internally undefined. */
/* Caller should free the allocated buffer! */
/* Note that calling this function on an empty vector might result in Undefined Behavior. */
static inline void_ptr* serialize_vector(const vector_t* const vector) {
	/* Sanity check. */
	assert(vector);

	/* Attempt to allocate the new buffer. */
	void_ptr *buffer = (void_ptr*) malloc(vector->length * vector->element_size);

	/* Check the allocation. */
	if (buffer == NULL)
		return NULL;

	/* Copy. */
	return memcpy(buffer, vector->array, vector->length * vector->element_size);
}

/* This function initializes a new vector and copies the source vector into it (including data). */
/* Returns NULL on allocation failure. */
/* Will exhibit undefined behavior if the vector is NULL or is internally undefined. */
/* Caller should free the allocated data! */
static inline int copy_vector(vector_t *restrict source, vector_t **restrict destination) {
	/* Sanity check. */
	assert(source && source->array && destination);

	/* Attempt to intialize an empty vector struct. */
	*destination = initialize_vector();
	if (*destination == NULL)
		return ALLOC_FAILURE_VECTOR_C;

	/* Set the fields. */
	(*destination)->power = source->power;
	(*destination)->length = source->length;
	(*destination)->element_size = source->element_size;
	(*destination)->last_element = source->last_element;
	(*destination)->empty = source->empty;
	(*destination)->array = serialize_vector(source);

	/* Check if the copy failed. */
	if ((*destination)->array == NULL) {
		/* Clean-up. */
		free(*destination);
		*destination = NULL;
		return ALLOC_FAILURE_VECTOR_C;
	}

	/* Done. */
	return SUCCESS_CODE_VECTOR_C;
}

/* This function frees a vector, free_function is used to free the data stored within. */
/* Undefined behavior on NULL vectors and malformed vectors. */
/* If free_function is NULL, then the data doesn't get freed. */
static inline void free_vector(vector_t *vector, void (*free_function)(const void*)) {
	/* Local variables. */
	size_t index;

	/* Sanity check. */
	assert(vector);

	/* Check if to free the data. */
	if (free_function != NULL)
		for (index = 0L; index <= vector->last_element; index++)
			free_function(*(vector->array + (index * vector->element_size)));

	/* Free the array. */
	free(vector->array);
	/* Free the vector. */
	free(vector);
}

/* Internal functions. */
/* This function checks if the vector needs to be grown or kept as is. */
static inline int check_vector_grow(const vector_t* const vector, const double threshold) {
	/* Sanity check. */
	assert(vector);

	/* Calculate the threshold and length. */
	size_t current_size = vector->last_element;
	size_t current_threshold = (size_t)((vector->length) * threshold);
	/* Check if it needs to be grown. */
	return (current_size >= current_threshold) ? CODE_GROW_VECTOR_C : CODE_KEEP_VECTOR_C;
}

/* This function checks if the vector needs to be shrunk or kept as is. */
static inline int check_vector_shrink(const vector_t* const vector, const double threshold) {
	/* Sanity check. */
	assert(vector);

	/* Calculate the threshold and length. */
	size_t current_size = vector->last_element;
	size_t current_threshold = (size_t)((vector->length) * (THRESHOLD_WHOLE_VECTOR_C - threshold));
	/* Check if it needs to be shrunk. */
	return (current_size <= current_threshold) ? CODE_SHRINK_VECTOR_C : CODE_KEEP_VECTOR_C;
}

/* This function grows a vector, doesn't change it on failure. */
/* Returns SUCCESS_CODE_VECTOR_C on success and FAILURE_CODE_VECTOR_C on failure. */
static inline int grow_vector(vector_t* const vector) {
	/* Sanity check. */
	assert(vector && (vector->array));

	/* Local variables. */
	size_t size;
	void* array;

	/* Calculate the new size. */
	size = ((vector->length * vector->element_size) * GROWTH_CONSTANT_VECTOR_C);

	/* Attempt to reallocate, and return the result. */
	array = realloc(vector->array, size);

	/* Check if the allocation succeeded. */
	if (array != NULL) {
		/* Put the new pointer in. */
		vector->array = array;
		/* Update the length. */
		vector->length = size;
		/* Return success. */
		return SUCCESS_CODE_VECTOR_C;
	}

	/* Allocation failed. */
	return FAILURE_CODE_VECTOR_C;
}

/* This function shrinks a vector, doesn't change it on failure. */
/* Note that if the vector cannot be shrunk according to the growth factor, data loss may occure. */
/* Returns SUCCESS_CODE_VECTOR_C on success and FAILURE_CODE_VECTOR_C on failure. */
static inline int shrink_vector(vector_t* const vector) {
	/* Sanity check. */
	assert(vector);

	/* Local variables. */
	size_t size;
	void* array;

	/* Calculate the new size. */
	size = ((vector->length * vector->element_size) / GROWTH_CONSTANT_VECTOR_C);

	/* Attempt to reallocate, and return the result. */
	array = realloc(vector->array, size);

	/* Check if the allocation succeeded. */
	if (array != NULL) {
		/* Put the new pointer in. */
		vector->array = array;
		/* Update the length. */
		vector->length = size;
		/* Return success. */
		return SUCCESS_CODE_VECTOR_C;
	}

	/* Allocation failed. */
	return FAILURE_CODE_VECTOR_C;
}

/* This function compacts a vector by pushing all the NULLs to the end. */
/* Try to avoid calling it unless needed as it has an O(n^2) runtime complexity. */
static inline void compact_vector(vector_t* const vector) {
	/* Sanity check. */
	assert(vector && (vector->array));

	/* Loop and push. */
	void_ptr *pointer = vector->array;
	size_t i, j;

	/* This loop handles compacting the vector in O(n^2), sort of like bubble sort for NULL values. */
	for (i = 0; i < vector->length; i++)
		for (j = 0; j < vector->length - 1; j++)
			if (*(pointer + (j * vector->element_size)) == (void_ptr) NULL) {
				/* Current pointer is NULL, swap with the next one. */
				swap_void_ptr(pointer + (j * vector->element_size), pointer + (j *(vector->element_size + 1)), vector->element_size);
			}
}

/* This function creates a "gap" (of NULL) at the start of the vector, doesn't do any sanity checking! */
static inline void push_vector(const vector_t* const vector, const size_t gap_length) {
	/* Sanity check. */
	 assert(vector && (vector->array));

	/* Local variables. */
	size_t i;

	/* Push from the end to the start. */
	for (i = vector->last_element; i >= 0L; i--)
		swap_void_ptr(vector->array + ((i + gap_length ) * vector->element_size), vector->array + (i * vector->element_size), vector->element_size);
	/* Put NULL in the start of the vector. */
	for (i = 0L; i < gap_length; i++)
		*(vector->array + (i * vector->element_size)) = (void*) NULL;
}