2 ** Copyright (C) 2002 by Kevin L. Mitchell <klmitch@mit.edu>
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.
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.
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,
19 ** @(#)$Id: dbprim.h.top,v 1.1 2003-03-07 02:36:10 klmitch Exp $
21 #ifndef __include_dbprim_h__
22 #define __include_dbprim_h__
23 /** \mainpage Database Primitives Library
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.
34 /** \defgroup dbprim_key Database keys
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.
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.
47 /** \defgroup dbprim_link Linked lists
48 * \brief Operations for linked lists.
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.
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
72 /** \defgroup dbprim_hash Hash tables
73 * \brief Operations for hash tables.
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.
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.
97 /** \defgroup dbprim_smat Sparse matrices
98 * \brief Operations for sparse matrices.
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
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
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.
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.
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.)
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().
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
166 /** \ingroup dbprim_key
167 * \brief Database key.
169 * This structure is a generic key containing a void * pointer and a
170 * length parameter. It should be accessed with * dk_key() and
173 typedef struct _db_key_s db_key_t;
175 /** \ingroup dbprim_link
176 * \brief Linked list head.
178 * This structure is the head of all linked lists maintained by this
181 typedef struct _link_head_s link_head_t;
183 /** \ingroup dbprim_link
184 * \brief Linked list element.
186 * This structure represents a single element of a linked list.
188 typedef struct _link_elem_s link_elem_t;
190 /** \ingroup dbprim_hash
193 * This structure is the basis of all hash tables maintained by this
196 typedef struct _hash_table_s hash_table_t;
198 /** \ingroup dbprim_hash
199 * \brief Hash table entry.
201 * This structure represents a single entry of a hash table.
203 typedef struct _hash_entry_s hash_entry_t;
205 /** \ingroup dbprim_smat
206 * \brief Sparse matrix table.
208 * This structure is the basis of all sparse matrices maintained by
211 typedef struct _smat_table_s smat_table_t;
213 /** \ingroup dbprim_smat
214 * \brief Sparse matrix list head.
216 * This structure is the head of a linked list of sparse matrix
219 typedef struct _smat_head_s smat_head_t;
221 /** \ingroup dbprim_smat
222 * \brief Sparse matrix entry.
224 * This structure is allocated by the library and represents a single
225 * element in a sparse matrix.
227 typedef struct _smat_entry_s smat_entry_t;
229 /** \ingroup dbprim_link
230 * \brief Linked list iteration callback.
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.
237 typedef unsigned long (*link_iter_t)(link_head_t *, link_elem_t *, void *);
239 /** \ingroup dbprim_link
240 * \brief Linked list comparison callback.
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.
246 typedef unsigned long (*link_comp_t)(db_key_t *, void *);
248 /** \ingroup dbprim_hash
249 * \brief Hash table iteration callback.
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.
256 typedef unsigned long (*hash_iter_t)(hash_table_t *, hash_entry_t *, void *);
258 /** \ingroup dbprim_hash
259 * \brief Hash function callback.
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.
266 typedef unsigned long (*hash_func_t)(hash_table_t *, db_key_t *);
268 /** \ingroup dbprim_hash
269 * \brief Hash table comparison callback.
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.
276 typedef unsigned long (*hash_comp_t)(hash_table_t *, db_key_t *, db_key_t *);
278 /** \ingroup dbprim_hash
279 * \brief Hash table resize callback.
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
286 typedef unsigned long (*hash_resize_t)(hash_table_t *, unsigned long);
288 /** \ingroup dbprim_smat
289 * \brief Sparse matrix table resize callback.
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.
296 typedef unsigned long (*smat_resize_t)(smat_table_t *, unsigned long);
298 /** \ingroup dbprim_smat
299 * \brief Sparse matrix iteration callback.
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.
306 typedef unsigned long (*smat_iter_t)(smat_table_t *, smat_entry_t *, void *);
308 /** \ingroup dbprim_smat
309 * \brief Sparse matrix comparison callback.
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.
315 typedef unsigned long (*smat_comp_t)(db_key_t *, smat_entry_t *);
317 /** \ingroup dbprim_link
318 * \brief Linked list location.
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
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
329 LINK_LOC_AFTER /**< Element should be inserted after specified
333 /** \ingroup dbprim_link
334 * \brief Linked list location.
336 * See the documentation for the enumeration #_link_loc_e.
338 typedef enum _link_loc_e link_loc_t;
340 /** \ingroup dbprim_smat
341 * \brief Sparse matrix location.
343 * This enumeration is used to specify whether an element is a row or
344 * column element. It should be referenced by the typedef
348 SMAT_LOC_FIRST, /**< First entry (``row''). */
349 SMAT_LOC_SECOND /**< Second entry (``column''). */
352 /** \ingroup dbprim_smat
353 * \brief Sparse matrix location.
355 * See the documentation for the enumeration #_smat_loc_e.
357 typedef enum _smat_loc_e smat_loc_t;
360 void *dk_key; /* Pointer to the key. */
361 int dk_len; /* Length of the key, if that has any meaning. */
364 /** \ingroup dbprim_key
365 * \brief Database key static initializer.
367 * This macro allows a #db_key_t to be initialized statically.
369 * \param key A pointer to the key.
370 * \param size Size of the key.
372 #define DB_KEY_INIT(key, size) { (key), (size) }
374 /** \ingroup dbprim_key
375 * \brief Database key accessor macro.
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.
380 * \param key A pointer to a #db_key_t.
381 * \return A pointer to a key (<CODE>void *</CODE>).
383 #define dk_key(key) ((key)->dk_key)
385 /** \ingroup dbprim_key
386 * \brief Database key length accessor macro.
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
392 * \param key A pointer to a #db_key_t.
393 * \return An \c int describing the length of the key.
395 #define dk_len(key) ((key)->dk_len)
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. */
405 #define LINK_HEAD_MAGIC 0x4c6155d7
407 /** \ingroup dbprim_link
408 * \brief Linked list head static initializer.
410 * This macro statically initializes a #link_head_t.
412 * \param extra Extra pointer data that should be associated with the
415 #define LINK_HEAD_INIT(extra) { LINK_HEAD_MAGIC, 0, 0, 0, (extra) }
417 /** \ingroup dbprim_link
418 * \brief Linked list head verification macro.
420 * This macro verifies that a given pointer actually does point to a
423 * \param list A pointer to a #link_head_t.
425 * \return Boolean true if \p list is a valid linked list head or
428 #define ll_verify(list) ((list) && \
429 (list)->lh_magic == LINK_HEAD_MAGIC)
431 /** \ingroup dbprim_link
432 * \brief Linked list count.
434 * This macro retrieves the number of elements in a linked list.
436 * \param list A pointer to a #link_head_t.
438 * \return An <CODE>unsigned long</CODE> containing a count of
439 * the number of elements in the linked list.
441 #define ll_count(list) ((list)->lh_count)
443 /** \ingroup dbprim_link
444 * \brief First element in linked list.
446 * This macro retrieves the first element in a linked list.
448 * \param list A pointer to a #link_head_t.
450 * \return A pointer to a #link_elem_t.
452 #define ll_first(list) ((list)->lh_first)
454 /** \ingroup dbprim_link
455 * \brief Last element in a linked list.
457 * This macro retrieves the last element in a linked list.
459 * \param list A pointer to a #link_head_t.
461 * \return A pointer to a #link_elem_t.
463 #define ll_last(list) ((list)->lh_last)
465 /** \ingroup dbprim_link
466 * \brief Extra pointer data in a linked list.
468 * This macro retrieves the extra pointer data associated with a
469 * particular linked list.
471 * \param list A pointer to a #link_head_t.
473 * \return A pointer to \c void.
475 #define ll_extra(list) ((list)->lh_extra)
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,
480 unsigned long ll_move(link_head_t *list, link_elem_t *elem, link_loc_t loc,
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,
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);
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 */
498 #define LINK_ELEM_MAGIC 0x97cdf72a
500 /** \ingroup dbprim_link
501 * \brief Linked list element static initializer.
503 * This macro statically initializes a #link_elem_t.
505 * \param obj A pointer to \c void representing the object
506 * associated with the element.
508 #define LINK_ELEM_INIT(obj) { LINK_ELEM_MAGIC, 0, 0, (obj), 0, 0 }
510 /** \ingroup dbprim_link
511 * \brief Linked list element verification macro.
513 * This macro verifies that a given pointer actually does point to a
514 * linked list element.
517 * A pointer to a #link_elem_t.
519 * \return Boolean true if \p element is a valid linked list
520 * element or false otherwise.
522 #define le_verify(element) ((element) && \
523 (element)->le_magic == LINK_ELEM_MAGIC)
525 /** \ingroup dbprim_link
526 * \brief Linked list element next pointer.
528 * This macro retrieves a pointer to the next element in the linked
531 * \param elem A pointer to a #link_elem_t.
533 * \return A pointer to a #link_elem_t representing the next
534 * element in the linked list.
536 #define le_next(elem) ((elem)->le_next)
538 /** \ingroup dbprim_link
539 * \brief Linked list element previous pointer.
541 * This macro retrieves a pointer to the previous element in the
544 * \param elem A pointer to a #link_elem_t.
546 * \return A pointer to a #link_elem_t representing the previous
547 * element in the linked list.
549 #define le_prev(elem) ((elem)->le_prev)
551 /** \ingroup dbprim_link
552 * \brief Linked list element object pointer.
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.
558 * \param elem A pointer to a #link_elem_t.
560 * \return A pointer to \c void representing the object
561 * associated with the linked list element.
563 #define le_object(elem) ((elem)->le_object)
565 /** \ingroup dbprim_link
566 * \brief Linked list element head pointer.
568 * This macro retrieves a pointer to the head of the linked list that
571 * \param elem A pointer to a #link_elem_t.
573 * \return A pointer to a #link_head_t representing the head of
574 * the linked list the element is in.
576 #define le_head(elem) ((elem)->le_head)
578 /** \ingroup dbprim_link
579 * \brief Linked list element flags.
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.
584 * \param elem A pointer to a #link_elem_t.
586 * \return An <CODE>unsigned long</CODE> containing the flags
587 * associated with the element.
589 #define le_flags(elem) ((elem)->le_flags)
591 unsigned long le_init(link_elem_t *elem, void *object);
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 */
607 #define HASH_TABLE_MAGIC 0x2da7ffd9
609 /** \ingroup dbprim_hash
610 * \brief Flag permitting a hash table to automatically grow.
612 * If passed in to #HASH_TABLE_INIT() or #ht_init(), allows the hash
613 * table to grow automatically.
615 #define HASH_FLAG_AUTOGROW 0x00000001 /* let table automatically grow */
617 /** \ingroup dbprim_hash
618 * \brief Flag permitting a hash table to automatically shrink.
620 * If passed in to #HASH_TABLE_INIT() or #ht_init(), allows the hash
621 * table to shrink automatically.
623 #define HASH_FLAG_AUTOSHRINK 0x00000002 /* let table automatically shrink */
625 #define HASH_FLAG_MASK (HASH_FLAG_AUTOGROW | HASH_FLAG_AUTOSHRINK)
627 #define HASH_FLAG_FREEZE 0x80000000 /* hash table frozen */
629 /** \ingroup dbprim_hash
630 * \brief Hash table static initializer.
632 * This macro statically initializes a #hash_table_t.
634 * \param flags A bit-wise OR of #HASH_FLAG_AUTOGROW and
635 * #HASH_FLAG_AUTOSHRINK. If neither behavior is
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
641 * A #hash_resize_t function pointer for determining
642 * whether resizing is permitted and/or for notification
644 * \param extra Extra pointer data that should be associated with the
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) }
651 /** \ingroup dbprim_hash
652 * \brief Hash table verification macro.
654 * This macro verifies that a given pointer actually does point to a
657 * \param table A pointer to a #hash_table_t.
659 * \return Boolean true if \p table is a valid hash table or
662 #define ht_verify(table) ((table) && \
663 (table)->ht_magic == HASH_TABLE_MAGIC)
665 /** \ingroup dbprim_hash
666 * \brief Hash table flags.
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.
674 * \param table A pointer to a #hash_table_t.
676 * \return An <CODE>unsigned long</CODE> containing the flags for
679 #define ht_flags(table) ((table)->ht_flags)
681 /** \ingroup dbprim_hash
682 * \brief Determine if a hash table is frozen.
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
688 * \param table A pointer to a #hash_table_t.
690 * \return A zero value if the table is not frozen or a non-zero
691 * value if the table is frozen.
693 #define ht_frozen(table) ((table)->ht_flags & HASH_FLAG_FROZEN)
695 /** \ingroup dbprim_hash
696 * \brief Hash table modulus.
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.
703 * \param table A pointer to a #hash_table_t.
705 * \return An <CODE>unsigned long</CODE> containing the number of
706 * buckets allocated for the hash table.
708 #define ht_modulus(table) ((table)->ht_modulus)
710 /** \ingroup dbprim_hash
711 * \brief Hash table count.
713 * This macro retrieves the total number of items actually in the hash
716 * \param table A pointer to a #hash_table_t.
718 * \return An <CODE>unsigned long</CODE> containing a count of
719 * the number of items in the hash table.
721 #define ht_count(table) ((table)->ht_count)
723 /** \ingroup dbprim_hash
724 * \brief Hash table hash function.
726 * This macro retrieves the hash function pointer.
728 * \param table A pointer to a #hash_table_t.
730 * \return A #hash_func_t.
732 #define ht_func(table) ((table)->ht_func)
734 /** \ingroup dbprim_hash
735 * \brief Hash table comparison function.
737 * This macro retrieves the comparison function pointer.
739 * \param table A pointer to a #hash_table_t.
741 * \return A #hash_comp_t.
743 #define ht_comp(table) ((table)->ht_comp)
745 /** \ingroup dbprim_hash
746 * \brief Hash table resize callback function.
748 * This macro retrieves the resize callback function pointer.
750 * \param table A pointer to a #hash_table_t.
752 * \return A #hash_resize_t.
754 #define ht_rsize(table) ((table)->ht_resize)
756 /** \ingroup dbprim_hash
757 * \brief Extra pointer data in a hash table.
759 * This macro retrieves the extra pointer data associated with a
760 * particular hash table.
762 * \param table A pointer to a #hash_table_t.
764 * \return A pointer to \c void.
766 #define ht_extra(table) ((table)->ht_extra)
768 /** \ingroup dbprim_hash
769 * \brief Hash table memory size.
771 * This macro returns the physical size of the bucket array allocated
772 * by the library for this hash table.
774 * \param table A pointer to a #hash_table_t.
776 * \return A \c size_t.
778 #define ht_size(table) ((table)->ht_modulus * sizeof(link_head_t))
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,
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,
792 unsigned long ht_resize(hash_table_t *table, unsigned long new_size);
793 unsigned long ht_free(hash_table_t *table);
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 */
804 #define HASH_ENTRY_MAGIC 0x35afaf51
806 /** \ingroup dbprim_hash
807 * \brief Hash table entry static initializer.
809 * This macro statically initializes a #hash_entry_t.
811 * \param value A pointer to \c void representing the object
812 * associated with the entry.
814 #define HASH_ENTRY_INIT(value) \
815 { HASH_ENTRY_MAGIC, LINK_ELEM_INIT(0), 0, 0, DB_KEY_INIT(0, 0), (value) }
817 /** \ingroup dbprim_hash
818 * \brief Hash table entry verification macro.
820 * This macro verifies that a given pointer actually does point to a
823 * \param entry A pointer to a #hash_entry_t.
825 * \return Boolean true if \p entry is a valid hash table entry
826 * or false otherwise.
828 #define he_verify(entry) ((entry) && \
829 (entry)->he_magic == HASH_ENTRY_MAGIC)
831 /** \ingroup dbprim_hash
832 * \brief Hash table entry linked list element.
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.
839 * \param entry A pointer to a #hash_entry_t.
841 * \return A pointer to a #link_elem_t.
843 #define he_link(entry) (&((entry)->he_elem))
845 /** \ingroup dbprim_hash
846 * \brief Hash table entry flags.
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.
851 * \param entry A pointer to a #hash_entry_t.
853 * \return An <CODE>unsigned long</CODE> containing the flags
854 * associated with the entry.
856 #define he_flags(entry) ((entry)->he_elem.le_flags)
858 /** \ingroup dbprim_hash
859 * \brief Hash table entry table pointer.
861 * This macro retrieves a pointer to the hash table the entry is in.
863 * \param entry A pointer to a #hash_entry_t.
865 * \return A pointer to a #hash_table_t.
867 #define he_table(entry) ((entry)->he_table)
869 /** \ingroup dbprim_hash
870 * \brief Hash table entry hash value.
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
876 * \param entry A pointer to a #hash_entry_t.
878 * \return An <CODE>unsigned long</CODE> containing the hash code
881 #define he_hash(entry) ((entry)->he_hash)
883 /** \ingroup dbprim_hash
884 * \brief Hash table entry key pointer.
886 * This macro retrieves the key associated with the hash table entry.
888 * \param entry A pointer to a #hash_entry_t.
890 * \return A pointer to a #db_key_t.
892 #define he_key(entry) (&((entry)->he_key))
894 /** \ingroup dbprim_hash
895 * \brief Hash table entry value pointer.
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.
901 * \param entry A pointer to a #hash_entry_t.
903 * \return A pointer to \c void representing the value associated
906 #define he_value(entry) ((entry)->he_value)
908 unsigned long he_init(hash_entry_t *entry, void *value);
910 unsigned long smat_cleanup(void);
911 unsigned long smat_freemem(void);
913 /* Macro to convert a link_elem_t into a smat_entry_t */
914 #define _smat_ent(ent) ((smat_entry_t *)le_object(ent))
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 */
922 #define SMAT_TABLE_MAGIC 0x2f92a7b1
924 /** \ingroup dbprim_smat
925 * \brief Sparse matrix table static initializer.
927 * This macro statically initializes a #smat_table_t.
929 * \param flags A bit-wise OR of #HASH_FLAG_AUTOGROW and
930 * #HASH_FLAG_AUTOSHRINK. If neither behavior is
933 * A #smat_resize_t function pointer for determining
934 * whether resizing is permitted and/or for notification
936 * \param extra Extra pointer data that should be associated with the
939 #define SMAT_TABLE_INIT(flags, resize, extra) \
940 { SMAT_TABLE_MAGIC, (resize), \
941 HASH_TABLE_INIT((flags), _smat_hash, _smat_comp, _smat_resize, \
944 /** \ingroup dbprim_smat
945 * \brief Sparse matrix table verification macro.
947 * This macro verifies that a given pointer actually does point to a
948 * sparse matrix table.
950 * \param table A pointer to a #smat_table_t.
952 * \return Boolean true if \p table is a valid sparse matrix
953 * table or false otherwise.
955 #define st_verify(table) ((table) && \
956 (table)->st_magic == SMAT_TABLE_MAGIC)
958 /** \ingroup dbprim_smat
959 * \brief Sparse matrix table flags.
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.
967 * \param table A pointer to a #smat_table_t.
969 * \return An <CODE>unsigned long</CODE> containing the flags for
970 * the sparse matrix table.
972 #define st_flags(table) ((table)->st_table.ht_flags)
974 /** \ingroup dbprim_smat
975 * \brief Determine if a sparse matrix is frozen.
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
981 * \param table A pointer to a #smat_table_t.
983 * \return A zero value if the matrix is not frozen or a non-zero
984 * value if the matrix is frozen.
986 #define st_frozen(table) ((table)->st_table.ht_flags & HASH_FLAG_FROZEN)
988 /** \ingroup dbprim_smat
989 * \brief Sparse matrix table modulus.
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.
996 * \param table A pointer to a #smat_table_t.
998 * \return An <CODE>unsigned long</CODE> containing the number of
999 * buckets allocated for the sparse matrix table.
1001 #define st_modulus(table) ((table)->st_table.ht_modulus)
1003 /** \ingroup dbprim_smat
1004 * \brief Sparse matrix table count.
1006 * This macro retrieves the total number of items actually in the
1007 * sparse matrix table.
1009 * \param table A pointer to a #smat_table_t.
1011 * \return An <CODE>unsigned long</CODE> containing a count of
1012 * the number of items in the sparse matrix table.
1014 #define st_count(table) ((table)->st_table.ht_count)
1016 /** \ingroup dbprim_hash
1017 * \brief Sparse matrix table resize callback function.
1019 * This macro retrieves the resize callback function pointer.
1021 * \param table A pointer to a #smat_table_t.
1023 * \return A #smat_resize_t.
1025 #define st_rsize(table) ((table)->st_resize)
1027 /** \ingroup dbprim_smat
1028 * \brief Extra pointer data in a sparse matrix table.
1030 * This macro retrieves the extra pointer data associated with a
1031 * particular sparse matrix table.
1033 * \param table A pointer to a #smat_table_t.
1035 * \return A pointer to \c void.
1037 #define st_extra(table) ((table)->st_table.ht_extra)
1039 /** \ingroup dbprim_smat
1040 * \brief Sparse matrix table memory size.
1042 * This macro returns the physical size of the memory allocated by the
1043 * library for this sparse matrix table.
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.
1049 * \param table A pointer to a #smat_table_t.
1051 * \return A \c size_t.
1053 #define st_size(table) ((table)->st_table.ht_modulus * sizeof(link_head_t) + \
1054 (table)->st_table.ht_count * sizeof(smat_entry_t))
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);
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,
1072 unsigned long st_resize(smat_table_t *table, unsigned long new_size);
1073 unsigned long st_free(smat_table_t *table);
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 */
1082 #define SMAT_HEAD_MAGIC 0x4e5d9b8e
1084 /** \ingroup dbprim_smat
1085 * \brief Sparse matrix list head static initializer.
1087 * This macro statically initializes a #smat_head_t.
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
1093 * A pointer to \c void representing the object
1094 * associated with the list head.
1096 #define SMAT_HEAD_INIT(elem, object) \
1097 { SMAT_HEAD_MAGIC, (elem), 0, LINK_HEAD_INIT(object) }
1099 /** \ingroup dbprim_smat
1100 * \brief Sparse matrix list head verification macro.
1102 * This macro verifies that a given pointer actually does point to a
1103 * sparse matrix head.
1105 * \param head A pointer to a #smat_head_t.
1107 * \return Boolean true if \p head is a valid sparse matrix head
1108 * or false otherwise.
1110 #define sh_verify(head) ((head) && \
1111 (head)->sh_magic == SMAT_HEAD_MAGIC)
1113 /** \ingroup dbprim_smat
1114 * \brief Sparse matrix list head element macro.
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.
1119 * \param head A pointer to #smat_head_t.
1121 * \return An #smat_loc_t.
1123 #define sh_elem(head) ((head)->sh_elem)
1125 /** \ingroup dbprim_smat
1126 * \brief Sparse matrix list head table pointer.
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.
1131 * \param head A pointer to #smat_head_t.
1133 * \return A pointer to #smat_table_t.
1135 #define sh_table(head) ((head)->sh_table)
1137 /** \ingroup dbprim_smat
1138 * \brief Determine if a sparse matrix is frozen.
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
1144 * \param head A pointer to a #smat_head_t.
1146 * \return A zero value if the matrix is not frozen or a non-zero
1147 * value if the matrix is frozen.
1149 #define sh_frozen(head) (st_frozen((head)->sh_table))
1151 /** \ingroup dbprim_smat
1152 * \brief Sparse matrix list count.
1154 * This macro retrieves the number of elements in the sparse matrix
1155 * list rooted at \p head.
1157 * \param head A pointer to #smat_head_t.
1159 * \return An <CODE>unsigned long</CODE> containing a count of
1160 * the number of elements in the sparse matrix list.
1162 #define sh_count(head) ((head)->sh_head.lh_count)
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.
1169 * This macro retrieves a pointer to the #smat_entry_t for the first
1170 * element in the sparse matrix list.
1172 * \warning This macro may evaluate the \c head argument twice.
1174 * \param head A pointer to #smat_head_t.
1176 * \return A pointer to #smat_entry_t.
1178 #define sh_first(head) (_sh_first(head) ? _smat_ent(_sh_first(head)) : 0)
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.
1185 * This macro retrieves a pointer to the #smat_entry_t for the last
1186 * element in the sparse matrix list.
1188 * \warning This macro may evaluate the \c head argument twice.
1190 * \param head A pointer to #smat_head_t.
1192 * \return A pointer to #smat_entry_t.
1194 #define sh_last(head) (_sh_last(head) ? _smat_ent(_sh_last(head)) : 0)
1196 /** \ingroup dbprim_smat
1197 * \brief Object represented by a sparse matrix list head.
1199 * This macro retrieves a pointer to the object referenced by the
1200 * sparse matrix list head.
1202 * \param head A pointer to #smat_head_t.
1204 * \return A pointer to \c void.
1206 #define sh_object(head) ((head)->sh_head.lh_extra)
1208 /** \ingroup dbprim_smat
1209 * \brief Sparse matrix list memory size.
1211 * This macro returns the physical size of the memory allocated by the
1212 * library for this sparse matrix list.
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.
1218 * \param head A pointer to #smat_head_t.
1220 * \return A \c size_t.
1222 #define sh_size(head) ((head)->sh_elem.lh_count * sizeof(smat_entry_t))
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,
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);
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 */
1241 #define SMAT_ENTRY_MAGIC 0x466b34b5
1243 /** \ingroup dbprim_smat
1244 * \brief Sparse matrix entry verification macro.
1246 * This macro verifies that a given pointer actually does point to a
1247 * sparse matrix entry.
1249 * \param entry A pointer to a #smat_entry_t.
1251 * \return Boolean true if \p entry is a valid sparse matrix
1252 * entry or false otherwise.
1254 #define se_verify(entry) ((entry) && \
1255 (entry)->se_magic == SMAT_ENTRY_MAGIC)
1257 /** \ingroup dbprim_smat
1258 * \brief Sparse matrix entry table.
1260 * This macro retrieves a pointer to the table that the sparse matrix
1263 * \param entry A pointer to a #smat_entry_t.
1265 * \return A pointer to a #smat_table_t.
1267 #define se_table(entry) ((entry)->se_table)
1269 /** \ingroup dbprim_smat
1271 * \brief Sparse matrix entry linked list element.
1273 * This macro provides access to the linked list element buried in the
1274 * sparse matrix entry for use by the free list routines.
1276 * \param entry A pointer to a #smat_entry_t.
1278 * \return A pointer to a #link_elem_t.
1280 #define _se_link(entry) (&((entry)->se_hash.he_elem))
1282 /** \ingroup dbprim_smat
1283 * \brief Sparse matrix entry flags.
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.
1288 * \param entry A pointer to a #smat_entry_t.
1290 * \return An <CODE>unsigned long</CODE> containing the flags
1291 * associated with the entry.
1293 #define se_flags(entry) ((entry)->se_hash.he_elem.le_flags)
1295 /** \ingroup dbprim_smat
1296 * \brief Sparse matrix table entry hash value.
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.
1302 * \param entry A pointer to a #smat_entry_t.
1304 * \return An <CODE>unsigned long</CODE> containing the hash code
1307 #define se_hash(entry) ((entry)->se_hash.he_hash)
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.
1314 * This macro retrieves a pointer to the #link_elem_t for the next
1315 * element in the sparse matrix list.
1317 * \warning This macro may evaluate the \c entry and \c n arguments
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.
1324 * \return A pointer to #smat_entry_t.
1326 #define se_next(entry, n) (_se_next(entry, n) ? \
1327 _smat_ent(_se_next(entry, n)) : 0)
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.
1334 * This macro retrieves a pointer to the #link_elem_t for the previous
1335 * element in the sparse matrix list.
1337 * \warning This macro may evaluate the \c entry and \c n arguments
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.
1344 * \return A pointer to #smat_entry_t.
1346 #define se_prev(entry, n) (_se_prev(entry, n) ? \
1347 _smat_ent(_se_prev(entry, n)) : 0)
1349 /** \ingroup dbprim_smat
1350 * \brief Flags associated with an entry in a sparse matrix list.
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
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.
1360 * \return An <CODE>unsigned long</CODE> containing the flags
1361 * associated with the entry.
1363 #define se_lflags(entry, n) ((entry)->se_link[(n)].le_flags)
1365 /** \ingroup dbprim_smat
1366 * \brief Object associated with an entry in a sparse matrix list.
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.
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.
1376 * \return A pointer to \c void representing the object.
1378 #define se_object(entry, n) ((entry)->se_object[(n)])
1380 /* begin dbprim_err.h */