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.

What is Kompimi?

Kompimi, a portmanteau of computer and the Swedish Piratbyrån's kopimi, is a series of high-quality public-domain software projects. Its mission is to make unencumbered solutions to important basic software engineering problems available to the software development community in perpetuity.

Kompimi is not against copyleft licenses or proprietary software. Large, complete systems can benefit from a focused effort and fair compensation. Kompimi projects do not aim to replace these systems, but to generate fundamental building blocks that can be used in all software. By releasing this code, we strive to end the endless reinventing of the wheel; by making it public domain, we avoid the issues of license paranoia and license incompatibility that so frequently plague code reuse.

Kompimi is also an alias: because public domain coders don't receive the benefit of a license clause that indemnifies them against litigation, their best defense is anonymity. I am currently the only one using this alias, but I invite others who share my mission to adopt it.

This blog is intended to provide progress updates on the many Kompimi projects that will come to be, as well as to discuss philosophy and events in public domain code. I always invite your feedback, and hope the community will benefit from this undertaking.

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.