Itzam/C

Documentation

This document is a work in progress. I tend to learn by looking at code, and strongly suggest that you study the examples in the distribution's test directory for working examples of Itzam code. Yet I know how important hard docs can be, so I'm open to suggestions for improving or updating this document.

The Itzam/C distribution files contain a copy of this document in printable (black on white) format.

Itzam/C manages data storage using B-tree indexes, storing key-value pairs. Keys are identifiers of any fixed-length type for their associated value, and there is a one-to-one relationship between keys and values. Itzam/C supports transactions with rollback, multiple threads accessing the same database, and other features not usually found in small database engines.

In the real world, Itzam/C is the foundation of many business applications, including mission-critical systems running 24/365.

Itzam is not a SQL database, or something that can be accessed from ADO. You can build relational (or network, or...) database systems with Itzam as the underlying mechanic — but that really isn't what Itzam was meant for. The vast majority of applications do not need Oracle or SQL Server — they need a simple way to associate information with a key value, for retrieval. This is the niche Itzam occupies.

History

Itzam has a long and varied history. It began as example code in my first book, C++ Components and Algorithms (1992). The original code was meant to teach C++, yet several people contacted me asking if they could use it in various projects. Some even offered to pay for the code.

And so I reworked the book code into something worthy of production code. After many versions (and a side-trip into Java under the name "Jisp"), I arrived at the Itzam you see today.

The current reference version is written in C for a variety of reasons. C produces small code and can be wrapped in various other programming languages. By writing in Standard C, I maintain portability. The current code has seen production and commercial use across PCs, cell phones, and Macs.

Why "Itzam"?

Naming projects is always difficult; I sometimes think every word in English has been appropriated by someone. So I've had to stretch my linguistic horizons. "Itzam" is one of several Mayan words for iguana; given the fondness of iguanas for trees, and the presence of an iguana in my house, the name seemed rather fitting.

The Itzam logo (and all other site art) was created by my eldest daughter Elora, using a combination of commercial and open source tools.

License

From version 5.1 forward, Itzam is licensed under the FreeBSD License (aka, the Simplified BSD License). It is as follows:

Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:

   1. Redistributions of source code must retain the
      above copyright notice, this list of conditions
      and the following disclaimer.

   2. Redistributions in binary form must reproduce the
      above copyright notice, this list of conditions and
      the following disclaimer in the documentation and/or
      other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY SCOTT ROBERT LADD ``AS IS'' AND ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
EVENT SHALL SCOTT ROBERT LADD OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

The views and conclusions contained in the software and documentation are those
of the author alone, and should not be interpreted as representing the official
policies, either expressed or implied, of anyoen other than Scott Robert Ladd.

Older versions were released under various incarnations of the GPL. I won't bore you with details of why I've meandered through various Open Source/Free Software licenses; suffice it to say that the balkanization and politics of the Free Software movement have rubbed me very raw.

Individual and corporate licensing is available under a closed-source license; I also provide maintenance contracts and custom development. For such matters, please contact me at scott.ladd@coyotegulch.com or scott.ladd@gmail.com.

Basic Concepts and Structures

Most of the processes and concepts used in Itzam are the same as those used "under the hood" by more complex database systems. Itzam is a nuts-and-bolts approach to database development, providing great flexibility and customization at the expense of abstraction. You define how data is connected and associated; such control requires careful understanding of your data.

Itzam associates key values with objects serialized in files, by creating one or more B-tree indexes to connect keys with objects. In many respects, Itzam is very object-oriented, with functions tied by name to target data structures in much the same way as a C++ program links methods to class objects.

Everything you need is defined in the itzam.h header files. You'll find several data structures and internal definitions inside; you can safely ignore most of this, since you'll be working directly with only a few core types and structures.

itzam_ref (simple type)

By default, an itzam_ref is the address (position) of information inside an Itzam-defined database. By default, Itzam uses 32-bit file pointers; defining the preprocessor macro ITZAM64 during compilation will create an Itzam library that uses 64-bit file pointers. The 32-bit file operations handle files with sizes up to 2,147,483,648 bytes (some file systems may impose a lower limit); using 64-bit file operations allows access to files up to 9 quintillion bytes long.

Using 64-bit file pointers will support the growing size of databases and 64-bit CPUs. Handling 64-bit values imposes a slight performance and has a significant affect on file size.

In general, itzam_int is simply a synonym for itzam_ref, reflecting different contexts. An itzam_int is a length or size, while and itzam_ref is a file reference (position).

itzam_status (enum)

Most Itzam functions return a status code, which can be set to ITZAM_OKAY, ITZAM_NOT_FOUND, or any of the other constants found in itzam.h. Note that many functions will call an error handler function for serious errors; itzam_status is designed for programatic purpose (e.g., discovering that a key was not found), as opposed to error handling.

itzam_datafile (struct)

An itzam_datafile is a structured data file for storing fixed- or variable-length records; it automatically writes new records in space freed by deleted records. This class is useful without any of the indexing capabilities inherent in itzam_btree. In some applications, it may be practical to store data in individual itzam_datafiles, indexing it via one or more itzam_btrees.

For the purposes of an itzam_datafile, consider "record" to be nothing more than a blob of binary data; the semantics of that "blob" is the province of your program. If you're talking to Itzam from Java, for example, you can serialize objects to and from byte streams stored in an itzam_datafile.

To handle variable-length records, itzam_datafile records the size of each record. When a record is deleted, the space it occupied is marked as empty. The file maintains a linked list of deleted record locations and their sizes.

Inserting a new record involves a traverse of the deleted list, looking for an empty record that is large enough to contain the new information. If the deleted list is empty, or the new record is too large to fit into any open slots, the new object record is appended to the file.

Reusing deleted record space has a drawback: it leaves dead space in the file when a newly-inserted record is smaller than the "deleted" space it overwrites. Deleted records also use space in the file until a new record is written into their location. If your record sizes vary widely, it may make sense to periodically compact the file by removing the wasted space, eliminating deleted records, and regenerating indexes. If your records are fixed-length, the data file shouldn't contain much waste space.

All functions that directly manipulate datafiles follow the naming pattern itzam_datafile_*.

itzam_btree (struct)

An itzam_btree organizes keys. A key is a fixed-length datum or data collection that will be sorted into an order, using a B-tree structure stored in an itzam_datafile. The order of the keys is determined by a user-defined comparison function. The actual content of the key is unrestricted, beyond the algorithmic requirement that it be fixed in length. A key could be a 32-bit numeric serial number and a 32- or 64-bit reference to the associated record. Or, for small records, the key could contain the entire data, with only "key" elements being used in the comparison fucntion for ordering and look-up purposes.

All functions that directly manipulate B-tree indexes follow the naming pattern itzam_btree_*.

itzam_btree_cursor (struct)

An itzam_btree_cursor is a list of the records in a database, and can be traversed in key order. It does not store records; instead, it is a forward and backward traversable list of records in order (as defined by the database's key comparison function.)

When you create an itzam_btree_cursor, it locks the mutex for the B-tree, preventing changes to that B-tree until the cursor is closed.

In many ways, an itzam_btree_cursor can be used like a traditional database cursor. You can also treat it like a query, filtering records as you iterate through a list of records.

All functions that directly manipulate B-tree cursors follow the naming pattern itzam_btree_cursor_*.

Example Code

Itzam/C includes several test and example programs, found in the test directory of the distribution.

itzam_btree_test_stress

This program performs a series of random inserts and removes from a B-tree index, verifying the validity of the database after each action, and using transactions with commits and recalls. It excercises almost every part of Itzam/C, and demonstrates how to use those features.

itzam_btree_insert

Created at the behest of several customers, to show how fast raw insertion is. This is simple a benchmark.

itzam_btree_test_threads

This program creates multiple threads that sumltaneously insert and rmeove records from the same B-tree index. Mutexes within Itzam/C control resource access, and shared memory improves performance.

itzam_btree_test_strvar

Here is an example of two oft-queried concepts: The use of variable-length string keys, and the storage of variable-length records. For a simple Itzam database of fixed-length records (as in the examples above), data can be embedded along with keys in the B-tree structure. For more complex data bases, the key can be linked to a reference to its asscoaited data -- in this case, an itzam_ref to a record stored independently with the B-tree file.

This example also illustrates a key feature of Itzam/C: B-tree files are also itzam_datafiles, and an itzam_btree index can reference data outside the B-tree — for example, a position in another fiel that could contain text, other binary data, or another itzam_datafile.

The B-tree cursor mechanism is also shown in this example.

Common Types and Structures

itzam_ref

By default, an itzam_ref is the address (position) of information inside an Itzam-defined database. By default, Itzam uses 32-bit file pointers; defining the preprocessor macro ITZAM64 during compilation will create an Itzam library that uses 64-bit file pointers. The 32-bit file operations handle files with sizes up to 2,147,483,648 bytes (some file systems may impose a lower limit); using 64-bit file operations allows access to files up to 9,223,372,036,854,775,808 bytes long (again, limited by file system).

Using 64-bit file pointers will support the growing size of databases and 64-bit CPUs. Handling 64-bit values imposes a slight performance and has a significant affect on file size.

  #if defined(ITZAM64)
    typedef int64_t itzam_ref;
  #else
    typedef int32_t itzam_ref;
  #endif

itzam_int

An itzam_int is the same type as itzam_ref, but used in a different context. While an itzam_ref is a file pointer, and itzam_int is a length, such as the size of a record.

  #if defined(ITZAM64)
    typedef int64_t itzam_int;
  #else
    typedef int32_t itzam_int;
  #endif

itzam_bool

Yes, I know -- another damned boolean type. Here's the problem: different platforms support different bool implementations of differing sizes. Itzam relies on predictable datum sizes, thus it implements an explicit boolean type.

  typedef int16_t itzam_bool;
  static const int16_t itzam_true  = -1;
  static const int16_t itzam_false =  0;

itzam_state

Most Itzam functions return a status code, which can be set to ITZAM_OKAY, ITZAM_NOT_FOUND, or any of the other constants found in itzam.h. Note that many functions will call an error handler function for serious errors; itzam_state is designed for programatic purpose (e.g., discovering that a key was not found), as opposed to error handling.

typedef enum
{
    ITZAM_OKAY,
    ITZAM_AT_END,
    ITZAM_AT_BEGIN,
    ITZAM_UNKNOWN,
    ITZAM_NOT_FOUND,
    ITZAM_DUPLICATE,
    ITZAM_32BIT_OVERFLOW
} itzam_state;

itzam_error

When Itzam encounters a serious probled, it calls the error handler defined for a given itzam_datafile. This enumeration identifies the problem.

typedef enum
{
    ITZAM_ERROR_SIGNATURE,
    ITZAM_ERROR_VERSION,
    ITZAM_ERROR_WRITE_FAILED,
    ITZAM_ERROR_OPEN_FAILED,
    ITZAM_ERROR_READ_FAILED,
    ITZAM_ERROR_CLOSE_FAILED,
    ITZAM_ERROR_SEEK_FAILED,
    ITZAM_ERROR_TELL_FAILED,
    ITZAM_ERROR_DUPE_REMOVE,
    ITZAM_ERROR_FLUSH_FAILED,
    ITZAM_ERROR_TOO_SMALL,
    ITZAM_ERROR_NULL_ALLOC,
    ITZAM_ERROR_PAGE_NOT_FOUND,
    ITZAM_ERROR_LOST_KEY,
    ITZAM_ERROR_KEY_NOT_WRITTEN,
    ITZAM_ERROR_KEY_SEEK_FAILED,
    ITZAM_ERROR_ITERATOR_COUNT
} itzam_error;

itzam_error handler

This type defines the signature of an error handling function.

typedef void itzam_error_handler(const char * function_name, itzam_error error);

Common Functions

itzam_set_default_error_handler

Sets the default error handler. When Itzam creates a new datafile, it assigns the default handler to the datafile object. You can change the default handler with this function, or set datafile-specific error handlers with itzam_datafile_set_error_handler. The default error handler displays a message to stderr and causes program termination.

void itzam_set_default_error_handler(itzam_error_handler * error_handler);

Parameters
error_handler - Address of user-defined error handler

Return Value
None

itzam_get_default_error_handler

Returns the address of the current default error handler.

itzam_error_handler * itzam_get_default_error_handler();

Parameters
None

Return Value
The address of the current default error handler.

Datafiles

An itzam_datafile is a structured data file for storing fixed- or variable-length records; it automatically writes new records in space freed by deleted records. This class is useful without any of the indexing capabilities inherent in itzam_btree. In some applications, it may be practical to store data in individual itzam_datafiles, indexing it via one or more itzam_btrees.

For the purposes of an itzam_datafile, consider "record" to be nothing more than a blob of binary data; the semantics of that "blob" is the province of your program. If you're talking to Itzam from Java, for example, you can serialize objects to and from byte streams stored in an itzam_datafile.

To handle variable-length records, itzam_datafile records the size of each record. When a record is deleted, the space it occupied is marked as empty. The file maintains a linked list of deleted record locations and their sizes.

Inserting a new record involves a traverse of the deleted list, looking for an empty record that is large enough to contain the new information. If the deleted list is empty, or the new record is too large to fit into any open slots, the new object record is appended to the file.

Reusing deleted record space has a drawback: it leaves dead space in the file when a newly-inserted record is smaller than the "deleted" space it overwrites. Deleted records also use space in the file until a new record is written into their location. If your record sizes vary widely, it may make sense to periodically compact the file by removing the wasted space, eliminating deleted records, and regenerating indexes. If your records are fixed-length, the data file shouldn't contain much waste space.

All functions that directly manipulate datafiles follow the naming pattern itzam_datafile_*.

Datafile Types and Structures

itzam_datafile

This structure encapsulates the elements used internally by Itzam to manipulate a datafile.

typedef struct
{
  // you can safely ignore the members
}
itzam_datafile;

Datafile Functions

itzam_datafile_create

Creates a new, empty data file. This function will automatically delete any file named filename.

itzam_state itzam_datafile_create(itzam_datafile * datafile,
                                  const char * filename);

Parameters
datafile - a pointer to the target itzam_datafile structure

filename - the platform-specific name of the new file

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_open

Opens an existing datafile. The file may be open read-only.

itzam_state itzam_datafile_open(itzam_datafile * datafile,
                                const char * filename,
                                bool read_only,
                                bool recover);

Parameters
datafile - a pointer to the target itzam_datafile structure
filename - platform-specific name of the file to be opened
read_only - determines if the file is opened read-only (writes disallowed) recover - if true, the database will rollback any unfinished transactions; if false, the old journal file will simply be removed

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_state itzam_datafile_close

Closes an open data file. This flushes any remaining data to external storage.

itzam_state itzam_datafile_close(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_set_error_handler

Sets an error handling function specific to a given datafile. If this function is not used, Itzam supplies a default error function, printing an error message to stderr and calling exit(1).

void itzam_datafile_set_error_handler(itzam_datafile * datafile,
                                      itzam_error_handler * error_handler);

Parameters
datafile - a pointer to the target itzam_datafile structure
error_handler - the address of an error handler function

Return Value
None

itzam_datafile_mutex_lock

Lock the mutex associated with this datafile, preventing other threads from altering the datafile's resources until an unlock is performed. Several datafile functions lock and unlock the mutex internally, as needed for resource contention control. As such, it should not usually be necessary to call this function explicitly.

void itzam_datafile_mutex_lock(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

itzam_datafile_mutex_unlock

Unlock the mutex associated with this datafile, allowing other threads access to the datafile's resources. Several datafile functions lock and unlock the mutex internally, as needed for resource contention control. As such, it should not usually be necessary to call this function explicitly.

void itzam_datafile_mutex_unlock(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

itzam_datafile_tell

Retrieves the file pointer for a given datafile.

itzam_ref itzam_datafile_tell(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
The position of the file pointer in datafile.

itzam_datafile_seek

Sets the file pointer for a given datafile.

itzam_state itzam_datafile_seek(itzam_datafile * datafile,
                                itzam_ref pos);

Parameters
datafile - a pointer to the target itzam_datafile structure
pos - The new position, as calculated from the beginning of the file

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_rewind

Sets the file pointer to the beginning of the first active (not deleted) record in a datafile.

itzam_state itzam_datafile_rewind(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_get_next_open

Finds a file pointer that can be used to write a record of length bytes. This will either be a deleted record of at least length bytes, or the end of the datafile. This fucntion is generally used internally, and should be used with caution.

itzam_ref itzam_datafile_get_next_open(itzam_datafile * datafile,
                                       itzam_int length);

Parameters
datafile - a pointer to the target itzam_datafile structure
length - the required number of bytes

Return Value
The file pointer of the first empty record than can hold length bytes, or ITZAM_NULL_POS if an error occurred.

itzam_datafile_write

Writes a record to the datafile at the current file position. The record will be stored in the first deleted record with adequate space, or it will be written to the end of the file if no adequate deleted record is available.

itzam_ref itzam_datafile_write(itzam_datafile * datafile,
                               const void * data,
                               itzam_int length);

Parameters
datafile - a pointer to the target itzam_datafile structure
data - a pointer to the record being written
length - the number of bytes pointed to by data

Return Value
The file pointer to the beginning of the newly-written record, or ITZAM_NULL_POS if an error occurred.

itzam_datafile_overwrite

Overwrite a portion of a record at a gievn offset. The where must point to the beginning of a valid record, and the offset + length must not exceed the record's boundaries. This function should be used with caution.

itzam_ref itzam_datafile_overwrite(itzam_datafile * datafile,
                                   const void * data,
                                   itzam_int length,
                                   itzam_ref where,
                                   itzam_int offset);

Parameters
datafile - a pointer to the target itzam_datafile structure
data - a pointer to the record being written
length - the number of bytes pointed to by data
where - start of header for record being modified
offset - offset in bytes from the beginning of record data where writing should take place

Return Value
ITZAM_TOO_LONG if the overwrite would exceed the record boundaries
ITZAM_OKAY on success

itzam_datafile_read

Reads the record at the current file pointer in the given data file. This function assumes that the file pointer is at the beginning of a valid record.

itzam_state itzam_datafile_read(itzam_datafile * datafile,
                                void * data,
                                itzam_int max_length);

Parameters
datafile - a pointer to the target itzam_datafile structure
data - a pointer to a buffer to contain the read record
length - the maximum number of bytes that can be written to data

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_read_alloc

Reads the record at the current file pointer in the given data file. This function assumes that the file pointer is at the beginning of a valid record. Where itzam_datafile_read requires a pointer to preallocated space, itzam_datafile_read_alloc dynamically allocates record space based on information stored in the record header. The caller is responsible for freeing the memory allocated to data.

itzam_state itzam_datafile_read_alloc(itzam_datafile * datafile,
                                      void ** data,
                                      itzam_ref * length);

Parameters
datafile - a pointer to the target itzam_datafile structure
data - a pointer to a pointer that references the allocated record buffer
length - the number of bytes allocated to data -

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_remove

Deletes the record at the current file pointer in the given data file. This function assumes that the file pointer is at the beginning of a valid record.

itzam_state itzam_datafile_remove(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_commit

Forces the datafile to write all data pending in cache to memory.

itzam_state itzam_datafile_commit(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_file_lock

Exclusively locks a datafile using OS-level file locking, preventing other processes or threads from making changes.

itzam_bool itzam_datafile_lock(itzam_datafile * datafile, bool read_only);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
itzam_true if the function succeeded
itzam_fale the function failed; datafile is in an unknown state

itzam_datafile_file_unlock

Removes an existing OS-level lock from the file.

itzam_bool itzam_datafile_unlock(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
itzam_true if the function succeeded
itzam_false the function failed; datafile is in an unknown state

itzam_datafile_transaction_start

Begins a new transaction and locks the file. Until a commit or reollback is performed, all changes to the datafile file are recorded in an external journal file.

itzam_state itzam_datafile_transaction_start(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_transaction_commit

Commits the current transaction, which makes all changes permanent. The temporary journal file is removed, and the file unlocked.

itzam_state itzam_datafile_transaction_commit(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_datafile_transaction_rollback

The current transaction is "rolled back", meaning that all changes to the file will be "undone". The temporary journal file is removed, and the file unlocked.

itzam_state itzam_datafile_transaction_rollback(itzam_datafile * datafile);

Parameters
datafile - a pointer to the target itzam_datafile structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

B-trees

The B-tree data structure maintains a list of keys in order, as determined by a user-supplied key comparison function. You determine the sort order via the comparison function supplied when opening or creating an itzam_btree. Just be certain that you always use the same comparison function whenever making changes to the index.

All keys must be unique in a B-tree index.

More about keys

Functions that directly manipulate B-tree indexes follow the naming pattern itzam_btree_*.

B-tree Types and Structures

itzam_btree

For the most part, you won't directly access the members of an itzam_btree structure. However, it is possible (and often quite desirable) to store non-index data in the same datafile used by an index. The example program does this very thing, combining contact records with the name-based B-tree index.

typedef struct
{
    itzam_datafile * m_datafile;       // file associated with this B-tree file

    // The rest is internal stuff
}
itzam_btree;

itzam_key_comparator

A B-tree index uses a comparator to determine the relative order of two keys. The user defines and supplies a comparator function pointer when opening or creating an index; the function's signature must match this type definition.

typedef int itzam_key_comparator(const void * key1, const void * key2);

Parameters
B-tree - a pointer to the target itzam_btree structure
filename - the platform-specific name of the file to be created
key_comparator - a function that compares two index keys

Return Value
< 0, if key1 is before key2
= 0, if key1 equals key2
> 0, if key1 is after key2

B-tree Functions

itzam_btree_create

Creates a new B-tree index by creating a data file with a specific internal structure. Keys will be ordered based on comparisons performed via the called-supplied key_comparator function.

itzam_state itzam_btree_create(itzam_btree * B-tree,
                               const char * filename,
                               uint16_t order,
                               itzam_int key_size,
                               itzam_key_comparator * key_comparator,
                               itzam_error_handler * error_handler);

Parameters
B-tree - a pointer to the target itzam_btree structure
filename - the platform-specific name of the file to be created
key_size - the number of bytes in key objects; all keys must be of this exact size
order - the number of keys held in each B-tree page; the predefined constant ITZAM_BTREE_ORDER_DEFAULT works well for most indexes
key_comparator - a function that compares two index keys error_handler - the function to be called when a fatal error occurs in Itzam

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_open

Opens an existing B-tree index file. The key_comparator function must produce the same results as the comparison functions used in previous manipulations of the index. In other words, always use the same key_comparator function for a given index.

itzam_state itzam_btree_open(itzam_btree * B-tree,
                             const char * filename,
                             itzam_key_comparator * key_comparator,
                             itzam_error_handler * error_handler,
                             itzam_bool recover,
                             itzam_bool read_only);

Parameters
B-tree - a pointer to the target itzam_btree structure
filename - the platform-specific name of the file to be opened
in a faster the index and a bigger the datafile
key_comparator - a function that compares two index keys
read_only - if true, the file will be opened read-only (no writes allowed); this is handled internally to ITzam, and only prevents this specific itzam_btree from performing inserts and removes.
recover - if true, any unfinished transactions will be rolled back; if false, existing transaction files are simply deleted

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_close

Closes an open B-tree file and flushes any remaining file operations.

itzam_state itzam_btree_close(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_mutex_lock

Lock the mutex associated with this B-tree, preventing other threads from altering the B-tree's resources until an unlock is performed. Several B-tree functions lock and unlock the mutex internally, as needed for resource contention control. As such, it should not usually be necessary to call this function explicitly.

This function is a convenience; it simply calls the itzam_datafile_mutex_lock fucntion for the datafile underlying the B-tree.

void itzam_btree_mutex_lock(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

itzam_btree_mutex_unlock

Unlock the mutex associated with this B-tree, allowing other threads access to the B-tree's resources. Several B-tree functions lock and unlock the mutex internally, as needed for resource contention control. As such, it should not usually be necessary to call this function explicitly.

This function is a convenience; it simply calls the itzam_datafile_mutex_unlock fucntion for the datafile underlying the B-tree.

void itzam_btree_mutex_unlock(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

itzam_btree_count

Returns the number of active keys stored in the B-tree.

uint64_t itzam_btree_count(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
The number of active keys in the B-tree.

itzam_btree_ticker

Returns a count of the number of times a key has been added to the B-tree.

uint64_t itzam_btree_ticker(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
The number of times a key has been added to the B-tree.

itzam_btree_insert

Adds a new record reference to the index, with a given key. The index does not place any semantics on the value of reference; it is merely stored in association with key. The reference can be a file pointer in B-tree->m_datafile or a file position in another datafile, or any other 64-bit value of the caller's choosing.

itzam_state itzam_btree_insert(itzam_btree * B-tree,
                               const void * key);

Parameters
B-tree - a pointer to the target itzam_btree structure
key - a pointer to the key data that identify the record reference

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_find

Finds the record reference associated with a given key.

itzam_ref itzam_btree_find(itzam_btree * B-tree,
                           const void * search_key
                           void * result);

Parameters
B-tree - a pointer to the target itzam_btree structure
search_key - a pointer to the key data that identifies the record result - a pointer to key data that will be updated with the contents found by searchign for search_key

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_remove

Removes the first key found that is associated with the given key. If ref is NULL, the function also attempts to remove the associated record from the B-tree->m_datafile. If ref is not NULL, this function returns the record reference associated with the deleted key.

itzam_state itzam_btree_remove(itzam_btree * B-tree,
                               const void * key);

Parameters
B-tree - a pointer to the target itzam_btree structure
key - a pointer to the key data that identifies the record

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_file_lock

A simple wrapper for itzam_datafile_file_lock.

itzam_bool itzam_btree_lock(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
itzam_true if the function succeeded
itzam_false the function failed; B-tree is in an unknown state

itzam_btree_file_unlock

A simple wrapper for itzam_datafile_file_unlock.

itzam_bool itzam_btree_unlock(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
itzam_true if the function succeeded
itzam_false the function failed; B-tree is in an unknown state

itzam_btree_transaction_start

Begins a new transaction and locks the file. Until a commit or reollback is performed, all changes to the B-tree file are recorded in an external journal file.

itzam_state itzam_btree_transaction_start(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_transaction_commit

Commits the current transaction, which makes all changes permanent. The temporary journal file is removed, and the file unlocked.

itzam_state itzam_btree_transaction_commit(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_transaction_rollback

The current transaction is "rolled back", meaning that all changes to the file will be "undone". The temporary journal file is removed, and the file unlocked.

itzam_state itzam_btree_transaction_rollback(itzam_btree * B-tree);

Parameters
B-tree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

Syraqua Logo

Scott
Robert
Ladd

Software Engineer
 

 
 

 


© 2013 Scott Robert Ladd
All rights reserved.

The grey-and-purple dragon logo, the blue coyote logo, Coyote Gulch Productions, Itzam, SigScope, Evocosm, and Acovea are all Trademarks of Scott Robert Ladd.