fastmap(3) -- library routines for fastmap files

SYNOPSIS

Build and Install

./configure && make && make install

Using

#include <fastmap.h>

Creating a fastmap

fastmap_attr_t attr;
fastmap_outhandle_t out;

fastmap_atom_t atoms[] = { 1, 2, 3, /* ... , */ 16631, /* ... , */ 999999 };

fastmap_attr_init(&attr);
fastmap_attr_setformat(&attr, FASTMAP_ATOM);
fastmap_attr_setrecords(&attr, sizeof(atoms) / sizeof(atoms[0]));
fastmap_attr_setksize(&attr, sizeof(atoms[0]));

fastmap_outhandle_init(&out, &attr, "/a/fastmap");

for (int i = 0; i < sizeof(atoms) / sizeof(atoms[0]); i++)
  fastmap_outhandle_put(&out, (fastmap_record_t*)&atoms[i]);

fastmap_outhandle_destory(&out);

Querying a fastmap

fastmap_atom_t atom;
fastmap_inhandle_t in;

fastmap_inhandle_init(&in, "/a/fastmap");

atom.key = 16631;
assert(fastmap_inhandle_get(&in, &atom) == FASTMAP_OK);

fastmap_inhandle_destroy(&in);

DESCRIPTION

A fastmap file represents an immutable key-value map.

When creating a fastmap, records must be inserted in sorted order.

One must decided, a priori, on certain parameters which affect how the fastmap will be created:

• The number of records the fastmap will contain.

• The size of a key.

• The fastmap format (see [FORMATS][FORMATS]).

Functions

• fastmap_attr_init(fastmap_attr_t *)
• fastmap_outhandle_init(fastmap_outhandle_t *, fastmap_attr_t *, const char *)
• fastmap_inhandle_init(fastmap_inhandle_t *, const char *)

Use these functions to initialize the fastmap data structures.

• fastmap_outhandle_put(fastmap_outhandle_t *, fastmap_record_t *)
• fastmap_inhandle_get(fastmap_inhandle_t *, fastmap_record_t *)

Use these functions to respectively put and get a fastmap record.

• fastmap_attr_destroy(fastmap_attr_t *)
• fastmap_outhandle_destroy(fastmap_outhandle_t *)
• fastmap_inhandle_destroy(fastmap_inhandle_t *)

Use these functions to de-initialize fastmap data structures, previously initialized.

• fastmap_attr_setrecords(fastmap_attr_t *, size_t)
• fastmap_attr_setksize(fastmap_attr_t *, size_t)
• fastmap_attr_setvsize(fastmap_attr_t *, size_t)
• fastmap_attr_setformat(fastmap_attr_t *, fastmap_format_t)

Use these functions to define the attributes of a fastmap before it is created.

• fastmap_attr_getrecords(fastmap_attr_t *, size_t *)
• fastmap_attr_getksize(fastmap_attr_t *, size_t *)
• fastmap_attr_getvsize(fastmap_attr_t *, size_t *)
• fastmap_attr_getformat(fastmap_attr_t *, fastmap_format_t *)

Use these functions to inspect the current values of the various attributes.

Fastmap function return values

Most fastmap functions return FASTMAP_OK on success, and a non-zero error value type int on failure. A user can obtain a string message for the given error with a call to fastmap_strerror(3). Note that the fastmap functions do not set errno.

Fastmap thread safety

The design of the library is such that a single thread, in a single process, will create the fastmap file. Once created it can then be queried by both the creating thread and other threads, even across processes -- so long as the operating system supports a form of shared memory mapped file. On POSIX systems this is accomplished with mmap(3) using the MAP_SHARED flag (on Windows, MapViewOfFile provides the mechanism). The library also relies on the operating systems page cache to deal with the caching of fastmap pages.

FORMATS

A fastmap supports multiple formats all are key-value storage formats, but they are provide various benefits and trade-offs to the user.

There are four formats supported:

[FORMATS]:

• FASTMAP_ATOM this is a degenerate key-value format, where the key is the value.

• FASTMAP_PAIR this is a fixed size key-value format, where the key size and the value size are the same, and all keys and values have the same size.

• FASTMAP_BLOCK this format has a fixed size key, and a fixed size value, but the size of the value is not necessarily the same size as the key. If this format is selected, on must also choose the size of a value in addition to the size of a key.

• FASTMAP_BLOB this format has a fixed size key, but the value sizes are variable.

FILE LAYOUT

A fastmap has a simple structure consisting of a header, search page levels, a leaf page level, and finally (if needed) the pages containing values.

Visually it looks something like this:

+-------------------------- +
| HEADER                    |
+---------------------------+
| SEARCH PAGE LEVEL (n - 1) |
+---------------------------+
| ...                       |
+---------------------------+
| SEARCH PAGE LEVEL (0)     |
+---------------------------+
| LEAF PAGE LEVEL           |
+---------------------------+
| [VALUE PAGES] (if needed) |
+---------------------------+

If the fastmap has a format of FASTMAP_ATOM or FASTMAP_PAIR the value pages will be omitted.

If the fastmap has a format of FASTMAP_BLOCK, and the size of a key plus the size of a value are a multiple of the page size, the value pages will also be omitted.

LIMITATIONS

Keys currently must be a multiple of the page size, this will be relaxed in a later release.

The page size is currently fixed to the size of a page on the filesystem on which the fastmap is created. This will become adjustable in the future.

This library is not portable to systems which do not implement mmap(3) (or simmilar).

The fastmap file format is not portable. To remedy this the utility fastmap2json is provided to produce a portable form which can safely be relocated to another system. There is also json2fastmap which converts the portable format back into a system specific form.