X-Git-Url: http://git.silcnet.org/gitweb/?p=runtime.git;a=blobdiff_plain;f=lib%2Fsilcutil%2Fsilctree.h;fp=lib%2Fsilcutil%2Fsilctree.h;h=e4d3f0623a02775d3eaa761d5ba67f98df78e9ba;hp=0000000000000000000000000000000000000000;hb=a6428c51f8544ca92870eb573f8a7bc7d1e16d19;hpb=0ec0cbbedc2ec9ab76aa1073b30572288441e9c9

diff --git a/lib/silcutil/silctree.h b/lib/silcutil/silctree.h
new file mode 100644
index 00000000..e4d3f062
--- /dev/null
+++ b/lib/silcutil/silctree.h
@@ -0,0 +1,427 @@
+/*
+
+  silctree.h
+
+  Author: Pekka Riikonen <priikone@silcnet.org>
+
+  Copyright (C) 2008 Pekka Riikonen
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; version 2 of the License.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+*/
+
+/****h* silcutil/Binary Search Tree Interface
+ *
+ * DESCRIPTION
+ *
+ * Binary Search Tree Interface provides simple interface for adding,
+ * deleting, retrieving and enumerating items in a tree.  The inteface
+ * allows also duplicate values in the tree, and it does not allocate any
+ * memory.  The interface can support many types of binary search trees.
+ *
+ * The interface is not thread-safe.  If the same SilcTree context must be
+ * used in multithreaded environment concurrency control must be employed.
+ *
+ ***/
+
+#ifndef SILCTREE_H
+#define SILCTREE_H
+
+/****s* silcutil/SilcTree
+ *
+ * NAME
+ *
+ *    typedef struct SilcTreeStruct SilcTree;
+ *
+ * DESCRIPTION
+ *
+ *    This is the SilcTree context, and is initialized by calling the
+ *    function silc_tree_init.  It need not be uninitialized.
+ *
+ ***/
+typedef struct SilcTreeStruct SilcTree;
+
+/****s* silcutil/SilcTreeHeader
+ *
+ * NAME
+ *
+ *    typedef struct SilcTreeHeaderStruct SilcTreeHeader;
+ *
+ * DESCRIPTION
+ *
+ *    This structure must be present in each context that is added to the
+ *    tree.  The structure can be at any place in the context.
+ *
+ * EXAMPLE
+ *
+ * // Structure that is going to be added to tree
+ * typedef struct {
+ *   SilcTreeHeader header;
+ *   char *name;
+ *   int id;
+ * } FooEntry;
+ *
+ ***/
+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
+ *
+ *    typedef enum { ... } SilcTreeType;
+ *
+ * DESCRIPTION
+ *
+ *    The supported tree types.
+ *
+ * SOURCE
+ */
+typedef enum {
+  /* AVL Tree.  Automatically balancing binary search tree that provides
+     excellent performance. */
+  SILC_TREE_AVL    = 0,
+} SilcTreeType;
+/***/
+
+#include "silctree_i.h"
+
+/* Tree implementations */
+extern DLLAPI const struct SilcTreeOpsStruct silc_tree_avl_ops;
+
+/****f* silcutil/silc_tree_init
+ *
+ * SYNOPSIS
+ *
+ *    SilcBool silc_tree_init(SilcTree tree, SilcTreeType type,
+ *                            SilcTreeCompare compare, void *context,
+ *                            SilcUInt16 offset, SilcBool duplicates);
+ *
+ * DESCRIPTION
+ *
+ *    Initializes the `tree' as a tree type indicated by `type'.  The
+ *    `compare' function will be called to compare entries in the tree,
+ *    for example, when finding entries from the tree.  The `context' is
+ *    delivered to the callback function.
+ *
+ *    The `offset' is the byte offset of the SilcTreeHeader structure field
+ *    in the entry structure that is going to be added to the tree.  Each
+ *    structure that is added to the tree must contain SilcTreeHeader
+ *    structure.  Use silc_offsetof to get the byte offset.
+ *
+ *    If the `duplicates' is TRUE the tree will allow the addition of
+ *    duplicate values.  However, the entry context to be added must not
+ *    already be in the tree, but its value may be same as some other
+ *    context's.
+ *
+ *    The `tree' need not be uninitialized.  The caller is responsible of
+ *    freeing the entries it has added to the tree.
+ *
+ *    Return FALSE if the `type' is of unknown tree type.  Returns TRUE
+ *    otherwise.  This function does not allocate any memory.
+ *
+ * EXAMPLE
+ *
+ * // Structure that is going to be added to tree
+ * typedef struct {
+ *   SilcTreeHeader header;
+ *   char *name;
+ *   int id;
+ * } FooEntry;
+ *
+ * SilcTree tree;
+ * silc_tree_init(tree, SILC_TREE_AVL, compare, context,
+ *                silc_offsetof(FooEntry, header));
+ *
+ ***/
+#define silc_tree_init(tree, type, compare, context, offset, d)	\
+  __silc_tree_init(&(tree), type, compare, context, offset, d)
+static inline
+SilcBool __silc_tree_init(SilcTree *tree,
+			  SilcTreeType type, SilcTreeCompare compare,
+			  void *context, SilcUInt32 offset,
+			  SilcBool duplicates)
+{
+  switch (type) {
+  case SILC_TREE_AVL:
+    tree->ops = &silc_tree_avl_ops;
+    break;
+
+  default:
+    return FALSE;
+    break;
+  }
+
+  tree->root = NULL;
+  tree->compare = compare;
+  tree->context = context;
+  tree->count = 0;
+  tree->offset = offset;
+  tree->duplicates = duplicates;
+
+  return TRUE;
+}
+
+/****f* silcutil/silc_tree_add
+ *
+ * SYNOPSIS
+ *
+ *    SilcBool silc_tree_add(SilcTree *tree, void *entry);
+ *
+ * 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
+ *    this will return FALSE if same value as `entry' is already in the
+ *    tree.
+ *
+ * EXAMPLE
+ *
+ * FooEntry *client_entry;
+ *
+ * client_entry->id = id;
+ * client_entry->name = name;
+ * silc_tree_add(tree, client_entry);
+ *
+ ***/
+#define silc_tree_add(tree, e) (tree).ops->add(&(tree), (e))
+
+/****f* silcutil/silc_tree_del
+ *
+ * SYNOPSIS
+ *
+ *    SilcBool silc_tree_del(SilcTree *tree, void *entry);
+ *
+ * DESCRIPTION
+ *
+ *    Delete entry from the `tree'.  If the `entry' is not the actual entry
+ *    context that was added to the tree but is merely a temporary context
+ *    it must be memset'ed to zero (0) initially.  The deletion routine will
+ *    assume that the given `entry' is the actual added entry context if its
+ *    SilcTreeHeader structure is not zeroed when deleting the entry.  If it
+ *    is zeroed the deletion will first try to find the entry from the tree
+ *    and then delete the found entry.  See example for both cases.
+ *
+ *    Return FALSE if the entry does not exist in the tree.  Returns TRUE
+ *    after successful deletion.
+ *
+ * EXAMPLE
+ *
+ * // Delete the entry, we have access to the originally added context
+ * silc_tree_del(tree, client_entry);
+ *
+ * // Delete client entry with ID 100
+ * FooEntry tmp;
+ * memset(&tmp, 0, sizeof(tmp));
+ * tmp.id = 100;
+ * silc_tree_del(tree, &tmp);
+ *
+ * // Delete all entries from the tree
+ * while ((entry = silc_tree_enumerate(tree, NULL)))
+ *   silc_tree_del(tree, entry);
+ *
+ ***/
+#define silc_tree_del(tree, e) (tree).ops->del(&(tree), (e))
+
+/****f* silcutil/silc_tree_find
+ *
+ * SYNOPSIS
+ *
+ *    void *silc_tree_find(SilcTree *tree, void *entry);
+ *
+ * DESCRIPTION
+ *
+ *    Find entry from the tree.  Returns the found entry or NULL if the
+ *    entry does not exist in the tree and sets silc_errno.
+ *
+ *    If there are duplicate values in the tree this will find the first
+ *    one.  Rest of the duplicate values can be found by calling
+ *    silc_tree_enumerate_duplicates.  It will stop the enumeration when
+ *    the last duplicate entry is returned.
+ *
+ * EXAMPLE
+ *
+ * FooEntry probe, *client_entry;
+ *
+ * // Find entry by ID 100
+ * probe.id = 100;
+ * client_entry = silc_tree_find(tree, &probe);
+ *
+ ***/
+#define silc_tree_find(tree, e) (tree).ops->find(&(tree), (e), NULL, NULL)
+
+/****f* silcutil/silc_tree_find_ext
+ *
+ * SYNOPSIS
+ *
+ *    void *silc_tree_find_ext(SilcTree *tree, void *entry,
+ *                             SilcTreeCompare compare, void *context);
+ *
+ * DESCRIPTION
+ *
+ *    Same as silc_tree_find but takes a separate comparison function as
+ *    argument.
+ *
+ ***/
+#define silc_tree_find_ext(tree, e, compare, context) \
+  (tree).ops->find(&(tree), (e), (compare), (context))
+
+/****f* silcutil/silc_tree_count
+ *
+ * SYNOPSIS
+ *
+ *    SilcUInt32 silc_tree_count(SilcTree *tree);
+ *
+ * DESCRIPTION
+ *
+ *    Returns the number of entries in the tree.
+ *
+ ***/
+#define silc_tree_count(tree) (tree).count
+
+/****f* silcutil/silc_tree_minmax
+ *
+ * SYNOPSIS
+ *
+ *    void *silc_tree_minmax(SilcTree *tree, SilcBool min);
+ *
+ * DESCRIPTION
+ *
+ *    Returns either smallest or largest value from the `tree'.  If the `min'
+ *    is TRUE returns the smallest, otherwise returns the largest.  Returns
+ *    NULL if the tree is empty.
+ *
+ ***/
+#define silc_tree_minmax(tree, min) __silc_tree_minmax(&(tree), (min))
+static inline
+void *__silc_tree_minmax(SilcTree *tree, SilcBool min)
+{
+  SilcTreeHeader *h;
+
+  h = tree->root;
+  if (!h)
+    return NULL;
+
+  if (min)
+    while (h->left)
+      h = h->left;
+  else
+    while (h->right)
+      h = h->right;
+
+  return SILC_TREE_GET_ENTRY(tree, h);
+}
+
+/****f* silcutil/silc_tree_enumerate
+ *
+ * SYNOPSIS
+ *
+ *    void *silc_tree_enumerate(SilcTree *tree, void *at);
+ *
+ * DESCRIPTION
+ *
+ *    Enumerates the `tree' starting/continuing at the `at'.  When `at' is
+ *    NULL this will start enumeration from the root of the tree.  The found
+ *    entry must be given as `at' for next call to continue the enumeration
+ *    in order.  The enumeration is done in ascending order starting from the
+ *    smallest value.  If there are duplicates in the tree, their order is
+ *    undefined.  Returns NULL at the end of the enumeration.
+ *
+ * EXAMPLE
+ *
+ * // Start enumerating from beginning in order
+ * for (entry = silc_tree_enumerate(tree, NULL); entry != NULL;
+ *      entry = silc_tree_enumerate(tree, entry))
+ *   printf("Client entry %s\n", entry->name);
+ *
+ * // Delete all entries from the tree
+ * while ((entry = silc_tree_enumerate(tree, NULL)))
+ *   silc_tree_del(tree, entry);
+ *
+ ***/
+#define silc_tree_enumerate(tree, e) __silc_tree_enumerate(&(tree), (e))
+static inline
+void *__silc_tree_enumerate(SilcTree *tree, void *at)
+{
+  SilcTreeHeader *h, *p;
+
+  if (at == NULL)
+    return __silc_tree_minmax(tree, TRUE);
+
+  h = SILC_TREE_GET_HEADER(tree, at);
+
+  if (h->dup)
+    return SILC_TREE_GET_ENTRY(tree, h->dup);
+  else if (h->duplicate)
+    for (h = h->parent; h->duplicate; h = h->parent) ;
+
+  if (h->right) {
+    for (h = h->right; h->left; h = h->left) ;
+    return SILC_TREE_GET_ENTRY(tree, h);
+  }
+
+  p = h->parent;
+  while (p && p->right == h) {
+    h = p;
+    p = p->parent;
+  }
+
+  return p ? SILC_TREE_GET_ENTRY(tree, p) : NULL;
+}
+
+/****f* silcutil/silc_tree_enumerate_duplicates
+ *
+ * SYNOPSIS
+ *
+ *    void *silc_tree_enumerate_duplicates(SilcTree *tree, void *at);
+ *
+ * DESCRIPTION
+ *
+ *    Enumerates all duplicate values starting at the `at'.  If `at' is the
+ *    only one of that value in the tree this will return NULL.  Returns same
+ *    values as `at' until there are no more and will then return NULL.  The
+ *    `at' must not be NULL.
+ *
+ * EXAMPLE
+ *
+ * // Find all entries of ID 100
+ * probe.id = 100;
+ * entry = silc_tree_find(tree, &probe);
+ * printf("Entry %p ID %d\n", entry, entry->id);
+ * while ((entry = silc_tree_enumerate_duplicates(tree, entry)))
+ *   printf("Entry %p ID %d\n", entry, entry->id);
+ *
+ ***/
+#define silc_tree_enumerate_duplicates(tree, e) \
+  __silc_tree_enumerate_dup(&(tree), (e))
+static inline
+void *__silc_tree_enumerate_dup(SilcTree *tree, void *at)
+{
+  SilcTreeHeader *h = SILC_TREE_GET_HEADER(tree, at);
+  return h->dup ? SILC_TREE_GET_ENTRY(tree, h->dup) : NULL;
+}
+
+#endif /* SILCTREE_H */