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

dbprim.h

Go to the documentation of this file.
00001 /* -*- c -*-
00002 ** Copyright (C) 2002, 2006 by Kevin L. Mitchell <klmitch@mit.edu>
00003 **
00004 ** This library is free software; you can redistribute it and/or
00005 ** modify it under the terms of the GNU Library General Public
00006 ** License as published by the Free Software Foundation; either
00007 ** version 2 of the License, or (at your option) any later version.
00008 **
00009 ** This library is distributed in the hope that it will be useful,
00010 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012 ** Library General Public License for more details.
00013 **
00014 ** You should have received a copy of the GNU Library General Public
00015 ** License along with this library; if not, write to the Free
00016 ** Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00017 ** MA 02111-1307, USA
00018 **
00019 ** @(#)$Id: dbprim.h,v 1.13 2006/07/15 18:06:18 klmitch Exp $
00020 */
00021 #ifndef __include_dbprim_h__
00022 #define __include_dbprim_h__
00023 
00230 #undef DBPRIM_BEGIN_C_DECLS
00231 #undef DBPRIM_END_C_DECLS
00232 #ifdef __cplusplus
00233 # define DBPRIM_BEGIN_C_DECLS extern "C" {
00234 # define DBPRIM_END_C_DECLS }
00235 #else
00236 # define DBPRIM_BEGIN_C_DECLS /* empty */
00237 # define DBPRIM_END_C_DECLS   /* empty */
00238 #endif
00239 
00240 DBPRIM_BEGIN_C_DECLS
00241 
00242 #ifndef __DBPRIM_LIBRARY__
00243 #include <dbprim/dbprim_err.h>
00244 #include <dbprim/dbprim_version.h>
00245 #endif /* __DBPRIM_LIBRARY__ */
00246 
00254 typedef struct _db_key_s db_key_t;
00255 
00262 typedef struct _link_head_s  link_head_t;
00263 
00269 typedef struct _link_elem_s  link_elem_t;
00270 
00277 typedef struct _hash_table_s hash_table_t;
00278 
00284 typedef struct _hash_entry_s hash_entry_t;
00285 
00292 typedef struct _smat_table_s smat_table_t;
00293 
00300 typedef struct _smat_head_s  smat_head_t;
00301 
00308 typedef struct _smat_entry_s smat_entry_t;
00309 
00316 typedef struct _rb_tree_s rb_tree_t;
00317 
00323 typedef struct _rb_node_s rb_node_t;
00324 
00342 typedef unsigned long (*link_iter_t)(link_head_t *list, link_elem_t *elem,
00343                                      void *extra);
00344 
00357 typedef unsigned long (*link_comp_t)(db_key_t *key, void *obj);
00358 
00376 typedef unsigned long (*hash_iter_t)(hash_table_t *table, hash_entry_t *ent,
00377                                      void *extra);
00378 
00392 typedef unsigned long (*hash_func_t)(hash_table_t *table, db_key_t *key);
00393 
00408 typedef unsigned long (*hash_comp_t)(hash_table_t *table, db_key_t *key1,
00409                                      db_key_t *key2);
00410 
00424 typedef unsigned long (*hash_resize_t)(hash_table_t *table,
00425                                        unsigned long new_mod);
00426 
00440 typedef unsigned long (*smat_resize_t)(smat_table_t *table,
00441                                        unsigned long new_mod);
00442 
00460 typedef unsigned long (*smat_iter_t)(smat_table_t *table, smat_entry_t *ent,
00461                                      void *extra);
00462 
00476 typedef unsigned long (*smat_comp_t)(db_key_t *key, smat_entry_t *ent);
00477 
00495 typedef unsigned long (*rb_iter_t)(rb_tree_t *tree, rb_node_t *node,
00496                                    void *extra);
00497 
00514 typedef long (*rb_comp_t)(rb_tree_t *tree, db_key_t *key1, db_key_t *key2);
00515 
00523 enum _link_loc_e {
00524   LINK_LOC_HEAD,        
00525   LINK_LOC_TAIL,        
00526   LINK_LOC_BEFORE,      
00528   LINK_LOC_AFTER        
00530 };
00531 
00537 typedef enum _link_loc_e link_loc_t;
00538 
00546 enum _smat_loc_e {
00547   SMAT_LOC_FIRST,       
00548   SMAT_LOC_SECOND       
00549 };
00550 
00556 typedef enum _smat_loc_e smat_loc_t;
00557 
00564 enum _rb_color_e {
00565   RB_COLOR_NONE,        
00566   RB_COLOR_RED,         
00567   RB_COLOR_BLACK        
00568 };
00569 
00575 typedef enum _rb_color_e rb_color_t;
00576 
00583 struct _db_key_s {
00584   void *dk_key;         
00585   int   dk_len;         
00586 };
00587 
00596 #define DB_KEY_INIT(key, size) { (key), (size) }
00597 
00608 #define dk_key(key)     ((key)->dk_key)
00609 
00621 #define dk_len(key)     ((key)->dk_len)
00622 
00629 #define DB_FLAG_REVERSE         0x80000000
00630 
00637 struct _link_head_s {
00638   unsigned long lh_magic;       
00639   unsigned long lh_count;       
00640   link_elem_t  *lh_first;       
00641   link_elem_t  *lh_last;        
00642   void         *lh_extra;       
00643 };
00644 
00651 #define LINK_HEAD_MAGIC 0x4c6155d7
00652 
00661 #define LINK_HEAD_INIT(extra)   { LINK_HEAD_MAGIC, 0, 0, 0, (extra) }
00662 
00676 #define ll_verify(list)         ((list) && \
00677                                  (list)->lh_magic == LINK_HEAD_MAGIC)
00678 
00689 #define ll_count(list)  ((list)->lh_count)
00690 
00700 #define ll_first(list)  ((list)->lh_first)
00701 
00711 #define ll_last(list)   ((list)->lh_last)
00712 
00723 #define ll_extra(list)  ((list)->lh_extra)
00724 
00739 unsigned long ll_init(link_head_t *list, void *extra);
00740 
00762 unsigned long ll_add(link_head_t *list, link_elem_t *new, link_loc_t loc,
00763                      link_elem_t *elem);
00764 
00788 unsigned long ll_move(link_head_t *list, link_elem_t *elem, link_loc_t loc,
00789                       link_elem_t *elem2);
00790 
00804 unsigned long ll_remove(link_head_t *list, link_elem_t *elem);
00805 
00832 unsigned long ll_find(link_head_t *list, link_elem_t **elem_p,
00833                       link_comp_t comp_func, link_elem_t *start,
00834                       db_key_t *key);
00835 
00863 unsigned long ll_iter(link_head_t *list, link_elem_t *start,
00864                       link_iter_t iter_func, void *extra, unsigned long flags);
00865 
00887 unsigned long ll_flush(link_head_t *list, link_iter_t flush_func, void *extra);
00888 
00895 struct _link_elem_s {
00896   unsigned long le_magic;       
00897   link_elem_t  *le_next;        
00898   link_elem_t  *le_prev;        
00899   void         *le_object;      
00900   link_head_t  *le_head;        
00901   unsigned long le_flags;       
00902 };
00903 
00911 #define LINK_ELEM_MAGIC 0x97cdf72a
00912 
00921 #define LINK_ELEM_INIT(obj) { LINK_ELEM_MAGIC, 0, 0, (obj), 0, 0 }
00922 
00936 #define le_verify(element)      ((element) && \
00937                                  (element)->le_magic == LINK_ELEM_MAGIC)
00938 
00950 #define le_next(elem)   ((elem)->le_next)
00951 
00963 #define le_prev(elem)   ((elem)->le_prev)
00964 
00977 #define le_object(elem) ((elem)->le_object)
00978 
00990 #define le_head(elem)   ((elem)->le_head)
00991 
01003 #define le_flags(elem)  ((elem)->le_flags)
01004 
01019 unsigned long le_init(link_elem_t *elem, void *object);
01020 
01034 unsigned long hash_fnv1(hash_table_t *table, db_key_t *key);
01035 
01049 unsigned long hash_fnv1a(hash_table_t *table, db_key_t *key);
01050 
01063 unsigned long hash_comp(hash_table_t *table, db_key_t *key1, db_key_t *key2);
01064 
01071 struct _hash_table_s {
01072   unsigned long ht_magic;       
01073   unsigned long ht_flags;       
01074   unsigned long ht_modulus;     
01076   unsigned long ht_count;       
01077   unsigned long ht_rollover;    
01078   unsigned long ht_rollunder;   
01079   link_head_t  *ht_table;       
01080   hash_func_t   ht_func;        
01081   hash_comp_t   ht_comp;        
01082   hash_resize_t ht_resize;      
01083   void         *ht_extra;       
01084 };
01085 
01092 #define HASH_TABLE_MAGIC 0x2da7ffd9
01093 
01100 #define HASH_FLAG_AUTOGROW   0x00000001 /* let table automatically grow */
01101 
01108 #define HASH_FLAG_AUTOSHRINK 0x00000002 /* let table automatically shrink */
01109 
01116 #define HASH_FLAG_MASK       (HASH_FLAG_AUTOGROW | HASH_FLAG_AUTOSHRINK)
01117 
01124 #define HASH_FLAG_FREEZE     0x80000000 /* hash table frozen */
01125 
01145 #define HASH_TABLE_INIT(flags, func, comp, resize, extra) \
01146         { HASH_TABLE_MAGIC, (flags) & HASH_FLAG_MASK, 0, 0, 0, 0, 0, \
01147           (func), (comp), (resize), (extra) }
01148 
01162 #define ht_verify(table)        ((table) && \
01163                                  (table)->ht_magic == HASH_TABLE_MAGIC)
01164 
01179 #define ht_flags(table)   ((table)->ht_flags)
01180 
01193 #define ht_frozen(table)  ((table)->ht_flags & HASH_FLAG_FREEZE)
01194 
01208 #define ht_modulus(table) ((table)->ht_modulus)
01209 
01221 #define ht_count(table)   ((table)->ht_count)
01222 
01232 #define ht_func(table)    ((table)->ht_func)
01233 
01243 #define ht_comp(table)    ((table)->ht_comp)
01244 
01254 #define ht_rsize(table)   ((table)->ht_resize)
01255 
01266 #define ht_extra(table)   ((table)->ht_extra)
01267 
01278 #define ht_size(table)    ((table)->ht_modulus * sizeof(link_head_t))
01279 
01310 unsigned long ht_init(hash_table_t *table, unsigned long flags,
01311                       hash_func_t func, hash_comp_t comp,
01312                       hash_resize_t resize, void *extra,
01313                       unsigned long init_mod);
01314 
01337 unsigned long ht_add(hash_table_t *table, hash_entry_t *entry, db_key_t *key);
01338 
01360 unsigned long ht_move(hash_table_t *table, hash_entry_t *entry, db_key_t *key);
01361 
01379 unsigned long ht_remove(hash_table_t *table, hash_entry_t *entry);
01380 
01397 unsigned long ht_find(hash_table_t *table, hash_entry_t **entry_p,
01398                       db_key_t *key);
01399 
01420 unsigned long ht_iter(hash_table_t *table, hash_iter_t iter_func, void *extra);
01421 
01444 unsigned long ht_flush(hash_table_t *table, hash_iter_t flush_func,
01445                        void *extra);
01446 
01465 unsigned long ht_resize(hash_table_t *table, unsigned long new_size);
01466 
01479 unsigned long ht_free(hash_table_t *table);
01480 
01487 struct _hash_entry_s {
01488   unsigned long he_magic;       
01489   link_elem_t   he_elem;        
01490   hash_table_t *he_table;       
01491   unsigned long he_hash;        
01492   db_key_t      he_key;         
01493   void         *he_value;       
01494 };
01495 
01502 #define HASH_ENTRY_MAGIC 0x35afaf51
01503 
01512 #define HASH_ENTRY_INIT(value) \
01513       { HASH_ENTRY_MAGIC, LINK_ELEM_INIT(0), 0, 0, DB_KEY_INIT(0, 0), (value) }
01514 
01528 #define he_verify(entry)        ((entry) && \
01529                                  (entry)->he_magic == HASH_ENTRY_MAGIC)
01530 
01543 #define he_link(entry)  (&((entry)->he_elem))
01544 
01556 #define he_flags(entry) ((entry)->he_elem.le_flags)
01557 
01567 #define he_table(entry) ((entry)->he_table)
01568 
01581 #define he_hash(entry)  ((entry)->he_hash)
01582 
01592 #define he_key(entry)   (&((entry)->he_key))
01593 
01606 #define he_value(entry) ((entry)->he_value)
01607 
01621 unsigned long he_init(hash_entry_t *entry, void *value);
01622 
01631 unsigned long smat_cleanup(void);
01632 
01642 unsigned long smat_freemem(void);
01643 
01656 #define _smat_ent(ent)  ((smat_entry_t *)le_object(ent))
01657 
01664 struct _smat_table_s {
01665   unsigned long st_magic;       
01666   smat_resize_t st_resize;      
01667   void         *st_extra;       
01668   hash_table_t  st_table;       
01669 };
01670 
01678 #define SMAT_TABLE_MAGIC 0x2f92a7b1
01679 
01693 #define st_verify(table)        ((table) && \
01694                                  (table)->st_magic == SMAT_TABLE_MAGIC)
01695 
01710 #define st_flags(table)   ((table)->st_table.ht_flags)
01711 
01724 #define st_frozen(table)  ((table)->st_table.ht_flags & HASH_FLAG_FREEZE)
01725 
01739 #define st_modulus(table) ((table)->st_table.ht_modulus)
01740 
01752 #define st_count(table)   ((table)->st_table.ht_count)
01753 
01763 #define st_rsize(table)   ((table)->st_resize)
01764 
01775 #define st_extra(table)   ((table)->st_extra)
01776 
01791 #define st_size(table) ((table)->st_table.ht_modulus * sizeof(link_head_t) + \
01792                         (table)->st_table.ht_count * sizeof(smat_entry_t))
01793 
01821 unsigned long st_init(smat_table_t *table, unsigned long flags,
01822                       smat_resize_t resize, void *extra,
01823                       unsigned long init_mod);
01824 
01873 unsigned long st_add(smat_table_t *table, smat_entry_t **entry_p,
01874                      smat_head_t *head1, link_loc_t loc1, smat_entry_t *ent1,
01875                      smat_head_t *head2, link_loc_t loc2, smat_entry_t *ent2);
01876 
01892 unsigned long st_remove(smat_table_t *table, smat_entry_t *entry);
01893 
01915 unsigned long st_find(smat_table_t *table, smat_entry_t **entry_p,
01916                       smat_head_t *head1, smat_head_t *head2);
01917 
01938 unsigned long st_iter(smat_table_t *table, smat_iter_t iter_func, void *extra);
01939 
01962 unsigned long st_flush(smat_table_t *table, smat_iter_t flush_func,
01963                        void *extra);
01964 
01983 unsigned long st_resize(smat_table_t *table, unsigned long new_size);
01984 
01997 unsigned long st_free(smat_table_t *table);
01998 
02005 struct _smat_head_s {
02006   unsigned long sh_magic;       
02007   smat_loc_t    sh_elem;        
02008   smat_table_t *sh_table;       
02009   link_head_t   sh_head;        
02010 };
02011 
02019 #define SMAT_HEAD_MAGIC 0x4e5d9b8e
02020 
02033 #define SMAT_HEAD_INIT(elem, object) \
02034         { SMAT_HEAD_MAGIC, (elem), 0, LINK_HEAD_INIT(object) }
02035 
02049 #define sh_verify(head)         ((head) && \
02050                                  (head)->sh_magic == SMAT_HEAD_MAGIC)
02051 
02062 #define sh_elem(head)   ((head)->sh_elem)
02063 
02074 #define sh_table(head)  ((head)->sh_table)
02075 
02088 #define sh_frozen(head) (st_frozen((head)->sh_table))
02089 
02101 #define sh_count(head)  ((head)->sh_head.lh_count)
02102 
02115 #define _sh_first(head) ((head)->sh_head.lh_first)
02116 
02129 #define sh_first(head)  (_sh_first(head) ? _smat_ent(_sh_first(head)) : 0)
02130 
02143 #define _sh_last(head)  ((head)->sh_head.lh_last)
02144 
02157 #define sh_last(head)   (_sh_last(head) ? _smat_ent(_sh_last(head)) : 0)
02158 
02169 #define sh_object(head) ((head)->sh_head.lh_extra)
02170 
02185 #define sh_size(head)   ((head)->sh_elem.lh_count * sizeof(smat_entry_t))
02186 
02204 unsigned long sh_init(smat_head_t *head, smat_loc_t elem, void *object);
02205 
02231 unsigned long sh_move(smat_head_t *head, smat_entry_t *elem, link_loc_t loc,
02232                       smat_entry_t *elem2);
02233 
02261 unsigned long sh_find(smat_head_t *head, smat_entry_t **elem_p,
02262                       smat_comp_t comp_func, smat_entry_t *start,
02263                       db_key_t *key);
02264 
02294 unsigned long sh_iter(smat_head_t *head, smat_entry_t *start,
02295                       smat_iter_t iter_func, void *extra, unsigned long flags);
02296 
02319 unsigned long sh_flush(smat_head_t *head, smat_iter_t flush_func, void *extra);
02320 
02327 struct _smat_entry_s {
02328   unsigned long se_magic;       
02329   smat_table_t *se_table;       
02330   hash_entry_t  se_hash;        
02331   link_elem_t   se_link[2];     
02332   void         *se_object[2];   
02333 };
02334 
02342 #define SMAT_ENTRY_MAGIC 0x466b34b5
02343 
02357 #define se_verify(entry)        ((entry) && \
02358                                  (entry)->se_magic == SMAT_ENTRY_MAGIC)
02359 
02370 #define se_table(entry)     ((entry)->se_table)
02371 
02383 #define _se_link(entry)     (&((entry)->se_hash.he_elem))
02384 
02396 #define se_flags(entry)     ((entry)->se_hash.he_elem.le_flags)
02397 
02410 #define se_hash(entry)      ((entry)->se_hash.he_hash)
02411 
02427 #define _se_next(entry, n)  ((entry)->se_link[(n)].le_next)
02428 
02445 #define se_next(entry, n)   (_se_next(entry, n) ? \
02446                              _smat_ent(_se_next(entry, n)) : 0)
02447 
02463 #define _se_prev(entry, n)  ((entry)->se_link[(n)].le_prev)
02464 
02481 #define se_prev(entry, n)   (_se_prev(entry, n) ? \
02482                              _smat_ent(_se_prev(entry, n)) : 0)
02483 
02499 #define se_lflags(entry, n) ((entry)->se_link[(n)].le_flags)
02500 
02515 #define se_object(entry, n) ((entry)->se_object[(n)])
02516 
02531 long rbtree_comp(rb_tree_t *tree, db_key_t *key1, db_key_t *key2);
02532 
02539 struct _rb_tree_s {
02540   unsigned long rt_magic;       
02541   unsigned long rt_flags;       
02542   unsigned long rt_count;       
02543   rb_node_t    *rt_root;        
02544   rb_comp_t     rt_comp;        
02545   void         *rt_extra;       
02546 };
02547 
02554 #define RB_TREE_MAGIC 0xd52695be
02555 
02562 #define RBT_FLAG_FREEZE 0x80000000 /* tree frozen */
02563 
02574 #define RB_TREE_INIT(comp, extra)   { RB_TREE_MAGIC, 0, 0, 0, (comp), (extra) }
02575 
02589 #define rt_verify(tree)         ((tree) && \
02590                                  (tree)->rt_magic == RB_TREE_MAGIC)
02591 
02604 #define rt_frozen(tree)         ((tree)->rt_flags & RBT_FLAG_FREEZE)
02605 
02617 #define rt_count(tree)          ((tree)->rt_count)
02618 
02628 #define rt_root(tree)           ((tree)->rt_root)
02629 
02639 #define rt_comp(tree)           ((tree)->rt_comp)
02640 
02651 #define rt_extra(tree)          ((tree)->rt_extra)
02652 
02659 #define RBT_ORDER_PRE   1
02660 
02667 #define RBT_ORDER_IN    2
02668 
02675 #define RBT_ORDER_POST  3
02676 
02682 #define RBT_ORDER_MASK  0x00000003
02683 
02705 #define rt_prev(tree, node_io, flags) \
02706         (rt_next((tree), (node_io), (flags) ^ DB_FLAG_REVERSE))
02707 
02722 unsigned long rt_init(rb_tree_t *tree, rb_comp_t comp, void *extra);
02723 
02741 unsigned long rt_add(rb_tree_t *tree, rb_node_t *node, db_key_t *key);
02742 
02764 unsigned long rt_move(rb_tree_t *tree, rb_node_t *node, db_key_t *key);
02765 
02781 unsigned long rt_remove(rb_tree_t *tree, rb_node_t *node);
02782 
02799 unsigned long rt_find(rb_tree_t *tree, rb_node_t **node_p, db_key_t *key);
02800 
02825 unsigned long rt_next(rb_tree_t *tree, rb_node_t **node_io,
02826                       unsigned long flags);
02827 
02859 unsigned long rt_iter(rb_tree_t *tree, rb_node_t *start,
02860                       rb_iter_t iter_func, void *extra, unsigned long flags);
02861 
02883 unsigned long rt_flush(rb_tree_t *tree, rb_iter_t flush_func, void *extra);
02884 
02891 struct _rb_node_s {
02892   unsigned long rn_magic;       
02893   rb_color_t    rn_color;       
02894   rb_tree_t    *rn_tree;        
02895   rb_node_t    *rn_parent;      
02896   rb_node_t    *rn_left;        
02897   rb_node_t    *rn_right;       
02898   db_key_t      rn_key;         
02899   void         *rn_value;       
02900 };
02901 
02908 #define RB_NODE_MAGIC 0x3dea4d01
02909 
02918 #define RB_NODE_INIT(value) \
02919         { RB_NODE_MAGIC, RB_COLOR_NONE, 0, 0, 0, 0, DB_KEY_INIT(0, 0), (value)}
02920 
02934 #define rn_verify(node)         ((node) && \
02935                                  (node)->rn_magic == RB_NODE_MAGIC)
02936 
02947 #define rn_color(node)          ((node)->rn_color)
02948 
02959 #define rn_tree(node)           ((node)->rn_tree)
02960 
02971 #define rn_parent(node)         ((node)->rn_parent)
02972 
02983 #define rn_left(node)           ((node)->rn_left)
02984 
02995 #define rn_right(node)          ((node)->rn_right)
02996 
03007 #define rn_key(node)            (&((node)->rn_key))
03008 
03021 #define rn_value(node)          ((node)->rn_value)
03022 
03036 #define rn_isblack(node)        (!(node) || (node)->rn_color == RB_COLOR_BLACK)
03037 
03051 #define rn_isred(node)          ((node) && (node)->rn_color == RB_COLOR_RED)
03052 
03067 #define rn_isleft(node)         ((node)->rn_parent && \
03068                                  (node)->rn_parent->rn_left == (node))
03069 
03084 #define rn_isright(node)        ((node)->rn_parent && \
03085                                  (node)->rn_parent->rn_right == (node))
03086 
03100 unsigned long rn_init(rb_node_t *node, void *value);
03101 
03102 DBPRIM_END_C_DECLS
03103 
03104 #endif /* __include_dbprim_h__ */

Generated on Sat Jul 15 14:10:33 2006 for DatabasePrimitivesLibrary by  doxygen 1.4.4