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.
|
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.
|
