- Notifications
You must be signed in to change notification settings - Fork9
A small, usability-oriented generic container library.
License
JacksonAllan/CC
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Convenient Containers (CC) is a small, usability-oriented generic container library for C that providesvectors,doubly linked lists,unordered maps,unordered sets,ordered maps, andordered sets.
Its features include:
- Fully generic API.
- Type safety.
- 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 compiler support fortypeof, 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 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 paradigms.
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 paradigm:#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 paradigm:#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 paradigm:#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 hybird 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 hybird 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 );}
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.
#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.cleanup(&our_list );return1; }cleanup(&our_list );// our_vec is cleaned-up automatically.}
CC includes default hash and comparison functions for fundamental integer types andNULL-terminated strings (char *). 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 signaturesint ( type val_1, type val_2 ) andsize_t ( type val ), respectively.
Maps and sets require both a hash and 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 comparision 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;}
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 form ofelement_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.
Future versions should includeNULL-terminated dynamic strings and more performance benchmarks.
About
A small, usability-oriented generic container library.