master branch:

master branch analysis:

documentation (generated by doing ./make_test.sh 8): HTML

libsrt has been included into Paul Hsieh's String Library Comparisons table. What a great honor! :-)

libsrt: Safe Real-Time library for the C programming language

libsrt is a C library that provides string, vector, bit set, set, map, hash set, and hash map handling. It's been designed for avoiding explicit memory management when using dynamic-size data structures, allowing safe and expressive code, while keeping high performance. It is also suitable for low level and hard real-time applications, because functions are predictable in both space and time (assuming OS and underlying C library is also real-time suitable).

Key points:

• Safe: write high-level-like C code. Write code faster and safer.
• Fast: using O(n)/O(log n)/O(1) state of the art algorithms.
• Rich: strings supporting raw data handling (per-byte), vector, bit set, set, map, hash set, and hash map data structures.
• Efficient: space optimized, minimum allocation calls (heap and stack support for ALL data structures).
• Compatible: OS-independent (e.g. built-in space-optimized UTF-8 support).
• Predictable: intended for both general purpose and for hard real-time applications.
• Unicode: although string internal representation is raw data (bytes), functions for handling Unicode interpretation/generation/transformation are provided, so when Unicode-specific functions are used, the result of these functions is stored internally as UTF-8 (also, caching some operations, like Unicode string length -e.g. ss_len()/ss_size() give length in bytes, and ss_len_u() the length in Unicode characters-).

How to build

• In most POSIX systems (e.g. Linux, Unix, and other Unix-like) "make -f Makefile.posix" will be enough, as the Makefile.posix includes platform detection for corner cases. However, you can use multiple flags for tuning the build (you can also mix them):

  • make -f Makefile.posix # Defaults (equivalent to make ADD_CFLAGS="-DS_CRC32_SLC=12")
  • make -f Makefile.posix -j 8 # Make, spawning up to 8 concurrent jobs (faster on multiprocessor systems)
  • make -f Makefile.posix DEBUG=1 # Disable optimizations (-O0 -ggdb)
  • make -f Makefile.posix PROFILING=1 # Profiling and coverage flags
  • make -f Makefile.posix CC=gcc PEDANTIC=1 C99=1 # Pedantic build for GCC in C99 mode (this should give no warnings)
  • make -f Makefile.posix CC=tcc # Use the Tiny C Compiler
  • make -f Makefile.posix CC=gcc CXX=g++ # Use gcc for the library and examples and g++ for the benchmark
  • make -f Makefile.posix CC=clang CXX=clang++ # Use CLang for the library and examples and CLang C++ for the benchmark
  • make -f Makefile.posix FORCE32=1 # Force 32 bit build on 64 bit system
  • make -f Makefile.posix MINIMAL=1 # Microcontroller-suitable build (optimize for size and low memory usage)
  • make -f Makefile.posix CC=gcc PROFILING=1 # Build with gcc and profiling
  • make -f Makefile.posix CC=gcc C90=1 # Build with gcc using C89/90 standard
  • make -f Makefile.posix CC=gcc C99=1 # Build with gcc using C99 standard
  • make -f Makefile.posix CC=gcc C11=1 # Build with gcc using C11 standard
  • make -f Makefile.posix CC=g++ # Build with g++ (C++ instead of C)
  • make -f Makefile.posix CC=clang++ CPP11=1 # Build with clang++ using C++11 standard (instead of C)
  • make -f Makefile.posix CC=clang CXX=clang++ C99=1 CPP11=1 # Build with clang using C99 mode and build the benchmark using C++11
  • make -f Makefile.posix CC=tcc DEBUG=1 # Build with TinyCC with debug symbols
  • make -f Makefile.posix CPP11=1 bench # Build the benchmark including C++11 support (for comparing libsrt vs C++/STL hash map/set)
  • make -f Makefile.posix CC=powerpc-linux-gnu-gcc # Build with gcc cross compiler (PPC)
  • make -f Makefile.posix CC=arm-linux-gnueabi-gcc # Build with gcc cross compiler (ARM)
  • make -f Makefile.posix ADD_CFLAGS="-DS_CRC32_SLC=0" # Build without CRC32 hash tables, 1 bit/loop (100MB/s on i5@3GHz)
  • make -f Makefile.posix ADD_CFLAGS="-DS_CRC32_SLC=1" # Build with CRC32 1024 byte hash table, 1 byte/loop (400MB/s on i5@3GHz)
  • make -f Makefile.posix ADD_CFLAGS="-DS_CRC32_SLC=4" # Build with CRC32 4096 byte hash table, 4 bytes/loop (1000MB/s on i5@3GHz)
  • make -f Makefile.posix ADD_CFLAGS="-DS_CRC32_SLC=8" # Build with CRC32 8192 byte hash table, 8 bytes/loop (2000MB/s on i5@3GHz)
  • make -f Makefile.posix ADD_CFLAGS="-DS_CRC32_SLC=12" # Build with CRC32 12288 byte hash table, 12 bytes/loop (2500MB/s on i5@3GHz) -this is the default CRC32 mode-
  • make -f Makefile.posix ADD_CFLAGS="-DS_CRC32_SLC=16" # Build with CRC32 16384 byte hash table, 16 bytes/loop (2700MB/s on i5@3GHz):
  • make -f Makefile.posix ADD_FLAGS=-DSD_DISABLE_HEURISTIC_GROWTH # Build with growth heuristics disabled (not recommended)
  • make -f Makefile.posix ADD_FLAGS=-DS_DISABLE_SM_STRING_OPTIMIZATION # Build without map string optimizations (not recommended, except for benchmarking)
  • make -f Makefile.posix HAS_PNG=1 HAS_JPG=1 # Build enabling PNG and JPG usage so the 'imgc' example can convert import/export those formats (libpng and jpeg 6b -e.g. libjpegturbo- compatible dev libs and headers must be installed in the system)

• Observations

  • Every make call, in addition to building the targets, it does a full test for that build (unit tests covering all the API function calls -'stest' executable-)
  • Between make calls with different parameters, please use "make clean"
  • It should build with any GCC version >= 2.95.2 (1999), in any hardware platform (x86, x86-64, MIPS32/64, MIPSLE, PPC/PPC64, ARM, etc.)
  • CLang should work in all versions (except in cases of reporting wrong/missing compiler or C standard version)
  • For Windows it is provided a .sln example just for building the test (used for the CI check)
  • In BSD systems not using GNU Make as default, use gmake instead of make

• For launching the extensive tests:

  • ./make_test.sh # All tests (used in the CI validation): all builds (23 * 4 tests), Valgrind memcheck, CLang static analyzer, documentation generation and validation, coding style check
  • ./make_test.sh 1 # Validate all available C/C++ builds
  • ./make_test.sh 2 # Valgrind memcheck
  • ./make_test.sh 4 # Clang static analyzer
  • ./make_test.sh 8 # Generate documentation
  • ./make_test.sh 16 # Check coding style
  • ./make_test.sh 24 # Like 8 plus 16 (3 would be like 1 plus 2, etc.)

• A preliminary Autoconf/Automake build is also provided:

  • ./bootstrap.sh
  • ./configure
  • make
  • make check

• A Visual Studio project is provided in win/vs2013/ for running the test through AppVeyor's CI.

Generic advantages

• Ease of use

  • Use strings, vectors, bit sets, sets, maps, hash sets, and hash maps in a similar way to higher level languages.

• Space-optimized

  • Dynamic one-block linear addressing space.
  • Internal structures use indexes instead of pointers (i.e. similar memory usage in both 32 and 64 bit mode).
  • Details: doc/benchmarks.md

• Time-optimized

  • Buffer direct access
  • Preallocation hints (reducing memory allocation calls)
  • Heap and stack memory allocation support
  • Details: doc/benchmarks.md

• Predictable (suitable for hard and soft real-time)

  • Predictable execution speed: all API calls have documented time complexity. Also space complexity, when extra space involving dynamic memory is required.
  • Hard real-time: allocating maximum size (strings, vector, bit set, set, map, hash set, hash map) will imply calling 0 or 1 times to the malloc() function (C library). Zero times if using the stack as memory or externally allocated memory pool, and one if using the heap. This is important because malloc() implementation has both memory and time overhead, as internally manages a pool of free memory (which could have O(1), O(log(n)), or even O(n), depending on the compiler provider C library implementation).
  • Soft real-time: logarithmic time memory allocation (when not doing preallocation): for 10^n new elements just log(n) calls to the malloc() function. This is not a guarantee for hard real time, but for soft real time (being careful could provide almost same results, except in the case of very poor malloc() implementation in the C library being used -not a problem with modern compilers-).

• RAM, ROM, and disk operation

  • Data structures can be stored in ROM memory.
  • Data structures are suitable for memory mapped operation, and disk store/restore. This is true for strings, vectors, and bit sets, and for sets/maps/hash sets/hash maps when using integer data and when using small strings (<= 19 bytes for S/SI/IS data types, and <= 54 bytes for SS).

• Known edge case behavior

  • Allowing both "carefree code" and per-operation error check. I.e. memory errors and UTF8 format error can be checked after every operation.

• Implementation

  • Simple internal structures, with linear addressing. It allows to reduce memory allocation calls to the minimum (using the stack it is possible to avoid heap usage).
  • Imp