ubiqx Modules

Module Overview

These are the little training wheels that keep getting re-invented; the small parts in that drawer in the kitchen. It's those things that are always in your way when you're looking for something else, but are never there when you really need them. Our goal is to be the good neighbor who always seems to have the missing flange-screw or cup of sugar that you need when you're in the middle of a project.

The ubiqx modules are written in ANSI C and have been tested on a variety of platforms including AmigaOS, Linux, OpenBSD, Irix, etc.

The core library consists of those modules found in the ubiqx/library/ directory in the distribution. We expect that all of the core modules will compile and work without modification on any platform that has an ANSI C compiler. If you find an exception, please let us know about it. There are additional modules in ubiqx/DB & ubiqx/DBimps, and sloppy example code in ubiqx/test-toys.

The modules currently available are:

Lists, Queues, and Stacks

These are the kinds of thing that are so basic that most programmers simply re-write them whenever they need them, and therein lies the problem. We've seen plenty of otherwise good code that has half a dozen re-implementations of a linked list. This is re-inventing the training wheel. Do it once, do it right, and don't do it again!

Binary Trees

We originally wrote these for the Amiga, an environment in which one must to be careful about the use of stack space. As a result, these modules are non-recursive. They are also designed in an object-oriented style using regular C (not C++ or Objective C).

Three types of binary tree are available:

• Simple, unbalanced binary trees
• AVL height-balanced trees
• Splay trees

The AVL and Splay Tree modules are descendant types of the basic Binary Tree module.

Each of these has its own characteristics. The API is quite complete and, to make things easy, there is a generic interface that is the same for all three tree types. Your choice of tree is determined simply by the header file which you include; the calls remain the same.

Generic Cache

The ubi_Cache module is built on ubi_SplayTree. It implements a simple caching system.

• It keeps track of the amount of memory in use by the cache
• It keeps a "cache hit" ratio
• If the cache gets too large (measured either by number of entries or by memory used), it is automatically trimmed back to within the limits you set.

These features, and the functions & macros that implement them, are all you need to build a quick, simple cache. The Splay tree moves most recently accessed cache entries toward the top of the tree, and less recently accessed entries toward the bottom. As a result, it is easy to purge less recently accessed entries when the cache exceeds any of the user defined maximums.

If you have used the binary tree modules, the cache should be fairly easy. Examples and "real" documentation may not appear for a while, but feel free to ask questions.

Simple Sparse Array

The ubi_SparseArray module is also built on top of the ubi_SplayTree. It provides the basic tools needed to build an in-memory hierarchical database.

Database Interface Modules

These modules, located in the ubiqx/DB directory, provide APIs for three types of table/database managers.

ubi_DB:

This is a base module. It contains bottom-level typedefs and utility macros.

ubi_KeyDB:

A key-access database API. It provides an API for unsorted, unique-key data managers such as hash tables (eg. ndbm/gdbm).

ubi_IndexDB:

A descendant type of ubi_KeyDB, it adds support for sorted-order storage and duplicate keys.

ubi_SparseArrayDB:

This is a descendant type of ubi_IndexDB. It allows multiple sets of data to exist in the same database. These sets are linked together in a hierarchical fashion. An entry in a set may have a link to another set. Sparse arrays are also called hierarchical or multi-dimensional associative arrays.

Database Implementation Modules

These modules, located in the ubiqx/DBimps directory, are the glue between the ubi_DB APIs and the actual table manager or database. They also serve as examples, so that you can write additional implementation modules. They include:

kdb_ll:

Implements a key-access database using an in-memory linked list. Lookups are performed by sequential search, and a search must be performed before each insertion to prevent duplicate entries. Not recommended for large lists. It takes about 35 to 40 minutes to store and dump 44K records on our 486-based/120MHz Linux box at home.

kdb_xdbm:

Implements a key-access database using ndbm or gdbm. It is a tiny bit awkward at times, but it runs our database store and dump test in around 8 minutes, about 1/5th the time needed by kdb_ll. Note that this module requires either ndbm or gdbm.

idb_tree:

Implements an index-order database using binary splay trees. This one finishes the store and dump test in less than six seconds. Compare that against 35+ minutes for the linked lists!

sa_tree:

Implements a sparse array using splay trees. Because the database types are object-oriented, this module can also run the store and dump test. As would be expected, it is almost exactly as fast as idb_tree.

Note that the database implementation modules do not have the "ubi_" prefix and are not considered to be part of the core library. They do things like allocate memory and open files and other real-world stuff like that.