C-Macro-Collections/docs/index.html.md

THIS IS A SAFE COPY OF THE MARKDOWN FOR THE DOCUMENTATION LOCATED AT https://leoven.github.io/C-Macro-Collections/

---

title: CMC Documentation

toc_footers:

• Documentation Powered by Slate

language_tabs: - C

search: true

Introduction

The C Macro Collections Library is a compilation of macros that can be used to generate common data structures for any desired type. These data structures are type safe.

The documentation is currently being written in hopes that in the future it can be used to help you get to know better this amazing C library.

Why this library

C is a low level language and lacks all the data structures that we commonly use. Many high level languages already come with these collections so that we don't have to implement everything ourselves. This is why the C Macro Collections Library was created.

The library currently provides many data structures, such as:

• Linear Collections
  • List, LinkedList, Deque, Stack, Queue
• Sets
  • HashSet, TreeSet, MultiSet
• Maps
  • HashMap, TreeMap, MultiMap
• Heaps
  • Heap, IntervalHeap

All with the following features:

• Type-safe - No void * pointers are used. A collection of type int will only accept integers;
• Customization - Custom struct name and function namespace;
• Bidirectional Iterators - Full support for iterators;
• Nesting - Collections can be nested (List of Lists, HashSet of Stacks, etc).

Library Structure

The src folder is subdivided in 5 other folders and one file:

The dev folder is an exact copy of cmc but it is filled with logging information regarding the code execution and debugging.

The sac library contains fixed-length collections with an internal C array.

• cmc - The main C Macro Collections Library
• dev - The main C Macro Collections Library for development
• ext - Extra collections
• sac - Statically Allocated Collections
• utl - Utility like ForEach macros, logging, etc
• macro_collections.h - Master header containing all collections and utilities

How to install

Include header files like this

#include <cmc/list.h>
#include <dev/deque.h>
#include <utl/assert.h>

Not like this

#include <list.h>
#include <deque.h>  // dev or cmc?
#include <assert.h> // this will import from the standard library

No installation is required. All you have to do is include the appropriate header files, generate any collections that you desire and then compile your program. It is recommended that you include the headers relative to the src folder and include it with -I path/to/library/src as shown in the following example.

The library has no external dependencies other than the C standard library.

Minimal Example

Lets create a list of type int, add some elements to it and get the sum of all the elements printed on the screen.

Include headers

#include <cmc/list.h>

First you need to include only the necessary headers. It is not recommended that you include everything with macro_collections.h, only in cases where you might be using almost all features from the library.

Generating a list

// CMC_GENERATE_LIST(PFX, SNAME, V)
CMC_GENERATE_LIST(il, int_list, int)

The List is also known as vector, ArrayList and dynamic array. In fact the latter is the best description for this collection. It is a dynamic array that can grow and shrink as needed. To generate it we can simply call the macro CMC_GENERATE_LIST after our includes. It has three parameters:

Parameter name	Purpose
PFX	Functions prefix (namespace)
SNAME	Struct name
V	The list value type (can be any valid data type)

All collections can be generated by using the macro CMC_GENERATE_ and then the name of the include (in this case list.h) but in uppercase without the `.h`.

Initializing and adding elements

// Allocate an int_list with an initial capacity of 100
int_list *list = il_new(100);

// Adding elements to the back of the list
for (int i = 0; i <= 1000; i++)
{
    if (!il_push_back(list, i))
    {
        // Something went wrong (check out documentation)
    }
}

To initialize any collection we call a function _new. Since the PFX parameter is set to il all functions related to our list of integer will be prefixed by il, so _new becomes il_new.

The list name is int_list as defined by SNAME. This type is a typedef like:

typedef struct SNAME##_s SNAME;

Which expands to:

typedef struct int_list_s int_list

To add elements to the back of a list we can use il_push_back. This function will first check if the list has enough space for a new element. If not, reallocate the internal buffer with doubled size and then add the new element.

Iteration

It is recommended that the iterator is allocated on the stack

// Resulting sum will be stored here
int sum = 0;

// Declare our iterator (allocating it on the stack)
int_list_iter it;

// Loop for each element
for (il_iter_init(&it, list); !il_iter_end(&it); il_iter_next(&it))
{
    // Accessing the value
    int elem = il_iter_value(&it);

    sum += elem;
}

printf("%d\n", sum);

There are 6 (2 optional) steps to iterate over the elements of any collection:

Step	Description	Function
1	Allocate the iterator (optional)	il_iter_new
2	Initialize the iterator given a target list	il_iter_init
3	Access the iterator's elements (value, index, etc)	il_iter_value
4	Go to the next element	il_iter_next
5	Check if we haven't reached the end of the list	il_iter_end
6	Free the iterator if it was allocated on the heap	il_iter_free

Note that all iterator functions are prefixed by the user defined prefix and then by iter (il + iter = il_iter). Also, the steps 1 and 6 are optional so il_iter_new and il_iter_free are not used in the example.

By the end of the example we have the variable sum with the sum of all integers inside our list. We can then print it and this example is almost done.

Freeing resources

// void il_free(int_list *_list_, void(*deallocator)(int))
il_free(list, NULL);

The list is currently allocated in memory. To deallocate it we call il_free. This function takes a pointer to the allocated list and a pointer to a deallocator function that will be responsible for deallocating each element in the list. This last parameter is optional and we won't be using it since our data type int is not allocated in the heap. This optional parameter can be set to NULL to be ignored by the il_free function.

Compile and run

source.c

#include <cmc/list.h>

CMC_GENERATE_LIST(il, int_list, int)

int main(void)
{
    int_list *list = il_new(100);

    for (int i = 0; i <= 1000; i++)
    {
        if (!il_push_back(list, i))
        {
            // Something went wrong (check out documentation)
        }
    }

    int sum = 0;

    int_list_iter it;

    for (il_iter_init(&it, list); !il_iter_end(&it); il_iter_next(&it))
    {
        int elem = il_iter_value(&it);
        sum += elem;
    }

    printf("%d\n", sum);

    il_free(list, NULL);
}

If the source file is source.c, all you have to do is to include the src folder to the include path and compile. The following example uses gcc:

gcc source.c -I path/to/library/src

Conclusion

The C Macro Collections Library is prepared to accept any data type and is highly customizable. It is also very easy to integrate and no previous compilation is required. The library also comes with many utilities in the utl folder that are designed to work well with all collections.

Upcoming

This documentation is still being written. Here is some of the things you will be able to find here:

• Full explanation about data structures
• Full documentation about all current collections and others to come
• Fully explained examples
• Benchmark examples