dbprim.h

Go to the documentation of this file.

/* -*- c -*-
** Copyright (C) 2002, 2006 by Kevin L. Mitchell <klmitch@mit.edu>
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Library General Public
** License as published by the Free Software Foundation; either
** version 2 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
** Library General Public License for more details.
**
** You should have received a copy of the GNU Library General Public
** License along with this library; if not, write to the Free
** Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
** MA 02111-1307, USA
**
** @(#)$Id: dbprim.h,v 1.13 2006/07/15 18:06:18 klmitch Exp $
*/
#ifndef __include_dbprim_h__
#define __include_dbprim_h__

#undef DBPRIM_BEGIN_C_DECLS
#undef DBPRIM_END_C_DECLS
#ifdef __cplusplus
# define DBPRIM_BEGIN_C_DECLS extern "C" {
# define DBPRIM_END_C_DECLS }
#else
# define DBPRIM_BEGIN_C_DECLS /* empty */
# define DBPRIM_END_C_DECLS   /* empty */
#endif

DBPRIM_BEGIN_C_DECLS

#ifndef __DBPRIM_LIBRARY__
#include <dbprim/dbprim_err.h>
#include <dbprim/dbprim_version.h>
#endif /* __DBPRIM_LIBRARY__ */

typedef struct _db_key_s db_key_t;

typedef struct _link_head_s  link_head_t;

typedef struct _link_elem_s  link_elem_t;

typedef struct _hash_table_s hash_table_t;

typedef struct _hash_entry_s hash_entry_t;

typedef struct _smat_table_s smat_table_t;

typedef struct _smat_head_s  smat_head_t;

typedef struct _smat_entry_s smat_entry_t;

typedef struct _rb_tree_s rb_tree_t;

typedef struct _rb_node_s rb_node_t;

typedef unsigned long (*link_iter_t)(link_head_t *list, link_elem_t *elem,
                                     void *extra);

typedef unsigned long (*link_comp_t)(db_key_t *key, void *obj);

typedef unsigned long (*hash_iter_t)(hash_table_t *table, hash_entry_t *ent,
                                     void *extra);

typedef unsigned long (*hash_func_t)(hash_table_t *table, db_key_t *key);

typedef unsigned long (*hash_comp_t)(hash_table_t *table, db_key_t *key1,
                                     db_key_t *key2);

typedef unsigned long (*hash_resize_t)(hash_table_t *table,
                                       unsigned long new_mod);

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

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

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

typedef unsigned long (*rb_iter_t)(rb_tree_t *tree, rb_node_t *node,
                                   void *extra);

typedef long (*rb_comp_t)(rb_tree_t *tree, db_key_t *key1, db_key_t *key2);

enum _link_loc_e {
  LINK_LOC_HEAD,        
  LINK_LOC_TAIL,        
  LINK_LOC_BEFORE,      
  LINK_LOC_AFTER        
};

typedef enum _link_loc_e link_loc_t;

enum _smat_loc_e {
  SMAT_LOC_FIRST,       
  SMAT_LOC_SECOND       
};

typedef enum _smat_loc_e smat_loc_t;

enum _rb_color_e {
  RB_COLOR_NONE,        
  RB_COLOR_RED,         
  RB_COLOR_BLACK        
};

typedef enum _rb_color_e rb_color_t;

struct _db_key_s {
  void *dk_key;         
  int   dk_len;         
};

#define DB_KEY_INIT(key, size) { (key), (size) }

#define dk_key(key)     ((key)->dk_key)

#define dk_len(key)     ((key)->dk_len)

#define DB_FLAG_REVERSE         0x80000000

struct _link_head_s {
  unsigned long lh_magic;       
  unsigned long lh_count;       
  link_elem_t  *lh_first;       
  link_elem_t  *lh_last;        
  void         *lh_extra;       
};

#define LINK_HEAD_MAGIC 0x4c6155d7

#define LINK_HEAD_INIT(extra)   { LINK_HEAD_MAGIC, 0, 0, 0, (extra) }

#define ll_verify(list)         ((list) && \
                                 (list)->lh_magic == LINK_HEAD_MAGIC)

#define ll_count(list)  ((list)->lh_count)

#define ll_first(list)  ((list)->lh_first)

#define ll_last(list)   ((list)->lh_last)

#define ll_extra(list)  ((list)->lh_extra)

unsigned long ll_init(link_head_t *list, void *extra);

unsigned long ll_add(link_head_t *list, link_elem_t *new, link_loc_t loc,
                     link_elem_t *elem);

unsigned long ll_move(link_head_t *list, link_elem_t *elem, link_loc_t loc,
                      link_elem_t *elem2);

unsigned long ll_remove(link_head_t *list, link_elem_t *elem);

unsigned long ll_find(link_head_t *list, link_elem_t **elem_p,
                      link_comp_t comp_func, link_elem_t *start,
                      db_key_t *key);

unsigned long ll_iter(link_head_t *list, link_elem_t *start,
                      link_iter_t iter_func, void *extra, unsigned long flags);

unsigned long ll_flush(link_head_t *list, link_iter_t flush_func, void *extra);

struct _link_elem_s {
  unsigned long le_magic;       
  link_elem_t  *le_next;        
  link_elem_t  *le_prev;        
  void         *le_object;      
  link_head_t  *le_head;        
  unsigned long le_flags;       
};

#define LINK_ELEM_MAGIC 0x97cdf72a

#define LINK_ELEM_INIT(obj) { LINK_ELEM_MAGIC, 0, 0, (obj), 0, 0 }

#define le_verify(element)      ((element) && \
                                 (element)->le_magic == LINK_ELEM_MAGIC)

#define le_next(elem)   ((elem)->le_next)

#define le_prev(elem)   ((elem)->le_prev)

#define le_object(elem) ((elem)->le_object)

#define le_head(elem)   ((elem)->le_head)

#define le_flags(elem)  ((elem)->le_flags)

unsigned long le_init(link_elem_t *elem, void *object);

unsigned long hash_fnv1(hash_table_t *table, db_key_t *key);

unsigned long hash_fnv1a(hash_table_t *table, db_key_t *key);

unsigned long hash_comp(hash_table_t *table, db_key_t *key1, db_key_t *key2);

struct _hash_table_s {
  unsigned long ht_magic;       
  unsigned long ht_flags;       
  unsigned long ht_modulus;     
  unsigned long ht_count;       
  unsigned long ht_rollover;    
  unsigned long ht_rollunder;   
  link_head_t  *ht_table;       
  hash_func_t   ht_func;        
  hash_comp_t   ht_comp;        
  hash_resize_t ht_resize;      
  void         *ht_extra;       
};

#define HASH_TABLE_MAGIC 0x2da7ffd9

#define HASH_FLAG_AUTOGROW   0x00000001 /* let table automatically grow */

#define HASH_FLAG_AUTOSHRINK 0x00000002 /* let table automatically shrink */

#define HASH_FLAG_MASK       (HASH_FLAG_AUTOGROW | HASH_FLAG_AUTOSHRINK)

#define HASH_FLAG_FREEZE     0x80000000 /* hash table frozen */

#define HASH_TABLE_INIT(flags, func, comp, resize, extra) \
        { HASH_TABLE_MAGIC, (flags) & HASH_FLAG_MASK, 0, 0, 0, 0, 0, \
          (func), (comp), (resize), (extra) }

#define ht_verify(table)        ((table) && \
                                 (table)->ht_magic == HASH_TABLE_MAGIC)

#define ht_flags(table)   ((table)->ht_flags)

#define ht_frozen(table)  ((table)->ht_flags & HASH_FLAG_FREEZE)

#define ht_modulus(table) ((table)->ht_modulus)

#define ht_count(table)   ((table)->ht_count)

#define ht_func(table)    ((table)->ht_func)

#define ht_comp(table)    ((table)->ht_comp)

#define ht_rsize(table)   ((table)->ht_resize)

#define ht_extra(table)   ((table)->ht_extra)

#define ht_size(table)    ((table)->ht_modulus * sizeof(link_head_t))

unsigned long ht_init(hash_table_t *table, unsigned long flags,
                      hash_func_t func, hash_comp_t comp,
                      hash_resize_t resize, void *extra,
                      unsigned long init_mod);

unsigned long ht_add(hash_table_t *table, hash_entry_t *entry, db_key_t *key);

unsigned long ht_move(hash_table_t *table, hash_entry_t *entry, db_key_t *key);

unsigned long ht_remove(hash_table_t *table, hash_entry_t *entry);

unsigned long ht_find(hash_table_t *table, hash_entry_t **entry_p,
                      db_key_t *key);

unsigned long ht_iter(hash_table_t *table, hash_iter_t iter_func, void *extra);

unsigned long ht_flush(hash_table_t *table, hash_iter_t flush_func,
                       void *extra);

unsigned long ht_resize(hash_table_t *table, unsigned long new_size);

unsigned long ht_free(hash_table_t *table);

struct _hash_entry_s {
  unsigned long he_magic;       
  link_elem_t   he_elem;        
  hash_table_t *he_table;       
  unsigned long he_hash;        
  db_key_t      he_key;         
  void         *he_value;       
};

#define HASH_ENTRY_MAGIC 0x35afaf51

#define HASH_ENTRY_INIT(value) \
      { HASH_ENTRY_MAGIC, LINK_ELEM_INIT(0), 0, 0, DB_KEY_INIT(0, 0), (value) }

#define he_verify(entry)        ((entry) && \
                                 (entry)->he_magic == HASH_ENTRY_MAGIC)

#define he_link(entry)  (&((entry)->he_elem))

#define he_flags(entry) ((entry)->he_elem.le_flags)

#define he_table(entry) ((entry)->he_table)

#define he_hash(entry)  ((entry)->he_hash)

#define he_key(entry)   (&((entry)->he_key))

#define he_value(entry) ((entry)->he_value)

unsigned long he_init(hash_entry_t *entry, void *value);

unsigned long smat_cleanup(void);

unsigned long smat_freemem(void);

#define _smat_ent(ent)  ((smat_entry_t *)le_object(ent))

struct _smat_table_s {
  unsigned long st_magic;       
  smat_resize_t st_resize;      
  void         *st_extra;       
  hash_table_t  st_table;       
};

#define SMAT_TABLE_MAGIC 0x2f92a7b1

#define st_verify(table)        ((table) && \
                                 (table)->st_magic == SMAT_TABLE_MAGIC)

#define st_flags(table)   ((table)->st_table.ht_flags)

#define st_frozen(table)  ((table)->st_table.ht_flags & HASH_FLAG_FREEZE)

#define st_modulus(table) ((table)->st_table.ht_modulus)

#define st_count(table)   ((table)->st_table.ht_count)

#define st_rsize(table)   ((table)->st_resize)

#define st_extra(table)   ((table)->st_extra)

#define st_size(table) ((table)->st_table.ht_modulus * sizeof(link_head_t) + \
                        (table)->st_table.ht_count * sizeof(smat_entry_t))

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

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

unsigned long st_remove(smat_table_t *table, smat_entry_t *entry);

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

unsigned long st_iter(smat_table_t *table, smat_iter_t iter_func, void *extra);

unsigned long st_flush(smat_table_t *table, smat_iter_t flush_func,
                       void *extra);

unsigned long st_resize(smat_table_t *table, unsigned long new_size);

unsigned long st_free(smat_table_t *table);

struct _smat_head_s {
  unsigned long sh_magic;       
  smat_loc_t    sh_elem;        
  smat_table_t *sh_table;       
  link_head_t   sh_head;        
};

#define SMAT_HEAD_MAGIC 0x4e5d9b8e

#define SMAT_HEAD_INIT(elem, object) \
        { SMAT_HEAD_MAGIC, (elem), 0, LINK_HEAD_INIT(object) }

#define sh_verify(head)         ((head) && \
                                 (head)->sh_magic == SMAT_HEAD_MAGIC)

#define sh_elem(head)   ((head)->sh_elem)

#define sh_table(head)  ((head)->sh_table)

#define sh_frozen(head) (st_frozen((head)->sh_table))

#define sh_count(head)  ((head)->sh_head.lh_count)

#define _sh_first(head) ((head)->sh_head.lh_first)

#define sh_first(head)  (_sh_first(head) ? _smat_ent(_sh_first(head)) : 0)

#define _sh_last(head)  ((head)->sh_head.lh_last)

#define sh_last(head)   (_sh_last(head) ? _smat_ent(_sh_last(head)) : 0)

#define sh_object(head) ((head)->sh_head.lh_extra)

#define sh_size(head)   ((head)->sh_elem.lh_count * sizeof(smat_entry_t))

unsigned long sh_init(smat_head_t *head, smat_loc_t elem, void *object);

unsigned long sh_move(smat_head_t *head, smat_entry_t *elem, link_loc_t loc,
                      smat_entry_t *elem2);

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

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

unsigned long sh_flush(smat_head_t *head, smat_iter_t flush_func, void *extra);

struct _smat_entry_s {
  unsigned long se_magic;       
  smat_table_t *se_table;       
  hash_entry_t  se_hash;        
  link_elem_t   se_link[2];     
  void         *se_object[2];   
};

#define SMAT_ENTRY_MAGIC 0x466b34b5

#define se_verify(entry)        ((entry) && \
                                 (entry)->se_magic == SMAT_ENTRY_MAGIC)

#define se_table(entry)     ((entry)->se_table)

#define _se_link(entry)     (&((entry)->se_hash.he_elem))

#define se_flags(entry)     ((entry)->se_hash.he_elem.le_flags)

#define se_hash(entry)      ((entry)->se_hash.he_hash)

#define _se_next(entry, n)  ((entry)->se_link[(n)].le_next)

#define se_next(entry, n)   (_se_next(entry, n) ? \
                             _smat_ent(_se_next(entry, n)) : 0)

#define _se_prev(entry, n)  ((entry)->se_link[(n)].le_prev)

#define se_prev(entry, n)   (_se_prev(entry, n) ? \
                             _smat_ent(_se_prev(entry, n)) : 0)

#define se_lflags(entry, n) ((entry)->se_link[(n)].le_flags)

#define se_object(entry, n) ((entry)->se_object[(n)])

long rbtree_comp(rb_tree_t *tree, db_key_t *key1, db_key_t *key2);

struct _rb_tree_s {
  unsigned long rt_magic;       
  unsigned long rt_flags;       
  unsigned long rt_count;       
  rb_node_t    *rt_root;        
  rb_comp_t     rt_comp;        
  void         *rt_extra;       
};

#define RB_TREE_MAGIC 0xd52695be

#define RBT_FLAG_FREEZE 0x80000000 /* tree frozen */

#define RB_TREE_INIT(comp, extra)   { RB_TREE_MAGIC, 0, 0, 0, (comp), (extra) }

#define rt_verify(tree)         ((tree) && \
                                 (tree)->rt_magic == RB_TREE_MAGIC)

#define rt_frozen(tree)         ((tree)->rt_flags & RBT_FLAG_FREEZE)

#define rt_count(tree)          ((tree)->rt_count)

#define rt_root(tree)           ((tree)->rt_root)

#define rt_comp(tree)           ((tree)->rt_comp)

#define rt_extra(tree)          ((tree)->rt_extra)

#define RBT_ORDER_PRE   1

#define RBT_ORDER_IN    2

#define RBT_ORDER_POST  3

#define RBT_ORDER_MASK  0x00000003

#define rt_prev(tree, node_io, flags) \
        (rt_next((tree), (node_io), (flags) ^ DB_FLAG_REVERSE))

unsigned long rt_init(rb_tree_t *tree, rb_comp_t comp, void *extra);

unsigned long rt_add(rb_tree_t *tree, rb_node_t *node, db_key_t *key);

unsigned long rt_move(rb_tree_t *tree, rb_node_t *node, db_key_t *key);

unsigned long rt_remove(rb_tree_t *tree, rb_node_t *node);

unsigned long rt_find(rb_tree_t *tree, rb_node_t **node_p, db_key_t *key);

unsigned long rt_next(rb_tree_t *tree, rb_node_t **node_io,
                      unsigned long flags);

unsigned long rt_iter(rb_tree_t *tree, rb_node_t *start,
                      rb_iter_t iter_func, void *extra, unsigned long flags);

unsigned long rt_flush(rb_tree_t *tree, rb_iter_t flush_func, void *extra);

struct _rb_node_s {
  unsigned long rn_magic;       
  rb_color_t    rn_color;       
  rb_tree_t    *rn_tree;        
  rb_node_t    *rn_parent;      
  rb_node_t    *rn_left;        
  rb_node_t    *rn_right;       
  db_key_t      rn_key;         
  void         *rn_value;       
};

#define RB_NODE_MAGIC 0x3dea4d01

#define RB_NODE_INIT(value) \
        { RB_NODE_MAGIC, RB_COLOR_NONE, 0, 0, 0, 0, DB_KEY_INIT(0, 0), (value)}

#define rn_verify(node)         ((node) && \
                                 (node)->rn_magic == RB_NODE_MAGIC)

#define rn_color(node)          ((node)->rn_color)

#define rn_tree(node)           ((node)->rn_tree)

#define rn_parent(node)         ((node)->rn_parent)

#define rn_left(node)           ((node)->rn_left)

#define rn_right(node)          ((node)->rn_right)

#define rn_key(node)            (&((node)->rn_key))

#define rn_value(node)          ((node)->rn_value)

#define rn_isblack(node)        (!(node) || (node)->rn_color == RB_COLOR_BLACK)

#define rn_isred(node)          ((node) && (node)->rn_color == RB_COLOR_RED)

#define rn_isleft(node)         ((node)->rn_parent && \
                                 (node)->rn_parent->rn_left == (node))

#define rn_isright(node)        ((node)->rn_parent && \
                                 (node)->rn_parent->rn_right == (node))

unsigned long rn_init(rb_node_t *node, void *value);

DBPRIM_END_C_DECLS

#endif /* __include_dbprim_h__ */

---