A pure C data structure and and algorithms library
The goal of this project is to provide reusable, fast, and efficient data structures
- String
- Vector
- Queue
- Doubly Linked List
- Priotity Queue
- Hashtable
- AVL Tree
- Generic Tree
- LRU
- Set
- Small Vector
- Binary search
- Bubble sort
- Insertion sort
- Merge sort
- Quick sort
- Tree traversals
-
cmake >= 3.10
-
gcc
-
Ensure you have the items listed in Requirements
-
Clone this repo
git clone git@github.com:vincer2040/vlib.git
cd vlib
- Build it
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
- Optionally run tests
from within the build directory:
make test
- Install
the default path is /usr/local/lib
make install
#include "vlib.h" into your project and compile vlib along with
your binary. The library should be statically linked.
A string implementation that is optimzed for small strings. Max string length for a small string is 23 bytes. If it is longer than 23 bytes, it will be allocated on the heap.
create a new vstr:
vstr vstr_new(void);create a vstr from a C string. Must be null terminated as strlen is called:
vstr vstr_from(const char* cstr);create a new vstr from a traditional C string of length len
vstr vstr_from_len(const char* cstr, size_t len);create a vstr from a formatted string
vstr vstr_format(const char* fmt, ...);get the length of the vstr:
size_t vstr_len(vstr* s);get the data buffer of a vstr:
const char* vstr_data(vstr* s);compare two vstrs:
int vstr_cmp(vstr* a, vstr* b);append a char to a vstr:
int vstr_push_char(vstr* s, char c);append a string to a vstr
int vstr_push_string(vstr* s, const char* str);free a vstr:
void vstr_free(vstr* s);A generic vector implementation
Allocate a new vector
vec* vec_new(size_t data_size);Allocate a new vector with an initial capacity
vec* vec_new_with_capacity(size_t data_size, size_t capacity);Append data to the vector
int vec_push(vec** vec, void* data);Remove the most recently push element from the vector
int vec_pop(vec* vec, void* out);Retrieve data from at an index
void* vec_get_at(vec* vec, size_t idx);Remove an element at a specific index
int vec_remove_at(vec* vec, size_t idx, void* out);Find an element in the vector using linear search
ssize_t vec_find(vec* vec, void* cmp_data, void* out, CmpFn* fn);Free a vector
void vec_free(vec* vec, FreeFn* fn);Search in a vector using binary search
int vec_binary_search(vec* vec, void* needle, CmpFn* fn);Sort a vector using bubble sort
void vec_bubble_sort(vec* vec, CmpFn* fn);sort a vector using insertion sort
void vec_insertion_sort(vec* vec, CmpFn* fn);sort a vector using merge sort
void vec_merge_sort(vec* vec, CmpFn* fn);Sort a vector using quick sort
void vec_quick_sort(vec* vec, CmpFn* fn);A node based queue implementation
Create a new queue
queue queue_new(size_t data_size);Get the number of elements in the queue
size_t queue_len(queue* q);Get the element at the front of the queue without dequing
void* queue_peek(queue* q);Enque data
int queue_enque(queue* q, void* data);Deque data
int queue_deque(queue* q, void* out);Free the queue
void queue_free(queue* q, FreeFn* fn);A doubly linked list based on the Java interface
Create a new list
list list_new(size_t data_size);Get the number of items in the list
size_t list_len(list* list);Insert data at a specific index
int list_insert_at(list* list, void* data, size_t idx);Remove a specific item from a list
int list_remove(list* list, void* data, void* out, CmpFn* cmp_fn);Remove an item from a specific index
int list_remove_at(list* list, size_t idx, void* out);Append data to end of the list
int list_append(list* list, void* data);Prepend data to front of the list
int list_prepend(list* list, void* data);Get an item from the list at a specific index
void* list_get(list* list, size_t idx);Free the whole list
void list_free(list* list, FreeFn* fn);A priority queue/min-heap implementation
Allocate a new pq
pq* pq_new(size_t data_size);Insert data into priority queue
int pq_insert(pq** pq, void* value, CmpFn* fn);Delete/poll from priority queue
int pq_delete(pq* pq, void* out, CmpFn* fn);Free the while priority queue
void pq_free(pq* pq, FreeFn* fn);A hashtable implementation
-
uses siphash 1-2 for hashing
-
uses buckets of vectors for handling collisions
create a new hashtable
ht ht_new(size_t data_size, CmpFn* cmp_keys);get the number of entries in a table
size_t ht_len(ht* ht);insert a value into the table
int ht_insert(ht* ht, void* key, size_t key_len, void* value, FreeFn* fn);try to insert a value into the table. if key is already in table, don't insert
int ht_try_insert(ht* ht, void* key, size_t key_len, void* value);retrieve an entry from the table
void* ht_get(ht* ht, void* key, size_t key_len);remove an entry from the table
int ht_delete(ht* ht, void* key, size_t key_len, FreeFn* free_key,
FreeFn* free_val);free the whole table
void ht_free(ht* ht, FreeFn* free_key, FreeFn* free_val);an avl tree implementation
create a new avl tree
avl_tree avl_tree_new(size_t key_size);insert a key into the tree
int avl_insert(avl_tree* tree, void* key, CmpFn* fn);delete a key from the tree
int avl_delete(avl_tree* tree, void* key, CmpFn* cmp_fn, FreeFn* free_fn);pre order traversal of the tree
vec* avl_pre_order(avl_tree* tree);in order traversal of the tree
vec* avl_in_order(avl_tree* tree);post order traversal of the tree
vec* avl_post_order(avl_tree* tree);free the tree
void avl_tree_free(avl_tree* tree, FreeFn* fn);a generic tree implementation
create a new tree
tree tree_new(size_t key_size);determine if a key is in the tree using depth first search
bool tree_depth_first_find(tree* tree, void* key, CmpFn* fn);determine if a key is in the tree using breadth first search
bool tree_breadth_first_find(tree* tree, void* key, CmpFn* fn);insert a key into the tree using depth first search
int tree_depth_first_insert(tree* tree, void* key, void* par_key, CmpFn* fn);insert a key into the tree using breadth first search
int tree_breadth_first_insert(tree* tree, void* key, void* par_key, CmpFn* fn);delete a key from the tree using depth first search
int tree_depth_first_delete(tree* tree, void* key, CmpFn* cmp_fn,
FreeFn* free_fn);delete a key from the tree using breadth first search
int tree_breadth_first_delete(tree* tree, void* key, CmpFn* cmp_fn,
FreeFn* free_fn);free the whole tree
void tree_free(tree* tree, FreeFn* fn);an least recently used cache implementation
create a new lru
lru lru_new(size_t cap, size_t data_size, CmpFn* cmp_keys);update a key in the lru
int lru_update(lru* l, void* key, size_t key_len, void* value, FreeFn* fn);get a value from the lru
void* lru_get(lru* l, void* key, size_t key_len);free the lru
void lru_free(lru* l, FreeFn* free_key, FreeFn* free_val);a generic hash set implementation
create a new set
set set_new(CmpFn* cmp_key);get the number of elements in the set
size_t set_len(set* set);check if a key is in the set
bool set_has(set* set, void* key, size_t key_len);insert a key in the set
int set_insert(set* set, void* key, size_t key_len);delete a key from the set
int set_delete(set* set, void* key, size_t key_len, FreeFn* free_fn);free the whole set
void set_free(set* set, FreeFn* free_fn);a small vector implementation. all memory for the vector is allocated on the stack
initialize the vector's type and functions
SMALL_VEC_INIT(type, name, capacity);initialize a vector
small_vec_t(name) vec = small_vec_init(name);get the number of elements in the vector
size_t len = small_vec_len(name, &vec);append an element to the vector
int res = small_vec_push(name, &vec, 5);remove the last element in the vector
int res = small_vec_pop(name, &vec, &out);get element at specific index in the vector
int* res = small_vec_get_at(name, &vec, 0);remove an element at a specific index in the vector
int res = small_vec_remove_at(name, &vec, 0);