offbrand Documentation

offbrand is a collection of reference counted generic data structures written in pure C for the C programmer. The library is intended to relieve the common need to reimplement a standard data structures in an application. Never again need to write an automatically resizing array for your application specific datatype and use the vector included in offbrand instead.

offbrand is based upon C style classes, and currently provides the following data structures out of the box:

• obdeque: A double ended linked list
• obint: an arbitrary precision integer
• obmap: A hash table with constant time insert and lookup
• obstring: a classic string type with more convenience methods than your standard c string.
• obvector: an automatically resizing array

The library also includes a script, mkobc (MaKe OffBrand Class), that generates new class skeletons for you, so you don't have to write a single piece of the boilerplate code required to make a datatype compatible with the data structure library. Just generate your new type with the script and add application specific logic to the generated files.

NOTE: The phrase "class" is used in this documentation to refer to a C style approximation of a class built from functions and incomplete types, rather than a traditional class in a language like Java or Ruby

offbrand is released under the MIT license, see the LICENSE.txt file in the root directory of the git repository for the license text.

Requirements

offbrand requires the following tools:

• ar
• gcc or clang
• glibc
• make

Any Linux distro or OS X with developer tools installed should be able to build the library with no issue. At this time Windows is not supported. If you would like to build the documentation for the project on your local machine then the Doxygen package is also required.

Knowledge Base: While the library is not terribly complex to use or understand, you should be comfortable with incomplete types, typecasting, and reference counted memory management to get the most out of offbrand.

Installation and Use

To build the library on your machine, clone the git repository and make:

$ git clone https://github.com/theck01/offbrand_lib.git
$ cd offbrand_lib
$ make fresh # builds library and runs all unit tests

If you do not want or need to run unit tests then subsitutue "make fresh" with "make". If you use clang rather than gcc edit the Makefile to contain the set the CC variable to clang:

CC = clang #rather than CC = gcc

Using offbrand is as simple as including some headers from the include/ subdirectory and linking your application to the bin/offbrand.a library archive.

Examples

Example applications can be found in the app/ subdirectory. The following example is the code for the pfinder application, a prime number generator:

#include "../../include/offbrand.h"
#include "../../include/obint.h"
#include "../../include/obstring.h"
#include "../../include/obvector.h"

int main(){

  uint64_t i, maybe_prime;
  obint *candidate, *next, *remainder;
  obstring *numstr;
  obvector *primes;

  // create vector with a small initial capacity
  primes = obvector_new(1);

  // seed primes vector with initial prime 2. Note the cast of
  // the obint to obj, an obvector stores the generic obj type rather than
  // any specific type
  candidate = obint_new(2);
  obvector_store_at_index(primes, (obj *)candidate, 0);

  // ob_release the candidate so the vector maintains the only reference to the
  // prime number. ob_release operates on the generic obj type, so the pointer
  // is cast
  ob_release((obj *)candidate);

  // begin the main prime finding loop
  candidate = obint_new(3);
  while(1){

    maybe_prime = 1;

    // search for a prime factor of candidate
    for(i=0; i<obvector_length(primes); i++){
      remainder = obint_mod(candidate, (obint *)obvector_obj_at_index(primes, i));
      // if the remainder is 0 then the candidate number is not prime
      if(obint_is_zero(remainder)) maybe_prime = 0;
      ob_release((obj *)remainder);
      if(!maybe_prime) break;
    }

    // if the number is still maybe prime then it is now definitely prime,
    // add it to the end of the primes vector
    if(maybe_prime){
      obvector_store_at_index(primes, (obj *)candidate, obvector_length(primes));
      numstr = obint_to_string(candidate);
      printf("Prime found: %s\n", obstring_cstring(numstr));
      ob_release((obj *)numstr);
    }

    // increment candidate by 2 and ob_release old candidate, it is not needed
    // by main loop
    next = obint_add_primitive(candidate, 2);
    ob_release((obj *)candidate);
    candidate = next;
  }
}

To build this example by hand (using gcc or clang):

$ gcc -Wall -Wextra apps/pfinder/main.c bin/offbrand.a -o pfinder

Documentation

The API references for classes can be found at this location, under the Modules tab. The documentation for each class is broken down by file. The public header documentation outlines the entire public API for each class, and should have all of the information required to use offbrand with standard applications. Any apps that will extend or modify the library builtins may benefit from the private header documentation, where the structure of the class data and private functions are documented.

This Doxygen documentation can be built locally if the system has the doxygen package installed, by using the documentation target of the project Makefile:

$ make documentation

After a successful build, documentation can be accessed in the docs/html/ subdirectory

File Structure

An offbrand compatible class (or builtin class) is split across 5 different files:

Documentation File

An optional file that serves to provide doxygen documentation for the general functionallity of the class. These files will be found in the docs/doxygen/ subdirectory of the library for builtin classes.

Public Header

Contains all functions operating on the class that are publicly accessable to call anywhere in any program. These files will be found in the include/ subdirectory of the library for builtin classes.

Private Header

Containing all functions operating on the class that should not be called directly by other programs and the definitions of all structs encapsulated by the class. Builtin private headers can be found in the include/private/ subdirectory.

Source File

Contains the implementation of all functions operating on the class, public and private. Source files for builtin classes can be be found in the src/classes/ subdirectory.

Unit Test File

An optional file, contains unit tests used to verify proper functionallity of the class. Test files can be found in the src/tests/ subdirectory.

Extending the Library

The offbrand library is intended to contain data structures common to many applications, but you are still left with the task of creating your own classes that are compatible with the library. Fortunately that task is not as tedious as it could be, the library includes a shell script to generate skeletons for all new classes.

mkobc (MaKe OffBrand Class) can be found in the scripts/ subdirectory. The best documentation for how to use the script can be found by running:

$ scripts/mkobc -h

This script generates 5 files containing the initial basis for a new class. These files contain all code required to make a class compatible with the rest of the library, and contain comments describing what code can be changed and what code should not be changed to ensure compatibility is maintained.

How it Works

offbrand is based on a property of the C language that dictates that all data types have a constant memory alignment, and that fields within a struct with be arranged sequentially in memory. That is, the memory layout of types within a struct can be reliably predicted, will be constant, and will be the same in two structs containing the same ordering of the same types of fields. A contrived example of how we can take advantage of this memory alignment:

struct B {
  int i;
};

struct A {
  struct B element_b;
  int j;
};

struct A *thing_a = malloc(sizeof(struct A)); 
thing_a->element_b.i = 10;

// A perfectly valid cast, you can now use the struct A as if it were a
// struct B
struct B *thing_b = (struct B *)thing_a;

// prints 10 to stdout
printf("%d\n", thing_b->i);

This memory alignment enables a struct A, which has struct B as it's first element, to be typecast and used as if it were struct B. In offbrand struct A is any of the offbrand classes and struct B is a special structure, "obj".

An obj ("object") encapsulates data common to all classes: a reference count, pointers to class specific versions of common functions, and a class name. obj is the generic type of the library, and casts from class pointers to obj pointers and back is common theme within offbrand code.

A standard library exists that operates exclusively on obj pointers. This basis allows any class instances to be compared, hashed, retained, released, etc. These functions call the class specific versions of each function, if they exist, hiding large numbers of class specific methods behind a small suite of common functions.

Next Steps and Contributing

The following tasks will/should/could be added to the library in the near future:

• A red-black tree datastructure
• The ability to build as a shared library and install the resulting .so and headers to system
• A better error handling mechanism (other than aborting on unexpected values)
• Unicode support for obstring

Clone, fork, submit issues and pull requests on github: https://github.com/theck01/offbrand_lib