judy
What is Judy? Judy is a C library that provides a state-of-the-art core technology that implements a sparse dynamic array. Judy arrays are declared simply with a null pointer. A Judy array consumes memory only when it is populated, yet can grow to take advantage of all available memory if desired. Judy's key benefits are scalability, high performance, and memory efficiency. A Judy array is extensible and can scale up to a very large number of elements, bounded only by machine memory. Since Judy is designed as an unbounded array, the size of a Judy array is not pre-allocated but grows and shrinks dynamically with the array population. Judy combines scalability with ease of use. The Judy API is accessed with simple insert, retrieve, and delete calls that do not require extensive programming. Tuning and configuring are not required (in fact not even possible). In addition, sort, search, count, and sequential access capabilities are built into Judy's design. Judy can be used whenever a developer needs dynamically sized arrays, associative arrays or a simple-to-use interface that requires no rework for expansion or contraction. Judy can replace many common data structures, such as arrays, sparse arrays, hash tables, B-trees, binary trees, linear lists, skiplists, other sort and search algorithms, and counting functions. Detailed Descriptions A 10 minute technical description A 3 hour technical description, slightly out of date, and very corny. Author Judy was invented by Doug Baskins (dougbaskins .AT, yahoo.com) and implemented by Hewlett-Packard.
