Main Page | Modules | Alphabetical List | Data Structures | File List | Data Fields | Globals

Sparse matrices


Detailed Description

Sparse matrices are advanced data structures used to represent associations. For instance, a manager may have several employees, but several of those employees may report to more than one manager. (Yes, this is a contrived example, so sue me.) The simplest way to represent such assocations is with a matrix, or a two-dimensional array. However, such an implementation cannot easily be extended dynamically--imagine if a manager retires and two more are hired, for instance. It would also use an enormous amount of memory, as most employees would only report to one or two managers.

A sparse matrix solves this problem by only allocating memory for the cells in the full matrix which are actually used. That is, no memory is allocated to represent Alice reporting to Bob unless Alice actually does report to Bob. This is a simple concept, but fairly difficult to implement efficiently--how do you tell if Alice reports to Bob? The solution utilized by this library is to combine the strengths of linked lists and hash tables. Each cell is in two linked lists, rooted at the rows and columns of the matrix, but a hash table is used when attempting to look up a given cell. If the cell is allocated, then there will be an entry in the hash table, and finding the given cell is as fast as a hash table look-up.

Because sparse matrices are so complicated, there are three structures and a variety of operations used. Two of the structures, smat_table_t and smat_head_t, are caller-allocated. However, the third structure, smat_entry_t, must be allocated by the library. To avoid too much overhead from malloc(), a free list is used. The free list may be managed with the smat_cleanup() and smat_freemem() calls.

The smat_table_t contains the hash table. Only one of these need be allocated per type of association--for instance, in the above example, only one smat_table_t needs to be allocated to represent the manager-employee relationship.

The smat_head_t contains the linked list. There are actually two kinds of these structures--one is SMAT_LOC_FIRST, which could be regarded as a ``row,'' and the other is SMAT_LOC_SECOND, which could be regarded as a ``column.'' Which one is used for which type of data is irrelevant, as long as consistency is maintained. For the above example, a smat_head_t for a manager may be SMAT_LOC_FIRST, and one for an employee must then be SMAT_LOC_SECOND. (These values are set when initializing the smat_head_t structure.)

An association may be created with the st_add() function, which allows an arbitrary ordering in the associated linked lists by the same mechanism as for the linked list component of the library. An association may be removed with st_remove(), or looked up with st_find(). If iteration over all associations is desired, use the st_iter() function. Removing all associations from a table may be performed with st_flush(), which optionally calls a user-defined clean-up function. The associated hash table may be resized with st_resize(), and the bucket table may be released with st_free().

An association may also be reordered within the linked lists using the sh_move() function. If a particular entry is desired, use the sh_find() function with a user-defined comparison function to locate it. Iteration may be performed with the sh_iter() function, and all entries in a given linked list may be removed with the sh_flush() function, which again may optionally call a user-defined clean-up function.


Data Structures

struct  _smat_table_s
 Sparse matrix table structure. More...
struct  _smat_head_s
 Sparse matrix list head structure. More...
struct  _smat_entry_s
 Sparse matrix entry structure. More...
struct  _sh_find_s
 Sparse matrix head find shim structure. More...
struct  _sh_flush_s
 Sparse matrix flush function shim structure. More...
struct  _sh_iter_s
 Sparse matrix iteration function shim structure. More...
struct  _st_flush_s
 Sparse matrix flush function shim structure. More...
struct  _st_iter_s
 Sparse matrix iteration function shim structure. More...

Defines

#define _smat_ent(ent)
 Retrieve pointer to sparse matrix entry.
#define SMAT_TABLE_MAGIC
 Sparse matrix table magic number.
#define st_verify(table)
 Sparse matrix table verification macro.
#define st_flags(table)
 Sparse matrix table flags.
#define st_frozen(table)
 Determine if a sparse matrix is frozen.
#define st_modulus(table)
 Sparse matrix table modulus.
#define st_count(table)
 Sparse matrix table count.
#define st_extra(table)
 Extra pointer data in a sparse matrix table.
#define st_size(table)
 Sparse matrix table memory size.
#define SMAT_HEAD_MAGIC
 Sparse matrix list head magic number.
#define SMAT_HEAD_INIT(elem, object)
 Sparse matrix list head static initializer.
#define sh_verify(head)
 Sparse matrix list head verification macro.
#define sh_elem(head)
 Sparse matrix list head element macro.
#define sh_table(head)
 Sparse matrix list head table pointer.
#define sh_frozen(head)
 Determine if a sparse matrix is frozen.
#define sh_count(head)
 Sparse matrix list count.
#define _sh_first(head)
 Access the first element pointer in a smat_head_t.
#define sh_first(head)
 First element in sparse matrix list.
#define _sh_last(head)
 Access the last element pointer in a smat_head_t.
#define sh_last(head)
 Last element in sparse matrix list.
#define sh_object(head)
 Object represented by a sparse matrix list head.
#define sh_size(head)
 Sparse matrix list memory size.
#define SMAT_ENTRY_MAGIC
 Sparse matrix entry magic number.
#define se_verify(entry)
 Sparse matrix entry verification macro.
#define se_table(entry)
 Sparse matrix entry table.
#define _se_link(entry)
 Sparse matrix entry linked list element.
#define se_flags(entry)
 Sparse matrix entry flags.
#define se_hash(entry)
 Sparse matrix table entry hash value.
#define _se_next(entry, n)
 Access the next element pointer in a smat_entry_t.
#define se_next(entry, n)
 Next element in sparse matrix list.
#define _se_prev(entry, n)
 Access the previous element pointer in a smat_entry_t.
#define se_prev(entry, n)
 Previous element in sparse matrix list.
#define se_lflags(entry, n)
 Flags associated with an entry in a sparse matrix list.
#define se_object(entry, n)
 Object associated with an entry in a sparse matrix list.
#define ST_REM_FIRST
 Flag requesting removal from first list.
#define ST_REM_SECOND
 Flag requesting removal from second list.
#define ST_REM_HASH
 Flag requesting removal from hash table.
#define ST_REM_FREE
 Flag requesting memory release.

Typedefs

typedef _smat_table_s smat_table_t
 Sparse matrix table.
typedef _smat_head_s smat_head_t
 Sparse matrix list head.
typedef _smat_entry_s smat_entry_t
 Sparse matrix entry.
typedef unsigned long(* smat_resize_t )(smat_table_t *table, unsigned long new_mod)
 Sparse matrix table resize callback.
typedef unsigned long(* smat_iter_t )(smat_table_t *table, smat_entry_t *ent, void *extra)
 Sparse matrix iteration callback.
typedef unsigned long(* smat_comp_t )(db_key_t *key, smat_entry_t *ent)
 Sparse matrix comparison callback.
typedef enum _smat_loc_e smat_loc_t
 Sparse matrix location.

Enumerations

enum  _smat_loc_e { SMAT_LOC_FIRST, SMAT_LOC_SECOND }
 Sparse matrix location. More...

Functions

unsigned long smat_cleanup (void)
 Clean up the smat free list.
unsigned long smat_freemem (void)
 Report how much memory is used by the free list.
unsigned long st_init (smat_table_t *table, unsigned long flags, smat_resize_t resize, void *extra, unsigned long init_mod)
 Dynamically initialize a sparse matrix table.
unsigned long st_add (smat_table_t *table, smat_entry_t **entry_p, smat_head_t *head1, link_loc_t loc1, smat_entry_t *ent1, smat_head_t *head2, link_loc_t loc2, smat_entry_t *ent2)
 Add an entry to a sparse matrix.
unsigned long st_remove (smat_table_t *table, smat_entry_t *entry)
 Remove an entry from a sparse matrix.
unsigned long st_find (smat_table_t *table, smat_entry_t **entry_p, smat_head_t *head1, smat_head_t *head2)
 Find an entry in a sparse matrix.
unsigned long st_iter (smat_table_t *table, smat_iter_t iter_func, void *extra)
 Iterate over each entry in a sparse matrix.
unsigned long st_flush (smat_table_t *table, smat_iter_t flush_func, void *extra)
 Flush a sparse matrix.
unsigned long st_resize (smat_table_t *table, unsigned long new_size)
 Resize a sparse matrix table.
unsigned long st_free (smat_table_t *table)
 Free memory used by an empty sparse matrix table.
unsigned long sh_init (smat_head_t *head, smat_loc_t elem, void *object)
 Dynamically initialize a sparse matrix row or column head.
unsigned long sh_move (smat_head_t *head, smat_entry_t *elem, link_loc_t loc, smat_entry_t *elem2)
 Move an entry within a row or column list.
unsigned long sh_find (smat_head_t *head, smat_entry_t **elem_p, smat_comp_t comp_func, smat_entry_t *start, db_key_t *key)
 Find an entry in a row or column of a sparse matrix.
unsigned long sh_iter (smat_head_t *head, smat_entry_t *start, smat_iter_t iter_func, void *extra, unsigned long flags)
 Iterate over each entry in a row or column of a sparse matrix.
unsigned long sh_flush (smat_head_t *head, smat_iter_t flush_func, void *extra)
 Flush a row or column of a sparse matrix.
unsigned long _st_remove (smat_table_t *table, smat_entry_t *entry, unsigned int remflag)
 Remove an entry from a sparse matrix (internal).
smat_entry_t_smat_alloc (void)
 Allocate a sparse matrix entry.
void _smat_free (smat_entry_t *entry)
 Release a sparse matrix entry.
unsigned long _smat_resize (hash_table_t *table, unsigned long new_mod)
 Sparse matrix resize function.
static unsigned long _sh_find_comp (db_key_t *key, void *data)
 Sparse matrix linked list comparision function.
static unsigned long _sh_flush_iter (link_head_t *head, link_elem_t *elem, void *extra)
 Sparse matrix linked list flush callback.
static unsigned long _sh_iter_iter (link_head_t *head, link_elem_t *elem, void *extra)
 Sparse matrix linked list iteration callback.
static unsigned long _st_flush_iter (hash_table_t *table, hash_entry_t *ent, void *extra)
 Sparse matrix hash flush callback.
static unsigned long _st_iter_iter (hash_table_t *table, hash_entry_t *ent, void *extra)
 Sparse matrix hash iteration callback.

Variables

static link_head_t _smat_freelist
 Sparse matrix freelist.


Define Documentation

#define _se_link entry   ) 
 

For internal use only.

This macro provides access to the linked list element buried in the sparse matrix entry for use by the free list routines.

Parameters:
[in] entry A pointer to a smat_entry_t.
Returns:
A pointer to a link_elem_t.

Definition at line 2383 of file dbprim.h.

Referenced by _smat_free().

#define _se_next entry,
 ) 
 

For internal use only.

This helper macro is used to directly access the next linked list element in a specific sparse matrix linked list.

Parameters:
[in] entry A pointer to smat_entry_t.
[in] n One of SMAT_LOC_FIRST or SMAT_LOC_SECOND to specify which list thread is desired.
Returns:
A pointer to a link_elem_t indicating the next element in the list.

Definition at line 2427 of file dbprim.h.

#define _se_prev entry,
 ) 
 

For internal use only.

This helper macro is used to directly access the previous linked list element in a specific sparse matrix linked list.

Parameters:
[in] entry A pointer to smat_entry_t.
[in] n One of SMAT_LOC_FIRST or SMAT_LOC_SECOND to specify which list thread is desired.
Returns:
A pointer to a link_elem_t indicating the previous element in the list.

Definition at line 2463 of file dbprim.h.

#define _sh_first head   ) 
 

For internal use only.

This helper macro is used to directly access the first linked list element of a smat_head_t.

Parameters:
[in] head A pointer to smat_head_t.
Returns:
A pointer to a link_elem_t indicating the first element in the list.

Definition at line 2115 of file dbprim.h.

#define _sh_last head   ) 
 

For internal use only.

This helper macro is used to directly access the last linked list element of a smat_head_t.

Parameters:
[in] head A pointer to smat_head_t.
Returns:
A pointer to a link_elem_t indicating the last element in the list.

Definition at line 2143 of file dbprim.h.

#define _smat_ent ent   ) 
 

For internal use only.

This simple macro simply retrieves a pointer to the sparse matrix entry from a linked list element. It is a helper macro for the other macros that access sparse matrix entries.

Parameters:
[in] ent A pointer to a link_elem_t.
Returns:
A pointer to the relevant smat_entry_t.

Definition at line 1656 of file dbprim.h.

#define se_flags entry   ) 
 

This macro retrieves a set of user-defined flags associated with the entry. It may be used as an lvalue to set those flags.

Parameters:
[in] entry A pointer to a smat_entry_t.
Returns:
An unsigned long containing the flags associated with the entry.

Definition at line 2396 of file dbprim.h.

#define se_hash entry   ) 
 

This macro retrieves the hash value of the given sparse matrix entry. If the sparse matrix hash been resized, this value may not be the same as a previous value.

Parameters:
[in] entry A pointer to a smat_entry_t.
Returns:
An unsigned long containing the hash code for the entry.

Definition at line 2410 of file dbprim.h.

#define se_lflags entry,
 ) 
 

This macro retrieves a set of user-defined flags associated with the entry in a sparse matrix list. It may be used as an lvalue to set those flags.

Parameters:
[in] entry A pointer to smat_entry_t.
[in] n One of SMAT_LOC_FIRST or SMAT_LOC_SECOND to specify which list thread is desired.
Returns:
An unsigned long containing the flags associated with the entry.

Definition at line 2499 of file dbprim.h.

#define se_next entry,
 ) 
 

This macro retrieves a pointer to the link_elem_t for the next element in the sparse matrix list.

Warning:
This macro evaluates the entry and n arguments twice.
Parameters:
[in] entry A pointer to smat_entry_t.
[in] n One of SMAT_LOC_FIRST or SMAT_LOC_SECOND to specify which list thread is desired.
Returns:
A pointer to smat_entry_t.

Definition at line 2445 of file dbprim.h.

#define se_object entry,
 ) 
 

This macro retrieves a pointer to one of the objects represented by the entry. It may be used as an lvalue to change the object pointed to. Care should be taken when using this feature.

Parameters:
[in] entry A pointer to smat_entry_t.
[in] n One of SMAT_LOC_FIRST or SMAT_LOC_SECOND to specify which list thread is desired.
Returns:
A pointer to void representing the object.

Definition at line 2515 of file dbprim.h.

#define se_prev entry,
 ) 
 

This macro retrieves a pointer to the link_elem_t for the previous element in the sparse matrix list.

Warning:
This macro evaluates the entry and n arguments twice.
Parameters:
[in] entry A pointer to smat_entry_t.
[in] n One of SMAT_LOC_FIRST or SMAT_LOC_SECOND to specify which list thread is desired.
Returns:
A pointer to smat_entry_t.

Definition at line 2481 of file dbprim.h.

#define se_table entry   ) 
 

This macro retrieves a pointer to the table that the sparse matrix entry is in.

Parameters:
[in] entry A pointer to a smat_entry_t.
Returns:
A pointer to a smat_table_t.

Definition at line 2370 of file dbprim.h.

#define se_verify entry   ) 
 

This macro verifies that a given pointer actually does point to a sparse matrix entry.

Warning:
This macro evaluates the entry argument twice.
Parameters:
[in] entry A pointer to a smat_entry_t.
Returns:
Boolean true if entry is a valid sparse matrix entry or false otherwise.

Definition at line 2357 of file dbprim.h.

Referenced by sh_find(), sh_iter(), sh_move(), st_add(), and st_remove().

#define sh_count head   ) 
 

This macro retrieves the number of elements in the sparse matrix list rooted at head.

Parameters:
[in] head A pointer to smat_head_t.
Returns:
An unsigned long containing a count of the number of elements in the sparse matrix list.

Definition at line 2101 of file dbprim.h.

#define sh_elem head   ) 
 

This macro retrieves the position indicator for the sparse matrix head. It will return one of SMAT_LOC_FIRST or SMAT_LOC_SECOND.

Parameters:
[in] head A pointer to smat_head_t.
Returns:
An smat_loc_t.

Definition at line 2062 of file dbprim.h.

#define sh_first head   ) 
 

This macro retrieves a pointer to the smat_entry_t for the first element in the sparse matrix list.

Warning:
This macro evaluates the head argument twice.
Parameters:
[in] head A pointer to smat_head_t.
Returns:
A pointer to smat_entry_t.

Definition at line 2129 of file dbprim.h.

#define sh_frozen head   ) 
 

This macro returns a non-zero value if the matrix is currently frozen. The sparse matrix may be frozen if there is an iteration in progress.

Parameters:
[in] head A pointer to a smat_head_t.
Returns:
A zero value if the matrix is not frozen or a non-zero value if the matrix is frozen.

Definition at line 2088 of file dbprim.h.

#define sh_last head   ) 
 

This macro retrieves a pointer to the smat_entry_t for the last element in the sparse matrix list.

Warning:
This macro evaluates the head argument twice.
Parameters:
[in] head A pointer to smat_head_t.
Returns:
A pointer to smat_entry_t.

Definition at line 2157 of file dbprim.h.

#define sh_object head   ) 
 

This macro retrieves a pointer to the object referenced by the sparse matrix list head.

Parameters:
[in] head A pointer to smat_head_t.
Returns:
A pointer to void.

Definition at line 2169 of file dbprim.h.

Referenced by st_add(), and st_find().

#define sh_size head   ) 
 

This macro returns the physical size of the memory allocated by the library for this sparse matrix list.

Note:
The st_size() macro already counts the memory for each list in the table. Summing the results of sh_size() and st_size() will over-count the amount of memory actually in use.
Parameters:
[in] head A pointer to smat_head_t.
Returns:
A size_t.

Definition at line 2185 of file dbprim.h.

#define sh_table head   ) 
 

If there are any elements in this sparse matrix list head, this macro will retrieve a pointer to the table in which they reside.

Parameters:
[in] head A pointer to smat_head_t.
Returns:
A pointer to smat_table_t.

Definition at line 2074 of file dbprim.h.

#define sh_verify head   ) 
 

This macro verifies that a given pointer actually does point to a sparse matrix head.

Warning:
This macro evaluates the head argument twice.
Parameters:
[in] head A pointer to a smat_head_t.
Returns:
Boolean true if head is a valid sparse matrix head or false otherwise.

Definition at line 2049 of file dbprim.h.

Referenced by sh_find(), sh_flush(), sh_iter(), sh_move(), st_add(), and st_find().

#define SMAT_ENTRY_MAGIC
 

For internal use only.

This is the magic number used for the sparse matrix entry structure.

Definition at line 2342 of file dbprim.h.

Referenced by _smat_alloc().

#define SMAT_HEAD_INIT elem,
object   ) 
 

This macro statically initializes a smat_head_t.

Parameters:
[in] elem One of SMAT_LOC_FIRST or SMAT_LOC_SECOND specifing whether the object is a member of the set of rows or columns.
[in] object A pointer to void representing the object associated with the list head.

Definition at line 2033 of file dbprim.h.

#define SMAT_HEAD_MAGIC
 

For internal use only.

This is the magic number used for the sparse matrix list head structure.

Definition at line 2019 of file dbprim.h.

Referenced by sh_init().

#define SMAT_TABLE_MAGIC
 

For internal use only.

This is the magic number used for the sparse matrix table structure.

Definition at line 1678 of file dbprim.h.

Referenced by st_init().

#define st_count table   ) 
 

This macro retrieves the total number of items actually in the sparse matrix table.

Parameters:
[in] table A pointer to a smat_table_t.
Returns:
An unsigned long containing a count of the number of items in the sparse matrix table.

Definition at line 1752 of file dbprim.h.

#define st_extra table   ) 
 

This macro retrieves the extra pointer data associated with a particular sparse matrix table.

Parameters:
[in] table A pointer to a smat_table_t.
Returns:
A pointer to void.

Definition at line 1775 of file dbprim.h.

#define st_flags table   ) 
 

This macro retrieves the flags associated with the sparse matrix table. Only HASH_FLAG_AUTOGROW and HASH_FLAG_AUTOSHRINK have any meaning to the application; all other bits are reserved for use in the library. This macro may be used as an lvalue, but care must be taken to avoid modifying the library-specific bits.

Parameters:
[in] table A pointer to a smat_table_t.
Returns:
An unsigned long containing the flags for the sparse matrix table.

Definition at line 1710 of file dbprim.h.

#define st_frozen table   ) 
 

This macro returns a non-zero value if the matrix is currently frozen. The sparse matrix may be frozen if there is an iteration in progress.

Parameters:
[in] table A pointer to a smat_table_t.
Returns:
A zero value if the matrix is not frozen or a non-zero value if the matrix is frozen.

Definition at line 1724 of file dbprim.h.

#define st_modulus table   ) 
 

This macro retrieves the number of buckets allocated for the sparse matrix table. An application may wish to save this value between invocations to avoid the overhead of growing the table while filling it with data.

Parameters:
[in] table A pointer to a smat_table_t.
Returns:
An unsigned long containing the number of buckets allocated for the sparse matrix table.

Definition at line 1739 of file dbprim.h.

#define ST_REM_FIRST
 

For internal use only.

This flag may be passed to _st_remove() to request that a sparse matrix entry should be removed from the SMAT_LOC_FIRST linked list.

Definition at line 165 of file dbprim_int.h.

Referenced by _sh_flush_iter(), _st_flush_iter(), _st_remove(), st_add(), and st_remove().

#define ST_REM_FREE
 

For internal use only.

This flag may be passed to _st_remove() to request that a sparse matrix entry be passed to _smat_free().

Definition at line 193 of file dbprim_int.h.

Referenced by _st_remove(), st_add(), and st_remove().

#define ST_REM_HASH
 

For internal use only.

This flag may be passed to _st_remove() to request that a sparse matrix entry should be removed from the hash table.

Definition at line 184 of file dbprim_int.h.

Referenced by _sh_flush_iter(), _st_remove(), st_add(), and st_remove().

#define ST_REM_SECOND
 

For internal use only.

This flag may be passed to _st_remove() to request that a sparse matrix entry should be removed from the SMAT_LOC_SECOND linked list.

Definition at line 175 of file dbprim_int.h.

Referenced by _sh_flush_iter(), _st_flush_iter(), _st_remove(), and st_remove().

#define st_size table   ) 
 

This macro returns the physical size of the memory allocated by the library for this sparse matrix table.

Note:
The st_size() macro already counts the memory for each list in the table. Summing the results of sh_size() and st_size() will over-count the amount of memory actually in use.
Parameters:
[in] table A pointer to a smat_table_t.
Returns:
A size_t.

Definition at line 1791 of file dbprim.h.

#define st_verify table   ) 
 

This macro verifies that a given pointer actually does point to a sparse matrix table.

Warning:
This macro evaluates the table argument twice.
Parameters:
[in] table A pointer to a smat_table_t.
Returns:
Boolean true if table is a valid sparse matrix table or false otherwise.

Definition at line 1693 of file dbprim.h.

Referenced by st_add(), st_find(), st_flush(), st_free(), st_iter(), st_remove(), and st_resize().


Typedef Documentation

typedef unsigned long(* smat_comp_t)(db_key_t *key, smat_entry_t *ent)
 

This function pointer references a callback used by sh_find(). It should return 0 if the sparse matrix entry represented by the second argument matches the key passed as the first argument.

Parameters:
[in] key The database key being searched for.
[in] ent A pointer to the smat_entry_t being considered.
Returns:
Zero if key matches ent, non-zero otherwise.

Definition at line 476 of file dbprim.h.

typedef struct _smat_entry_s smat_entry_t
 

This structure is allocated by the library and represents a single element in a sparse matrix.

Definition at line 308 of file dbprim.h.

typedef struct _smat_head_s smat_head_t
 

This structure is the head of a linked list of sparse matrix entries.

Definition at line 300 of file dbprim.h.

typedef unsigned long(* smat_iter_t)(smat_table_t *table, smat_entry_t *ent, void *extra)
 

This function pointer references a callback used by st_iter(), st_flush(), sh_iter(), and sh_flush(). It should return 0 for success. A non-zero return value will terminate the operation and will become the return value of the call.

Parameters:
[in] table A pointer to a smat_table_t.
[in] ent A pointer to the smat_entry_t being considered.
[in] extra A void pointer passed to st_iter(), st_flush(), sh_iter(), or sh_flush().
Returns:
Zero for success, or non-zero to terminate the iteration.

Definition at line 460 of file dbprim.h.

typedef enum _smat_loc_e smat_loc_t
 

See the documentation for the enumeration _smat_loc_e.

Definition at line 556 of file dbprim.h.

typedef unsigned long(* smat_resize_t)(smat_table_t *table, unsigned long new_mod)
 

This function pointer references a callback that will be called with both the old and new sparse matrix table sizes whenever a sparse matrix's hash table table is resized. It should return non-zero only when the resize should be inhibited.

Parameters:
[in] table A pointer to a smat_table_t.
[in] new_mod The new table modulus.
Returns:
Zero to permit the table resize, non-zero otherwise.

Definition at line 440 of file dbprim.h.

typedef struct _smat_table_s smat_table_t
 

This structure is the basis of all sparse matrices maintained by this library.

Definition at line 292 of file dbprim.h.


Enumeration Type Documentation

enum _smat_loc_e
 

This enumeration is used to specify whether an element is a row or column element. It should be referenced by the typedef smat_loc_t.

Enumerator:
SMAT_LOC_FIRST  First entry (``row'').
SMAT_LOC_SECOND  Second entry (``column'').

Definition at line 546 of file dbprim.h.


Function Documentation

static unsigned long _sh_find_comp db_key_t key,
void *  data
[static]
 

For internal use only.

This function is a link_comp_t comparison callback that is used as a shim between the sh_find() function and the ll_find function, which it uses internally.

Parameters:
[in] key The database key being searched for.
[in] data The sparse matrix linked list entry.
Returns:
Zero if the sparse matrix linked list entry matches the key, non-zero otherwise.

Definition at line 61 of file sh_find.c.

References dk_key, _sh_find_s::sf_comp, and _sh_find_s::sf_key.

Referenced by sh_find().

static unsigned long _sh_flush_iter link_head_t head,
link_elem_t elem,
void *  extra
[static]
 

For internal use only.

This function is a link_iter_t iteration callback that is used as a shim between the sh_flush() function and the ll_flush() function, which it uses internally.

Parameters:
[in] head The linked list being iterated over.
[in] elem The specific linked list element being processed.
[in] extra Extra caller-specific data to pass to the iteration function. In this case, a pointer to a struct _sh_flush_s is passed.
Returns:
Zero to continue flushing, non-zero otherwise.

Definition at line 67 of file sh_flush.c.

References _smat_free(), _st_remove(), le_object, _sh_flush_s::sf_elem, _sh_flush_s::sf_extra, _sh_flush_s::sf_flush, _sh_flush_s::sf_table, SMAT_LOC_FIRST, ST_REM_FIRST, ST_REM_HASH, and ST_REM_SECOND.

Referenced by sh_flush().

Here is the call graph for this function:

static unsigned long _sh_iter_iter link_head_t head,
link_elem_t elem,
void *  extra
[static]
 

For internal use only.

This function is a link_iter_t iteration callback that is used as a shim between the st_iter() function and the ll_iter() function, which it uses internally.

Parameters:
[in] head The linked list being iterated over.
[in] elem The specific linked list element being processed.
[in] extra Extra caller-specific data to pass to the iteration function. In this case, a pointer to a struct _sh_iter_s is passed.
Returns:
Zero to continue iteration, non-zero otherwise.

Definition at line 66 of file sh_iter.c.

References le_object, _sh_iter_s::si_extra, _sh_iter_s::si_iter, and _sh_iter_s::si_table.

Referenced by sh_iter().

smat_entry_t* _smat_alloc void   ) 
 

For internal use only.

This function is used to allocate a sparse matrix entry. In cooperation with _smat_free(), it maintains a freelist in order to reduce memory fragmentation. If a sparse matrix entry cannot be allocated from the freelist, a new one will be allocated with malloc().

Returns:
A pointer to an initialized sparse matrix entry.

Definition at line 48 of file smat_freelist.c.

References he_init(), le_init(), le_object, ll_count, ll_first, ll_remove(), _smat_entry_s::se_hash, _smat_entry_s::se_link, _smat_entry_s::se_magic, _smat_entry_s::se_object, _smat_entry_s::se_table, SMAT_ENTRY_MAGIC, SMAT_LOC_FIRST, and SMAT_LOC_SECOND.

Referenced by st_add().

Here is the call graph for this function:

void _smat_free smat_entry_t entry  ) 
 

For internal use only.

This function is used to release a sparse matrix entry. In cooperatio with _smat_alloc(), it maintains a freelist in order to reduce memory fragmentation. Sparse matrix entries passed to this function will generally be added to the free list.

Parameters:
[in] entry The entry to release.

Definition at line 77 of file smat_freelist.c.

References _se_link, le_object, LINK_LOC_HEAD, ll_add(), and _smat_entry_s::se_magic.

Referenced by _sh_flush_iter(), _st_flush_iter(), _st_remove(), and st_add().

Here is the call graph for this function:

unsigned long _smat_resize hash_table_t table,
unsigned long  new_mod
 

For internal use only.

This function is a hash table-compatible resize callback for use by sparse matrices.

Parameters:
[in] table The hash table being resized.
[in] new_mod The new hash table bucket size.
Returns:
Zero if the resize operation should be performed, non-zero otherwise.

Definition at line 34 of file _smat_resize.c.

References ht_extra, and _smat_table_s::st_resize.

Referenced by st_init().

static unsigned long _st_flush_iter hash_table_t table,
hash_entry_t ent,
void *  extra
[static]
 

For internal use only.

This function is a hash_iter_t iteration callback that is used as a shim between the st_flush() function and the ht_flush() function, which it uses internally.

Parameters:
[in] table The hash table being iterated over.
[in] ent The specific hash table entry being processed.
[in] extra Extra caller-specific data to pass to the iteration function. In this case, a pointer to a struct _st_flush_s is passed.
Returns:
Zero to continue flushing, non-zero otherwise.

Definition at line 66 of file st_flush.c.

References _smat_free(), _st_remove(), he_value, _st_flush_s::sf_extra, _st_flush_s::sf_flush, _st_flush_s::sf_table, ST_REM_FIRST, and ST_REM_SECOND.

Referenced by st_flush().

Here is the call graph for this function:

static unsigned long _st_iter_iter hash_table_t table,
hash_entry_t ent,
void *  extra
[static]
 

For internal use only.

This function is a hash_iter_t iteration callback that is used as a shim between the st_iter() function and the ht_iter() function, which it uses internally.

Parameters:
[in] table The hash table being iterated over.
[in] ent The specific hash table entry being processed.
[in] extra Extra caller-specific data to pass to the iteration function. In this case, a pointer to a struct _st_iter_s is passed.
Returns:
Zero to continue iteration, non-zero otherwise.

Definition at line 66 of file st_iter.c.

References he_value, _st_iter_s::si_extra, _st_iter_s::si_iter, and _st_iter_s::si_table.

Referenced by st_iter().

unsigned long _st_remove smat_table_t table,
smat_entry_t entry,
unsigned int  remflag
 

For internal use only.

This function implements the actual logic that removes a sparse matrix entry from a sparse matrix table. Sparse matrix entries must be removed from three different locations before they can be passed to free(), and there are several places in the library where they are removed from one location and must subsequently be removed from the others. This routine allows the caller to specify exactly what must be removed through the use of the remflag argument.

Parameters:
[in] table A pointer to a smat_table_t.
[in] entry A pointer to a smat_entry_t to be removed from the table.
[in] remflag A bitwise mask of ST_REM_FIRST, ST_REM_SECOND, ST_REM_HASH, and ST_REM_FREE indicating which portions of the removal logic must be executed.
Returns:
The function returns zero if the requested operations were completed successfully. A non-zero return value indicates a catastrophic failure condition, but is unlikely to occur.

Definition at line 35 of file st_remove.c.

References _smat_free(), ht_remove(), ll_remove(), _smat_entry_s::se_hash, _smat_entry_s::se_link, SMAT_LOC_FIRST, SMAT_LOC_SECOND, ST_REM_FIRST, ST_REM_FREE, ST_REM_HASH, ST_REM_SECOND, and _smat_table_s::st_table.

Referenced by _sh_flush_iter(), _st_flush_iter(), and st_remove().

Here is the call graph for this function:

unsigned long sh_find smat_head_t head,
smat_entry_t **  elem_p,
smat_comp_t  comp_func,
smat_entry_t start,
db_key_t key
 

This function iterates through the given row or column of a sparse matrix looking for an element that matches the given key.

Parameters:
[in] head A pointer to a smat_head_t.
[out] elem_p A pointer to a pointer to a smat_entry_t. NULL is an invalid value.
[in] comp_func A pointer to a comparison function used to compare the key to a particular entry. See the documentation for smat_comp_t for more information.
[in] start A pointer to a smat_entry_t describing where in the row or column to start. If NULL is passed, the beginning of the row or column will be assumed.
[in] key A key to search for.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_WRONGTABLE start is not in this row or column.
DB_ERR_NOENTRY No matching entry was found.

Definition at line 72 of file sh_find.c.

References _sh_find_comp(), dk_key, le_object, ll_find(), _smat_entry_s::se_link, se_verify, _sh_find_s::sf_comp, _sh_find_s::sf_key, _smat_head_s::sh_elem, _smat_head_s::sh_head, and sh_verify.

Here is the call graph for this function:

unsigned long sh_flush smat_head_t head,
smat_iter_t  flush_func,
void *  extra
 

This function flushes a sparse matrix row or column--that is, it removes each element from that row or column. If a flush_func is specified, it will be called on the entry after it has been removed from the row or column, and may safely call free().

Parameters:
[in] head A pointer to a smat_head_t.
[in] flush_func A pointer to a callback function used to perform user-specifed actions on an entry after removing it from the row or column. May be NULL. See the documentation for smat_iter_t for more information.
[in] extra A void pointer that will be passed to flush_func.
Return values:
DB_ERR_BADARGS An argument was invalid.

Definition at line 90 of file sh_flush.c.

References _sh_flush_iter(), ll_flush(), _sh_flush_s::sf_elem, _sh_flush_s::sf_extra, _sh_flush_s::sf_flush, _sh_flush_s::sf_table, _smat_head_s::sh_elem, _smat_head_s::sh_head, _smat_head_s::sh_table, and sh_verify.

Here is the call graph for this function:

unsigned long sh_init smat_head_t head,
smat_loc_t  elem,
void *  object
 

This function dynamically initializes a sparse matrix row or column linked list head. The elem argument specifies whether the object is to be associated with a SMAT_LOC_FIRST list or a SMAT_LOC_SECOND list.

Parameters:
[in] head A pointer to a smat_head_t to be initialized.
[in] elem Either SMAT_LOC_FIRST or SMAT_LOC_SECOND.
[in] object A pointer to the object containing the sparse matrix row or column head.
Return values:
DB_ERR_BADARGS An invalid argument was given.

Definition at line 34 of file sh_init.c.

References ll_init(), _smat_head_s::sh_elem, _smat_head_s::sh_head, _smat_head_s::sh_magic, _smat_head_s::sh_table, SMAT_HEAD_MAGIC, SMAT_LOC_FIRST, and SMAT_LOC_SECOND.

Here is the call graph for this function:

unsigned long sh_iter smat_head_t head,
smat_entry_t start,
smat_iter_t  iter_func,
void *  extra,
unsigned long  flags
 

This function iterates over a row or column of a sparse matrix, executing the given iter_func for each entry.

Parameters:
[in] head A pointer to a smat_head_t.
[in] start A pointer to a smat_entry_t describing where in the row or column to start. If NULL is passed, the beginning of the row or column will be assumed.
[in] iter_func A pointer to a callback function used to perform user-specified actions on an entry in a row or column of a sparse matrix. NULL is an invalid value. See the documentation for smat_iter_t for more information.
[in] extra A void pointer that will be passed to iter_func.
[in] flags If DB_FLAG_REVERSE is given, iteration will be done from the end of the list backwards towards the head.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_WRONGTABLE start is not in this row or column.

Definition at line 77 of file sh_iter.c.

References _sh_iter_iter(), ll_iter(), _smat_entry_s::se_link, se_verify, _smat_head_s::sh_elem, _smat_head_s::sh_head, _smat_head_s::sh_table, sh_verify, _sh_iter_s::si_extra, _sh_iter_s::si_iter, and _sh_iter_s::si_table.

Here is the call graph for this function:

unsigned long sh_move smat_head_t head,
smat_entry_t elem,
link_loc_t  loc,
smat_entry_t elem2
 

This function allows the specified entry to be shifted within the linked list describing the row or column. It is very similar to the ll_move() function.

Parameters:
[in] head A pointer to a smat_head_t.
[in] elem A pointer to the smat_entry_t describing the entry to be moved.
[in] loc A link_loc_t indicating where the entry should be moved to.
[in] elem2 A pointer to a smat_entry_t describing another entry in the list if loc is LINK_LOC_BEFORE or LINK_LOC_AFTER.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_BUSY elem and elem2 are the same entry.
DB_ERR_WRONGTABLE elem or elem2 are in a different row or column.
DB_ERR_UNUSED elem or elem2 are not in any row or column.

Definition at line 35 of file sh_move.c.

References ll_move(), _smat_entry_s::se_link, se_verify, _smat_head_s::sh_elem, _smat_head_s::sh_head, and sh_verify.

Here is the call graph for this function:

unsigned long smat_cleanup void   ) 
 

This function frees all smat_entry_t objects on the internal free list. It is always successful and returns 0.

Returns:
This function always returns 0.

Definition at line 90 of file smat_freelist.c.

References le_object, ll_first, and ll_remove().

Here is the call graph for this function:

unsigned long smat_freemem void   ) 
 

This function returns the amount of memory being used by the internal free list of smat_entry_t objects.

Returns:
A number indicating the size, in bytes, of the memory allocated for smat_entry_t objects on the free list.

Definition at line 106 of file smat_freelist.c.

References ll_count.

unsigned long st_add smat_table_t table,
smat_entry_t **  entry_p,
smat_head_t head1,
link_loc_t  loc1,
smat_entry_t ent1,
smat_head_t head2,
link_loc_t  loc2,
smat_entry_t ent2
 

This function adds an entry to a sparse matrix. The entry is referenced in three different places, thus the complex set of arguments. This function will allocate a smat_entry_t and return it through the entry_p result parameter.

Parameters:
[in] table A pointer to a smat_table_t.
[out] entry_p A pointer to a pointer to a smat_entry_t. If NULL is passed, the addition will be performed and an appropriate error code returned.
[in] head1 A pointer to a smat_head_t representing a SMAT_LOC_FIRST sparse matrix list.
[in] loc1 A link_loc_t indicating where the entry should be added for head1.
[in] ent1 A pointer to a smat_entry_t describing another element in the list represented by head1 if loc1 is LINK_LOC_BEFORE or LINK_LOC_AFTER.
[in] head2 A pointer to a smat_head_t representing a SMAT_LOC_SECOND sparse matrix list.
[in] loc2 A link_loc_t indicating where the entry should be added for head2.
[in] ent2 A pointer to a smat_entry_t describing another element in the list represented by head2 if loc2 is LINK_LOC_BEFORE or LINK_LOC_AFTER.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_BUSY One of the arguments is already in the table.
DB_ERR_FROZEN The table is currently frozen.
DB_ERR_NOTABLE The bucket table has not been allocated and automatic growth is not enabled.
DB_ERR_WRONGTABLE One of the arguments was not in the proper table or list.
DB_ERR_UNUSED One of the ent arguments is not presently in a list.
DB_ERR_UNRECOVERABLE An unrecoverable error occurred while resizing the table.
ENOMEM No memory could be allocated for the smat_entry_t structure.

Definition at line 36 of file st_add.c.

References _smat_alloc(), _smat_free(), dk_key, dk_len, ht_add(), ht_remove(), LINK_LOC_AFTER, LINK_LOC_BEFORE, ll_add(), ll_remove(), _smat_entry_s::se_hash, _smat_entry_s::se_link, _smat_entry_s::se_object, _smat_entry_s::se_table, se_verify, _smat_head_s::sh_elem, _smat_head_s::sh_head, sh_object, _smat_head_s::sh_table, sh_verify, SMAT_LOC_FIRST, SMAT_LOC_SECOND, ST_REM_FIRST, ST_REM_FREE, ST_REM_HASH, _smat_table_s::st_table, and st_verify.

Here is the call graph for this function:

unsigned long st_find smat_table_t table,
smat_entry_t **  entry_p,
smat_head_t head1,
smat_head_t head2
 

This function looks up the entry matching the given head1 and head2.

Parameters:
[in] table A pointer to a smat_table_t.
[out] entry_p A pointer to a pointer to a smat_entry_t. If NULL is passed, the lookup will be performed and an appropriate error code returned.
[in] head1 A pointer to a smat_head_t initialized to SMAT_LOC_FIRST.
[in] head2 A pointer to a smat_head_t initialized to SMAT_LOC_SECOND.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_WRONGTABLE One or both of head1 or head2 are not referenced in this table.
DB_ERR_NOENTRY No matching entry was found.

Definition at line 36 of file st_find.c.

References dk_key, dk_len, he_value, ht_find(), _link_head_s::lh_count, _smat_head_s::sh_elem, _smat_head_s::sh_head, sh_object, _smat_head_s::sh_table, sh_verify, SMAT_LOC_FIRST, SMAT_LOC_SECOND, _smat_table_s::st_table, and st_verify.

Here is the call graph for this function:

unsigned long st_flush smat_table_t table,
smat_iter_t  flush_func,
void *  extra
 

This function flushes a sparse matrix--that is, it removes each entry from the matrix. If a flush_func is specified, it will be called on the entry after it has been removed from the table, and may safely call free().

Parameters:
[in] table A pointer to a smat_table_t.
[in] flush_func A pointer to a callback function used to perform user-specified actions on an entry after removing it from the table. May be NULL. See the documentation for smat_iter_t for more information.
[in] extra A void pointer that will be passed to iter_func.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_FROZEN The sparse matrix is frozen.

Definition at line 86 of file st_flush.c.

References _st_flush_iter(), ht_flush(), _st_flush_s::sf_extra, _st_flush_s::sf_flush, _st_flush_s::sf_table, _smat_table_s::st_table, and st_verify.

Here is the call graph for this function:

unsigned long st_free smat_table_t table  ) 
 

This function releases the memory used by the bucket table of the empty hash table associated with a sparse matrix.

Parameters:
[in] table A pointer to a smat_table_t.
Return values:
DB_ERR_BADARGS An invalid argument was given.
DB_ERR_FROZEN The table is frozen.
DB_ERR_NOTEMPTY The table is not empty.

Definition at line 34 of file st_free.c.

References ht_free(), _smat_table_s::st_table, and st_verify.

Here is the call graph for this function:

unsigned long st_init smat_table_t table,
unsigned long  flags,
smat_resize_t  resize,
void *  extra,
unsigned long  init_mod
 

This function initializes a sparse matrix table.

Parameters:
[in] table A pointer to a smat_table_t to be initialized.
[in] flags A bit-wise OR of HASH_FLAG_AUTOGROW and HASH_FLAG_AUTOSHRINK. If neither behavior is desired, use 0.
[in] resize A hash_resize_t function pointer for determining whether resizing is permitted and/or for notification of the resize.
[in] extra Extra pointer data that should be associated with the sparse matrix table.
[in] init_mod An initial modulus for the table. This will presumably be extracted by st_modulus() in a previous invocation of the application. A 0 value is valid.
Return values:
DB_ERR_BADARGS An invalid argument was given.
ENOMEM Unable to allocate memory.

Definition at line 34 of file st_init.c.

References _smat_resize(), hash_comp(), hash_fnv1a(), ht_init(), SMAT_TABLE_MAGIC, _smat_table_s::st_extra, _smat_table_s::st_magic, _smat_table_s::st_resize, and _smat_table_s::st_table.

Here is the call graph for this function:

unsigned long st_iter smat_table_t table,
smat_iter_t  iter_func,
void *  extra
 

This function iterates over every entry in a sparse matrix (in an unspecified order), executing the given iter_func on each entry.

Parameters:
[in] table A pointer to a smat_table_t.
[in] iter_func A pointer to a callback function used to perform user-specified actions on an entry in a sparse matrix. NULL is an invalid value. See the documentation for smat_iter_t for more information.
[in] extra A void pointer that will be passed to iter_func.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_FROZEN The sparse matrix is frozen.

Definition at line 77 of file st_iter.c.

References _st_iter_iter(), ht_iter(), _st_iter_s::si_extra, _st_iter_s::si_iter, _st_iter_s::si_table, _smat_table_s::st_table, and st_verify.

Here is the call graph for this function:

unsigned long st_remove smat_table_t table,
smat_entry_t entry
 

This function removes the given entry from the specified sparse matrix.

Parameters:
[in] table A pointer to a smat_table_t.
[in] entry A pointer to a smat_entry_t to be removed from the table.
Return values:
DB_ERR_BADARGS An invalid argument was given.
DB_ERR_WRONGTABLE Entry is not in this sparse matrix.
DB_ERR_UNRECOVERABLE An unrecoverable error occurred while removing the entry from the table.

Definition at line 63 of file st_remove.c.

References _st_remove(), _smat_entry_s::se_table, se_verify, ST_REM_FIRST, ST_REM_FREE, ST_REM_HASH, ST_REM_SECOND, and st_verify.

Here is the call graph for this function:

unsigned long st_resize smat_table_t table,
unsigned long  new_size
 

This function resizes the hash table associated with a sparse matrix based on the new_size parameter. See the documentation for ht_resize() for more information.

Parameters:
[in] table A pointer to a smat_table_t.
[in] new_size A new size value for the table.
Return values:
DB_ERR_BADARGS An argument was invalid.
DB_ERR_FROZEN The table is currently frozen.
DB_ERR_UNRECOVERABLE A catastrophic error was encountered. The table is now unusable.
ENOMEM No memory could be allocated for the new bucket table.

Definition at line 34 of file st_resize.c.

References ht_resize(), _smat_table_s::st_table, and st_verify.

Here is the call graph for this function:


Variable Documentation

link_head_t _smat_freelist [static]
 

For internal use only.

This variable is the head of a linked list of free smat_entry_t structures.

Definition at line 45 of file smat_freelist.c.


Generated on Sat Jul 15 14:11:04 2006 for DatabasePrimitivesLibrary by  doxygen 1.4.4