<commit_before>Acknowledgements
===

* RB tree implementation based on <NAME>`s red-black tree insert and delete top down algorithms (beautiful)
 * http://www.eternallyconfuzzled.com/tuts/datastructures/jsw\_tut\_rbtree.aspx
* Rabin-Karp search algorithm
 * http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
* 7-bit parallel case conversions learned from Paul Hsieh examples
 * http://www.azillionmonkeys.com/qed/asmexample.html

References (recommended lectures and code reviewed)
===

Generic data structures
---

* libulz
 * https://github.com/rofl0r/libulz
* GDSL (reentrant): http://home.gna.org/gdsl/
* Gnulib: https://www.gnu.org/software/gnulib/
 * http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=tree;f=lib;h=7f936d3be56da0cbeb950256c60cc7bb900826f4;hb=HEAD
* Apache APR
 * Includes iconv, snprintf, etc. Very interesting.
 * https://apr.apache.org/download.cgi
 * atomic: atomic increments
 * dso: dynamic library
 * encoding: ASCII <-> EBCDIC, escape/unscape URL, hex, escape/unscape "entity" (ML)
 * file\_io: copy dir, seek, r/w, open, mktemp, dup, stat
 * locks: spinlock, mutex
 * memory: memory pool (Win32-only)
 * misc: utf8, charset, rand, error codes, env
 * mmap: map file on memory
 * network_io: sockets
 * passwd: 
 * poll: fd poll (unix, os2)
 * random: random + sha256/384/512
 * shmem: shared memory IPC
 * strings: strnatcmp, strtok, fnmatch, snprintf, strings, cpystrn (no full Unicode support)
 * support: 3KB. waitio (Unix fd poll)
 * tables: hash table, skip list, memory leak detection helpers
 * test: unit tests
 * threadproc: thread, process, and signal utilities
 * time: time utils
 * tools: test generator helper
 * user: userinfo, groupinfo:
* GLib
 * https://developer.gnome.org/glib/stable/glib-String-Utility-Functions.html
 * Inspected: g_strnfill, g_str_has_prefix, g_str_to_ascii, g_str_is_ascii, g_ascii_islower, ...
* SGLIB
 * http://sglib.sourceforge.net/
 * Simple Generic Library for C
 * Faster than glib
 * BSD-like
* Attractive Chaos klib
 * Generic containers using C macros
 * https://github.com/attractivechaos/klib
 * http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/
 * https://attractivechaos.wordpress.com/2008/10/13/the-rdehash_map-hash-library/
* clibutils
 * http://sourceforge.net/projects/clibutils/
 * https://github.com/rustyrussell/ccan/tree/master/junkcode/dongre.avinash%40gmail.com-clibutils
* liblfds
 * http://liblfds.org/
* BSD
 * http://openbsd.cs.toronto.edu/cgi-bin/cvsweb/src/sys/sys/queue.h
 * http://openbsd.cs.toronto.edu/cgi-bin/cvsweb/src/sys/sys/tree.h
* sparsehash
 * https://code.google.com/p/sparsehash/?redir=1
* Cliff Click`s hash table
 * http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/
* uSTL
 * https://msharov.github.io/ustl/
 * https://github.com/msharov/ustl
* libwayne (Wayne`s Little Data Structures and Algorithms Library)
 * http://www.cs.toronto.edu/~wayne/libwayne/
* klib
 * http://blog.qoid.us/2014/04/10/klib.html
* qlib
 * https://github.com/wolkykim/qlibc
* libxc (Extended C Library)
 * http://sourceforge.net/projects/libxc/
 * It has threaded support (POSIX-only). Doxygen doc.
 * xvector: 20+4KB. Growable array (shrinking not supported), del/insert use memmove (i.e. slow)
 * xtree: 9+1KB. Not sorted trees, but trivial generic tree.
 * xstring: 34+1KB. Without Unicode support. Slow search. Very limited functionality.
 * xsparse: 13+1KB. Naive map-like array. Uses xdict.
 * xsock: 19+1KB. TCP sockets wrapper.
 * xshare: 8+2KB. Dynamic library handling wrapper.
 * xsarray: 12+1KB. Sorted array. Bult over xvector.
 * xproc: Empty. Shows plans for thread wrapper implementation.
 * xmalloc: 10+2KB. Wrapper for malloc.
 * xfile: 15+1KB. Some file utilities. A bit strange.
 * xerror: 5+4KB. Error reporting (log-like).
 * xdict: 19+1KB. Map implementation ("associative arrays"). Naive implementation.
 * xcrypto: 43KB. Random numbers and SHA256 hashes.
 * xcfg: 24+1KB. Configuration file handling (read/write of key-value elements).
* libshl (not reviewed yet)
 * https://github.com/dvdhrm/libshl
* libscl (not reviewed yet)
 * http://sourceforge.net/projects/libscl/
* The Art of Computer Programming (Donald Knuth): not used for this, but it is always a nice mention.

Strings
---

* SDS (Salvatore Sanfilippo, antirez)
 * README.md structure.
 * Equivalent sdsfromlonglong(), sdstrim() functionality.
* strbuf (Git project)
 * Equivalent strbuf\_grow(), strbuf\_split\_\*() functionality.
 * Documentation structure (https://github.com/git/git/blob/master/Documentation/technical/api-strbuf.txt)
* string library comparison
 * http://www.and.org/vstr/comparison
 * http://bstring.sourceforge.net/features.html

Unicode / character handling
---

* Unicode case/folding: http://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt
* Unicode table: http://unicode-table.com/en/

Sorting
---

* Generic
 * https://stackoverflow.com/questions/10604693/fastest-sorting-technique
*  Timsort
 * https://en.wikipedia.org/wiki/Timsort
 * http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124

Hash tables
---

* uthash
 * https://troydhanson.github.io/uthash/
* Benchmarks
 * http://incise.org/hash-table-benchmarks.html

Trees
---

* StackOverflow stuff
 * http://stackoverflow.com/questions/647537/b-tree-faster-than-avl-or-redblack-tree
* Julienne Walker web site
 * http://www.eternallyconfuzzled.com
* Wikipedia
 * http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
 * http://en.wikipedia.org/wiki/B-tree
 * http://en.wikipedia.org/wiki/Tree_traversal
 * http://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree
 * http://en.wikipedia.org/wiki/2%E2%80%933_tree
 * http://en.wikipedia.org/wiki/2%E2%80%933%E2%80%934_tree
* Misc
 * http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html
 * http://www.canonware.com/rb/
 * http://www.teachsolaisgames.com/articles/balanced_left_leaning.html
 * http://25thandclement.com/~william/projects/llrb.h.html
 * http://t-t-travails.blogspot.com/2010/04/red-black-trees-revisited.html

Memory allocation
---

 * http://stackoverflow.com/questions/282926/time-complexity-of-memory-allocation
 * http://www.gii.upv.es/tlsf/
 * http://www.design-reuse.com/articles/25090/dynamic-memory-allocation-fragmentation-c.htm

Node cache size impact
---

* Effect of Node Size on the Performance of CacheConscious B+trees (<NAME>, <NAME>)

String Matching
---

* Simple Real-Time Constant-Space String Matching (<NAME>, <NAME>, <NAME>)
* Text Searching Algorithms vol II: Backward String Matching (<NAME>)

Predictability
---

* Building Timing Predictable Embedded Systems (<NAME>, <NAME>, <NAME>, ...) [2012]
* Static Timing Analysis for Hard Real-Time Systems (<NAME>, <NAME>, ...)
* Timing-Predictable Memory Allocation In Hard Real-Time Systems (Jrg Herter) [2014]

C language
---<commit_msg>doc update<commit_after>Acknowledgements
===

* RB tree implementation based on Julienne Walker`s red-black tree insert and delete top down algorithms (beautiful)
 * http://www.eternallyconfuzzled.com/tuts/datastructures/jsw\_tut\_rbtree.aspx
* Rabin-Karp search algorithm
 * http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
* 7-bit parallel case conversions learned from Paul Hsieh examples
 * http://www.azillionmonkeys.com/qed/asmexample.html

References (recommended lectures and code reviewed)
===

Generic data structures
---

* libulz
 * https://github.com/rofl0r/libulz
* GDSL (reentrant): http://home.gna.org/gdsl/
* Gnulib: https://www.gnu.org/software/gnulib/
 * http://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=tree;f=lib;h=7f936d3be56da0cbeb950256c60cc7bb900826f4;hb=HEAD
* Apache APR
 * Includes iconv, snprintf, etc. Very interesting.
 * https://apr.apache.org/download.cgi
 * atomic: atomic increments
 * dso: dynamic library
 * encoding: ASCII <-> EBCDIC, escape/unscape URL, hex, escape/unscape "entity" (ML)
 * file\_io: copy dir, seek, r/w, open, mktemp, dup, stat
 * locks: spinlock, mutex
 * memory: memory pool (Win32-only)
 * misc: utf8, charset, rand, error codes, env
 * mmap: map file on memory
 * network_io: sockets
 * passwd: 
 * poll: fd poll (unix, os2)
 * random: random + sha256/384/512
 * shmem: shared memory IPC
 * strings: strnatcmp, strtok, fnmatch, snprintf, strings, cpystrn (no full Unicode support)
 * support: 3KB. waitio (Unix fd poll)
 * tables: hash table, skip list, memory leak detection helpers
 * test: unit tests
 * threadproc: thread, process, and signal utilities
 * time: time utils
 * tools: test generator helper
 * user: userinfo, groupinfo:
* GLib
 * https://developer.gnome.org/glib/stable/glib-String-Utility-Functions.html
 * Inspected: g_strnfill, g_str_has_prefix, g_str_to_ascii, g_str_is_ascii, g_ascii_islower, ...
* SGLIB
 * http://sglib.sourceforge.net/
 * Simple Generic Library for C
 * Faster than glib
 * BSD-like
* Attractive Chaos klib
 * Generic containers using C macros
 * https://github.com/attractivechaos/klib
 * http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/
 * https://attractivechaos.wordpress.com/2008/10/13/the-rdehash_map-hash-library/
* clibutils
 * http://sourceforge.net/projects/clibutils/
 * https://github.com/rustyrussell/ccan/tree/master/junkcode/dongre.avinash%40gmail.com-clibutils
* liblfds
 * http://liblfds.org/
* BSD
 * http://openbsd.cs.toronto.edu/cgi-bin/cvsweb/src/sys/sys/queue.h
 * http://openbsd.cs.toronto.edu/cgi-bin/cvsweb/src/sys/sys/tree.h
* sparsehash
 * https://code.google.com/p/sparsehash/?redir=1
* Cliff Click`s hash table
 * http://preshing.com/20130605/the-worlds-simplest-lock-free-hash-table/
* uSTL
 * https://msharov.github.io/ustl/
 * https://github.com/msharov/ustl
* libwayne (Wayne`s Little Data Structures and Algorithms Library)
 * http://www.cs.toronto.edu/~wayne/libwayne/
* klib
 * http://blog.qoid.us/2014/04/10/klib.html
* qlib
 * https://github.com/wolkykim/qlibc
* libxc (Extended C Library)
 * http://sourceforge.net/projects/libxc/
 * It has threaded support (POSIX-only). Doxygen doc.
 * xvector: 20+4KB. Growable array (shrinking not supported), del/insert use memmove (i.e. slow)
 * xtree: 9+1KB. Not sorted trees, but trivial generic tree.
 * xstring: 34+1KB. Without Unicode support. Slow search. Very limited functionality.
 * xsparse: 13+1KB. Naive map-like array. Uses xdict.
 * xsock: 19+1KB. TCP sockets wrapper.
 * xshare: 8+2KB. Dynamic library handling wrapper.
 * xsarray: 12+1KB. Sorted array. Bult over xvector.
 * xproc: Empty. Shows plans for thread wrapper implementation.
 * xmalloc: 10+2KB. Wrapper for malloc.
 * xfile: 15+1KB. Some file utilities. A bit strange.
 * xerror: 5+4KB. Error reporting (log-like).
 * xdict: 19+1KB. Map implementation ("associative arrays"). Naive implementation.
 * xcrypto: 43KB. Random numbers and SHA256 hashes.
 * xcfg: 24+1KB. Configuration file handling (read/write of key-value elements).
* libshl (not reviewed yet)
 * https://github.com/dvdhrm/libshl
* libscl (not reviewed yet)
 * http://sourceforge.net/projects/libscl/
* The Art of Computer Programming (Donald Knuth): not used for this, but it is always a nice mention.

Strings
---

* SDS (<NAME>, antirez)
 * README.md structure.
 * Equivalent sdsfromlonglong(), sdstrim() functionality.
* strbuf (Git project)
 * Equivalent strbuf\_grow(), strbuf\_split\_\*() functionality.
 * Documentation structure (https://github.com/git/git/blob/master/Documentation/technical/api-strbuf.txt)
* string library comparison
 * http://www.and.org/vstr/comparison
 * http://bstring.sourceforge.net/features.html

Unicode / character handling
---

* Unicode case/folding: http://ftp.unicode.org/Public/UNIDATA/CaseFolding.txt
* Unicode table: http://unicode-table.com/en/

Sorting
---

* Generic
 * https://stackoverflow.com/questions/10604693/fastest-sorting-technique
*  Timsort
 * https://en.wikipedia.org/wiki/Timsort
 * http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6804124

Hash tables
---

* uthash
 * https://troydhanson.github.io/uthash/
* Benchmarks
 * http://incise.org/hash-table-benchmarks.html

Trees
---

* StackOverflow stuff
 * http://stackoverflow.com/questions/647537/b-tree-faster-than-avl-or-redblack-tree
* <NAME> web site
 * http://www.eternallyconfuzzled.com
* Wikipedia
 * http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
 * http://en.wikipedia.org/wiki/B-tree
 * http://en.wikipedia.org/wiki/Tree_traversal
 * http://en.wikipedia.org/wiki/Left-leaning_red%E2%80%93black_tree
 * http://en.wikipedia.org/wiki/2%E2%80%933_tree
 * http://en.wikipedia.org/wiki/2%E2%80%933%E2%80%934_tree
* Misc
 * http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html
 * http://www.canonware.com/rb/
 * http://www.teachsolaisgames.com/articles/balanced_left_leaning.html
 * http://25thandclement.com/~william/projects/llrb.h.html
 * http://t-t-travails.blogspot.com/2010/04/red-black-trees-revisited.html

Memory allocation
---

 * http://stackoverflow.com/questions/282926/time-complexity-of-memory-allocation
 * http://www.gii.upv.es/tlsf/
 * http://www.design-reuse.com/articles/25090/dynamic-memory-allocation-fragmentation-c.htm

Node cache size impact
---

* Effect of Node Size on the Performance of CacheConscious B+trees (<NAME>, <NAME>)

String Matching
---

* Simple Real-Time Constant-Space String Matching (<NAME>, <NAME>, <NAME>)
* Text Searching Algorithms vol II: Backward String Matching (<NAME>)

Predictability
---

* Building Timing Predictable Embedded Systems (<NAME>, <NAME>, <NAME>, ...) [2012]
* Static Timing Analysis for Hard Real-Time Systems (<NAME>, <NAME>, ...)
* Timing-Predictable Memory Allocation In Hard Real-Time Systems (<NAME>) [2014]

Data compression
---

* Improving LZW (<NAME>) http://webhome.cs.uvic.ca/~nigelh/Publications/improvingLZW.pdf
* https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
* http://www2.scssoft.com/~petr/gfx/lzw.html
* https://es.wikipedia.org/wiki/Run-length\_encoding

C language
---
{'fraction_non_alphanumeric': 0.14452281560385777, 'fraction_numerical': 0.02943716712249892, 'mean_word_length': 4.176974664679583, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 32, 'https://': 34, 'lorem ipsum': 0, 'www.': 21, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3694675', 'n_tokens_mistral': 5320, 'n_tokens_neox': 4847, 'n_words': 1022}