A library of generic data structures.

Overview

Collections-C

A library of generic data structures including a list, array, hashtable, deque etc..

Build Status License: LGPL v3

Examples

Check the documentation page for mode detailed examples. (This is still in progress). The source of the documentation can be found here.

HashTable

// Crate a new table
CC_HashTable *table;
if (cc_hashtable_new(&table) != CC_OK) {
    // something went wrong
    ...
}
// Add key-value pair
if (cc_hashtable_add(table, "some_key", "some_value") != CC_OK) {
    // something went wrong
    ...
}
// Retrieve a value associated with a key
char *value;
if (cc_hashtable_get(table, "some_key", (void*) &value) == CC_OK)
    printf("%s", value);

// Remove a key
cc_hashtable_remove(table, "foo", NULL);
cc_hashtable_destroy(table);

Array (dynamic array)

// Create a new array
CC_Array *ar;
if (cc_array_new(&ar) != CC_OK) {
    // something went wrong
    ...
}
// Add an element
enum cc_stat status = cc_array_add(ar, "foo");
if (status == CC_OK) {
    ...
} else if (status == CC_ERR_ALLOC) {
    ...
} else {
    ...
}
// Retrieve a value
char *foo;
cc_array_get_at(ar, 0, (void*) &foo);

// Remove a value
char *removed;
cc_array_remove_at(ar, 0, (void*) &removed);

cc_array_destroy(ar);

Building and Installation

Dependencies

  • C compiler (gcc, clang, etc...)
  • cmake (>= 3.5)
  • [testing only] cpputest (>=3.8)
  • pkg-config

These packages can usually be installed through your distributions package manager.

Building on windows requires MinGW which provides all the tools needed to build the project.

Building the project

To build the project, we first need to create a separate build directory:

mkdir build

Now that we've created our build directory (assuming it's created in the projct root), we can cd into it and run cmake and pass the parent directory path to it, which is where the CMakeLists.txt file is located:

cd build
cmake ..

Once cmake is done generating makefiles, we can build the library by running make inside our build directory:

make

This will build both the static and the dynamic library.

Running tests

make test

Running individual tests

make build
build/test/array_test -c -v

Installing

To install the library run:

sudo make install

By default the libraries and headers will be installed in /usr/local/lib/ and /usr/local/include directories.

You have to make the system's runtime aware of the location of the new library to be able to run dynamically linked applications. This might be as simple as running the following command if your /etc/ld.so.conf contains the install directory.

Note: macOS doesn't support ldconfig.

sudo ldconfig

Using Collections-C in your programs

A simple program

If we already built and installed the library, we can write a simple hello world program and save it to a file named hello.c:

#include <stdio.h>
#include <collectc/cc_array.h>

int main(int argc, char **argv) {
    // Create a new array
    CC_Array *ar;
    cc_array_new(&ar);

    // Add a string to the array
    cc_array_add(ar, "Hello World!\n");

    // Retreive the string and print it
    char *str;
    cc_array_get_at(ar, 0, (void*) &str);
    printf("%s", str);

    return 0;
}

Now we need to compile and link our program. Since make builds both the static and the dynamic library we can choose which one we wish to link into our program.

Linking statically

If we wish to statically link the library to our program we can pass the -static flag to the compiler

Note: On macOS, the -static flag is not very friendly (it requires that all the libraries are statically linked). So we can replace -static -lcollectc with the full path to the static library. Which is /usr/local/lib/libcollectc.a by default.

gcc hello.c -static -lcollectc -o hello

or similarly when compiling with clang:

clang hello.c -static -lcollectc -o hello

This will link the library by copying it into the executable. We can use this option if we don't wish to have Collections-C as a runtime dependency, however this comes at the expense of generating a larger executable.

Linking dynamically

We can also choose to link with the library dynamically at runtime. This is the default behaviour if ommit the -static compiler flag:

gcc hello.c -lcollectc -o hello

or with clang:

clang hello.c -lcollectc -o hello

Linking dynamically produces a smaller executable, but requires libcollectc.so to be present on every system on which the program is going to be executed.

Linking problems

Sometimes the compiler may have trouble finding the library or the headers. This is usually because it's looking for them in the wrong directory, which may happen if the library or the headers or both are installed in a non-standard directory or not installed at all.

If this is the case, we can explicitly tell the compiler where to look for them by passing the -I[path to headers] and -L[path to libraries] options:

gcc hello.c `pkg-config --cflags --libs collectionc` -o hello

Running the program

If everything went well with the compilation we can run the executable:

./hello

and it should print Hello, World! to the console.

Contributing

Contributions are welcome.

If you have a feature request, or have found a bug, feel free to open a new issue. If you wish to contribute code, see CONTRIBUTING.md for more details.

Comments
  • Use of pointer comparison

    Use of pointer comparison

    Hi,

    The treetable datastructure uses the pointer that is added as keys to compare. The function used is cc_common_comp_ptr. Since it is possible to add any pointer, this data structure will often compare pointers that are from different structures.

    In general, this is also the function you use to see if two pointers are equal in the context of ArrayContains for example.

    However, comparing pointers using < and > is undefined behavior. It is not guaranteed that if ptr1 < ptr2 returns 0, ptr2 < ptr1 will not also return 0 even if the pointers are different. This might happen due to compiler optimisations.

    See this description.

    opened by giltho 12
  • Made the include guards unique, or, rather unique.

    Made the include guards unique, or, rather unique.

    I read the suggestions in the discussion, and implemented making the include guards unique. Sure, they are long, and pedantic, but I highly doubt anyone is going to be using those names.

    opened by Nekel-Seyew 8
  • is a Vector data structure available?

    is a Vector data structure available?

    Does the library provide a vector data structure? By a vector, I mean a similar data structure to C++/STL vector, ie a right-extensible array containing elements placed in contiguous storage and you can access by integer indexing.

    The library provide a deque data structure ; however elements (not their address) are not placed in a contiguous sequence of bytes.

    EDIT The issue is solved since vectors are implemented in array.c.

    EDIT 2

    After checking more closely, it appears that an array objetct is not a true container: the array stores only a reference to your data element:

    enum cc_stat array_add(Array *ar, void *element)
    {
        if (ar->size >= ar->capacity) {
            enum cc_stat status = expand_capacity(ar);
            if (status != CC_OK)
                return status;
        }
    
        ar->buffer[ar->size] = element;
        ar->size++;
    
        return CC_OK;
    }
    

    And the hash table has the same problem. I see little use cases where this kind of implementation could be of interest.

    question 
    opened by Pascal-Ortiz 7
  • in array.c array_contains() doesn't work

    in array.c array_contains() doesn't work

    /**
     * Returns the number of occurrences of the element within the specified array.
     *
     * @param[in] ar the array that is being searched
     * @param[in] element the element that is being searched for
     *
     * @return the number of occurrences of the element
     */
    size_t array_contains(Array *ar, void *element)
    {
        size_t o = 0;
        size_t i;
        for (i = 0; i < ar->size; i++) {
            if (element == ar->buffer[i])  <------------ this line
                o++;
        }
        return o;
    }
    

    in array.c you are comparing only the addresses not the actual data, you need a comparison function as argument to array_contains @srdja

    enhancement 
    opened by gianmaria 7
  • Fix some tests in the list test suite

    Fix some tests in the list test suite

    There was a bug in the test for list_zip_iter_replace. The second list_index_of call wasn't working because it was looking for the value in the wrong list. The return value of the function call wasn't checked to be CC_OK. Since the first call returned the same expected index and put it at the same address, the test was still passing.

    opened by giltho 6
  • Potential memory leaks in slist functions

    Potential memory leaks in slist functions

    There are potential memory leaks in the functions like below - if the caller provides 'out', they can free it afterwards; but if not, the memory will leak.

    enum cc_stat slist_iter_remove(SListIter *iter, void **out)
    {
        if (!iter->current)
            return CC_ERR_VALUE_NOT_FOUND;
    
        void *e = unlink(iter->list, iter->current, iter->prev);
        iter->current = NULL;
        iter->index--;
    
        if (out)
            *out = e;
    
        return CC_OK;
    }
    
    opened by f2404 6
  • Make include guards unique

    Make include guards unique

    I find that include guards like "COMMON_H_" and "LIST_H_" are too short for the safe reuse of your header files (when they belong to an application programming interface).

    low-hanging fruit 
    opened by elfring 6
  • Added basic callbacks to the list

    Added basic callbacks to the list

    This implementation is similar to what you suggested in #10

    It can only trigger the callback if you add a single element to the list. Any ideas how we should do this with add_all or add_all_at?

    Signed-off-by: Marius Messerschmidt [email protected]

    opened by mame98 6
  • Add Ring Buffer?

    Add Ring Buffer?

    Ring buffers (or circular buffers) are pretty important data structures that are used in many embedded applications (keyboards, drivers, etc). They're pretty similar to queues and are often pretty easy to implement, as the data they store usually consists of relatively small integer values.

    enhancement 
    opened by svaniksharma 5
  • Addition of Bitset

    Addition of Bitset

    First of all, I add definitions of the basic functions for the bitset, like creation, deletion, access of bits, manipulation of bits etc, @srdja please have a check, as soon the work for it will be completed I will merge it to the master, as you gave me the write access, or otherwise you can do it

    opened by nimitbhardwaj 5
  • deque_remove_first not implemented correctly.

    deque_remove_first not implemented correctly.

    Issue repro steps

    1. Add 4 numbers 1,2,3,4 in a deque.

    2. Apply deque_remove_first on the deque.

    3. Get the first number using deque_get_first. (We get 2 as expected)

    4. But if we apply deque_get_buffer on the deque and get buff[0] we get 1.

    Root cause

    enum cc_stat deque_remove_first(Deque *deque, void **out)
    {
        if (deque->size == 0)
            return CC_ERR_OUT_OF_RANGE;
    
        void *element = deque->buffer[deque->first];
        deque->first = (deque->first + 1) & (deque->capacity - 1);
        deque->size--;
    
        if (out)
            *out = element;
    
        return CC_OK;
    }
    
    

    In the above code, we only move the pointer a step and we din't move the buffer data causing the confusion. deque_get_first gets the value indexed at first and not the buff[0].

    Suggestion for fix We shall return the buffer starting from first here in the function deque_get_buffer.

    const void* const *deque_get_buffer(Deque const * const deque)
    {
        return (const void* const*) (deque->buffer + deque->first);
    }
    
    

    Another way is to memmove in deque_remove_first itself.

    Let me know your thoughts on this @srdja !

    notabug 
    opened by argonlaser 4
  • cc_array_reverse() fails when element count is even

    cc_array_reverse() fails when element count is even

    Summary: The array reverse function fails to correctly reverse the elements. Look at the following example:

    // ...
    struct cc_array *arr;
    cc_array_new(&arr);
    
    int v0 = 0, v1 = 1, v2 = 2, v3 = 3;
    cc_array_add(arr, &v0);
    cc_array_add(arr, &v1);
    cc_array_add(arr, &v2);
    cc_array_add(arr, &v3);
    
    cc_array_reverse(arr);
    
    for (size_t i = 0; i < arr->size; ++i) {
        int *elem;
        cc_array_get_at(arr, i, (void *) &elem);
        printf("i=%zu arr[%zu]=%d\n", i, i, *elem);
    }
    // ...
    

    The expected output should be:

    i=0 arr[0]=3
    i=1 arr[1]=2
    i=2 arr[2]=1
    i=3 arr[3]=0
    

    However, instead this is the result:

    i=0 arr[0]=3
    i=1 arr[1]=1
    i=2 arr[2]=2
    i=3 arr[3]=0
    

    Cause: It seems the problem is in cc_array.c, line 690, when the list has an even amount of elements. Changing it to this: for (size_t i = 0, j = ar->size - 1; i < j; i++, j--) fixes the problem.

    opened by 766F6964 0
  • deque_remove_at  error

    deque_remove_at error

    Issue repro steps:

    1. Add at least 2 elements with deque_add_first.

    2. Use deque_remove_at to get a element which index greater than 0,your will find element is wrong.

    I think the problem is at this sentence 'void *removed = deque->buffer[index];', in which 'index' should be replaced by 'p'.

    enum cc_stat deque_remove_at(Deque *deque, size_t index, void **out) { if (index >= deque->size) return CC_ERR_OUT_OF_RANGE;

    const size_t c = deque->capacity - 1;
    const size_t l = deque->last & c;
    const size_t f = deque->first & c;
    const size_t p = (deque->first + index) & c;
    
    void *removed  = deque->buffer[index];
    
    if (index == 0)
    

    ......

    opened by yaoture3 0
  • (deque.c): inline function upper_pow_two only valid for 32 bit size_t

    (deque.c): inline function upper_pow_two only valid for 32 bit size_t

    In the common.h header file, MAX_POW_TWO is defined like this:

    #ifdef ARCH_64
    #define MAX_POW_TWO (((size_t) 1) << 63)
    #else
    

    This macro is for example used in the function, static size_t upper_pow_two (size_t), of the deque.c file. It either returns MAX_POW_TWO or the given argument rounded up to the next higher power of two. As far as I am aware, those bit manipulations:

    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    

    used to round the argument to the next power are only valid up to 32-bit, not 64-bit . Is this by design or by accident?

    opened by fhilgers 3
  • How about adding AVL or Red Black tree data structure?

    How about adding AVL or Red Black tree data structure?

    I would love to see self balancing Binary Search Tree data structure with generics support. Ready to start working on it as long as it is OK. Here I have a draft version written for my own library. Should be changed to match the overall standards of Collections-C repository. My AVL tree implementation:

    https://github.com/khasanovasad/TheAlgorithms/blob/main/data-structures/include/ue_avl.h https://github.com/khasanovasad/TheAlgorithms/blob/main/data-structures/src/ue_avl.c

    opened by khasanovasad 4
  • Using non-string hash{table,set} is harder than needed

    Using non-string hash{table,set} is harder than needed

    The documentation gives some hints that the default hashtable and hashset implementation are assuming C strings as keys. However, the "official" documentation use some defines that have been removed in the meantime, i.e. in 9b4c3cb. As of now using the hashing data structures with anything but strings as keys is rather a PITA. There is also no test case that would show how much boilerplate code is required (in comparison to string keys).

    I propose re-adding the lost comparison functions and defines and adding new explicit functions that initialize hashsets and hashtables for use with pointers, strings (and maybe even a generic version if it makes sense) respectively, e.g. hashtable_new_str and hashtable_new_ptr.

    opened by stefanct 2
  • invalid access in priority queue

    invalid access in priority queue

    This fixes an out-of-bounds lookup, which results in a segfault when popping/heapifying:

    diff --git a/src/pqueue.c b/src/pqueue.c
    index 0293922..875d40c 100644
    --- a/src/pqueue.c
    +++ b/src/pqueue.c
    @@ -306,13 +306,13 @@ static void pqueue_heapify(PQueue *pq, size_t index)
         size_t R   = CC_RIGHT(index);
         size_t tmp = index;
     
    +    if (L >= pq->size || R >= pq->size)
    +        return;
    +
         void *left     = pq->buffer[L];
         void *right    = pq->buffer[R];
         void *indexPtr = pq->buffer[index];
     
    -    if (L >= pq->size || R >= pq->size)
    -        return;
    -
         if (pq->cmp(indexPtr, left) < 0) {
             indexPtr = left;
             index = L;
    
    opened by coleifer 0
A collecton of generic reference counted data structures, tools to create compatible C style classes, and demo applications

The Offbrand library is a collection of reference counted generic data structures written in C for C. The library includes bash scripts to assist in t

Tyler Heck 82 Mar 4, 2022
Generic Data Structures In C

Generic Data Structures In C Objective: ability to use data structures with full functionality on any data type type safety is absolutely critical, ma

null 5 May 4, 2022
Typesafe, Generic & Fastest Set Data structure implementation in C

Typesafe & Fast as fuck Set in C Key Features Extremely fast non-cryptographic hash algorithm XXHash Complete Typesafe APIs Double Hashing to avoid bo

Robus Gauli 4 Sep 6, 2021
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

Lib9wada Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada Usage Compile the library with mak

Lprogrammers Lm9awdine 51 Sep 12, 2022
Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -l9wada

LibC+ Wonderful library with lots of useful functions, algorithms and data structures in C, link it with -lC+ Better than C, not as much as c++ Usage

BnademOverflow 52 Sep 23, 2022
A library of assorted data structures in C

C Data Structures A library of data structures in C. Documentation is available here. Maps Stores key/value pairs. Keys are null-terminated strings, w

Don Isaac 3 Sep 10, 2022
Step is a C++17, header-only library of STL-like algorithms and data structures

Step is a C++17, header-only library of STL-like algorithms and data structures. Installation git clone --depth 1 https://github.com/storm-ptr/step.gi

storm-ptr 3 Sep 1, 2022
🔗 Common Data Structures and Algorithms

?? Data Structures and Algorithms This library provides common data structures. It will also provide some data structures which needed in render or ga

Recep Aslantas 42 Sep 6, 2022
Repository of problems and solutions of labsheets used for Data Structures and Algorithms (CS F211) in Semester 2, 2020-21 at BITS Pilani - Hyderabad Campus.

CS F211 Data Structures and Algorithms (BITS Pilani - Hyderabad Campus) This repository contains the problems, solution approaches & explanations and

Rohit Dwivedula 27 Apr 13, 2022
An assortment of commonly used algorithms and data structures implemented with C++.

Algorithms-And-Data-Structures This repo contains C++ implementations of common algorithms and data structures, grouped by topics. The list will be sp

Tony Sheng 23 Nov 9, 2021
A collection of basic data structures syntaxes, useful for competitive coding and placement exams

Data-Structures A collection of basic data structures syntaxes, useful for competitive coding and placement exams 1. Array 2. Matrix 3. Linked List Si

MAINAK CHAUDHURI 2 Aug 8, 2021
The aim of this repository is to make it a one final stop for revision for technical interviews involving data structures and algorithms .

Hey ??‍♂️ This repository is meant for data structures and algorithms . I will be updating this often and will include all the data structures importa

Prakhar Rai 50 Sep 22, 2022
This is a beginner-friendly project aiming to build a problem-set on different data structures and algorithms in different programming languages.

DSAready Overview This is a beginner-friendly project that aims to create a problem-set for various Data Structures and Algorithms. Being a programmer

Riddhi Jain 13 Aug 17, 2022
Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design

Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. It contains solutions in various languages such as C++, Python and Java.

DSC-Banasthali 52 Jul 24, 2022
Explore the world of Data Structures and Algorithm

Hey Everyone! ?? DSA- PlayYard is the first open source project of Lets Grow More Community. It is the perfect place to start with or to test your DSA

LetsGrowMore 14 Nov 24, 2021
Postmodern immutable and persistent data structures for C++ — value semantics at scale

immer is a library of persistent and immutable data structures written in C++. These enable whole new kinds of architectures for interactive and concu

Juanpe Bolívar 2.1k Sep 22, 2022
Templates, algorithms and data structures implemented and collected for programming contests.

Templates, algorithms and data structures implemented and collected for programming contests.

Shahjalal Shohag 1.9k Sep 21, 2022
Implementation of various data structures and algorithms.

Data Structures and Algorithms A place where you can find and learn the copious number of algorithms in an efficient manner. This repository covers va

Google DSC, GVP Chapter 15 Jul 24, 2022