Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork12
A small, ergonomic generic container library.
License
JacksonAllan/CC
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Convenient Containers (CC) is an ergonomic, high-performance generic container library for C that providesvectors,doubly linked lists,unordered maps,unordered sets,ordered maps,ordered sets, andnull-terminated strings.
Its features include:
- Fully generic API.
- Type safety without boilerplate container-type definitions.
- User-defined destructor, comparison, and hash functions associated with element and key types.
- No assumption of successful memory allocation.
- Single header.
- Compiles in C and C++.
It requires C23, or C11 and support fortypeof (available in every major compiler), or C++11.
It is distributed under the MIT license.
Try it onlinehere.
Traditionally, C container libraries require users to define types for every container/content type combination and to specify the container type and (often) the content types (whether by casting, type-specific function names, or some other mechanism) at every API call. This causes verbosity and syntax noise.
In contrast,CC requires no boilerplate type definitions and provides an API agnostic to container and content types. The result is simpler, more readable code. The following table comparesCC usage to other container library patterns.
CC:#include<stdio.h>#include"cc.h"intmain(void ){vec(int )our_vec;init(&our_vec );push(&our_vec,5 );printf("%d\n",*get(&our_vec,0 ) );cleanup(&our_vec );map(int,float )our_map;init(&our_map );insert(&our_map,5,0.5f );printf("%f\n",*get(&our_map,5 ) );cleanup(&our_map );} | Template-instantiation pattern:#include<stdio.h>#include"other_container_lib.h"DEFINE_VEC(int,int_vec )DEFINE_MAP(int,float,int_float_map )intmain(void ){int_vecour_vec;int_vec_init(&our_vec );int_vec_push(&our_vec,5 );printf("%d\n",*int_vec_get(&our_vec,0 ) );int_vec_cleanup(&our_vec );int_float_mapour_map;int_float_map_init(&our_map );int_float_map_insert(&our_map,5,0.5f );printf("%f\n",*int_float_map_get(&our_map,5 ) );int_float_map_cleanup(&our_map );} |
Typed-pointer/hidden-metadata pattern:#include<stdio.h>#include"other_container_lib.h"typedefstruct{intkey;floatelement;}int_float_pair;intmain(void ){int*our_vec=NULL;vec_push(our_vec,5 );printf("%d\n",our_vec[0 ] );vec_cleanup(our_vec );int_float_pair*our_map=NULL;map_insert(our_map,5,0.5f );printf("%f\n",*map_get(our_map,5 ) );map_cleanup(our_map );} | void-pointers pattern:#include<stdio.h>#include"other_container_lib.h"intmain(void ){vecour_vec;vec_init(&our_vec,sizeof(int ) );vec_push(&our_vec,&(int){5 } );printf("%d\n",*(int*)vec_get(&our_vec,0 ) );vec_cleanup(&our_vec );mapour_map;map_init(&our_map,sizeof(int ),sizeof(float ) );map_insert(&our_map,&(int){5 },&(float){0.5f } );printf("%f\n",*(float*)map_get(&our_map,&(int){5 } ) );map_cleanup(&our_map );} |
Justdownloadcc.h and place it in your project's directory or your shared header directory.
Avec is a dynamic array that stores elements in contiguous memory.
#include<stdio.h>#include"cc.h"intmain(void ){vec(int )our_vec;init(&our_vec );// Adding elements to end.for(inti=0;i<10;++i )if( !push(&our_vec,i ) ) {// Out of memory, so abort.cleanup(&our_vec );return1; }// Inserting an element at an index.for(inti=0;i<10;++i )if( !insert(&our_vec,i*2,i ) ) {// Out of memory, so abort.cleanup(&our_vec );return1; }// Retrieving and erasing elements.for(inti=0;i<size(&our_vec ); )if(*get(&our_vec,i ) %3==0 )erase(&our_vec,i );else++i;// Iteration #1.for_each(&our_vec,el )printf("%d ",*el );// Printed: 1 1 2 2 4 4 5 5 7 7 8 8// Iteration #2.for(int*el=first(&our_vec );el!=end(&our_vec );el=next(&our_vec,el ) )printf("%d ",*el );// Printed: Same as above.cleanup(&our_vec );}
Alist is a doubly linked list.
#include<stdio.h>#include"cc.h"intmain(void ){list(int )our_list;init(&our_list );// Adding elements to end.for(inti=0;i<10;++i )if( !push(&our_list,i ) ) {// Out of memory, so abort.cleanup(&our_list );return1; }// Inserting an element before another element.for(int*el=first(&our_list );el!=end(&our_list );el=next(&our_list,el ) )if( !insert(&our_list,el,*el ) ) {// Out of memory, so abort.cleanup(&our_list );return1; }// Erasing elements.for(int*el=first(&our_list );el!=end(&our_list ); )if(*el %3==0 )el=erase(&our_list,el );elseel=next(&our_list,el );// Iteration #1.for_each(&our_list,el )printf("%d ",*el );// Printed: 1 1 2 2 4 4 5 5 7 7 8 8// Iteration #2.for(int*el=first(&our_list );el!=end(&our_list );el=next(&our_list,el ) )printf("%d ",*el );// Printed: Same as above.cleanup(&our_list );}
Amap is an unordered associative container mapping elements to keys, implemented as a hybrid open-addressing, chained hash table that is also available as astandalone library.
#include<stdio.h>#include"cc.h"intmain(void ){// Declare a map with int keys and short elements.map(int,short )our_map;init(&our_map );// Inserting elements.for(inti=0;i<10;++i )if( !insert(&our_map,i,i+1 ) ) {// Out of memory, so abort.cleanup(&our_map );return1; }// Erasing elements.for(inti=0;i<10;i+=3 )erase(&our_map,i );// Retrieving elements.for(inti=0;i<10;++i ) {short*el=get(&our_map,i );if(el )printf("%d:%d ",i,*el ); }// Printed: 1:2 2:3 4:5 5:6 7:8 8:9// Iteration #1 (elements only).for_each(&our_map,el )printf("%d ",*el );// Printed: 3 5 8 2 6 9// Iteration #2 (elements and keys).for_each(&our_map,key,el )printf("%d:%d ",*key,*el );// Printed: 2:3 4:5 7:8 1:2 5:6 8:9// Iteration #3.for(short*el=first(&our_map );el!=end(&our_map );el=next(&our_map,el ) )printf("%d:%d ",*key_for(&our_map,el ),*el );// Printed: Same as above.cleanup(&our_map );}
Aset is an unordered associative container for elements without a separate key, implemented as a hybrid open-addressing, chained hash table also available as astandalone library.
#include<stdio.h>#include"cc.h"intmain(void ){set(int )our_set;init(&our_set );// Inserting elements.for(inti=0;i<10;++i )if( !insert(&our_set,i ) ) {// Out of memory, so abort.cleanup(&our_set );return1; }// Erasing elements.for(inti=0;i<10;i+=3 )erase(&our_set,i );// Retrieving elements.for(inti=0;i<10;++i ) {int*el=get(&our_set,i );if(el )printf("%d ",*el ); }// Printed: 1 2 4 5 7 8// Iteration #1.for_each(&our_set,el )printf("%d ",*el );// Printed: 2 4 7 1 5 8// Iteration #2.for(int*el=first(&our_set );el!=end(&our_set );el=next(&our_set,el ) )printf("%d ",*el );// Printed: Same as above.cleanup(&our_set );}
Anomap is an ordered associative container mapping elements to keys, implemented as a red-black tree.
#include<stdio.h>#include"cc.h"intmain(void ){// Declare an ordered map with int keys and short elements.omap(int,short )our_omap;init(&our_omap );// Inserting elements.for(inti=0;i<10;++i )if( !insert(&our_omap,i,i+1 ) ) {// Out of memory, so abort.cleanup(&our_omap );return1; }// Erasing elements.for(inti=0;i<10;i+=3 )erase(&our_omap,i );// Retrieving elements.for(inti=0;i<10;++i ) {short*el=get(&our_omap,i );if(el )printf("%d:%d ",i,*el ); }// Printed: 1:2 2:3 4:5 5:6 7:8 8:9// Iteration #1 (elements only).for_each(&our_omap,el )printf("%d ",*el );// Printed: 2 3 5 6 8 9// Iteration #2 (elements and keys).for_each(&our_omap,key,el )printf("%d:%d ",*key,*el );// Printed: 1:2 2:3 4:5 5:6 7:8 8:9// Iteration #3.for(short*el=first(&our_omap );el!=end(&our_omap );el=next(&our_omap,el ) )printf("%d:%d ",*key_for(&our_omap,el ),*el );// Printed: Same as above.// Iteration over a key range, namely from 2 (inclusive) to 7 (exclusive).for(short*el=first(&our_omap,2 ),*range_end=first(&our_omap,7 );el!=range_end;el=next(&our_omap,el ) )printf("%d:%d ",*key_for(&our_omap,el ),*el );// Printed: 2:3 4:5 5:6cleanup(&our_omap );}
Aoset is an ordered associative container for elements without a separate key, implemented as a red-black tree.
#include<stdio.h>#include"cc.h"intmain(void ){oset(int )our_oset;init(&our_oset );// Inserting elements.for(inti=0;i<10;++i )if( !insert(&our_oset,i ) ) {// Out of memory, so abort.cleanup(&our_oset );return1; }// Erasing elements.for(inti=0;i<10;i+=3 )erase(&our_oset,i );// Retrieving elements.for(inti=0;i<10;++i ) {int*el=get(&our_oset,i );if(el )printf("%d ",*el ); }// Printed: 1 2 4 5 7 8// Iteration #1.for_each(&our_oset,el )printf("%d ",*el );// Printed: 1 2 4 5 7 8// Iteration #2.for(int*el=first(&our_oset );el!=end(&our_oset );el=next(&our_oset,el ) )printf("%d ",*el );// Printed: Same as above.// Iteration over an element range, namely from 2 (inclusive) to 7 (exclusive).for(int*el=first(&our_oset,2 ),*range_end=first(&our_oset,7 );el!=range_end;el=next(&our_oset,el ) )printf("%d ",*el );// Printed: 2 4 5cleanup(&our_oset );}
Anstr is a dynamic, null-terminated array representing a sequence of characters.
#include<stdio.h>#include"cc.h"intmain(void ){str(char )our_str;init(&our_str );// Appending formatted data.constcharmodel[]="Hornet CB900F";constcharmanufacturer[]="Honda";unsignedintyear_introduced=2002;unsignedintyear_discontinued=2007;doublehorsepower=103.0;doubletorque=84.9;if( !push_fmt(&our_str,"The ",model," is a motorcycle that was manufactured by ",manufacturer," from ",year_introduced," to ",year_discontinued,".\nIt makes ",horsepower,"hp and ",torque,"Nm of torque.\n" ) ) {// Out of memory, so abort.cleanup(&our_str );return1; }// Inserting formatted data at an index.constcharalternative_model_name[]="919";if( !insert_fmt(&our_str,17,", also known as the ",alternative_model_name,"," ) ) {// Out of memory, so abort.cleanup(&our_str );return1; }printf(first(&our_str ) );// Printed:// The Hornet CB900F, also known as the 919, is a motorcycle that was manufactured by// Honda from 2002 to 2007.// It makes 103.00hp and 84.90Nm of torque.// Erasing elements.erase_n(&our_str,108,41 );printf(first(&our_str ) );// Printed:// The Hornet CB900F, also known as the 919, is a motorcycle that was manufactured by// Honda from 2002 to 2007.// Iteration #1.for_each(&our_str,el )printf("%c",*el );// Printed: Same as above.// Iteration #2.for(char*el=first(&our_str );el!=end(&our_str );el=next(&our_str,el ) )printf("%c",*el );// Printed: Same as above.cleanup(&our_str );}
CC macro names may collide with names in your own code. If so, defineCC_NO_SHORT_NAMES before includingcc.h to expose only the prefixed API.
#defineCC_NO_SHORT_NAMES#include"cc.h"intmain(void ){// All API macros, including container declarations, are now prefixed with "cc_".cc_vec(int )our_vec;cc_init(&our_vec );if( !cc_push(&our_vec,5 ) ) {// Out of memory, so abort.cc_cleanup(&our_vec );return1; }cc_cleanup(&our_vec );}
CC supports per-type destructors with the signaturevoid ( type val ). A destructor is automatically called whenever an element or key of the associated type is removed from a container (except aCC string). Typically, a destructor frees the dynamic memory owned by the element or key.
#include<stdio.h>#include"cc.h"#defineCC_DTOR int, { printf( "%d ", val ); } // First #define CC_DTOR as <type>, { <function body> }.#include"cc.h"// Then re-include cc.h.intmain(void ){vec(int )our_vec;init(&our_vec );if( !push(&our_vec,5 ) ) {// Out of memory, so abort.cleanup(&our_vec );return1; }cleanup(&our_vec );// Printed: 5}
Destructors are especially useful when creating containers of containers.
#include"cc.h"#defineCC_DTOR vec( int ), { cleanup( &val ); }#include"cc.h"intmain(void ){list(vec(int ) )our_list;init(&our_list );vec(int )our_vec;init(&our_vec );if( !push(&our_list,our_vec ) ) {// Out of memory, so abort.// This requires cleaning up our_vec, as well as our_list, because it was not inserted and// the list therefore did not take ownership of it.cleanup(&our_vec );cleanup(&our_list );return1; }cleanup(&our_list );// our_vec is in our_list, so it is cleaned-up automatically.}
CC includes default hash and comparison functions for fundamental integer types, null-terminated C strings (char * andconst char *), andCC strings. Hence, these types can be used as map and ordered map keys, and set and ordered set elements, straight away.
To use other types or overwrite the default functions for the aforementioned types, define custom hash and/or comparison functions with the signaturessize_t ( type val ) andint ( type val_1, type val_2 ), respectively.
Maps and sets require both a hash and a comparison function, whereas ordered maps and ordered sets require only a comparison function.
#include"cc.h"typedefstruct{unsignedintid;}our_type;// First #define CC_CMPR and CC_HASH as comparison and hash functions.// The comparison function should return 0 in the case of val_1 == val_2,// < 0 in the case of val_1 < val_2, and > 0 in the case of val_1 > val_2.#defineCC_CMPR our_type, { return val_1.id < val_2.id ? -1 : val_1.id > val_2.id; }#defineCC_HASH our_type, { return val.id * 2654435761ull; }#include"cc.h"// Then re-include cc.h.intmain(void ){// Now we can use our own type as map and ordered map keys and set and ordered set elements.map(our_type,int )our_map;omap(our_type,int )our_omap;set(our_type )our_set;oset(our_type )our_oset;}
CC strings are designed for easy interoperability with otherCC containers.
To this end,CC defines default hash, comparison, and memory-freeing destructor functions for allCC string types.
Additionally, whenCC strings are used as the key and/or element type of another container, many API macros that operate on the container may alternatively take, as their key and/or element argument, a regular C string of the corresponding character type. In this case, the library automatically converts the C string into aCC string. This functionality is called "heterogeneous" insertion and lookup. The API macros that support heterogeneous insertion arepush,insert, andget_or_insert, while those that support heterogeneous lookup areget anderase. In the lookup case,CC performs no memory allocations.
The following example demonstrates howCC strings can be used with a map:
#include<stdio.h>#include"cc.h"// No need to define a hash, comparison, or destructor function for CC strings here as these// functions are defined by default.intmain(void ){map(str(char ),str(char ) )our_map;init(&our_map );// Regular insertion of CC strings.str(char )our_str_key;str(char )our_str_el;init(&our_str_key );init(&our_str_el );if( !push_fmt(&our_str_key,"France" )|| !push_fmt(&our_str_el,"Paris" )|| !insert(&our_map,our_str_key,our_str_el ) ) {// Out of memory, so abort.// This requires cleaning up the strings, too, since they were not inserted and the map therefore// did not take ownership of them.cleanup(&our_str_key );cleanup(&our_str_el );cleanup(&our_map );return1; }// Heterogeneous insertion of C strings.// CC automatically creates CC strings (and cleans them up if the operation fails).if( !insert(&our_map,"Japan","Tokyo" ) ) {// Out of memory, so abort.cleanup(&our_map );return1; }// Regular lookup using a CC string.str(char )our_str_lookup_key;init(&our_str_lookup_key );if( !push_fmt(&our_str_lookup_key,"Japan" ) ) {// Out of memory, so abort.cleanup(&our_str_lookup_key );cleanup(&our_map );return1; }str(char )*el=get(&our_map,our_str_lookup_key );cleanup(&our_str_lookup_key );printf(first(el ) );// Printed: Tokyo// Heterogeneous lookup using a C string.// This requires no dynamic memory allocations.el=get(&our_map,"France" );printf(first(el ) );// Printed: Pariscleanup(&our_map );}
By default,CC usesrealloc andfree to manage memory. Overwrite these functions by definingCC_REALLOC andCC_FREE.
#include<stdio.h>#include<stdlib.h>#include"cc.h"void*our_realloc(void*ptr,size_tsize ){printf("our_realloc called\n" );void*new_ptr=realloc(ptr,size );if( !new_ptr )exit(1 );// Out of memory, so just abort.returnnew_ptr;}voidour_free(void*ptr ){printf("our_free called\n" );free(ptr );}#defineCC_REALLOC our_realloc#defineCC_FREE our_free// Now our_realloc and our_free will be used wherever the definitions are visible.intmain(void ){vec(int )our_vec;init(&our_vec );push(&our_vec,10 );// Printed: our_realloc calledcleanup(&our_vec );// Printed: our_free called}
Full API documentation is availablehere.
CC associates type information with a container by declaring it as a pointer in the following form:
element_type (*(*)[container_type_id ])(key_type* )
The pointer points to the container's metadata and contents. API macros usesizeof,typeof, and_Generic tricks to deduce the container, element, and key types from this pointer at compile time, selecting the relevant function and passing the type information, along with the pointer, into it.
Destructor, comparison, and hash functions are also deduced via a novel technique for user-extendible_Generic macros.
Articles detailing these and other techniques are in the works.
CC has been tested under GCC, Clang, MinGW, and MSVC.tests/unit_tests.c includes unit tests for all container types, with an emphasis on corner cases.tests/tests_against_stl.cpp includes randomized tests that perform the same operations on equivalentCC and C++ STL containers and then check that they remain in sync. Both test suites use a tracking and randomly failing memory allocator in order to detect memory leaks and test out-of-memory conditions.
When used correctly,CC should not generate any compiler warnings under the following settings:
| Compiler | Warning options |
|---|---|
| GCC |
|
| Clang |
|
| MSVC |
|
For a discussion ofCC's future direction, seehere.
There are several ways that you can supportCC:
- Star this repository ⭐.
- Report any issues or bugs you find when using the library.
- Sponsor or donate to the library's continued development 🩷.
About
A small, ergonomic generic container library.
Topics
Resources
License
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Sponsor this project
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Contributors5
Uh oh!
There was an error while loading.Please reload this page.