Below are implementations of various different algorithms. All of the code was written by me, so any bugs are mine. I stink at math, so if I have overlooked some breathtaking optimization anywhere, please speak up. :-) I welcome all suggestions and/or constructive criticism. If you are using any of these packages and like them please let me know. Seems pointless to do all of this work when it only benefits me.
Ternary Search Trie
I first read about Ternary Search Tries in Algorithms in C 3rd. Edition by Sedgewick. Basically, I needed a fast symbol table algorithm for null terminated character strings, and binary trees weren't fast enough and there were too many balancing problems. My ternary search trie package has the basic search and insert and delete functions.
This package is now being used within an Apache (my own, not bundled) piped logging module to cache file names and match them up with their descriptors. Note: I have seen some grumbling about how nodes are allocated. The method is very simplistic and does slow down insertions. The reason it is there is because in order to support deletions, the nodes need to be freed/reused individually, since over time a given node may be part of several different strings. So, a better method for doing this is needed. In addition, it is possible to add an option to make the structure "append only", which would allow a simpler node allcation strategy to be used.
String hashing code
This is a very basic hashing algorithm for strings. The main algorithm is from The Algorithm Design Manual, page 177. I added a way to limit how much of the string gets hashed with the hash_limit parameter. There are versions below for C and Perl.
Linked List Source
I had written a couple linked list libraries that maintain a "free list" of nodes and allocated the nodes in chunks to make it more efficient. What is included here is a more of an "in place" solution. The idea is that you are putting items into a linked list, you generally have to malloc() memory for whatever it is you are storing. This can require another library to efficiently allocate these structures for you. You can't really do this properly with a library by passing in an object size, because you run into alignment issues with different systems. So, this is not a library, but a source file and header. You define LL_DATA_TYPE to be the data that is stored in each linked list item, as well as LL_PREFIX, which gives a prefix to all of the internal data types and functions, so you don't collide with any other program or library that may use this list source as well. The source is ll.c and the header is ll.h.
thread safe strtok
This is much like strtok_r, but doesn't require that silly REENTRANT define and doesn't call any other functions. Short and simple but useful, here is el_strtok.c.
C++ class for anonymous shared memory
This is a simple class for creating anonymous shared memory segments (memory shared between related processes). If MAP_ANON is defined then that flag is passed to mmap(), otherwise /dev/zero gets mapped. Here is the source and the header.
Binary Search for character array
This is a very simple function for performing binary searches of character arrays. This is handy for things like parsers, where you have a list of characters in various groupings, and you need to determine if a given character is part of a particular group. Get the C source.
Function for skipping RFC822 commenting folding white space
This function is used for skipping RFC822 commenting folding white space in structured header bodies. Get the C source.
Code snippet to proxy two TCP sockets
This function is used to proxy two TCP sockets. Non-blocking I/O is used, with select() used for determining ready set and timing out operations. Get the C source.
Non-recursive quicksort.
This is based on code from Algorithms in C 3rd. Edition by Sedgewick. The quicksort routine I was using was blowing up the stack on certain inputs so I needed something heap based. This code is a combination of the non-recursive code example plus some of the optimizations suggested. I haven't gotten around to adding the insertion sort optimization. Note that while it does not use recursive function calls, it does have to save the subfiles on a stack in memory, which you can still run out of. In order to avoid frequent calls to malloc(), as each stack item is allocated and then released it is stored in a linked list so it can be re-used. This stack is freed before the sort returns. Try the C source.

Peter A. Friend pafriend@octavian.org
3/25/2008