libgcds

Library for Generic C Data Structures

Data structures

For the moment, libgcds features the following data structures:

• CircularLinkedList -- A circular doubly linked list implementation accepting insertion and removal operations at the beginning, at the end, or at a specified index in the circular linked list.
• LinkedList -- A doubly linked list implementation accepting insertion and removal operations at the beginning, at the end, or at a specified index in the linked list.
• Queue -- A queue implementation accepting enqueue and dequeue operations.
• Stack -- A stack implementation accepting push and pop operations.
• Vector -- A vector implementation using an underlying resizing array.

More data structures will be added in the future.

API

The API of each data structure is detailed in the documentation.

The TL;DR API for a hypothetical DataStructure containing elements of type Item* is as follows:

DataStructure* ds = data_structure_create();   // NULL if error
int status = ds->some_add_operation(ds, item); // 0 for success; refer to APIs for insertion methods
int index = ds->index(ds, item);               // -1 if not found
Item* item = (Item*) ds->remove_at(ds, index); // NULL if error; refer to APIs for other delete methods
assert (!ds->contains(ds, item);               // item already removed
ds->free(ds);

Important notes:

• The return codes for the different methods should be tested (e.g. above, item is null if some_remove_operation failed, which may occur for instance if you try to remove items from an empty data structure).
• The data structures are dynamically allocated, and must therefore be freed through the provided free method.
• Since the library is generic, data structures store data as void*. Therefore whatever happens to your data after it has been added to a data structure will be reflected therein. This is also true if you store data of type Item rather than Item* in a data structure by calling ds->some_add_operation(ds, &item).

Examples

Usage examples for each data structure are provided in the examples directory.

Binaries

Header files and GNU/Linux x86_64 binaries are provided in the bin directory. Alternatively, new releases are issued at every significant change.

How to install the library

If you prefer to compile the library from source instead of using the binaries, you will need cmake and make to build a static libgcds.a library that can be used in your projects.

First, clone the libgcds repository:

git clone https://github.com/alexandra-zaharia/libgcds.git

Then, create a build directory for CMake and cd into it:

cd libgcds
mkdir build
cd build

Next, run cmake to generate a makefile:

cmake .. -DCMAKE_INSTALL_PREFIX=../bin

You may omit the -DCMAKE_INSTALL_PREFIX flag, in which case libgcds will be installed to a standard location such as /usr/local. Finally, make and install the library:

make && make install

This results in copying the library's header files in the include/ subdirectory in your CMAKE_INSTALL_PREFIX (or /usr/local if an install prefix was not specified), and in copying the static library libgcds.a in the lib/ subdirectory in the CMAKE_INSTALL_PREFIX.

How to use the library

Simply include the required header files for your project, e.g. #include "stack.h" if you plan on using a Stack. For detailed information on the API of each data structure in libgcds, see the documentation.

When compiling a program that uses libgcds you will need to:

• specify where the header files are located (-I for gcc);
• specify the library search path (-L for gcc);
• specify gcds, the library the linker needs to link with (-l for gcc).

Example:

gcc -o main main.c -I /path/to/libgcds/install/dir/include -L /path/to/libgcds/install/dir/lib -lgcds

Tests

Tests for each data structure are provided in the tests directory. They need to be linked with cmocka.