This page attempts to gather information about various data structures used for storing dynamic content in c.
Simple dynamic arrays
A simple implementation here. It usses
realloc() to change the size of the array, that may become slow. Also note
this StackOverflow answer
about the strategy to use when resizing. Since elements are continous in
memory may be fast when accessing content sequentially.
An obstack is a pool of memory containing a stack of objects. You can create any number of separate obstacks, and then allocate objects in specified obstacks. Within each obstack, the last object allocated must always be the first one freed, but distinct obstacks are independent of each other.
- Sourceforge repo has latest version 1.0.5 released in May 2009
- Home site at judy.sourceforge.net.
- Wikipedia entry
- 2003 testing by Sean Barrett
- an implementation in 1250 lines, last update ine June 2013; there is some work on github by JanX2
- compression-code Public Domain implementation of Adaptive Huffman Coding in C; Implement Vitters modification to algorithm FGK in C code.
- Hashtables vs Judy Arrays, Round 1 (2008)
Repositories on Github - https://github.com/alanpearson/judy - https://github.com/electromatter/judy-svn - https://github.com/darconeous/judy - https://github.com/dump247/judy - https://github.com/tony2001/judy build system cleaned - https://github.com/bpowers/judyarrays Markdown - https://github.com/qiq/judy-fk This is a modified JudySL implementation, so that keys are not NUL-terminated C strings, but fixed-length sequence of bytes. Except this, it is the same as original JudySL implementation. - https://github.com/felix-lang/judy
Project page; written by Karl Malbrain.
A HAT tree consists of a cascaded series of root radix director nodes for leading key bytes, which then point to either another radix node, or a hash bucket, or a string array which contains the rest of the bytes in the keys
- github.com/dcjones/hat-trie This a ANSI C99 implementation of the HAT-trie data structure of Askitis and Sinha, an extremely efficient (space and time) modern variant of tries. The version implemented here maps arrays of bytes to words (i.e., unsigned longs), which can be used to store counts, pointers, etc, or not used at all if you simply want to maintain a set of unique strings.
Implement Lehman and Yao's high concurrency B-Tree in C language with Jaluta's balanced B-link tree operations including a locking enhancement for increased concurrency.
discovered while researching this:
- Arena memory allocator in C - A bit map is used to track allocated memory in storage arenas;
- byte-oriented-aes Implementation of a byte-oriented approach to the Advanced Encryption Standard in standard C code. By careful tracking of the input and output state array indicies, the MixColumns, SubBytes, and ShiftRows steps are combined into a single round operation;
- regular-expression-evaluator A hybrid regular expression evaluator for xsd:pattern combines memoization with features from the DFA and NFA approaches to provide excellent run-time characteristics with time O(mn) and space O(mn) where m is the pattern size and n is the source length.
- secure-remote-password A small footprint implementation of the Secure Remote Password protocol in C
- kernel-doc linux kernel documentation style
- C Code Archive network website and repo