lkml.org 
[lkml]   [1999]   [Nov]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [patch] rbtrees [was Re: AVL trees vs. Red-Black trees]
On Mon, Nov 29, 1999 at 08:18:17PM +0100, Manfred Spraul wrote:
> What about something similar to the "end_request()" implementation?
>
> ie you #define a name and the (inline) compare function, then you
> #include <rbtree.h>. <rbtree.h> creates all functions that you need.

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/

\
 
 \ /
  Last update: 2005-03-22 13:55    [W:1.306 / U:0.104 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site