I don't much like this method - IMO, it obfuscates the #include directive.
That said, however, I implemented a generic AVL tree implementation using a
similar idea. Basically, I define a couple of MACROs: AVL_FIND and
AVL_FINDWITHSTACK (needed by AVL trees to do a bottom-up insert/delete).
These macros take a compare function as a parameter. If the compare
function is declared as inline, or if it is a macro, it will be compiled
inline and without the overhead of a call instruction.
I'm including a sample usage, plus an excerpt from my avltree.h header file
- just to give a sample of how I would implement generic trees.
I can provide more code upon request. I've got inserts working, but
removes are becoming a myriad of special cases..
Note: I tried to be "clever", and store the tree height in the low-order
bytes of a pointer. It works, but it's pretty ugly.
-Kevin
============= Sample application usage ===============
struct hrmm {
int num;
avl_node_t treenode;
};
static inline int
mycmp(avl_node_t *x, avl_node_t *y)
{
int a,b;
a = avl_entry(x, struct hrmm, treenode)->num;
b = avl_entry(y, struct hrmm, treenode)->num;
return (a < b ? -1 : a > b ? 1 : 0);
}
int
my_insert(avl_node_t **tree, struct hrmm *node)
{
return AVL_INSERT(tree,&node->treenode,mycmp);
}
int
my_remove(avl_node_t **tree, struct hrmm *node)
{
return AVL_REMOVE(tree,&node->treenode,mycmp);
}
struct hrmm *
my_find(avl_node_t *tree, struct hrmm *node)
{
return avl_entry(AVL_FIND(tree,&node->treenode,mycmp)
, struct hrmm, treenode);
}
============= Macros from header file ===============
#define AVL_FIND(__Tree,__Node,__Compare) ({ \
avl_node_t *__tree = (__Tree); \
\
while (__tree) { \
int __compval = __Compare((__Node),__tree); \
\
if (__compval < 0) { \
__tree = getChild(__tree, TREE_LEFT); \
} else if (__compval > 0) { \
__tree = getChild(__tree, TREE_RIGHT); \
} else { \
break; \
} \
} \
__tree;})
#define AVL_FINDWITHSTACK(__TreeP,__Node,__Stack,__Count,__Compare) ({ \
avl_node_t **__tree = (__TreeP), *__tmp; \
avl_dptr_t *__stack = (__Stack); \
int *__count = (__Count), __found=0; \
\
__tmp = *__tree; \
*__count = 0; \
__stack[0] = (avl_dptr_t) __tree; \
while (__tmp) { \
int __compval = __Compare((__Node), __tmp); \
\
if (__compval < 0) { \
(*__count)++; \
setPtr(&__stack[*__count], __tmp, TREE_LEFT); \
__tmp = getChild(__tmp, TREE_LEFT); \
} else if (__compval > 0) { \
(*__count)++; \
setPtr(&__stack[*__count], __tmp, TREE_RIGHT); \
__tmp = getChild(__tmp, TREE_RIGHT); \
} else { \
__found = 1; \
break; \
} \
} \
__found;})
#define AVL_REMOVE(__TreeP,__Node,__Compare) ({ \
avl_dptr_t __stk[AVL_MAXHEIGHT]; \
int __cnt, __ret; \
\
if (! AVL_FINDWITHSTACK((__TreeP),(__Node) \
,__stk,&__cnt,__Compare)) { \
__ret = 0; \
} else { \
avl_remove(__stk, __cnt); \
__ret = 1; \
} \
__ret;})
#define AVL_INSERT(__TreeP,__Node,__Compare) ({ \
avl_dptr_t __stk[AVL_MAXHEIGHT]; \
int __cnt, __ret; \
\
if (AVL_FINDWITHSTACK((__TreeP),(__Node) \
,__stk,&__cnt,__Compare)) { \
__ret = 0; \
} else { \
avl_insert((__Node), __stk, __cnt); \
__ret = 1; \
} \
__ret;})
-- ------------------------------------------------------------------------ | Kevin O'Connor "BTW, IMHO we need a FAQ for | | koconnor@cse.buffalo.edu 'IMHO', 'FAQ', 'BTW', etc. !" | ------------------------------------------------------------------------- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/