SilcTree: Replace SilcTreeCompare with SilcCompare

Added also new internal, undocumented, macro API for defining all kinds
of trees.

diff --git a/lib/silcutil/silcavltree.c b/lib/silcutil/silcavltree.c
index cef09195d6dd6aa4414f764695ec5a4afb0cd481..44d313e9bd9243a14acb51d1386d0b1cb988d8ca 100644 (file)
--- 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 e4d3f0623a02775d3eaa761d5ba67f98df78e9ba..67a92ae30c37a8cfaeed3a5948fde1e6498830c9 100644 (file)
--- 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 9f3a6aa36607fe21456081dd6e976f62613a7412..734c1ce92b3035d949cf6ae281afb29a83a9acac 100644 (file)
--- 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 */