Itzam/Core

C API Documentation (Hash Table Indexes)



 

Itzam/Core 4.0.7 Download: (tar.gz) (bzip2) (zip) Open Source License (GPL) Non-free, Closed-Source License: $749 Itzam/Java 2.1.1 Download: (source) (extension) Open Source License (GPL) Non-free, Closed-Source License: $749 Documents Itzam Home Page C API Documentation Java Class Documentation

Index

General Types & Functions
Datafiles
About Keys
B-tree Indexes
B-tree Index Cursors
Hash Indexes
Sparse Matrix Indexes
 

The hash table maps keys to records via a "hash function" that converts the key's value to a numeric index. While this technique is much faster (and smaller) than maintaining the complex structure of a hash table, a hash index does not allow keys in-order.

More about keys

All functions that directly manipulate hash indexes follow the naming pattern itzam_hash_*.

Types and Structures

itzam_hash

For the most part, you won't directly access the members of an itzam_hash 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 hash table index.

typedef struct
{
    itzam_datafile * m_datafile;       // file associated with this hash file
    
    // The rest is internal stuff
}
itzam_hash;

itzam_hash_function

A hash table index uses a function to convert a key into a hash value. The user defines and supplies a hash function pointer when opening or creating an index; this function must always return the same value. The supplied function's signature must match this type definition.

typedef itzam_int itzam_hash_function(const void * key, itzam_int buckets);

Parameters
key - a pointer to a key value
buckets - number of "buckets" in the hash table

Return Value
the hash value of the object pointed to by key, in the range [0..buckets-1]

itzam_key_comparator

A hash table index uses a comparator to determine the equality 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
btree - 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

Functions

itzam_hash_create

Creates a new hash table 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_hash_create(itzam_hash * hash,
                              const char * filename,
                              itzam_file_lock_mode   lock_mode,
                              itzam_int              buckets,
                              uint32_t               sizeof_key,
                              itzam_hash_function  * hasher,
                              itzam_key_comparator * comparator);

Parameters
hash - a pointer to the target itzam_hash structure
filename - the platform-specific name of the file to be created
lock_mode - the mode of file locking; possible values include ITZAM_LOCK_NONE (no locking), ITZAM_LOCK_OS (lock via operating system functions), and ITZAM_LOCK_FILE (lock using temporary secondary file)
buckets - the number of "buckets" held in the hash table; a larger number of buckets results in a faster the index and a bigger the datafile
key_size - the number of bytes in the key being stored
hasher - a function that produces a hash index from a given key value
key_comparator - a function that compares two index keys

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

itzam_hash_open

Opens an existing hash table 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_hash_open(itzam_hash * hash,
                            const char * filename,
                            itzam_file_lock_mode   lock_mode,
                            itzam_hash_function  * hasher,
                            itzam_key_comparator * comparator,
                            bool read_only,
                            bool recover);

Parameters
hash - a pointer to the target itzam_hash structure
filename - the platform-specific name of the file to be opened
lock_mode - the mode of file locking; possible values include ITZAM_LOCK_NONE (no locking), ITZAM_LOCK_OS (lock via operating system functions), and ITZAM_LOCK_FILE (lock using temporary secondary file)
hasher - a function that produces a hash index from a given key value
key_comparator - a function that compares two index keys
read_only - if true, the file will be opened read-only (no writes allowed)
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_hash_close

Closes an open hash table file and flushes any remaining file operations.

itzam_state itzam_hash_close(itzam_hash * hash);

Parameters
hash - a pointer to the target itzam_hash structure

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

itzam_hash_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 hash->m_datafile or a file position in another datafile, or any other 64-bit value of the caller's choosing.

itzam_state itzam_hash_insert(itzam_hash * hash,
                               const void * key);

Parameters
hash - a pointer to the target itzam_hash structure
key - a pointer to the key data that identifies the record reference

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

itzam_hash_insert_rec

Adds a new record to the index and its associated datafile, associating it with the given key.

itzam_state itzam_hash_insert(itzam_hash * hash,
                              const void * key);

Parameters
hash - a pointer to the target itzam_hash 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_hash_find

Finds the record reference associated with a given key.

itzam_ref itzam_hash_find(itzam_hash * hash,
                           const void * search_key,
                           void * result);

Parameters
hash - a pointer to the target itzam_hash 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_hash_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 hash->m_datafile. If ref is not NULL, this function returns the record reference associated with the deleted key.

itzam_state itzam_hash_remove(itzam_hash * hash,
                               const void * key);

Parameters
hash - a pointer to the target itzam_hash structure
key - a pointer to the key data that identifies the record
ref - see function description above

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

itzam_hash_lock

Exclusively locks a hashtable index, preventing other processes or threads form making changes.

bool itzam_hash_lock(itzam_hash * hash, bool read_only);

Parameters
hash - a pointer to the target itzam_hash structure

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

itzam_hash_unlock

Removes an existing lock from the file.

bool itzam_hash_unlock(itzam_hash * hash);

Parameters
hash - a pointer to the target itzam_hash structure

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

itzam_hash_transaction_start

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

itzam_state itzam_hash_transaction_start(itzam_hash * hash);

Parameters
hash - a pointer to the target itzam_hash structure

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

itzam_hash_transaction_commit

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

itzam_state itzam_hash_transaction_commit(itzam_hash * hash);

Parameters
hash - a pointer to the target itzam_hash structure

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

itzam_hash_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_hash_transaction_rollback(itzam_hash * hash);

Parameters
hash - a pointer to the target itzam_hash structure

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