From 55dac5fbf2f83e8ca4278fa6fcdbbccbeb1d12cd Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Sun, 21 Sep 2008 15:28:20 +0300 Subject: [PATCH] SilcTree: Replace SilcTreeCompare with SilcCompare Added also new internal, undocumented, macro API for defining all kinds of trees. --- lib/silcutil/silcavltree.c | 12 +++++++----- lib/silcutil/silctree.h | 25 ++++--------------------- lib/silcutil/silctree_i.h | 36 ++++++++++++++++++++++++++++++------ 3 files changed, 41 insertions(+), 32 deletions(-) diff --git a/lib/silcutil/silcavltree.c b/lib/silcutil/silcavltree.c index cef09195..44d313e9 100644 --- a/lib/silcutil/silcavltree.c +++ b/lib/silcutil/silcavltree.c @@ -142,10 +142,10 @@ static int silc_avl_tree_rot_right(SilcTree *tree, SilcTreeHeader *h) /* Find entry */ void *silc_avl_tree_find(SilcTree *tree, void *entry, - SilcTreeCompare compare, void *context) + SilcCompare compare, void *context) { SilcTreeHeader *h; - SilcTreeCompare cmp = compare ? compare : tree->compare; + SilcCompare cmp = compare ? compare : tree->compare; void *cmp_context = compare ? context : tree->context; int ret; @@ -154,10 +154,12 @@ void *silc_avl_tree_find(SilcTree *tree, void *entry, h = tree->root; while (h) { ret = cmp(entry, SILC_TREE_GET_ENTRY(tree, h), cmp_context); - if (!ret) { + if (ret == SILC_COMPARE_EQUAL_TO) { SILC_LOG_DEBUG(("Found %p", SILC_TREE_GET_ENTRY(tree, h))); return SILC_TREE_GET_ENTRY(tree, h); } + if (ret == SILC_COMPARE_STOP) + return NULL; h = ret > 0 ? h->right : h->left; } @@ -199,13 +201,13 @@ SilcBool silc_avl_tree_add(SilcTree *tree, void *entry) } ret = tree->compare(entry, SILC_TREE_GET_ENTRY(tree, h), tree->context); - if (!tree->duplicates && ret == 0) { + if (!tree->duplicates && ret == SILC_COMPARE_EQUAL_TO) { silc_set_errno(SILC_ERR_ALREADY_EXISTS); return FALSE; } /* Duplicate entry, add to list */ - if (ret == 0) { + if (ret == SILC_COMPARE_EQUAL_TO) { q = SILC_TREE_GET_HEADER(tree, entry); q->duplicate = TRUE; q->parent = h; diff --git a/lib/silcutil/silctree.h b/lib/silcutil/silctree.h index e4d3f062..67a92ae3 100644 --- a/lib/silcutil/silctree.h +++ b/lib/silcutil/silctree.h @@ -71,23 +71,6 @@ typedef struct SilcTreeStruct SilcTree; ***/ typedef struct SilcTreeHeaderStruct SilcTreeHeader; -/****f* silcutil/SilcTreeCompare - * - * SYNOPSIS - * - * typedef int (*SilcTreeCompare)(void *entry1, void *entry2, - * void *context); - * - * DESCRIPTION - * - * Callback function of this type is called to compare values in the - * tree. If the `entry1' is smaller, equal to or greater than `entry2' - * this function must return less than, equal to, or greater than zero, - * respectively. - * - ***/ -typedef int (*SilcTreeCompare)(void *entry1, void *entry2, void *context); - /****d* silcutil/SilcTreeType * * NAME @@ -117,7 +100,7 @@ extern DLLAPI const struct SilcTreeOpsStruct silc_tree_avl_ops; * SYNOPSIS * * SilcBool silc_tree_init(SilcTree tree, SilcTreeType type, - * SilcTreeCompare compare, void *context, + * SilcCompare compare, void *context, * SilcUInt16 offset, SilcBool duplicates); * * DESCRIPTION @@ -161,7 +144,7 @@ extern DLLAPI const struct SilcTreeOpsStruct silc_tree_avl_ops; __silc_tree_init(&(tree), type, compare, context, offset, d) static inline SilcBool __silc_tree_init(SilcTree *tree, - SilcTreeType type, SilcTreeCompare compare, + SilcTreeType type, SilcCompare compare, void *context, SilcUInt32 offset, SilcBool duplicates) { @@ -194,7 +177,7 @@ SilcBool __silc_tree_init(SilcTree *tree, * DESCRIPTION * * Add `entry' to the `tree'. Returns TRUE after the entry has been - * added to the tree. If the `tree' does not allocate duplicate entries + * added to the tree. If the `tree' does not allow duplicate entries * this will return FALSE if same value as `entry' is already in the * tree. * @@ -278,7 +261,7 @@ SilcBool __silc_tree_init(SilcTree *tree, * SYNOPSIS * * void *silc_tree_find_ext(SilcTree *tree, void *entry, - * SilcTreeCompare compare, void *context); + * SilcCompare compare, void *context); * * DESCRIPTION * diff --git a/lib/silcutil/silctree_i.h b/lib/silcutil/silctree_i.h index 9f3a6aa3..734c1ce9 100644 --- a/lib/silcutil/silctree_i.h +++ b/lib/silcutil/silctree_i.h @@ -28,16 +28,16 @@ struct SilcTreeOpsStruct { SilcBool (*add)(SilcTree *tree, void *entry); SilcBool (*del)(SilcTree *tree, void *entry); - void *(*find)(SilcTree *tree, void *entry, SilcTreeCompare compare, + void *(*find)(SilcTree *tree, void *entry, SilcCompare compare, void *context); }; /* Generic tree header, present in each entry in tree */ struct SilcTreeHeaderStruct { - struct SilcTreeHeaderStruct *parent; - struct SilcTreeHeaderStruct *left; - struct SilcTreeHeaderStruct *right; - struct SilcTreeHeaderStruct *dup; + struct SilcTreeHeaderStruct *parent; /* Parent of this node */ + struct SilcTreeHeaderStruct *left; /* Left leaft */ + struct SilcTreeHeaderStruct *right; /* Right leaft */ + struct SilcTreeHeaderStruct *dup; /* Duplicates, middle leaf, etc. */ SilcInt16 t; unsigned int duplicate : 1; }; @@ -46,7 +46,7 @@ struct SilcTreeHeaderStruct { struct SilcTreeStruct { const struct SilcTreeOpsStruct *ops; SilcTreeHeader *root; - SilcTreeCompare compare; + SilcCompare compare; void *context; SilcUInt32 count; unsigned int offset : 31; @@ -61,4 +61,28 @@ struct SilcTreeStruct { #define SILC_TREE_GET_ENTRY(tree, pos) \ ((void *)((unsigned char *)(pos) - tree->offset)) +/* Low level undocumented macro API for creating three-leaf binary trees. */ + +#define silc_tree_set_root(tree, root) \ + (tree).root = SILC_TREE_GET_HEADER(&(tree), (root)) +#define silc_tree_set_parent(tree, at, parent) \ + (at)->parent = SILC_TREE_GET_HEADER(&(tree), (parent)) +#define silc_tree_set_left(tree, at, left) \ + (at)->left = SILC_TREE_GET_HEADER(&(tree), (left)) +#define silc_tree_set_middle(tree, at, middle) \ + (at)->dup = SILC_TREE_GET_HEADER(&(tree), (middle)) +#define silc_tree_set_right(tree, at, right) \ + (at)->right = SILC_TREE_GET_HEADER(&(tree), (right)) + +#define silc_tree_get_root(tree) \ + SILC_TREE_GET_ENTRY(&(tree), (tree).root) +#define silc_tree_get_parent(tree, at) \ + SILC_TREE_GET_ENTRY(&(tree), (at)->parent) +#define silc_tree_get_left(tree, at) \ + SILC_TREE_GET_ENTRY(&(tree), (at)->left) +#define silc_tree_get_middle(tree, at) \ + SILC_TREE_GET_ENTRY(&(tree), (at)->middle) +#define silc_tree_get_right(tree, at) \ + SILC_TREE_GET_ENTRY(&(tree), (at)->right) + #endif /* SILCTREE_I_H */ -- 2.24.0