Skip to content

Instantly share code, notes, and snippets.

@eurocat2k
Last active August 9, 2023 13:24
Show Gist options
  • Save eurocat2k/66f58fc608f170c98c2f09224e0d0f01 to your computer and use it in GitHub Desktop.
Save eurocat2k/66f58fc608f170c98c2f09224e0d0f01 to your computer and use it in GitHub Desktop.
vector data type library for C
#include "vector.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// instance of vector_t
struct vector_instance_t {
void *data;
size_t data_size;
int capacity;
int length;
int err_code;
bool initialized;
};
// API
void _vector_init(vector_ptr_t v, size_t data_size) {
assert((v != NULL));
assert(data_size);
v->initialized = false;
v->capacity = VECTOR_INIT_CAPACITY;
v->length = 0;
v->data_size = 0;
v->err_code = VECTOR_NO_ERROR;
if ((v->data = (void *)malloc(data_size * v->capacity)) != NULL) {
v->data_size = data_size;
v->initialized = true;
} else {
v->err_code = VECTOR_ERROR_ALLOC;
}
}
// vector new
vector_ptr_t vector_new(size_t data_size) {
vector_ptr_t v = NULL;
if ((v = (vector_ptr_t)calloc(1, sizeof(struct vector_instance_t))) != NULL) {
_vector_init(v, data_size);
if (v->err_code != VECTOR_NO_ERROR) {
free(v);
v = NULL;
return NULL;
}
return v;
}
return NULL;
}
//
void vector_init(vector_ptr_t v, size_t data_size) {
assert((v != NULL));
assert(data_size);
v->initialized = false;
v->capacity = VECTOR_INIT_CAPACITY;
v->length = 0;
v->data_size = 0;
v->err_code = VECTOR_NO_ERROR;
if ((v->data = (void *)malloc(data_size * v->capacity)) != NULL) {
v->data_size = data_size;
v->initialized = true;
} else {
v->err_code = VECTOR_ERROR_ALLOC;
}
}
//
int vector_length(vector_ptr_t v) {
assert((v != NULL));
return v->length;
}
//
int vector_capacity(vector_ptr_t v) {
assert((v != NULL));
return v->capacity;
}
//
size_t vector_data_size(vector_ptr_t v) {
assert((v != NULL));
return v->data_size;
}
//
bool vector_empty(vector_ptr_t v) {
assert((v != NULL));
return vector_length(v) == 0;
}
//
int vector_error_code(vector_ptr_t v) {
assert(v != NULL);
return v->err_code;
}
//
void vector_resize(vector_ptr_t v, int capacity) {
assert((v != NULL));
assert(v->initialized);
#ifdef DEBUG_ON
printf("vector_resize: %d to %d\n", v->capacity, capacity);
#endif
void *data = NULL;
v->err_code = VECTOR_NO_ERROR;
if ((data = realloc(v->data, (v->data_size * capacity))) != NULL) {
v->data = data;
v->capacity = capacity;
} else {
v->err_code = VECTOR_ERROR_REALLOC;
}
}
//
void _vector_resize(vector_ptr_t v) {
assert(v != NULL);
if (v->length == v->capacity) {
v->err_code = VECTOR_NO_ERROR;
int cap = v->capacity += v->capacity / 2;
void *data = NULL;
if ((data = realloc(v->data, v->data_size * cap)) != NULL) {
v->data = data;
} else {
v->err_code = VECTOR_ERROR_REALLOC;
}
}
}
//
void _vector_add_in(vector_ptr_t v, void *item, size_t pos) {
assert(v != NULL);
assert(item != NULL);
assert(pos <= v->length);
_vector_resize(v); // add new space for element if needed
if (!vector_error_code(v)) {
// no error occurred
// move elements to let new element fit in slot at position
void *ptr1, *ptr2, *ptr3 = v->data + (pos * v->data_size);
for (size_t i = v->length; i > pos; --i) {
ptr1 = v->data + (i * v->data_size);
ptr2 = v->data + ((i - 1) * v->data_size);
memmove(ptr1, (const void*) ptr2, v->data_size);
}
memmove(ptr3, (const void*)item, v->data_size);
v->length += 1;
}
}
//
void vector_push_at(vector_ptr_t v, void *item, size_t pos) {
assert(v != NULL);
assert(item != NULL);
assert(pos <= v->length);
_vector_add_in(v, item, pos);
}
//
void _vector_delete_in(vector_ptr_t v, size_t pos) {
if (pos < v->length) {
void *ptr1, *ptr2, *ptr3 = v->data;
// move elements
for (size_t i = pos; i < v->length - 1; ++i) {
ptr1 = ptr3 + (i * v->data_size);
ptr2 = ptr3 + ((i + 1) * v->data_size);
memmove(ptr1, ptr2, v->data_size);
}
_vector_resize(v);
if (v->err_code == 0) {
v->length -= 1;
}
}
}
//
void vector_delete_at(vector_ptr_t v, size_t pos) {
assert(v != NULL);
assert(v->initialized);
assert(pos);
if (v->length && pos < v->length) {
_vector_delete_in(v, pos);
}
}
//
void vector_delete_back(vector_ptr_t v) {
assert(v != NULL);
assert(v->initialized);
if (v->length) {
_vector_delete_in(v, v->length - 1);
}
}
//
void vector_delete_front(vector_ptr_t v) {
assert(v != NULL);
assert(v->initialized);
if (v->length) {
_vector_delete_in(v, 0);
}
}
//
void vector_push_back(vector_ptr_t v, void *item) {
assert((v != NULL));
assert(item != NULL);
assert(v->initialized);
_vector_resize(v); // add new space for element if needed
if (v->err_code == 0) {
// no error
if (v->length == 0) {
_vector_add_in(v, item, 0);
} else {
_vector_add_in(v, item, v->length);
}
}
}
//
void vector_push_front(vector_ptr_t v, void *item) {
assert(v != NULL);
assert(item != NULL);
assert(v->initialized);
_vector_add_in(v, item, 0);
}
//
void _vector_destroy(vector_ptr_t v) {
assert(v != NULL);
assert(v->initialized);
if (v->data != NULL) {
free(v->data);
v->data = NULL;
}
v->length = 0;
v->capacity = 0;
v->err_code = 0;
v->initialized = false;
}
//
void vector_destroy(vector_ptr_t *v) {
vector_ptr_t _v = *v;
_vector_destroy(_v);
free(_v);
_v = NULL;
*v = _v;
}
//
void vector_resize_to_fit(vector_ptr_t v) {
assert(v != NULL);
assert(v->initialized);
if (v->length) {
v->err_code = VECTOR_NO_ERROR;
void *data = NULL;
size_t cap = v->length + 1;
if ((data = realloc(v->data, (cap * v->data_size))) != NULL) {
v->capacity = cap;
v->data = data;
} else {
v->err_code = VECTOR_ERROR_REALLOC;
}
}
}
//
void _vector_set_at(vector_ptr_t v, void *item, size_t pos) {
if (pos < v->length) {
void *ptr = v->data + (pos * v->data_size);
memmove(ptr, (const void *)item, v->data_size);
}
}
//
void vector_set_at(vector_ptr_t v, void *item, size_t pos) {
assert(v != NULL);
assert(item != NULL);
assert(v->initialized);
_vector_set_at(v, item, pos);
}
//
void vector_set_front(vector_ptr_t v, void *item) {
assert(v != NULL);
assert(item != NULL);
assert(v->initialized);
_vector_set_at(v, item, 0);
}
//
void vector_set_back(vector_ptr_t v, void *item) {
assert(v != NULL);
assert(item != NULL);
assert(v->initialized);
_vector_set_at(v, item, v->length - 1);
}
//
void *_vector_get_at(vector_ptr_t v, size_t pos) {
return (v->data + (pos * v->data_size));
}
//
void *vector_get_at(vector_ptr_t v, size_t pos) {
assert(v != NULL);
assert(v->initialized);
if (pos < v->length) {
return (v->data + (pos * v->data_size));
}
return NULL;
}
//
void *vector_get_front(vector_ptr_t v) {
assert(v != NULL);
assert(v->initialized);
return _vector_get_at(v, 0);
}
//
void *vector_get_back(vector_ptr_t v) {
assert(v != NULL);
assert(v->initialized);
return _vector_get_at(v, v->length - 1);
}
#ifndef __VECTOR_H__
#define __VECTOR_H__
#include <unistd.h>
#include <stdlib.h>
#include <stdbool.h>
#ifdef __cplusplus
extern "C" {
#endif
#define VECTOR_INIT_CAPACITY 4
// define error codes
#define VECTOR_NO_ERROR 0
#define VECTOR_ERROR_ALLOC -1
#define VECTOR_ERROR_REALLOC -2
typedef struct vector_instance_t vector_t;
typedef vector_t* vector_ptr_t;
vector_ptr_t vector_new(size_t);
void vector_init(vector_ptr_t, size_t);
void vector_destroy(vector_ptr_t *);
int vector_error_code(vector_ptr_t);
int vector_length(vector_ptr_t);
int vector_capacity(vector_ptr_t);
bool vector_empty(vector_ptr_t);
void vector_resize(vector_ptr_t, int);
void vector_resize_to_fit(vector_ptr_t);
size_t vector_data_size(vector_ptr_t);
void vector_push_back(vector_ptr_t, void *);
void vector_push_front(vector_ptr_t, void *);
void vector_push_at(vector_ptr_t, void *, size_t);
void vector_delete_back(vector_ptr_t);
void vector_delete_front(vector_ptr_t);
void vector_delete_at(vector_ptr_t, size_t);
void *vector_get_at(vector_ptr_t, size_t);
void *vector_get_front(vector_ptr_t);
void *vector_get_back(vector_ptr_t);
void vector_set_at(vector_ptr_t, void *, size_t);
void vector_set_front(vector_ptr_t, void *);
void vector_set_back(vector_ptr_t, void *);
#ifdef __cplusplus
}
#endif
#endif // __VECTOR_H__
@eurocat2k
Copy link
Author

eurocat2k commented Aug 9, 2023

Vector data type and library written for C language

This little C library written to handle vector data type - similar in C++ - the memory management allows to handle item insertions or deletions dynamically.

API

Constructor

    vector_ptr_t vector_new(size_t);

Destructor

    void vector_destroy(vector_ptr_t *);

Destructs the vector data instance - free up memory used by.

Creates vector_ptr_t instance and initializes with VECTOR_INIT_CAPACITY free slots. The vector container data items are empty - no initialized, undefined - do not use them before set them!

Vector attribute setters and getters and aux functions

    void vector_init(vector_ptr_t, size_t);
    int vector_length(vector_ptr_t);
    int vector_capacity(vector_ptr_t);
    bool vector_empty(vector_ptr_t);
    size_t vector_data_size(vector_ptr_t);
  • vector_init (re)initializes the vector container updating the container's capacity. If the vector has got items in the data storage, after initialization they could be lost if the new capacity value is less than original capacity. Otherwise they will be intact.
  • vector_length returns the used slots in the vector container - the range between 0..capacity-1.
  • vector_capacity returns the capacity of the vector container - how many slots allocated for items.
  • vector_empty checks if vector container is empty - length = 0.
  • vector_data_size returns current vector container's elements size.

Vector element manipulations

  • void vector_push_back adds new element at the tail of the vector. If capacity equals with length, then try to allocate more memory for the new element. If no error, the vector data storage will be updated with all relevant attribute values as well.
  • vector_push_front adds new element at the head of the vector. All existing elements shift one position at insertion to let function reallocate and store new element. Error code set in vector instance - to check its value call vector_error_code(vector_ptr_t vec) - if 0, then insertion succeeded. Otherwise no insertion occurs.
  • vector_push_at inserts new element at position.
  • vector_delete_back removes the element at the tail position. The removed element going to be lost. If you need it, then get it, and save it before remove!
  • vector_delete_front same as above, but now the head element will be dropped out from the vector.
  • vector_delete_at delete element from vector at given position. The position check does not allow elements are not inside the vector.
  • vector_get_at gets element (well a pointer to the element in the vector's data storage) at given position. Position check does not allow to get none existing elements in the vector. In this case NULL will be the return value.
  • vector_get_front gets element at the head of the vector.
  • vector_get_back gets element from the tail of the vector.
  • vector_set_at modifies vector element at given position - see position check issues above. If position is in range between 0 and length - 1, then the new value will override the old one.
  • vector_set_front updates element at head of the vector.
  • vector_set_back updates element at the tail of the vector.

Sample code for test with integers

main.c

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include "vector.h"

int main(int argc, char **argv, char **envp) {
    // test vector for integers
    vector_ptr_t vec1 = vector_new(sizeof(int));
    printf("Address or vec1: %p\n", vec1);
    printf("Capacity of vec1: %d\n", vector_capacity(vec1));
    printf("Length of vec1: %d\n", vector_length(vec1));
    // test resize 1: grow
    vector_resize(vec1, 10);
    printf("Address or vec1 after resize 1: %p\n", vec1);
    printf("Capacity of vec1 after resize 1: %d\n", vector_capacity(vec1));
    printf("Length of vec1 after resize 1: %d\n", vector_length(vec1));
    if (vector_error_code(vec1)) {
        printf("Vector resize grow: NOK!\n");
    } else {
        printf("Vector resize grow: OK!\n");
    }
    // test resize 2: shrink
    vector_resize(vec1, 7);
    printf("Address or vec1 after resize 2: %p\n", vec1);
    printf("Capacity of vec1 after resize 2: %d\n", vector_capacity(vec1));
    printf("Length of vec1 after resize 2: %d\n", vector_length(vec1));
    if (vector_error_code(vec1)) {
        printf("Vector resize shrink: NOK!\n");
    } else {
        printf("Vector resize shrink: OK!\n");
    }
    // test fill random integer
    srand(time(NULL));  // initialize random generator
    int rnum = 0, *pnum = NULL, maxlen = 0, oldvalue;
    size_t pos = 0;
    for (int i = 0; i < vector_capacity(vec1); i += 1) {
        rnum = rand() % 100;
        printf("Push %d to vec1 at index %d\n", rnum, i);
        vector_push_back(vec1, (void *)&rnum);
    }
    maxlen = vector_length(vec1) - 1;
    printf("Address or vec1 after push: %p\n", vec1);
    printf("Capacity of vec1 after push: %d\n", vector_capacity(vec1));
    printf("Length of vec1 after push: %d\n", vector_length(vec1));
    // get front element
    pnum = vector_get_front(vec1);
    printf("First element in vec1: %d\n", *(int *)pnum);
    pnum = vector_get_back(vec1);
    printf("Last element in vec1: %d\n", *(int *)pnum);
    // pick an index from the vector
    pos = (size_t)(rand() % maxlen);
    pnum = vector_get_at(vec1, pos);
    printf("Element at pos %lu in vec1: %d\n", pos, *(int *)pnum);
    // modify the value of the element at pos
    rnum = 0;
    vector_push_at(vec1, &rnum, pos);
    pnum = vector_get_at(vec1, pos);
    printf("Element at pos %lu in vec1 after adding %d: %d\n", pos, rnum, *(int *)pnum);
    if (*(int *)pnum == rnum) {
        printf("Test modification at position: OK!\n");
    } else {
        printf("Test modification at position: NOK!\n");
    }
    // list vector elems
    for (int i = 0; i < vector_length(vec1); i += 1) {
        pnum = vector_get_at(vec1, i);
        printf("%d. Elem is %d in vec1\n", i, *(int *)pnum);
    }
    // test modify item at pos
    rnum = -1;
    printf("Test modify item at %zu with %d\n", pos, rnum);
    printf("List original vector:\n");
    pnum = vector_get_at(vec1, pos);
    oldvalue = *(int *)pnum;
    // list vector elems
    for (int i = 0; i < vector_length(vec1); i += 1) {
        pnum = vector_get_at(vec1, i);
        printf("%d. Elem is %d in vec1\n", i, *(int *)pnum);
    }
    vector_set_at(vec1, &rnum, pos);
    printf("Element modified from %d to %d at pos %zu\n", oldvalue, rnum, pos);
    printf("List modified vector 1 with size %d:\n", vector_length(vec1));
    for (int i = 0; i < vector_length(vec1); i += 1) {
        pnum = vector_get_at(vec1, i);
        printf("%d. Elem is %d in vec1\n", i, *(int *)pnum);
    }
    // test remove item at pos
    printf("Remove element from vec1 at pos %zu\n", pos);
    vector_delete_at(vec1, pos);
    printf("List modified vector 2 with size %d:\n", vector_length(vec1));
    for (int i = 0; i < vector_length(vec1); i += 1) {
        pnum = vector_get_at(vec1, i);
        printf("%d. Elem is %d in vec1\n", i, *(int *)pnum);
    }
    // Finish
    vector_destroy(vec1);
    printf("Check vec1 address: %p\n", vec1);
    return 0;
}

Compile and run

    % cc -o vector_test main.c vector.c vector.h

On my machine the result with valgrind looks like this:

Address or vec1: 0x54ce780
Capacity of vec1: 4
Length of vec1: 0
Address or vec1 after resize 1: 0x54ce780
Capacity of vec1 after resize 1: 10
Length of vec1 after resize 1: 0
Vector resize grow: OK!
Address or vec1 after resize 2: 0x54ce780
Capacity of vec1 after resize 2: 7
Length of vec1 after resize 2: 0
Vector resize shrink: OK!
Push 6 to vec1 at index 0
Push 17 to vec1 at index 1
Push 15 to vec1 at index 2
Push 87 to vec1 at index 3
Push 13 to vec1 at index 4
Push 93 to vec1 at index 5
Push 59 to vec1 at index 6
Address or vec1 after push: 0x54ce780
Capacity of vec1 after push: 7
Length of vec1 after push: 7
First element in vec1: 6
Last element in vec1: 59
Element at pos 5 in vec1: 93
Element at pos 5 in vec1 after adding 0: 0
Test modification at position: OK!
0. Elem is 6 in vec1
1. Elem is 17 in vec1
2. Elem is 15 in vec1
3. Elem is 87 in vec1
4. Elem is 13 in vec1
5. Elem is 0 in vec1
6. Elem is 93 in vec1
7. Elem is 59 in vec1
Test modify item at 5 with -1
List original vector:
0. Elem is 6 in vec1
1. Elem is 17 in vec1
2. Elem is 15 in vec1
3. Elem is 87 in vec1
4. Elem is 13 in vec1
5. Elem is 0 in vec1
6. Elem is 93 in vec1
7. Elem is 59 in vec1
Element modified from 0 to -1 at pos 5
List modified vector 1 with size 8:
0. Elem is 6 in vec1
1. Elem is 17 in vec1
2. Elem is 15 in vec1
3. Elem is 87 in vec1
4. Elem is 13 in vec1
5. Elem is -1 in vec1
6. Elem is 93 in vec1
7. Elem is 59 in vec1
Remove element from vec1 at pos 5
List modified vector 2 with size 7:
0. Elem is 6 in vec1
1. Elem is 17 in vec1
2. Elem is 15 in vec1
3. Elem is 87 in vec1
4. Elem is 13 in vec1
5. Elem is 93 in vec1
6. Elem is 59 in vec1
Check vec1 address: 0x0
==37332== 
==37332== HEAP SUMMARY:
==37332==     in use at exit: 6,000 bytes in 4 blocks
==37332==   total heap usage: 9 allocs, 5 frees, 6,156 bytes allocated
==37332== 
==37332== LEAK SUMMARY:
==37332==    definitely lost: 0 bytes in 0 blocks
==37332==    indirectly lost: 0 bytes in 0 blocks
==37332==      possibly lost: 0 bytes in 0 blocks
==37332==    still reachable: 1,904 bytes in 3 blocks
==37332==         suppressed: 4,096 bytes in 1 blocks
==37332== Rerun with --leak-check=full to see details of leaked memory
==37332== 
==37332== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
--37332-- 
--37332-- used_suppression:      1 MEMCHECK-LIBC-REACHABLE-1 /usr/local/libexec/valgrind/default.supp:582 suppressed: 4,096 bytes in 1 blocks
==37332== 
==37332== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment