libs/dbprim/dbprim.h.top

   1 /* -*- c -*-
   2 ** Copyright (C) 2002 by Kevin L. Mitchell <klmitch@mit.edu>
   3 **
   4 ** This library is free software; you can redistribute it and/or
   5 ** modify it under the terms of the GNU Library General Public
   6 ** License as published by the Free Software Foundation; either
   7 ** version 2 of the License, or (at your option) any later version.
   8 **
   9 ** This library is distributed in the hope that it will be useful,
  10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 ** Library General Public License for more details.
  13 **
  14 ** You should have received a copy of the GNU Library General Public
  15 ** License along with this library; if not, write to the Free
  16 ** Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  17 ** MA 02111-1307, USA
  18 **
  19 ** @(#)$Id: dbprim.h.top,v 1.1 2003-03-07 02:36:10 klmitch Exp $
  20 */
  21 #ifndef __include_dbprim_h__
  22 #define __include_dbprim_h__
  23 /** \mainpage Database Primitives Library
  24  *
  25  * This library contains a set of database primitives.  The primitives
  26  * defined by this library include a powerful linked list abstraction,
  27  * a hash table with optional automatic resizing, and a powerful and
  28  * efficient sparse matrix implementation.  All of the necessary
  29  * declarations for using this library are found in the header file
  30  * dbprim.h.  For more information about the components of this
  31  * library, see the module list.
  32  */
  33
  34 /** \defgroup dbprim_key Database keys
  35  *
  36  * This module contains interfaces common to all database
  37  * modules--mainly the macros concerned with manipulating database
  38  * keys and the definition of the key structure.
  39  *
  40  * The key may be any arbitrary pointer, including a pointer to a
  41  * string.  Everything that handles a key either copies the contents
  42  * of the #db_key_t structure or passes it to a user-defined
  43  * function.  If required, as in the case of a string, a length may
  44  * also be represented in the key structure.
  45  */
  46
  47 /** \defgroup dbprim_link Linked lists
  48  * \brief Operations for linked lists.
  49  *
  50  * Linked lists are a very basic data structure used in building
  51  * databases.  This library provides a simple yet powerful
  52  * implementation of generic linked lists, based on two
  53  * caller-allocated structures.  The #link_head_t structure describes
  54  * the head of a linked list and contains information regarding the
  55  * number of elements in the linked list as well as pointers
  56  * referencing the first and last elements in the list.  The
  57  * #link_elem_t structure describes a specific element in the linked
  58  * list and contains pointers referencing the next and previous
  59  * elements in the list, as well as a pointer to the object, a pointer
  60  * to the head of the linked list, and a set of user-specified flags.
  61  *
  62  * Elements may be added at any arbitrary location in the linked list
  63  * with ll_add(); moved to any other arbitrary location in the linked
  64  * list with ll_move(), or removed from the list with ll_remove().  In
  65  * addition, the user may search the list using a user-defined
  66  * comparison function with ll_find(); iterate over every element in
  67  * the list with ll_iter(); or remove all items from the list with
  68  * ll_flush(), optionally executing a user-specified clean-up
  69  * function.
  70  */
  71
  72 /** \defgroup dbprim_hash Hash tables
  73  * \brief Operations for hash tables.
  74  *
  75  * Hash tables are a basic data structure used in building databases.
  76  * Hash tables provide a means of storing data such that an arbitrary
  77  * entry may be looked up efficiently.  This library implements a hash
  78  * table that may optionally grow and shrink to provide maximum
  79  * efficiency.  The implementation is with two kinds of
  80  * caller-allocated structures--a #hash_table_t structure that
  81  * describes the table and a #hash_entry_t structure for each entry in
  82  * the table.  The library allocates a bucket array which must be
  83  * released with the ht_free() function when the hash table has been
  84  * emptied.  Additionally, the hash table may be manually resized with
  85  * the ht_resize() function.
  86  *
  87  * Entries may be added to and removed from the table using the
  88  * ht_add() and ht_remove() functions.  Additionally, the key on a
  89  * given entry may be changed using the ht_move() function.  Of
  90  * course, any given entry may be looked up using the ht_find()
  91  * function, and ht_iter() will execute a user-defined function for
  92  * each entry in the hash table (in an unspecified order).  The
  93  * ht_flush() function will remove all entries from the hash table,
  94  * optionally executing a user-specified clean-up function.
  95  */
  96
  97 /** \defgroup dbprim_smat Sparse matrices
  98  * \brief Operations for sparse matrices.
  99  *
 100  * Sparse matrices are advanced data structures used to represent
 101  * associations.  For instance, a manager may have several employees,
 102  * but several of those employees may report to more than one
 103  * manager.  (Yes, this is a contrived example, so sue me.)  The
 104  * simplest way to represent such assocations is with a matrix, or a
 105  * two-dimensional array.  However, such an implementation cannot
 106  * easily be extended dynamically--imagine if a manager retires and
 107  * two more are hired, for instance.  It would also use an enormous
 108  * amount of memory, as most employees would only report to one or two
 109  * managers.
 110  *
 111  * A sparse matrix solves this problem by only allocating memory for
 112  * the cells in the full matrix which are actually used.  That is, no
 113  * memory is allocated to represent Alice reporting to Bob unless
 114  * Alice actually does report to Bob.  This is a simple concept, but
 115  * fairly difficult to implement efficiently--how do you tell if Alice
 116  * reports to Bob?  The solution utilized by this library is to
 117  * combine the strengths of linked lists and hash tables.  Each cell
 118  * is in two linked lists, rooted at the rows and columns of the
 119  * matrix, but a hash table is used when attempting to look up a given
 120  * cell.  If the cell is allocated, then there will be an entry in the
 121  * hash table, and finding the given cell is as fast as a hash table
 122  * look-up.
 123  *
 124  * Because sparse matrices are so complicated, there are three
 125  * structures and a variety of operations used.  Two of the
 126  * structures, #smat_table_t and #smat_head_t, are caller-allocated.
 127  * However, the third structure, #smat_entry_t, must be allocated by
 128  * the library.  To avoid too much overhead from malloc(), a free list
 129  * is used.  The free list may be managed with the smat_cleanup() and
 130  * smat_freemem() calls.
 131  *
 132  * The #smat_table_t contains the hash table.  Only one of these need
 133  * be allocated per type of association--for instance, in the above
 134  * example, only one #smat_table_t needs to be allocated to represent
 135  * the manager-employee relationship.
 136  *
 137  * The #smat_head_t contains the linked list.  There are actually two
 138  * kinds of these structures--one is #SMAT_LOC_FIRST, which could be
 139  * regarded as a ``row,'' and the other is #SMAT_LOC_SECOND, which
 140  * could be regarded as a ``column.''  Which one is used for which
 141  * type of data is irrelevant, as long as consistency is maintained.
 142  * For the above example, a #smat_head_t for a manager may be
 143  * #SMAT_LOC_FIRST, and one for an employee must then be
 144  * #SMAT_LOC_SECOND.  (These values are set when initializing the
 145  * #smat_head_t structure.)
 146  *
 147  * An association may be created with the st_add() function, which
 148  * allows an arbitrary ordering in the associated linked lists by the
 149  * same mechanism as for the linked list component of the library.  An
 150  * association may be removed with st_remove(), or looked up with
 151  * st_find().  If iteration over all associations is desired, use the
 152  * st_iter() function.  Removing all associations from a table may be
 153  * performed with st_flush(), which optionally calls a user-defined
 154  * clean-up function.  The associated hash table may be resized with
 155  * st_resize(), and the bucket table may be released with st_free().
 156  *
 157  * An association may also be reordered within the linked lists using
 158  * the sh_move() function.  If a particular entry is desired, use the
 159  * sh_find() function with a user-defined comparison function to
 160  * locate it.  Iteration may be performed with the sh_iter() function,
 161  * and all entries in a given linked list may be removed with the
 162  * sh_flush() function, which again may optionally call a user-defined
 163  * clean-up function.
 164  */
 165
 166 /** \ingroup dbprim_key
 167  * \brief Database key.
 168  *
 169  * This structure is a generic key containing a void * pointer and a
 170  * length parameter.  It should be accessed with * dk_key() and
 171  * dk_len().
 172  */
 173 typedef struct _db_key_s     db_key_t;
 174
 175 /** \ingroup dbprim_link
 176  * \brief Linked list head.
 177  *
 178  * This structure is the head of all linked lists maintained by this
 179  * library.
 180  */
 181 typedef struct _link_head_s  link_head_t;
 182
 183 /** \ingroup dbprim_link
 184  * \brief Linked list element.
 185  *
 186  * This structure represents a single element of a linked list.
 187  */
 188 typedef struct _link_elem_s  link_elem_t;
 189
 190 /** \ingroup dbprim_hash
 191  * \brief Hash table.
 192  *
 193  * This structure is the basis of all hash tables maintained by this
 194  * library.
 195  */
 196 typedef struct _hash_table_s hash_table_t;
 197
 198 /** \ingroup dbprim_hash
 199  * \brief Hash table entry.
 200  *
 201  * This structure represents a single entry of a hash table.
 202  */
 203 typedef struct _hash_entry_s hash_entry_t;
 204
 205 /** \ingroup dbprim_smat
 206  * \brief Sparse matrix table.
 207  *
 208  * This structure is the basis of all sparse matrices maintained by
 209  * this library.
 210  */
 211 typedef struct _smat_table_s smat_table_t;
 212
 213 /** \ingroup dbprim_smat
 214  * \brief Sparse matrix list head.
 215  *
 216  * This structure is the head of a linked list of sparse matrix
 217  * entries.
 218  */
 219 typedef struct _smat_head_s  smat_head_t;
 220
 221 /** \ingroup dbprim_smat
 222  * \brief Sparse matrix entry.
 223  *
 224  * This structure is allocated by the library and represents a single
 225  * element in a sparse matrix.
 226  */
 227 typedef struct _smat_entry_s smat_entry_t;
 228
 229 /** \ingroup dbprim_link
 230  * \brief Linked list iteration callback.
 231  *
 232  * This function pointer references a callback used by ll_iter() and
 233  * ll_flush().  It should return 0 for success.  A non-zero return
 234  * value will terminate the operation and will become the return value
 235  * of the ll_iter() or ll_flush() call.
 236  */
 237 typedef unsigned long (*link_iter_t)(link_head_t *, link_elem_t *, void *);
 238
 239 /** \ingroup dbprim_link
 240  * \brief Linked list comparison callback.
 241  *
 242  * This function pointer references a callback used by ll_find().  It
 243  * should return 0 if the entry passed as the second argument matches
 244  * the key passed as the first argument.
 245  */
 246 typedef unsigned long (*link_comp_t)(db_key_t *, void *);
 247
 248 /** \ingroup dbprim_hash
 249  * \brief Hash table iteration callback.
 250  *
 251  * This function pointer references a callback used by ht_iter() and
 252  * ht_flush().  It should return 0 for success.  A non-zero return
 253  * value will terminate the operation and will become the return value
 254  * of the ht_iter() or ht_flush() call.
 255  */
 256 typedef unsigned long (*hash_iter_t)(hash_table_t *, hash_entry_t *, void *);
 257
 258 /** \ingroup dbprim_hash
 259  * \brief Hash function callback.
 260  *
 261  * This function is associated with a hash table, and is responsible
 262  * for generating a hash value.  The full 32-bit range of an
 263  * <CODE>unsigned long</CODE> should be used--do *not* reduce the hash
 264  * value by the modulus of the hash table.
 265  */
 266 typedef unsigned long (*hash_func_t)(hash_table_t *, db_key_t *);
 267
 268 /** \ingroup dbprim_hash
 269  * \brief Hash table comparison callback.
 270  *
 271  * This function pointer references a callback used to compare entries
 272  * in a hash table.  It should return 0 for identical entries and
 273  * non-zero otherwise.  No assumptions should be made about the order
 274  * in which the two keys are passed to this function.
 275  */
 276 typedef unsigned long (*hash_comp_t)(hash_table_t *, db_key_t *, db_key_t *);
 277
 278 /** \ingroup dbprim_hash
 279  * \brief Hash table resize callback.
 280  *
 281  * This function pointer references a callback that will be called
 282  * with both the old and new hash table sizes whenever a hash table is
 283  * resized.  It should return non-zero only when the resize should be
 284  * inhibited.
 285  */
 286 typedef unsigned long (*hash_resize_t)(hash_table_t *, unsigned long);
 287
 288 /** \ingroup dbprim_smat
 289  * \brief Sparse matrix table resize callback.
 290  *
 291  * This function pointer references a callback that will be called
 292  * with both the old and new sparse matrix table sizes whenever a
 293  * sparse matrix's hash table table is resized.  It should return
 294  * non-zero only when the resize should be inhibited.
 295  */
 296 typedef unsigned long (*smat_resize_t)(smat_table_t *, unsigned long);
 297
 298 /** \ingroup dbprim_smat
 299  * \brief Sparse matrix iteration callback.
 300  *
 301  * This function pointer references a callback used by st_iter(),
 302  * st_flush(), sh_iter(), and sh_flush().  It should return 0 for
 303  * success.  A non-zero return value will terminate the operation and
 304  * will become the return value of the call.
 305  */
 306 typedef unsigned long (*smat_iter_t)(smat_table_t *, smat_entry_t *, void *);
 307
 308 /** \ingroup dbprim_smat
 309  * \brief Sparse matrix comparison callback.
 310  *
 311  * This function pointer references a callback used by sh_find().  It
 312  * should return 0 if the sparse matrix entry represented by the
 313  * second argument matches the key passed as the first argument.
 314  */
 315 typedef unsigned long (*smat_comp_t)(db_key_t *, smat_entry_t *);
 316
 317 /** \ingroup dbprim_link
 318  * \brief Linked list location.
 319  *
 320  * This enumeration is used to specify where an element in a linked
 321  * list should be placed.  It should be referenced by the typedef
 322  * #link_loc_t.
 323  */
 324 enum _link_loc_e {
 325   LINK_LOC_HEAD,        /**< Element should be inserted at head of list. */
 326   LINK_LOC_TAIL,        /**< Element should be inserted at tail of list. */
 327   LINK_LOC_BEFORE,      /**< Element should be inserted before specified
 328                              element. */
 329   LINK_LOC_AFTER        /**< Element should be inserted after specified
 330                              element. */
 331 };
 332
 333 /** \ingroup dbprim_link
 334  * \brief Linked list location.
 335  *
 336  * See the documentation for the enumeration #_link_loc_e.
 337  */
 338 typedef enum _link_loc_e link_loc_t;
 339
 340 /** \ingroup dbprim_smat
 341  * \brief Sparse matrix location.
 342  *
 343  * This enumeration is used to specify whether an element is a row or
 344  * column element.  It should be referenced by the typedef
 345  * #smat_loc_t.
 346  */
 347 enum _smat_loc_e {
 348   SMAT_LOC_FIRST,       /**< First entry (``row''). */
 349   SMAT_LOC_SECOND       /**< Second entry (``column''). */
 350 };
 351
 352 /** \ingroup dbprim_smat
 353  * \brief Sparse matrix location.
 354  *
 355  * See the documentation for the enumeration #_smat_loc_e.
 356  */
 357 typedef enum _smat_loc_e smat_loc_t;
 358
 359 struct _db_key_s {
 360   void *dk_key;         /* Pointer to the key. */
 361   int   dk_len;         /* Length of the key, if that has any meaning. */
 362 };
 363
 364 /** \ingroup dbprim_key
 365  * \brief Database key static initializer.
 366  *
 367  * This macro allows a #db_key_t to be initialized statically.
 368  *
 369  * \param key   A pointer to the key.
 370  * \param size  Size of the key.
 371  */
 372 #define DB_KEY_INIT(key, size) { (key), (size) }
 373
 374 /** \ingroup dbprim_key
 375  * \brief Database key accessor macro.
 376  *
 377  * This macro allows access to the key field of a #db_key_t.  It may
 378  * be used as an lvalue in order to assign a key to a #db_key_t.
 379  *
 380  * \param key   A pointer to a #db_key_t.
 381  * \return      A pointer to a key (<CODE>void *</CODE>).
 382  */
 383 #define dk_key(key)     ((key)->dk_key)
 384
 385 /** \ingroup dbprim_key
 386  * \brief Database key length accessor macro.
 387  *
 388  * This macro allows access to the key length field of a #db_key_t.
 389  * It may be used as an lvalue in order to assign a length to a
 390  * #db_key_t.
 391  *
 392  * \param key   A pointer to a #db_key_t.
 393  * \return      An \c int describing the length of the key.
 394  */
 395 #define dk_len(key)     ((key)->dk_len)
 396
 397 struct _link_head_s {
 398   unsigned long lh_magic;       /* Magic number. */
 399   unsigned long lh_count;       /* Number of entries in the linked list. */
 400   link_elem_t  *lh_first;       /* First element in the list. */
 401   link_elem_t  *lh_last;        /* Last element in the list. */
 402   void         *lh_extra;       /* Extra data associated with list. */
 403 };
 404
 405 #define LINK_HEAD_MAGIC 0x4c6155d7
 406
 407 /** \ingroup dbprim_link
 408  * \brief Linked list head static initializer.
 409  *
 410  * This macro statically initializes a #link_head_t.
 411  *
 412  * \param extra Extra pointer data that should be associated with the
 413  *              list head.
 414  */
 415 #define LINK_HEAD_INIT(extra)   { LINK_HEAD_MAGIC, 0, 0, 0, (extra) }
 416
 417 /** \ingroup dbprim_link
 418  * \brief Linked list head verification macro.
 419  *
 420  * This macro verifies that a given pointer actually does point to a
 421  * linked list head.
 422  *
 423  * \param list  A pointer to a #link_head_t.
 424  *
 425  * \return      Boolean true if \p list is a valid linked list head or
 426  *              false otherwise.
 427  */
 428 #define ll_verify(list)         ((list) && \
 429                                  (list)->lh_magic == LINK_HEAD_MAGIC)
 430
 431 /** \ingroup dbprim_link
 432  * \brief Linked list count.
 433  *
 434  * This macro retrieves the number of elements in a linked list.
 435  *
 436  * \param list  A pointer to a #link_head_t.
 437  *
 438  * \return      An <CODE>unsigned long</CODE> containing a count of
 439  *              the number of elements in the linked list.
 440  */
 441 #define ll_count(list)  ((list)->lh_count)
 442
 443 /** \ingroup dbprim_link
 444  * \brief First element in linked list.
 445  *
 446  * This macro retrieves the first element in a linked list.
 447  *
 448  * \param list  A pointer to a #link_head_t.
 449  *
 450  * \return      A pointer to a #link_elem_t.
 451  */
 452 #define ll_first(list)  ((list)->lh_first)
 453
 454 /** \ingroup dbprim_link
 455  * \brief Last element in a linked list.
 456  *
 457  * This macro retrieves the last element in a linked list.
 458  *
 459  * \param list  A pointer to a #link_head_t.
 460  *
 461  * \return      A pointer to a #link_elem_t.
 462  */
 463 #define ll_last(list)   ((list)->lh_last)
 464
 465 /** \ingroup dbprim_link
 466  * \brief Extra pointer data in a linked list.
 467  *
 468  * This macro retrieves the extra pointer data associated with a
 469  * particular linked list.
 470  *
 471  * \param list  A pointer to a #link_head_t.
 472  *
 473  * \return      A pointer to \c void.
 474  */
 475 #define ll_extra(list)  ((list)->lh_extra)
 476
 477 unsigned long ll_init(link_head_t *list, void *extra);
 478 unsigned long ll_add(link_head_t *list, link_elem_t *new, link_loc_t loc,
 479                      link_elem_t *elem);
 480 unsigned long ll_move(link_head_t *list, link_elem_t *elem, link_loc_t loc,
 481                       link_elem_t *elem2);
 482 unsigned long ll_remove(link_head_t *list, link_elem_t *elem);
 483 unsigned long ll_find(link_head_t *list, link_elem_t **elem_p,
 484                       link_comp_t comp_func, link_elem_t *start,
 485                       db_key_t *key);
 486 unsigned long ll_iter(link_head_t *list, link_iter_t iter_func, void *extra);
 487 unsigned long ll_flush(link_head_t *list, link_iter_t flush_func, void *extra);
 488
 489 struct _link_elem_s {
 490   unsigned long le_magic;       /* magic number */
 491   link_elem_t  *le_next;        /* next element in list */
 492   link_elem_t  *le_prev;        /* previous element in list */
 493   void         *le_object;      /* the object pointed to by this link */
 494   link_head_t  *le_head;        /* the head of the list */
 495   unsigned long le_flags;       /* flags associated with this element */
 496 };
 497
 498 #define LINK_ELEM_MAGIC 0x97cdf72a
 499
 500 /** \ingroup dbprim_link
 501  * \brief Linked list element static initializer.
 502  *
 503  * This macro statically initializes a #link_elem_t.
 504  *
 505  * \param obj   A pointer to \c void representing the object
 506  *              associated with the element.
 507  */
 508 #define LINK_ELEM_INIT(obj) { LINK_ELEM_MAGIC, 0, 0, (obj), 0, 0 }
 509
 510 /** \ingroup dbprim_link
 511  * \brief Linked list element verification macro.
 512  *
 513  * This macro verifies that a given pointer actually does point to a
 514  * linked list element.
 515  *
 516  * \param element
 517  *              A pointer to a #link_elem_t.
 518  *
 519  * \return      Boolean true if \p element is a valid linked list
 520  *              element or false otherwise.
 521  */
 522 #define le_verify(element)      ((element) && \
 523                                  (element)->le_magic == LINK_ELEM_MAGIC)
 524
 525 /** \ingroup dbprim_link
 526  * \brief Linked list element next pointer.
 527  *
 528  * This macro retrieves a pointer to the next element in the linked
 529  * list.
 530  *
 531  * \param elem  A pointer to a #link_elem_t.
 532  *
 533  * \return      A pointer to a #link_elem_t representing the next
 534  *              element in the linked list.
 535  */
 536 #define le_next(elem)   ((elem)->le_next)
 537
 538 /** \ingroup dbprim_link
 539  * \brief Linked list element previous pointer.
 540  *
 541  * This macro retrieves a pointer to the previous element in the
 542  * linked list.
 543  *
 544  * \param elem  A pointer to a #link_elem_t.
 545  *
 546  * \return      A pointer to a #link_elem_t representing the previous
 547  *              element in the linked list.
 548  */
 549 #define le_prev(elem)   ((elem)->le_prev)
 550
 551 /** \ingroup dbprim_link
 552  * \brief Linked list element object pointer.
 553  *
 554  * This macro retrieves a pointer to the object represented by the
 555  * element.  It may be used as an lvalue to change the object pointed
 556  * to.  Care should be taken when using this feature.
 557  *
 558  * \param elem  A pointer to a #link_elem_t.
 559  *
 560  * \return      A pointer to \c void representing the object
 561  *              associated with the linked list element.
 562  */
 563 #define le_object(elem) ((elem)->le_object)
 564
 565 /** \ingroup dbprim_link
 566  * \brief Linked list element head pointer.
 567  *
 568  * This macro retrieves a pointer to the head of the linked list that
 569  * the element is in.
 570  *
 571  * \param elem  A pointer to a #link_elem_t.
 572  *
 573  * \return      A pointer to a #link_head_t representing the head of
 574  *              the linked list the element is in.
 575  */
 576 #define le_head(elem)   ((elem)->le_head)
 577
 578 /** \ingroup dbprim_link
 579  * \brief Linked list element flags.
 580  *
 581  * This macro retrieves a set of user-defined flags associated with
 582  * the element.  It may be used as an lvalue to set those flags.
 583  *
 584  * \param elem  A pointer to a #link_elem_t.
 585  *
 586  * \return      An <CODE>unsigned long</CODE> containing the flags
 587  *              associated with the element.
 588  */
 589 #define le_flags(elem)  ((elem)->le_flags)
 590
 591 unsigned long le_init(link_elem_t *elem, void *object);
 592
 593 struct _hash_table_s {
 594   unsigned long ht_magic;       /* magic number */
 595   unsigned long ht_flags;       /* flags associated with the table */
 596   unsigned long ht_modulus;     /* size (modulus) of the hash table--prime */
 597   unsigned long ht_count;       /* number of elements in the table */
 598   unsigned long ht_rollover;    /* size at which the table grows */
 599   unsigned long ht_rollunder;   /* size at which the table shrinks */
 600   link_head_t  *ht_table;       /* actual table entries */
 601   hash_func_t   ht_func;        /* function for computing the hash */
 602   hash_comp_t   ht_comp;        /* function for comparing hash keys */
 603   hash_resize_t ht_resize;      /* function for resize notify/inhibit */
 604   void         *ht_extra;       /* extra data associated with the table */
 605 };
 606
 607 #define HASH_TABLE_MAGIC 0x2da7ffd9
 608
 609 /** \ingroup dbprim_hash
 610  * \brief Flag permitting a hash table to automatically grow.
 611  *
 612  * If passed in to #HASH_TABLE_INIT() or #ht_init(), allows the hash
 613  * table to grow automatically.
 614  */
 615 #define HASH_FLAG_AUTOGROW   0x00000001 /* let table automatically grow */
 616
 617 /** \ingroup dbprim_hash
 618  * \brief Flag permitting a hash table to automatically shrink.
 619  *
 620  * If passed in to #HASH_TABLE_INIT() or #ht_init(), allows the hash
 621  * table to shrink automatically.
 622  */
 623 #define HASH_FLAG_AUTOSHRINK 0x00000002 /* let table automatically shrink */
 624
 625 #define HASH_FLAG_MASK       (HASH_FLAG_AUTOGROW | HASH_FLAG_AUTOSHRINK)
 626
 627 #define HASH_FLAG_FREEZE     0x80000000 /* hash table frozen */
 628
 629 /** \ingroup dbprim_hash
 630  * \brief Hash table static initializer.
 631  *
 632  * This macro statically initializes a #hash_table_t.
 633  *
 634  * \param flags A bit-wise OR of #HASH_FLAG_AUTOGROW and
 635  *              #HASH_FLAG_AUTOSHRINK.  If neither behavior is
 636  *              desired, use 0.
 637  * \param func  A #hash_func_t function pointer for a hash function.
 638  * \param comp  A #hash_comp_t function pointer for a comparison
 639  *              function.
 640  * \param resize
 641  *              A #hash_resize_t function pointer for determining
 642  *              whether resizing is permitted and/or for notification
 643  *              of the resize.
 644  * \param extra Extra pointer data that should be associated with the
 645  *              hash table.
 646  */
 647 #define HASH_TABLE_INIT(flags, func, comp, resize, extra) \
 648         { HASH_TABLE_MAGIC, (flags) & HASH_FLAG_MASK, 0, 0, 0, 0, 0, \
 649           (func), (comp), (resize), (extra) }
 650
 651 /** \ingroup dbprim_hash
 652  * \brief Hash table verification macro.
 653  *
 654  * This macro verifies that a given pointer actually does point to a
 655  * hash table.
 656  *
 657  * \param table A pointer to a #hash_table_t.
 658  *
 659  * \return      Boolean true if \p table is a valid hash table or
 660  *              false otherwise.
 661  */
 662 #define ht_verify(table)        ((table) && \
 663                                  (table)->ht_magic == HASH_TABLE_MAGIC)
 664
 665 /** \ingroup dbprim_hash
 666  * \brief Hash table flags.
 667  *
 668  * This macro retrieves the flags associated with the hash table.
 669  * Only #HASH_FLAG_AUTOGROW and #HASH_FLAG_AUTOSHRINK have any meaning
 670  * to the application; all other bits are reserved for use in the
 671  * library.  This macro may be used as an lvalue, but care must be
 672  * taken to avoid modifying the library-specific bits.
 673  *
 674  * \param table A pointer to a #hash_table_t.
 675  *
 676  * \return      An <CODE>unsigned long</CODE> containing the flags for
 677  *              the hash table.
 678  */
 679 #define ht_flags(table)   ((table)->ht_flags)
 680
 681 /** \ingroup dbprim_hash
 682  * \brief Determine if a hash table is frozen.
 683  *
 684  * This macro returns a non-zero value if the table is currently
 685  * frozen.  The hash table may be frozen if there is an iteration in
 686  * progress.
 687  *
 688  * \param table A pointer to a #hash_table_t.
 689  *
 690  * \return      A zero value if the table is not frozen or a non-zero
 691  *              value if the table is frozen.
 692  */
 693 #define ht_frozen(table)  ((table)->ht_flags & HASH_FLAG_FROZEN)
 694
 695 /** \ingroup dbprim_hash
 696  * \brief Hash table modulus.
 697  *
 698  * This macro retrieves the number of buckets allocated for the hash
 699  * table.  An application may wish to save this value between
 700  * invocations to avoid the overhead of growing the table while
 701  * filling it with data.
 702  *
 703  * \param table A pointer to a #hash_table_t.
 704  *
 705  * \return      An <CODE>unsigned long</CODE> containing the number of
 706  *              buckets allocated for the hash table.
 707  */
 708 #define ht_modulus(table) ((table)->ht_modulus)
 709
 710 /** \ingroup dbprim_hash
 711  * \brief Hash table count.
 712  *
 713  * This macro retrieves the total number of items actually in the hash
 714  * table.
 715  *
 716  * \param table A pointer to a #hash_table_t.
 717  *
 718  * \return      An <CODE>unsigned long</CODE> containing a count of
 719  *              the number of items in the hash table.
 720  */
 721 #define ht_count(table)   ((table)->ht_count)
 722
 723 /** \ingroup dbprim_hash
 724  * \brief Hash table hash function.
 725  *
 726  * This macro retrieves the hash function pointer.
 727  *
 728  * \param table A pointer to a #hash_table_t.
 729  *
 730  * \return      A #hash_func_t.
 731  */
 732 #define ht_func(table)    ((table)->ht_func)
 733
 734 /** \ingroup dbprim_hash
 735  * \brief Hash table comparison function.
 736  *
 737  * This macro retrieves the comparison function pointer.
 738  *
 739  * \param table A pointer to a #hash_table_t.
 740  *
 741  * \return      A #hash_comp_t.
 742  */
 743 #define ht_comp(table)    ((table)->ht_comp)
 744
 745 /** \ingroup dbprim_hash
 746  * \brief Hash table resize callback function.
 747  *
 748  * This macro retrieves the resize callback function pointer.
 749  *
 750  * \param table A pointer to a #hash_table_t.
 751  *
 752  * \return      A #hash_resize_t.
 753  */
 754 #define ht_rsize(table)   ((table)->ht_resize)
 755
 756 /** \ingroup dbprim_hash
 757  * \brief Extra pointer data in a hash table.
 758  *
 759  * This macro retrieves the extra pointer data associated with a
 760  * particular hash table.
 761  *
 762  * \param table A pointer to a #hash_table_t.
 763  *
 764  * \return      A pointer to \c void.
 765  */
 766 #define ht_extra(table)   ((table)->ht_extra)
 767
 768 /** \ingroup dbprim_hash
 769  * \brief Hash table memory size.
 770  *
 771  * This macro returns the physical size of the bucket array allocated
 772  * by the library for this hash table.
 773  *
 774  * \param table A pointer to a #hash_table_t.
 775  *
 776  * \return      A \c size_t.
 777  */
 778 #define ht_size(table)    ((table)->ht_modulus * sizeof(link_head_t))
 779
 780 unsigned long ht_init(hash_table_t *table, unsigned long flags,
 781                       hash_func_t func, hash_comp_t comp,
 782                       hash_resize_t resize, void *extra,
 783                       unsigned long init_mod);
 784 unsigned long ht_add(hash_table_t *table, hash_entry_t *entry, db_key_t *key);
 785 unsigned long ht_move(hash_table_t *table, hash_entry_t *entry, db_key_t *key);
 786 unsigned long ht_remove(hash_table_t *table, hash_entry_t *entry);
 787 unsigned long ht_find(hash_table_t *table, hash_entry_t **entry_p,
 788                       db_key_t *key);
 789 unsigned long ht_iter(hash_table_t *table, hash_iter_t iter_func, void *extra);
 790 unsigned long ht_flush(hash_table_t *table, hash_iter_t flush_func,
 791                        void *extra);
 792 unsigned long ht_resize(hash_table_t *table, unsigned long new_size);
 793 unsigned long ht_free(hash_table_t *table);
 794
 795 struct _hash_entry_s {
 796   unsigned long he_magic;       /* magic number */
 797   link_elem_t   he_elem;        /* link element */
 798   hash_table_t *he_table;       /* hash table we're in */
 799   unsigned long he_hash;        /* hash value */
 800   db_key_t      he_key;         /* entry's key */
 801   void         *he_value;       /* actual entry */
 802 };
 803
 804 #define HASH_ENTRY_MAGIC 0x35afaf51
 805
 806 /** \ingroup dbprim_hash
 807  * \brief Hash table entry static initializer.
 808  *
 809  * This macro statically initializes a #hash_entry_t.
 810  *
 811  * \param value A pointer to \c void representing the object
 812  *              associated with the entry.
 813  */
 814 #define HASH_ENTRY_INIT(value) \
 815       { HASH_ENTRY_MAGIC, LINK_ELEM_INIT(0), 0, 0, DB_KEY_INIT(0, 0), (value) }
 816
 817 /** \ingroup dbprim_hash
 818  * \brief Hash table entry verification macro.
 819  *
 820  * This macro verifies that a given pointer actually does point to a
 821  * hash table entry.
 822  *
 823  * \param entry A pointer to a #hash_entry_t.
 824  *
 825  * \return      Boolean true if \p entry is a valid hash table entry
 826  *              or false otherwise.
 827  */
 828 #define he_verify(entry)        ((entry) && \
 829                                  (entry)->he_magic == HASH_ENTRY_MAGIC)
 830
 831 /** \ingroup dbprim_hash
 832  * \brief Hash table entry linked list element.
 833  *
 834  * This macro provides access to the linked list element buried in the
 835  * hash table entry.  It should *not* be used on entries currently in
 836  * a hash table.  The purpose of this macro is to allow an object
 837  * containing a hash table entry to be placed upon a free list.
 838  *
 839  * \param entry A pointer to a #hash_entry_t.
 840  *
 841  * \return      A pointer to a #link_elem_t.
 842  */
 843 #define he_link(entry)  (&((entry)->he_elem))
 844
 845 /** \ingroup dbprim_hash
 846  * \brief Hash table entry flags.
 847  *
 848  * This macro retrieves a set of user-defined flags associated with
 849  * the entry.  It may be used as an lvalue to set those flags.
 850  *
 851  * \param entry A pointer to a #hash_entry_t.
 852  *
 853  * \return      An <CODE>unsigned long</CODE> containing the flags
 854  *              associated with the entry.
 855  */
 856 #define he_flags(entry) ((entry)->he_elem.le_flags)
 857
 858 /** \ingroup dbprim_hash
 859  * \brief Hash table entry table pointer.
 860  *
 861  * This macro retrieves a pointer to the hash table the entry is in.
 862  *
 863  * \param entry A pointer to a #hash_entry_t.
 864  *
 865  * \return      A pointer to a #hash_table_t.
 866  */
 867 #define he_table(entry) ((entry)->he_table)
 868
 869 /** \ingroup dbprim_hash
 870  * \brief Hash table entry hash value.
 871  *
 872  * This macro retrieves the hash value of the given hash entry.  If
 873  * the hash table has been resized, this value may not be the same as
 874  * a previous value.
 875  *
 876  * \param entry A pointer to a #hash_entry_t.
 877  *
 878  * \return      An <CODE>unsigned long</CODE> containing the hash code
 879  *              for the entry.
 880  */
 881 #define he_hash(entry)  ((entry)->he_hash)
 882
 883 /** \ingroup dbprim_hash
 884  * \brief Hash table entry key pointer.
 885  *
 886  * This macro retrieves the key associated with the hash table entry.
 887  *
 888  * \param entry A pointer to a #hash_entry_t.
 889  *
 890  * \return      A pointer to a #db_key_t.
 891  */
 892 #define he_key(entry)   (&((entry)->he_key))
 893
 894 /** \ingroup dbprim_hash
 895  * \brief Hash table entry value pointer.
 896  *
 897  * This macro retrieves the value associated with the hash table
 898  * entry.  It may be treated as an lvalue to change that value.  Care
 899  * should be taken when using this option.
 900  *
 901  * \param entry A pointer to a #hash_entry_t.
 902  *
 903  * \return      A pointer to \c void representing the value associated
 904  *              with this entry.
 905  */
 906 #define he_value(entry) ((entry)->he_value)
 907
 908 unsigned long he_init(hash_entry_t *entry, void *value);
 909
 910 unsigned long smat_cleanup(void);
 911 unsigned long smat_freemem(void);
 912
 913 /* Macro to convert a link_elem_t into a smat_entry_t */
 914 #define _smat_ent(ent)  ((smat_entry_t *)le_object(ent))
 915
 916 struct _smat_table_s {
 917   unsigned long st_magic;       /* magic number */
 918   smat_resize_t st_resize;      /* function pointer for resize callback */
 919   hash_table_t  st_table;       /* hash table */
 920 };
 921
 922 #define SMAT_TABLE_MAGIC 0x2f92a7b1
 923
 924 /** \ingroup dbprim_smat
 925  * \brief Sparse matrix table static initializer.
 926  *
 927  * This macro statically initializes a #smat_table_t.
 928  *
 929  * \param flags A bit-wise OR of #HASH_FLAG_AUTOGROW and
 930  *              #HASH_FLAG_AUTOSHRINK.  If neither behavior is
 931  *              desired, use 0.
 932  * \param resize
 933  *              A #smat_resize_t function pointer for determining
 934  *              whether resizing is permitted and/or for notification
 935  *              of the resize.
 936  * \param extra Extra pointer data that should be associated with the
 937  *              sparse matrix.
 938  */
 939 #define SMAT_TABLE_INIT(flags, resize, extra) \
 940         { SMAT_TABLE_MAGIC, (resize), \
 941           HASH_TABLE_INIT((flags), _smat_hash, _smat_comp, _smat_resize, \
 942                           (extra)) }
 943
 944 /** \ingroup dbprim_smat
 945  * \brief Sparse matrix table verification macro.
 946  *
 947  * This macro verifies that a given pointer actually does point to a
 948  * sparse matrix table.
 949  *
 950  * \param table A pointer to a #smat_table_t.
 951  *
 952  * \return      Boolean true if \p table is a valid sparse matrix
 953  *              table or false otherwise.
 954  */
 955 #define st_verify(table)        ((table) && \
 956                                  (table)->st_magic == SMAT_TABLE_MAGIC)
 957
 958 /** \ingroup dbprim_smat
 959  * \brief Sparse matrix table flags.
 960  *
 961  * This macro retrieves the flags associated with the sparse matrix
 962  * table.  Only #HASH_FLAG_AUTOGROW and #HASH_FLAG_AUTOSHRINK have any
 963  * meaning to the application; all other bits are reserved for use in
 964  * the library.  This macro may be used as an lvalue, but care must be
 965  * taken to avoid modifying the library-specific bits.
 966  *
 967  * \param table A pointer to a #smat_table_t.
 968  *
 969  * \return      An <CODE>unsigned long</CODE> containing the flags for
 970  *              the sparse matrix table.
 971  */
 972 #define st_flags(table)   ((table)->st_table.ht_flags)
 973
 974 /** \ingroup dbprim_smat
 975  * \brief Determine if a sparse matrix is frozen.
 976  *
 977  * This macro returns a non-zero value if the matrix is currently
 978  * frozen.  The sparse matrix may be frozen if there is an iteration
 979  * in progress.
 980  *
 981  * \param table A pointer to a #smat_table_t.
 982  *
 983  * \return      A zero value if the matrix is not frozen or a non-zero
 984  *              value if the matrix is frozen.
 985  */
 986 #define st_frozen(table)  ((table)->st_table.ht_flags & HASH_FLAG_FROZEN)
 987
 988 /** \ingroup dbprim_smat
 989  * \brief Sparse matrix table modulus.
 990  *
 991  * This macro retrieves the number of buckets allocated for the sparse
 992  * matrix table.  An application may wish to save this value between
 993  * invocations to avoid the overhead of growing the table while
 994  * filling it with data.
 995  *
 996  * \param table A pointer to a #smat_table_t.
 997  *
 998  * \return      An <CODE>unsigned long</CODE> containing the number of
 999  *              buckets allocated for the sparse matrix table.
1000  */
1001 #define st_modulus(table) ((table)->st_table.ht_modulus)
1002
1003 /** \ingroup dbprim_smat
1004  * \brief Sparse matrix table count.
1005  *
1006  * This macro retrieves the total number of items actually in the
1007  * sparse matrix table.
1008  *
1009  * \param table A pointer to a #smat_table_t.
1010  *
1011  * \return      An <CODE>unsigned long</CODE> containing a count of
1012  *              the number of items in the sparse matrix table.
1013  */
1014 #define st_count(table)   ((table)->st_table.ht_count)
1015
1016 /** \ingroup dbprim_hash
1017  * \brief Sparse matrix table resize callback function.
1018  *
1019  * This macro retrieves the resize callback function pointer.
1020  *
1021  * \param table A pointer to a #smat_table_t.
1022  *
1023  * \return      A #smat_resize_t.
1024  */
1025 #define st_rsize(table)   ((table)->st_resize)
1026
1027 /** \ingroup dbprim_smat
1028  * \brief Extra pointer data in a sparse matrix table.
1029  *
1030  * This macro retrieves the extra pointer data associated with a
1031  * particular sparse matrix table.
1032  *
1033  * \param table A pointer to a #smat_table_t.
1034  *
1035  * \return      A pointer to \c void.
1036  */
1037 #define st_extra(table)   ((table)->st_table.ht_extra)
1038
1039 /** \ingroup dbprim_smat
1040  * \brief Sparse matrix table memory size.
1041  *
1042  * This macro returns the physical size of the memory allocated by the
1043  * library for this sparse matrix table.
1044  *
1045  * \note The st_size() macro already counts the memory for each list
1046  * in the table.  Summing the results of sh_size() and st_size() will
1047  * over-count the amount of memory actually in use.
1048  *
1049  * \param table A pointer to a #smat_table_t.
1050  *
1051  * \return      A \c size_t.
1052  */
1053 #define st_size(table) ((table)->st_table.ht_modulus * sizeof(link_head_t) + \
1054                         (table)->st_table.ht_count * sizeof(smat_entry_t))
1055
1056 unsigned long _smat_hash(hash_table_t *table, db_key_t *key);
1057 unsigned long _smat_comp(hash_table_t *table, db_key_t *key1, db_key_t *key2);
1058 unsigned long _smat_resize(hash_table_t *table, unsigned long new_mod);
1059
1060 unsigned long st_init(smat_table_t *table, unsigned long flags,
1061                       smat_resize_t resize, void *extra,
1062                       unsigned long init_mod);
1063 unsigned long st_add(smat_table_t *table, smat_entry_t **entry_p,
1064                      smat_head_t *head1, link_loc_t loc1, smat_entry_t *ent1,
1065                      smat_head_t *head2, link_loc_t loc2, smat_entry_t *ent2);
1066 unsigned long st_remove(smat_table_t *table, smat_entry_t *entry);
1067 unsigned long st_find(smat_table_t *table, smat_entry_t **entry_p,
1068                       smat_head_t *head1, smat_head_t *head2);
1069 unsigned long st_iter(smat_table_t *table, smat_iter_t iter_func, void *extra);
1070 unsigned long st_flush(smat_table_t *table, smat_iter_t flush_func,
1071                        void *extra);
1072 unsigned long st_resize(smat_table_t *table, unsigned long new_size);
1073 unsigned long st_free(smat_table_t *table);
1074
1075 struct _smat_head_s {
1076   unsigned long sh_magic;       /* magic number */
1077   smat_loc_t    sh_elem;        /* 0 or 1 to indicate first or second */
1078   smat_table_t *sh_table;       /* table this object's in */
1079   link_head_t   sh_head;        /* linked list head */
1080 };
1081
1082 #define SMAT_HEAD_MAGIC 0x4e5d9b8e
1083
1084 /** \ingroup dbprim_smat
1085  * \brief Sparse matrix list head static initializer.
1086  *
1087  * This macro statically initializes a #smat_head_t.
1088  *
1089  * \param elem  One of #SMAT_LOC_FIRST or #SMAT_LOC_SECOND specifing
1090  *              whether the object is a member of the set of rows or
1091  *              columns.
1092  * \param object
1093  *              A pointer to \c void representing the object
1094  *              associated with the list head.
1095  */
1096 #define SMAT_HEAD_INIT(elem, object) \
1097         { SMAT_HEAD_MAGIC, (elem), 0, LINK_HEAD_INIT(object) }
1098
1099 /** \ingroup dbprim_smat
1100  * \brief Sparse matrix list head verification macro.
1101  *
1102  * This macro verifies that a given pointer actually does point to a
1103  * sparse matrix head.
1104  *
1105  * \param head  A pointer to a #smat_head_t.
1106  *
1107  * \return      Boolean true if \p head is a valid sparse matrix head
1108  *              or false otherwise.
1109  */
1110 #define sh_verify(head)         ((head) && \
1111                                  (head)->sh_magic == SMAT_HEAD_MAGIC)
1112
1113 /** \ingroup dbprim_smat
1114  * \brief Sparse matrix list head element macro.
1115  *
1116  * This macro retrieves the position indicator for the sparse matrix
1117  * head.  It will return one of #SMAT_LOC_FIRST or #SMAT_LOC_SECOND.
1118  *
1119  * \param head  A pointer to #smat_head_t.
1120  *
1121  * \return      An #smat_loc_t.
1122  */
1123 #define sh_elem(head)   ((head)->sh_elem)
1124
1125 /** \ingroup dbprim_smat
1126  * \brief Sparse matrix list head table pointer.
1127  *
1128  * If there are any elements in this sparse matrix list head, this
1129  * macro will retrieve a pointer to the table in which they reside.
1130  *
1131  * \param head  A pointer to #smat_head_t.
1132  *
1133  * \return      A pointer to #smat_table_t.
1134  */
1135 #define sh_table(head)  ((head)->sh_table)
1136
1137 /** \ingroup dbprim_smat
1138  * \brief Determine if a sparse matrix is frozen.
1139  *
1140  * This macro returns a non-zero value if the matrix is currently
1141  * frozen.  The sparse matrix may be frozen if there is an iteration
1142  * in progress.
1143  *
1144  * \param head  A pointer to a #smat_head_t.
1145  *
1146  * \return      A zero value if the matrix is not frozen or a non-zero
1147  *              value if the matrix is frozen.
1148  */
1149 #define sh_frozen(head) (st_frozen((head)->sh_table))
1150
1151 /** \ingroup dbprim_smat
1152  * \brief Sparse matrix list count.
1153  *
1154  * This macro retrieves the number of elements in the sparse matrix
1155  * list rooted at \p head.
1156  *
1157  * \param head  A pointer to #smat_head_t.
1158  *
1159  * \return      An <CODE>unsigned long</CODE> containing a count of
1160  *              the number of elements in the sparse matrix list.
1161  */
1162 #define sh_count(head)  ((head)->sh_head.lh_count)
1163
1164 /* helper macro to directly reference the link element */
1165 #define _sh_first(head) ((head)->sh_head.lh_first)
1166 /** \ingroup dbprim_smat
1167  * \brief First element in sparse matrix list.
1168  *
1169  * This macro retrieves a pointer to the #smat_entry_t for the first
1170  * element in the sparse matrix list.
1171  *
1172  * \warning This macro may evaluate the \c head argument twice.
1173  *
1174  * \param head  A pointer to #smat_head_t.
1175  *
1176  * \return      A pointer to #smat_entry_t.
1177  */
1178 #define sh_first(head)  (_sh_first(head) ? _smat_ent(_sh_first(head)) : 0)
1179
1180 /* helper macro to directly reference the link element */
1181 #define _sh_last(head)  ((head)->sh_head.lh_last)
1182 /** \ingroup dbprim_smat
1183  * \brief Last element in sparse matrix list.
1184  *
1185  * This macro retrieves a pointer to the #smat_entry_t for the last
1186  * element in the sparse matrix list.
1187  *
1188  * \warning This macro may evaluate the \c head argument twice.
1189  *
1190  * \param head  A pointer to #smat_head_t.
1191  *
1192  * \return      A pointer to #smat_entry_t.
1193  */
1194 #define sh_last(head)   (_sh_last(head) ? _smat_ent(_sh_last(head)) : 0)
1195
1196 /** \ingroup dbprim_smat
1197  * \brief Object represented by a sparse matrix list head.
1198  *
1199  * This macro retrieves a pointer to the object referenced by the
1200  * sparse matrix list head.
1201  *
1202  * \param head  A pointer to #smat_head_t.
1203  *
1204  * \return      A pointer to \c void.
1205  */
1206 #define sh_object(head) ((head)->sh_head.lh_extra)
1207
1208 /** \ingroup dbprim_smat
1209  * \brief Sparse matrix list memory size.
1210  *
1211  * This macro returns the physical size of the memory allocated by the
1212  * library for this sparse matrix list.
1213  *
1214  * \note The st_size() macro already counts the memory for each list
1215  * in the table.  Summing the results of sh_size() and st_size() will
1216  * over-count the amount of memory actually in use.
1217  *
1218  * \param head  A pointer to #smat_head_t.
1219  *
1220  * \return      A \c size_t.
1221  */
1222 #define sh_size(head)   ((head)->sh_elem.lh_count * sizeof(smat_entry_t))
1223
1224 unsigned long sh_init(smat_head_t *head, smat_loc_t elem, void *object);
1225 unsigned long sh_move(smat_head_t *head, smat_entry_t *elem, link_loc_t loc,
1226                       smat_entry_t *elem2);
1227 unsigned long sh_find(smat_head_t *head, smat_entry_t **elem_p,
1228                       smat_comp_t comp_func, smat_entry_t *start,
1229                       db_key_t *key);
1230 unsigned long sh_iter(smat_head_t *head, smat_iter_t iter_func, void *extra);
1231 unsigned long sh_flush(smat_head_t *head, smat_iter_t flush_func, void *extra);
1232
1233 struct _smat_entry_s {
1234   unsigned long se_magic;       /* magic number */
1235   smat_table_t *se_table;       /* sparse matrix table */
1236   hash_entry_t  se_hash;        /* hash table entry */
1237   link_elem_t   se_link[2];     /* linked list elements */
1238   void         *se_object[2];   /* objects */
1239 };
1240
1241 #define SMAT_ENTRY_MAGIC 0x466b34b5
1242
1243 /** \ingroup dbprim_smat
1244  * \brief Sparse matrix entry verification macro.
1245  *
1246  * This macro verifies that a given pointer actually does point to a
1247  * sparse matrix entry.
1248  *
1249  * \param entry A pointer to a #smat_entry_t.
1250  *
1251  * \return      Boolean true if \p entry is a valid sparse matrix
1252  *              entry or false otherwise.
1253  */
1254 #define se_verify(entry)        ((entry) && \
1255                                  (entry)->se_magic == SMAT_ENTRY_MAGIC)
1256
1257 /** \ingroup dbprim_smat
1258  * \brief Sparse matrix entry table.
1259  *
1260  * This macro retrieves a pointer to the table that the sparse matrix
1261  * entry is in.
1262  *
1263  * \param entry A pointer to a #smat_entry_t.
1264  *
1265  * \return      A pointer to a #smat_table_t.
1266  */
1267 #define se_table(entry)     ((entry)->se_table)
1268
1269 /** \ingroup dbprim_smat
1270  * \internal
1271  * \brief Sparse matrix entry linked list element.
1272  *
1273  * This macro provides access to the linked list element buried in the
1274  * sparse matrix entry for use by the free list routines.
1275  *
1276  * \param entry A pointer to a #smat_entry_t.
1277  *
1278  * \return      A pointer to a #link_elem_t.
1279  */
1280 #define _se_link(entry)     (&((entry)->se_hash.he_elem))
1281
1282 /** \ingroup dbprim_smat
1283  * \brief Sparse matrix entry flags.
1284  *
1285  * This macro retrieves a set of user-defined flags associated with
1286  * the entry.  It may be used as an lvalue to set those flags.
1287  *
1288  * \param entry A pointer to a #smat_entry_t.
1289  *
1290  * \return      An <CODE>unsigned long</CODE> containing the flags
1291  *              associated with the entry.
1292  */
1293 #define se_flags(entry)     ((entry)->se_hash.he_elem.le_flags)
1294
1295 /** \ingroup dbprim_smat
1296  * \brief Sparse matrix table entry hash value.
1297  *
1298  * This macro retrieves the hash value of the given sparse matrix
1299  * entry.  If the sparse matrix hash been resized, this value may not
1300  * be the same as a previous value.
1301  *
1302  * \param entry A pointer to a #smat_entry_t.
1303  *
1304  * \return      An <CODE>unsigned long</CODE> containing the hash code
1305  *              for the entry.
1306  */
1307 #define se_hash(entry)      ((entry)->se_hash.he_hash)
1308
1309 /* helper macro to directly reference the link element */
1310 #define _se_next(entry, n)  ((entry)->se_link[(n)].le_next)
1311 /** \ingroup dbprim_smat
1312  * \brief Next element in sparse matrix list.
1313  *
1314  * This macro retrieves a pointer to the #link_elem_t for the next
1315  * element in the sparse matrix list.
1316  *
1317  * \warning This macro may evaluate the \c entry and \c n arguments
1318  * twice.
1319  *
1320  * \param entry A pointer to #smat_entry_t.
1321  * \param n     One of #SMAT_LOC_FIRST or #SMAT_LOC_SECOND to specify
1322  *              which list thread is desired.
1323  *
1324  * \return      A pointer to #smat_entry_t.
1325  */
1326 #define se_next(entry, n)   (_se_next(entry, n) ? \
1327                              _smat_ent(_se_next(entry, n)) : 0)
1328
1329 /* helper macro to directly reference the link element */
1330 #define _se_prev(entry, n)  ((entry)->se_link[(n)].le_prev)
1331 /** \ingroup dbprim_smat
1332  * \brief Previous element in sparse matrix list.
1333  *
1334  * This macro retrieves a pointer to the #link_elem_t for the previous
1335  * element in the sparse matrix list.
1336  *
1337  * \warning This macro may evaluate the \c entry and \c n arguments
1338  * twice.
1339  *
1340  * \param entry A pointer to #smat_entry_t.
1341  * \param n     One of #SMAT_LOC_FIRST or #SMAT_LOC_SECOND to specify
1342  *              which list thread is desired.
1343  *
1344  * \return      A pointer to #smat_entry_t.
1345  */
1346 #define se_prev(entry, n)   (_se_prev(entry, n) ? \
1347                              _smat_ent(_se_prev(entry, n)) : 0)
1348
1349 /** \ingroup dbprim_smat
1350  * \brief Flags associated with an entry in a sparse matrix list.
1351  *
1352  * This macro retrieves a set of user-defined flags associated with
1353  * the entry in a sparse matrix list.  It may be used as an lvalue to
1354  * set those flags.
1355  *
1356  * \param entry A pointer to #smat_entry_t.
1357  * \param n     One of #SMAT_LOC_FIRST or #SMAT_LOC_SECOND to specify
1358  *              which list thread is desired.
1359  *
1360  * \return      An <CODE>unsigned long</CODE> containing the flags
1361  *              associated with the entry.
1362  */
1363 #define se_lflags(entry, n) ((entry)->se_link[(n)].le_flags)
1364
1365 /** \ingroup dbprim_smat
1366  * \brief Object associated with an entry in a sparse matrix list.
1367  *
1368  * This macro retrieves a pointer to one of the object represented by
1369  * the entry.  It may be used as an lvalue to change the object
1370  * pointed to.  Care should be taken when using this feature.
1371  *
1372  * \param entry A pointer to #smat_entry_t.
1373  * \param n     One of #SMAT_LOC_FIRST or #SMAT_LOC_SECOND to specify
1374  *              which list thread is desired.
1375  *
1376  * \return      A pointer to \c void representing the object.
1377  */
1378 #define se_object(entry, n) ((entry)->se_object[(n)])
1379
1380 /* begin dbprim_err.h */
1381