/* * This is a generic vector implementation in C (it can store data of any type: * int, floats, structs, strings, etc). This implementation includes a * vector iterator for flexibility and efficiency reasons. * With the iterator, freeing heap-allocated insertions, dumping the data to * stdout, or implementing callback routines for each entry is easy to do. * * If you like this vector implementation or have any ideas of your own, you are * free to copy, share, and modify this program. */ #include #include #include #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) struct vector { unsigned int capacity; unsigned int size; void **data; }; struct vector_iter { struct vector *vector; unsigned int pos; void *entry; }; /* * Initializes a vector with the capacity we requested. If the number of * entries to be inserted are known ahead of time, it's much better to allocate * the memory up front to avoid reallocations. * A reasonable initial capacity is usually somewhere between 8 or 16. */ static int vector_create(struct vector *vector, unsigned int initial_capacity) { vector->capacity = initial_capacity; vector->size = 0; vector->data = malloc(vector->capacity * sizeof(*vector->data)); /* Turn the NULL-check into a boolean result. */ return !!vector->data; } static int vector_resize(struct vector *vector, unsigned int new_capacity) { /* * NOTE: realloc() may return NULL on failure and we do not want to * lose access to the initial memory block if it does. * To avoid it, we store the return value in a temporary. */ void **resized = realloc(vector->data, new_capacity * sizeof(*vector->data)); if (resized) { vector->data = resized; vector->capacity = new_capacity; return 1; } /* Reallocation failed */ return 0; } static int vector_reverse(struct vector *vector) { unsigned int i, size = vector->size; if (size < 2) { fputs("[Error]: Not enough elements to reverse!\n", stderr); return 0; } /* * Swap every entry on the lefthand side with the entry at the * righthand side until we reach the middle. */ for (i = 0; i < size >> 1; i++) { void *temp = vector->data[i]; vector->data[i] = vector->data[size-i-1]; vector->data[size-i-1] = temp; } return 1; } static int vector_insert(struct vector *vector, const void *data, unsigned int index) { unsigned int i; if (index > vector->size) return 0; /* Increment size and check if we need to grow the vector. */ if (++vector->size >= vector->capacity) if (!vector_resize(vector, vector->capacity << 1)) return 0; /* * Shift all entries one step ahead of the index to make * room for the new entry. */ for (i = vector->size; i > index; i--) vector->data[i] = vector->data[i-1]; /* Store the value */ vector->data[index] = (void *)data; return 1; } static int vector_append(struct vector *vector, const void *data) { if (vector->size >= vector->capacity) if (!vector_resize(vector, vector->capacity << 1)) return 0; vector->data[vector->size++] = (void *)data; return 1; } static int vector_prepend(struct vector *vector, const void *data) { return vector_insert(vector, data, 0); } /* Returns the element stored at position 'index' or NULL. */ static void *vector_get(const struct vector *vector, unsigned int index) { return (index < vector->size) ? vector->data[index] : NULL; } /* Look up an entry by value instead of its position in the vector. */ static void *vector_lookup(const struct vector *vector, void *data, int (*compare)(const void *a, const void *b)) { unsigned int pos = 0, size = vector->size; for (pos = 0; pos < size; pos++) if (compare(vector->data[pos], data) == 0) return vector->data[pos]; return NULL; } /* * Removes an entry from the vector at position 'index', the removed * entry is returned (as we may have to free it). */ static void *vector_remove(struct vector *vector, unsigned int index) { unsigned int i; void *ret = NULL; if (index >= vector->size) return NULL; /* Remove the entry */ ret = vector->data[index]; vector->data[index] = NULL; /* * Shift all the elements ahead of the removed entry * one step back. */ for (i = index; i < vector->size-1; i++) { vector->data[i] = vector->data[i + 1]; vector->data[i + 1] = NULL; } /* * Shrink the capacity by half if number of elements is * one fourth of the capacity. We want some overhead * to avoid growing the vector with the next insertion. */ if (--vector->size < vector->capacity >> 2) vector_resize(vector, vector->capacity << 1); return ret; } static void vector_free(struct vector *vector) { free(vector->data); memset(vector, 0, sizeof(*vector)); } static unsigned int vector_get_size(const struct vector *vector) { return vector->size; } static unsigned int vector_get_capacity(const struct vector *vector) { return vector->capacity; } /* Initializes a vector iterator. Accepts any vector we want to iterate over. */ static void vector_iter_init(struct vector_iter *iter, struct vector *vector) { iter->vector = vector; iter->pos = 0; iter->entry = NULL; } /* Returns the current entry and goes to the next. */ static const void *vector_iter_next(struct vector_iter *iter) { while (iter->pos < iter->vector->size) { iter->entry = iter->vector->data[iter->pos++]; return iter->entry ? iter->entry : NULL; } /* * Reset the position and return NULL when the last * entry is reached. */ iter->pos = 0; return NULL; } /* ------------------ End of Vector Implementation ---------------------- */ /* * The following two function-like macros are just helpers to * make the layout look a bit nicer. */ #define show_separator(width, ch) \ do { \ short w; \ for (w = 0; w < (width); w++) \ putchar(ch); \ putchar('\n'); \ } while (0) /* A function like macro which does nice two column splits. */ #define two_column_split(last, distro) \ do { \ printf("%c%-9s%c", \ (last) ? ' ' : '\t', distro, \ (last) ? '\n' : ' '); \ } while (0) /* * strdup() is POSIX standard but not ISO-C standard, so this is a * custom implementation of it (note the underscore). */ static char *strdup_(const char *src) { char *dup = malloc(strlen(src) + 1); return dup ? strcpy(dup, src) : NULL; } /* We pass this to vector_lookup() to find an entry by value. */ static int compare_str(const void *a, const void *b) { const char *str_a = a; const char *str_b = b; return strcmp(str_a, str_b); } static void test_vector_of_strings(void) { struct vector distrolist; struct vector_iter iter; unsigned int i; char *pick; /* Strings of GNU/Linux distributions (can by anything). */ const char *distributions[] = { "Redhat", "Gentoo", "Arch", "Artix", "Fedora", "Debian", "Ubuntu", "OpenSUSE", "CentOS", "Slackware", "Trisquel", "Parabola", "Alpine", "Manjaro" }; if (!vector_create(&distrolist, 8)) { fputs("Allocation failure: Vector creation failed!", stderr); return; } /* * We insert a copy of each string (a duplicate) which we * must remember to free later on... */ for (i = 0; i < ARRAY_SIZE(distributions); i++) vector_append(&distrolist, strdup_(distributions[i])); /* Display all the strings inserted into the vector */ puts("Available GNU/Linux Distros: "); vector_iter_init(&iter, &distrolist); for (i = 0; vector_iter_next(&iter); i++) { char *distro = iter.entry; two_column_split((i & 1), distro); } /* Print out the current capacity */ printf("\n> Vector Size: %-6uCapacity: %u\n", vector_get_size(&distrolist), vector_get_capacity(&distrolist)); show_separator(40, '_'); /* * Remove an entry from the vector at index '1' - the removed entry * is returned which allows us to free it. */ pick = vector_remove(&distrolist, 1); printf("\n> You picked: %s as your distribution. " "(Chosen distro will be removed).\n", pick); free(pick); /* Get an element from the vector at index '4' */ pick = vector_get(&distrolist, 4); printf("\n> You picked: %s as your backup distribution. " "(Chosen distro will be saved).\n\n", pick); /* Because we removed Gentoo from the vector we shouldn't find it. */ pick = vector_lookup(&distrolist, "Gentoo", compare_str); printf("Looking up Gentoo in the vector...\nStatus: Gentoo %s\n\n", pick ? "was found." : "was not found."); /* * The vector contains heap-allocated data and we must free each entry * before freeing the vector. The way I normally do it is by creating a * shorthand function named, ex, vector_free_() which does all * the cleanup stuff behind the scenes. */ puts("The following distributions are available: "); for (i = 0; vector_iter_next(&iter); i++) { char *distro = iter.entry; two_column_split((i & 1), distro); free(distro); } printf("\n\n> Vector Size: %-6uCapacity: %u\n", vector_get_size(&distrolist), vector_get_capacity(&distrolist)); /* Free the vector. */ vector_free(&distrolist); } static void test_vector_of_integers(void) { int i, another = 128, numbers[] = { 1, 2, 4, 8 }; struct vector vec; struct vector_iter iter; if (!vector_create(&vec, 4)) { fputs("Allocation Failure: Vector creation failed!", stderr); return; } printf("Created a vector with a capacity of %u, current size is: %u\n", vector_get_capacity(&vec), vector_get_size(&vec)); /* Add every number to the end of the vector */ fputs("Added: ", stdout); for (i = 0; i < ARRAY_SIZE(numbers); i++) { printf("%d ", numbers[i]); vector_append(&vec, &numbers[i]); } putchar('\n'); /* Reverse the order of all vector elements. */ puts("Reversed vector."); vector_reverse(&vec); /* Insert an element twice to the beginning of the vector. */ printf("\nInserted: %d at the beginning of the vector twice.\n", another); vector_insert(&vec, &another, 0); vector_prepend(&vec, &another); /* Insert an element at the end of the vector. */ printf("Inserted: %d at last position in the vector.\n\n", another); vector_insert(&vec, &another, vector_get_size(&vec)); /* Iterate through the vector and print out each entry. */ fputs("Vector Data: ", stdout); vector_iter_init(&iter, &vec); while (vector_iter_next(&iter)) { int num = *(int *)iter.entry; printf("%d ", num); } putchar('\n'); /* Print out the vector's size and capacity now that all the elements are added. */ show_separator(40, '-'); printf("Size: %u\tCapacity: %u\n", vector_get_size(&vec), vector_get_capacity(&vec)); vector_free(&vec); } int main(void) { puts("Vector of strings: "); show_separator(40, '_'); test_vector_of_strings(); show_separator(40, '_'); printf("\n\n\n\n"); puts("Vector of integers: "); show_separator(40, '_'); test_vector_of_integers(); return 0; } /* * This file is part of generic-vector.c * Created by Komodo64. * * 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 2 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 . */

[Data Structures] : Generic Vector in C