vector.c

// The MIT License (MIT)
// Copyright (c) 2016 Peter Goldsborough
// 
// Permission is hereby granted, free of charge, to any person obtaining a copy of
// this software and associated documentation files (the "Software"), to deal in
// the Software without restriction, including without limitation the rights to
// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
// the Software, and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
// 
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
	
#define __STDC_WANT_LIB_EXT1__ 1

#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "vector.h"

int vector_setup(Vector* vector, size_t capacity, size_t element_size) {
	assert(vector != NULL);

	if (vector == NULL) return VECTOR_ERROR;

	vector->size = 0;
	vector->capacity = MAX(VECTOR_MINIMUM_CAPACITY, capacity);
	vector->element_size = element_size;
	vector->data = malloc(vector->capacity * element_size);

	return vector->data == NULL ? VECTOR_ERROR : VECTOR_SUCCESS;
}

int vector_copy(Vector* destination, Vector* source) {
	assert(destination != NULL);
	assert(source != NULL);
	assert(vector_is_initialized(source));
	assert(!vector_is_initialized(destination));

	if (destination == NULL) return VECTOR_ERROR;
	if (source == NULL) return VECTOR_ERROR;
	if (vector_is_initialized(destination)) return VECTOR_ERROR;
	if (!vector_is_initialized(source)) return VECTOR_ERROR;

	/* Copy ALL the data */
	destination->size = source->size;
	destination->capacity = source->size * 2;
	destination->element_size = source->element_size;

	/* Note that we are not necessarily allocating the same capacity */
	destination->data = malloc(destination->capacity * source->element_size);
	if (destination->data == NULL) return VECTOR_ERROR;

	memcpy(destination->data, source->data, vector_byte_size(source));

	return VECTOR_SUCCESS;
}

int vector_copy_assign(Vector* destination, Vector* source) {
	assert(destination != NULL);
	assert(source != NULL);
	assert(vector_is_initialized(source));
	assert(vector_is_initialized(destination));

	if (destination == NULL) return VECTOR_ERROR;
	if (source == NULL) return VECTOR_ERROR;
	if (!vector_is_initialized(destination)) return VECTOR_ERROR;
	if (!vector_is_initialized(source)) return VECTOR_ERROR;

	vector_destroy(destination);

	return vector_copy(destination, source);
}

int vector_move(Vector* destination, Vector* source) {
	assert(destination != NULL);
	assert(source != NULL);

	if (destination == NULL) return VECTOR_ERROR;
	if (source == NULL) return VECTOR_ERROR;

	*destination = *source;
	source->data = NULL;

	return VECTOR_SUCCESS;
}

int vector_move_assign(Vector* destination, Vector* source) {
	vector_swap(destination, source);
	return vector_destroy(source);
}

int vector_swap(Vector* destination, Vector* source) {
	void* temp;

	assert(destination != NULL);
	assert(source != NULL);
	assert(vector_is_initialized(source));
	assert(vector_is_initialized(destination));

	if (destination == NULL) return VECTOR_ERROR;
	if (source == NULL) return VECTOR_ERROR;
	if (!vector_is_initialized(destination)) return VECTOR_ERROR;
	if (!vector_is_initialized(source)) return VECTOR_ERROR;

	_vector_swap(&destination->size, &source->size);
	_vector_swap(&destination->capacity, &source->capacity);
	_vector_swap(&destination->element_size, &source->element_size);

	temp = destination->data;
	destination->data = source->data;
	source->data = temp;

	return VECTOR_SUCCESS;
}

int vector_destroy(Vector* vector) {
	assert(vector != NULL);

	if (vector == NULL) return VECTOR_ERROR;

	free(vector->data);
	vector->data = NULL;

	return VECTOR_SUCCESS;
}

/* Insertion */
int vector_push_back(Vector* vector, void* element) {
	assert(vector != NULL);
	assert(element != NULL);

	if (_vector_should_grow(vector)) {
		if (_vector_adjust_capacity(vector) == VECTOR_ERROR) {
			return VECTOR_ERROR;
		}
	}

	_vector_assign(vector, vector->size, element);

	++vector->size;

	return VECTOR_SUCCESS;
}

int vector_push_front(Vector* vector, void* element) {
	return vector_insert(vector, 0, element);
}

int vector_insert(Vector* vector, size_t index, void* element) {
	void* offset;

	assert(vector != NULL);
	assert(element != NULL);
	assert(index <= vector->size);

	if (vector == NULL) return VECTOR_ERROR;
	if (element == NULL) return VECTOR_ERROR;
	if (vector->element_size == 0) return VECTOR_ERROR;
	if (index > vector->size) return VECTOR_ERROR;

	if (_vector_should_grow(vector)) {
		if (_vector_adjust_capacity(vector) == VECTOR_ERROR) {
			return VECTOR_ERROR;
		}
	}

	/* Move other elements to the right */
	if (_vector_move_right(vector, index) == VECTOR_ERROR) {
		return VECTOR_ERROR;
	}

	/* Insert the element */
	offset = _vector_offset(vector, index);
	memcpy(offset, element, vector->element_size);
	++vector->size;

	return VECTOR_SUCCESS;
}

int vector_assign(Vector* vector, size_t index, void* element) {
	assert(vector != NULL);
	assert(element != NULL);
	assert(index < vector->size);

	if (vector == NULL) return VECTOR_ERROR;
	if (element == NULL) return VECTOR_ERROR;
	if (vector->element_size == 0) return VECTOR_ERROR;
	if (index >= vector->size) return VECTOR_ERROR;

	_vector_assign(vector, index, element);

	return VECTOR_SUCCESS;
}

/* Deletion */
int vector_pop_back(Vector* vector) {
	assert(vector != NULL);
	assert(vector->size > 0);

	if (vector == NULL) return VECTOR_ERROR;
	if (vector->element_size == 0) return VECTOR_ERROR;

	--vector->size;

#ifndef VECTOR_NO_SHRINK
	if (_vector_should_shrink(vector)) {
		_vector_adjust_capacity(vector);
	}
#endif

	return VECTOR_SUCCESS;
}

int vector_pop_front(Vector* vector) {
	return vector_erase(vector, 0);
}

int vector_erase(Vector* vector, size_t index) {
	assert(vector != NULL);
	assert(index < vector->size);

	if (vector == NULL) return VECTOR_ERROR;
	if (vector->element_size == 0) return VECTOR_ERROR;
	if (index >= vector->size) return VECTOR_ERROR;

	/* Just overwrite */
	_vector_move_left(vector, index);

#ifndef VECTOR_NO_SHRINK
	if (--vector->size == vector->capacity / 4) {
		_vector_adjust_capacity(vector);
	}
#endif

	return VECTOR_SUCCESS;
}

int vector_clear(Vector* vector) {
	return vector_resize(vector, 0);
}

/* Lookup */
void* vector_get(Vector* vector, size_t index) {
	assert(vector != NULL);
	assert(index < vector->size);

	if (vector == NULL) return NULL;
	if (vector->element_size == 0) return NULL;
	if (index >= vector->size) return NULL;

	return _vector_offset(vector, index);
}

const void* vector_const_get(const Vector* vector, size_t index) {
	assert(vector != NULL);
	assert(index < vector->size);

	if (vector == NULL) return NULL;
	if (vector->element_size == 0) return NULL;
	if (index >= vector->size) return NULL;

	return _vector_const_offset(vector, index);
}

void* vector_front(Vector* vector) {
	return vector_get(vector, 0);
}

void* vector_back(Vector* vector) {
	return vector_get(vector, vector->size - 1);
}

/* Information */

bool vector_is_initialized(const Vector* vector) {
	return vector->data != NULL;
}

size_t vector_byte_size(const Vector* vector) {
	return vector->size * vector->element_size;
}

size_t vector_free_space(const Vector* vector) {
	return vector->capacity - vector->size;
}

bool vector_is_empty(const Vector* vector) {
	return vector->size == 0;
}

/* Memory management */
int vector_resize(Vector* vector, size_t new_size) {
	if (new_size <= vector->capacity * VECTOR_SHRINK_THRESHOLD) {
		vector->size = new_size;
		if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1) {
			return VECTOR_ERROR;
		}
	} else if (new_size > vector->capacity) {
		if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1) {
			return VECTOR_ERROR;
		}
	}

	vector->size = new_size;

	return VECTOR_SUCCESS;
}

int vector_reserve(Vector* vector, size_t minimum_capacity) {
	if (minimum_capacity > vector->capacity) {
		if (_vector_reallocate(vector, minimum_capacity) == VECTOR_ERROR) {
			return VECTOR_ERROR;
		}
	}

	return VECTOR_SUCCESS;
}

int vector_shrink_to_fit(Vector* vector) {
	return _vector_reallocate(vector, vector->size);
}

/* Iterators */
Iterator vector_begin(Vector* vector) {
	return vector_iterator(vector, 0);
}

Iterator vector_end(Vector* vector) {
	return vector_iterator(vector, vector->size);
}

Iterator vector_iterator(Vector* vector, size_t index) {
	Iterator iterator = {NULL, 0};

	assert(vector != NULL);
	assert(index <= vector->size);

	if (vector == NULL) return iterator;
	if (index > vector->size) return iterator;
	if (vector->element_size == 0) return iterator;

	iterator.pointer = _vector_offset(vector, index);
	iterator.element_size = vector->element_size;

	return iterator;
}

void* iterator_get(Iterator* iterator) {
	return iterator->pointer;
}

int iterator_erase(Vector* vector, Iterator* iterator) {
	size_t index = iterator_index(vector, iterator);

	if (vector_erase(vector, index) == VECTOR_ERROR) {
		return VECTOR_ERROR;
	}

	*iterator = vector_iterator(vector, index);

	return VECTOR_SUCCESS;
}

void iterator_increment(Iterator* iterator) {
	assert(iterator != NULL);
	iterator->pointer += iterator->element_size;
}

void iterator_decrement(Iterator* iterator) {
	assert(iterator != NULL);
	iterator->pointer -= iterator->element_size;
}

void* iterator_next(Iterator* iterator) {
	void* current = iterator->pointer;
	iterator_increment(iterator);

	return current;
}

void* iterator_previous(Iterator* iterator) {
	void* current = iterator->pointer;
	iterator_decrement(iterator);

	return current;
}

bool iterator_equals(Iterator* first, Iterator* second) {
	assert(first->element_size == second->element_size);
	return first->pointer == second->pointer;
}

bool iterator_is_before(Iterator* first, Iterator* second) {
	assert(first->element_size == second->element_size);
	return first->pointer < second->pointer;
}

bool iterator_is_after(Iterator* first, Iterator* second) {
	assert(first->element_size == second->element_size);
	return first->pointer > second->pointer;
}

size_t iterator_index(Vector* vector, Iterator* iterator) {
	assert(vector != NULL);
	assert(iterator != NULL);
	return (iterator->pointer - vector->data) / vector->element_size;
}

/***** PRIVATE *****/

bool _vector_should_grow(Vector* vector) {
	assert(vector->size <= vector->capacity);
	return vector->size == vector->capacity;
}

bool _vector_should_shrink(Vector* vector) {
	assert(vector->size <= vector->capacity);
	return vector->size == vector->capacity * VECTOR_SHRINK_THRESHOLD;
}

size_t _vector_free_bytes(const Vector* vector) {
	return vector_free_space(vector) * vector->element_size;
}

void* _vector_offset(Vector* vector, size_t index) {
	return vector->data + (index * vector->element_size);
}

const void* _vector_const_offset(const Vector* vector, size_t index) {
	return vector->data + (index * vector->element_size);
}

void _vector_assign(Vector* vector, size_t index, void* element) {
	/* Insert the element */
	void* offset = _vector_offset(vector, index);
	memcpy(offset, element, vector->element_size);
}

int _vector_move_right(Vector* vector, size_t index) {
	assert(vector->size < vector->capacity);

	/* The location where to start to move from. */
	void* offset = _vector_offset(vector, index);

	/* How many to move to the right. */
	size_t elements_in_bytes = (vector->size - index) * vector->element_size;

#ifdef __STDC_LIB_EXT1__
	size_t right_capacity_in_bytes =
			(vector->capacity - (index + 1)) * vector->element_size;

	/* clang-format off */
	int return_code =  memmove_s(
		offset + vector->element_size,
		right_capacity_in_bytes,
		offset,
		elements_in_bytes
	);
	/* clang-format on */

	return return_code == 0 ? VECTOR_SUCCESS : VECTOR_ERROR;

#else
	memmove(offset + vector->element_size, offset, elements_in_bytes);
	return VECTOR_SUCCESS;
#endif
}

void _vector_move_left(Vector* vector, size_t index) {
	size_t right_elements_in_bytes;
	void* offset;

	/* The offset into the memory */
	offset = _vector_offset(vector, index);

	/* How many to move to the left */
	right_elements_in_bytes = (vector->size - index - 1) * vector->element_size;

	memmove(offset, offset + vector->element_size, right_elements_in_bytes);
}

int _vector_adjust_capacity(Vector* vector) {
	return _vector_reallocate(vector,
														MAX(1, vector->size * VECTOR_GROWTH_FACTOR));
}

int _vector_reallocate(Vector* vector, size_t new_capacity) {
	size_t new_capacity_in_bytes;
	void* old;
	assert(vector != NULL);

	if (new_capacity < VECTOR_MINIMUM_CAPACITY) {
		if (vector->capacity > VECTOR_MINIMUM_CAPACITY) {
			new_capacity = VECTOR_MINIMUM_CAPACITY;
		} else {
			/* NO-OP */
			return VECTOR_SUCCESS;
		}
	}

	new_capacity_in_bytes = new_capacity * vector->element_size;
	old = vector->data;

	if ((vector->data = malloc(new_capacity_in_bytes)) == NULL) {
		return VECTOR_ERROR;
	}

#ifdef __STDC_LIB_EXT1__
	/* clang-format off */
	if (memcpy_s(vector->data,
							 new_capacity_in_bytes,
							 old,
							 vector_byte_size(vector)) != 0) {
		return VECTOR_ERROR;
	}
/* clang-format on */
#else
	memcpy(vector->data, old, vector_byte_size(vector));
#endif

	vector->capacity = new_capacity;

	free(old);

	return VECTOR_SUCCESS;
}

void _vector_swap(size_t* first, size_t* second) {
	size_t temp = *first;
	*first = *second;
	*second = temp;
}