smbase: A Utility Library

Introduction

"smbase" stands for Scott McPeak's Base Library (sorry, naming things is not my specialty). It's a bunch of utility modules I use in virtually all of my projects. The entire library is in the public domain.

There is some overlap in functionality between smbase and the C++ Standard Library. Partly this is because smbase predates the standard library, and partly this is because that library has aspects to its design that I disagree with (for example, I think it is excessively templatized, given flaws in the C++ template mechanism). However, the intent is that client code can use smbase and the standard library at the same time.

smbase has developed organically, in response to specific needs. While each module individually has been reasonably carefully designed, the library as a whole has not. Consequently, the modules to not always orthogonally cover a given design space, and some of the modules are now considered obsolete (marked below as such).

Some of the links below refer to generated documentation files. If you are reading this from your local filesystem, you may have to say "make gendoc" (after "./configure") to get them.

Build Instructions

  $ ./configure
  $ make
  $ make check
./configure understands these options. You can also look at the Makefile.

Modules

The following sections list all the smbase modules, grouped by functionality.

Linked Lists

Linked lists are sequences of objects with O(1) insertion at the front and iterators for traversal. Most also have mutators for traversing and modifying.

The two main lists classes are ObjList and SObjList. Both are lists of pointers to objects; the former owns the objects, and will delete them when it goes away, while the latter does not.

There are a couple of variants that support O(1) appending.

Finally, two stacks implemented with lists. Recently, I've been preferring to use array-based stacks (array.h), so these are somewhat obsolete.

Arrays

Arrays are sequences of objects with O(1) random access and replacement.

The main array header, array.h, contains several array classes. GrowArray supports bounds checking and a method to grow the array. ArrayStack supports a distinction between the length of the sequence and the size of the array allocated to store it, and grows the latter automatically.

The other array modules are less-used.

This is obsolete.

Arrays of Bits

Arrays of bits are handled specially, because they are implemented by storing multiple bits per byte.

Hash Tables and Maps

Maps support mapping from arbitrary domains to arbitrary ranges. Mappings can be added and queried in amortized O(1) time, but the constant factor is considerably higher than for arrays and lists.

Probably the most common map is the PtrMap template, which will map from pointers to pointers, for arbitrary pointed-to types.

If the key can always be derived from the data (for example, the key is stored in the data object), then it is inefficient to store both in the table. The following variants require a function pointer to map from data to keys.

The above can be used to efficiently implement a set of T*.

There are two specialized versions that combine O(1) insertion and query of a hash table with O(1) enqueue and dequeue of an array.

Maps with Strings as Keys

Mapping from strings is a nontrivial extension of the above maps because comparison is more than a pointer equality test. So there are some specialized maps from strings.

If you have a function that can map from data to (string) key, then StringHash and TStringHash (the template version) are the most efficient:

The StringVoidDict and templates wrapped around it are more general. They do not require a function to map from data to key, support query-then-modify-result, and alphabetic iteration.

Finally, there is a module to map from strings to strings.

Strings

Strings are sequences of characters.

System Utilities

The following modules provide access to or wrappers around various low-level system services.

Portability

These modules help insulate client code from the details of the system it is running on.

Allocation

These modules provide additional control over the allocator.

Exceptions

These modules define or throw exceptions.

Serialization

The "flatten" serialization scheme is intended to allow sets of objects to read and write themselves to files.

Compiler/Translator Support

smbase has a number of modules that are of use to programs that read and/or write source code.

Testing and Debugging

Miscellaneous

Test Drivers

Test drivers. Below are the modules that are purely test drivers for other modules. They're separated out from the list above to avoid the clutter.

Utility Scripts

Module Dependencies

The scan-depends.pl script is capable of generating a module dependency description in the Dot format. Not all the modules appear; I try to show the most important modules, and try to avoid making Dot do weird things. Below is its output.

Module Dependencies
There's also a Postscript version.

Valid HTML 4.01!