--- /dev/null
+/*
+
+ 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 */
projects / runtime.git / blobdiff