Kompimi C Data Structure Library: Dynamic Arrays

Although it's been slow going, the first Kompimi component is in development - the Kompimi C Data Structure Library. Its Sourceforge page is here:

http://sourceforge.net/projects/kompimi-cdsl/

So far I've implemented dynamic arrays, also known as vectors in C++, a vector permitting insertions and deletions that automatically grows to accomodate new elements. The interface was designed to include all the functionality of C++ vectors. The interface still needs some better documentation, and I need to adopt a consistent doc format that can be used to generate pretty interface web pages.

This container is very generally useful, and also surprisingly subtle in its implementation - ensuring that a sequence of insert/remove operations at the end of the array takes amortized constant time requires not only geometric expansion, but also requires that the expansion and unexpansion ratios be chosen in a way that prevents continual reallocation in an insert/remove/insert/remove/... sequence.

More concepts in the design document here:

http://sourceforge.net/docman/display_doc.php?docid=114694&group_id=231603

Preliminary unit tests are included. When this interface is thoroughly documented, next comes the next most important data structure: the list. I plan to implement this with unrolled linked lists to make it efficient.

All content in this document is granted into the public domain. Where this is not legally possible, the copyright owner releases all rights. This notice may be modified or removed.