The goal of the ubiqx project is to develop a set of clean,
small, re-usable code modules which implement fundamental constructs and
mechanisms, and to make them available under the terms of the GNU Library General Public
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/DBimps, and sloppy example
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:
The AVL and Splay Tree modules are descendant types of the basic
Binary Tree module.
- Simple, unbalanced binary trees
- AVL height-balanced trees
- Splay trees
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.
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.
- 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.
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
- 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
provide APIs for three types of table/database managers.
- This is a base module. It contains bottom-level typedefs and
- A key-access database API. It provides an API for unsorted,
unique-key data managers such as hash tables (eg. ndbm/gdbm).
- A descendant type of ubi_KeyDB, it adds support for sorted-order
storage and duplicate keys.
- 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
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:
- 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.
- 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.
- 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
- 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
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.