Daniel raised a good point about it being naughty that all our AVL trees
have an open coded lookup function.
On the other hand, there was originally a desire to have lookups code as
fast as possible, with an inline comparison function.
What if we did the following in avltree.h:
/*
* 'pparent', 'unbalanced' and 'is_left' are only used for
* insertions. Normally GCC will notice this and get rid of them for
* lookups.
*/
static inline struct avltree_node *do_lookup(const struct avltree_node *key,
const struct avltree *tree,
struct avltree_node **pparent,
struct avltree_node
**unbalanced,
int *is_left,
avltree_cmp_fn_t cmp_fn)
{
struct avltree_node *node = tree->root;
int res = 0;
*pparent = NULL;
*unbalanced = node;
*is_left = 0;
while (node) {
if (get_balance(node) != 0)
*unbalanced = node;
res = cmp_fn(node, key);
if (res == 0)
return node;
*pparent = node;
if ((*is_left = res > 0))
node = node->left;
else
node = node->right;
}
return NULL;
}
static inline
struct avltree_node *avltree_lookup(const struct avltree_node *key,
const struct avltree *tree,
avltree_cmp_fn_t cmp_fn)
{
struct avltree_node *parent, *unbalanced;
int is_left;
return do_lookup(key, tree, &parent, &unbalanced, &is_left, cmp_fn);
}
With a given table defining an inline compare function, that allows it's
lookup calls to be completely inlined (with code that really is pretty
suitable for inlining).
If we wanted to make all uses of cmp_fn inline, avltree_insert could be
broken out as:
struct avltree_node *avltree_do_insert(struct avltree_node *node,
struct avltree *tree,
struct avltree_node *key,
struct avltree_node *parent,
struct avltree_node *unbalanced,
int is_left)
static inline
struct avltree_node *avltree_insert(struct avltree_node *node,
struct avltree *tree,
avltree_cmp_fn_t cmp_fn)
{
struct avltree_node *key, *parent, *unbalanced;
int is_left;
key = do_lookup(node, tree, &parent, &unbalanced, &is_left, cmp_fn);
if (key)
return key;
return avltree_do_insert(node, tree, key, parent, unbalanced,
is_left);
}
We then remove cmp_fn from struct avltree (it is also used in avltree_inf
and avltree_sup, but those functions will go away with the removal of the
old dirent cache).
Frank
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
------------------------------------------------------------------------------
Announcing the Oxford Dictionaries API! The API offers world-renowned
dictionary content that is easy and intuitive to access. Sign up for an
account today to start using our lexical data to power your apps and
projects. Get started today and enter our developer competition.
http://sdm.link/oxford
_______________________________________________
Nfs-ganesha-devel mailing list
Nfs-ganesha-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nfs-ganesha-devel
