lib/silcutil/silctree.h

   1 /*
   2
   3   silctree.h
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2008 Pekka Riikonen
   8
   9   This program is free software; you can redistribute it and/or modify
  10   it under the terms of the GNU General Public License as published by
  11   the Free Software Foundation; version 2 of the License.
  12
  13   This program is distributed in the hope that it will be useful,
  14   but WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16   GNU General Public License for more details.
  17
  18 */
  19
  20 /****h* silcutil/Binary Search Tree Interface
  21  *
  22  * DESCRIPTION
  23  *
  24  * Binary Search Tree Interface provides simple interface for adding,
  25  * deleting, retrieving and enumerating items in a tree.  The inteface
  26  * allows also duplicate values in the tree, and it does not allocate any
  27  * memory.  The interface can support many types of binary search trees.
  28  *
  29  * The interface is not thread-safe.  If the same SilcTree context must be
  30  * used in multithreaded environment concurrency control must be employed.
  31  *
  32  ***/
  33
  34 #ifndef SILCTREE_H
  35 #define SILCTREE_H
  36
  37 /****s* silcutil/SilcTree
  38  *
  39  * NAME
  40  *
  41  *    typedef struct SilcTreeStruct SilcTree;
  42  *
  43  * DESCRIPTION
  44  *
  45  *    This is the SilcTree context, and is initialized by calling the
  46  *    function silc_tree_init.  It need not be uninitialized.
  47  *
  48  ***/
  49 typedef struct SilcTreeStruct SilcTree;
  50
  51 /****s* silcutil/SilcTreeHeader
  52  *
  53  * NAME
  54  *
  55  *    typedef struct SilcTreeHeaderStruct SilcTreeHeader;
  56  *
  57  * DESCRIPTION
  58  *
  59  *    This structure must be present in each context that is added to the
  60  *    tree.  The structure can be at any place in the context.
  61  *
  62  * EXAMPLE
  63  *
  64  * // Structure that is going to be added to tree
  65  * typedef struct {
  66  *   SilcTreeHeader header;
  67  *   char *name;
  68  *   int id;
  69  * } FooEntry;
  70  *
  71  ***/
  72 typedef struct SilcTreeHeaderStruct SilcTreeHeader;
  73
  74 /****d* silcutil/SilcTreeType
  75  *
  76  * NAME
  77  *
  78  *    typedef enum { ... } SilcTreeType;
  79  *
  80  * DESCRIPTION
  81  *
  82  *    The supported tree types.
  83  *
  84  * SOURCE
  85  */
  86 typedef enum {
  87   /* AVL Tree.  Automatically balancing binary search tree that provides
  88      excellent performance. */
  89   SILC_TREE_AVL    = 0,
  90 } SilcTreeType;
  91 /***/
  92
  93 #include "silctree_i.h"
  94
  95 /* Tree implementations */
  96 extern DLLAPI const struct SilcTreeOpsStruct silc_tree_avl_ops;
  97
  98 /****f* silcutil/silc_tree_init
  99  *
 100  * SYNOPSIS
 101  *
 102  *    SilcBool silc_tree_init(SilcTree tree, SilcTreeType type,
 103  *                            SilcCompare compare, void *context,
 104  *                            SilcUInt16 offset, SilcBool duplicates);
 105  *
 106  * DESCRIPTION
 107  *
 108  *    Initializes the `tree' as a tree type indicated by `type'.  The
 109  *    `compare' function will be called to compare entries in the tree,
 110  *    for example, when finding entries from the tree.  The `context' is
 111  *    delivered to the callback function.
 112  *
 113  *    The `offset' is the byte offset of the SilcTreeHeader structure field
 114  *    in the entry structure that is going to be added to the tree.  Each
 115  *    structure that is added to the tree must contain SilcTreeHeader
 116  *    structure.  Use silc_offsetof to get the byte offset.
 117  *
 118  *    If the `duplicates' is TRUE the tree will allow the addition of
 119  *    duplicate values.  However, the entry context to be added must not
 120  *    already be in the tree, but its value may be same as some other
 121  *    context's.
 122  *
 123  *    The `tree' need not be uninitialized.  The caller is responsible of
 124  *    freeing the entries it has added to the tree.
 125  *
 126  *    Return FALSE if the `type' is of unknown tree type.  Returns TRUE
 127  *    otherwise.  This function does not allocate any memory.
 128  *
 129  * EXAMPLE
 130  *
 131  * // Structure that is going to be added to tree
 132  * typedef struct {
 133  *   SilcTreeHeader header;
 134  *   char *name;
 135  *   int id;
 136  * } FooEntry;
 137  *
 138  * SilcTree tree;
 139  * silc_tree_init(tree, SILC_TREE_AVL, compare, context,
 140  *                silc_offsetof(FooEntry, header));
 141  *
 142  ***/
 143 #define silc_tree_init(tree, type, compare, context, offset, d) \
 144   __silc_tree_init(&(tree), type, compare, context, offset, d)
 145 static inline
 146 SilcBool __silc_tree_init(SilcTree *tree,
 147                           SilcTreeType type, SilcCompare compare,
 148                           void *context, SilcUInt32 offset,
 149                           SilcBool duplicates)
 150 {
 151   switch (type) {
 152   case SILC_TREE_AVL:
 153     tree->ops = &silc_tree_avl_ops;
 154     break;
 155
 156   default:
 157     return FALSE;
 158     break;
 159   }
 160
 161   tree->root = NULL;
 162   tree->compare = compare;
 163   tree->context = context;
 164   tree->count = 0;
 165   tree->offset = offset;
 166   tree->duplicates = duplicates;
 167
 168   return TRUE;
 169 }
 170
 171 /****f* silcutil/silc_tree_add
 172  *
 173  * SYNOPSIS
 174  *
 175  *    SilcBool silc_tree_add(SilcTree *tree, void *entry);
 176  *
 177  * DESCRIPTION
 178  *
 179  *    Add `entry' to the `tree'.  Returns TRUE after the entry has been
 180  *    added to the tree.  If the `tree' does not allow duplicate entries
 181  *    this will return FALSE if same value as `entry' is already in the
 182  *    tree.
 183  *
 184  * EXAMPLE
 185  *
 186  * FooEntry *client_entry;
 187  *
 188  * client_entry->id = id;
 189  * client_entry->name = name;
 190  * silc_tree_add(tree, client_entry);
 191  *
 192  ***/
 193 #define silc_tree_add(tree, e) (tree).ops->add(&(tree), (e))
 194
 195 /****f* silcutil/silc_tree_del
 196  *
 197  * SYNOPSIS
 198  *
 199  *    SilcBool silc_tree_del(SilcTree *tree, void *entry);
 200  *
 201  * DESCRIPTION
 202  *
 203  *    Delete entry from the `tree'.  If the `entry' is not the actual entry
 204  *    context that was added to the tree but is merely a temporary context
 205  *    it must be memset'ed to zero (0) initially.  The deletion routine will
 206  *    assume that the given `entry' is the actual added entry context if its
 207  *    SilcTreeHeader structure is not zeroed when deleting the entry.  If it
 208  *    is zeroed the deletion will first try to find the entry from the tree
 209  *    and then delete the found entry.  See example for both cases.
 210  *
 211  *    Return FALSE if the entry does not exist in the tree.  Returns TRUE
 212  *    after successful deletion.
 213  *
 214  * EXAMPLE
 215  *
 216  * // Delete the entry, we have access to the originally added context
 217  * silc_tree_del(tree, client_entry);
 218  *
 219  * // Delete client entry with ID 100
 220  * FooEntry tmp;
 221  * memset(&tmp, 0, sizeof(tmp));
 222  * tmp.id = 100;
 223  * silc_tree_del(tree, &tmp);
 224  *
 225  * // Delete all entries from the tree
 226  * while ((entry = silc_tree_enumerate(tree, NULL)))
 227  *   silc_tree_del(tree, entry);
 228  *
 229  ***/
 230 #define silc_tree_del(tree, e) (tree).ops->del(&(tree), (e))
 231
 232 /****f* silcutil/silc_tree_find
 233  *
 234  * SYNOPSIS
 235  *
 236  *    void *silc_tree_find(SilcTree *tree, void *entry);
 237  *
 238  * DESCRIPTION
 239  *
 240  *    Find entry from the tree.  Returns the found entry or NULL if the
 241  *    entry does not exist in the tree and sets silc_errno.
 242  *
 243  *    If there are duplicate values in the tree this will find the first
 244  *    one.  Rest of the duplicate values can be found by calling
 245  *    silc_tree_enumerate_duplicates.  It will stop the enumeration when
 246  *    the last duplicate entry is returned.
 247  *
 248  * EXAMPLE
 249  *
 250  * FooEntry probe, *client_entry;
 251  *
 252  * // Find entry by ID 100
 253  * probe.id = 100;
 254  * client_entry = silc_tree_find(tree, &probe);
 255  *
 256  ***/
 257 #define silc_tree_find(tree, e) (tree).ops->find(&(tree), (e), NULL, NULL)
 258
 259 /****f* silcutil/silc_tree_find_ext
 260  *
 261  * SYNOPSIS
 262  *
 263  *    void *silc_tree_find_ext(SilcTree *tree, void *entry,
 264  *                             SilcCompare compare, void *context);
 265  *
 266  * DESCRIPTION
 267  *
 268  *    Same as silc_tree_find but takes a separate comparison function as
 269  *    argument.
 270  *
 271  ***/
 272 #define silc_tree_find_ext(tree, e, compare, context) \
 273   (tree).ops->find(&(tree), (e), (compare), (context))
 274
 275 /****f* silcutil/silc_tree_count
 276  *
 277  * SYNOPSIS
 278  *
 279  *    SilcUInt32 silc_tree_count(SilcTree *tree);
 280  *
 281  * DESCRIPTION
 282  *
 283  *    Returns the number of entries in the tree.
 284  *
 285  ***/
 286 #define silc_tree_count(tree) (tree).count
 287
 288 /****f* silcutil/silc_tree_minmax
 289  *
 290  * SYNOPSIS
 291  *
 292  *    void *silc_tree_minmax(SilcTree *tree, SilcBool min);
 293  *
 294  * DESCRIPTION
 295  *
 296  *    Returns either smallest or largest value from the `tree'.  If the `min'
 297  *    is TRUE returns the smallest, otherwise returns the largest.  Returns
 298  *    NULL if the tree is empty.
 299  *
 300  ***/
 301 #define silc_tree_minmax(tree, min) __silc_tree_minmax(&(tree), (min))
 302 static inline
 303 void *__silc_tree_minmax(SilcTree *tree, SilcBool min)
 304 {
 305   SilcTreeHeader *h;
 306
 307   h = tree->root;
 308   if (!h)
 309     return NULL;
 310
 311   if (min)
 312     while (h->left)
 313       h = h->left;
 314   else
 315     while (h->right)
 316       h = h->right;
 317
 318   return SILC_TREE_GET_ENTRY(tree, h);
 319 }
 320
 321 /****f* silcutil/silc_tree_enumerate
 322  *
 323  * SYNOPSIS
 324  *
 325  *    void *silc_tree_enumerate(SilcTree *tree, void *at);
 326  *
 327  * DESCRIPTION
 328  *
 329  *    Enumerates the `tree' starting/continuing at the `at'.  When `at' is
 330  *    NULL this will start enumeration from the root of the tree.  The found
 331  *    entry must be given as `at' for next call to continue the enumeration
 332  *    in order.  The enumeration is done in ascending order starting from the
 333  *    smallest value.  If there are duplicates in the tree, their order is
 334  *    undefined.  Returns NULL at the end of the enumeration.
 335  *
 336  * EXAMPLE
 337  *
 338  * // Start enumerating from beginning in order
 339  * for (entry = silc_tree_enumerate(tree, NULL); entry != NULL;
 340  *      entry = silc_tree_enumerate(tree, entry))
 341  *   printf("Client entry %s\n", entry->name);
 342  *
 343  * // Delete all entries from the tree
 344  * while ((entry = silc_tree_enumerate(tree, NULL)))
 345  *   silc_tree_del(tree, entry);
 346  *
 347  ***/
 348 #define silc_tree_enumerate(tree, e) __silc_tree_enumerate(&(tree), (e))
 349 static inline
 350 void *__silc_tree_enumerate(SilcTree *tree, void *at)
 351 {
 352   SilcTreeHeader *h, *p;
 353
 354   if (at == NULL)
 355     return __silc_tree_minmax(tree, TRUE);
 356
 357   h = SILC_TREE_GET_HEADER(tree, at);
 358
 359   if (h->dup)
 360     return SILC_TREE_GET_ENTRY(tree, h->dup);
 361   else if (h->duplicate)
 362     for (h = h->parent; h->duplicate; h = h->parent) ;
 363
 364   if (h->right) {
 365     for (h = h->right; h->left; h = h->left) ;
 366     return SILC_TREE_GET_ENTRY(tree, h);
 367   }
 368
 369   p = h->parent;
 370   while (p && p->right == h) {
 371     h = p;
 372     p = p->parent;
 373   }
 374
 375   return p ? SILC_TREE_GET_ENTRY(tree, p) : NULL;
 376 }
 377
 378 /****f* silcutil/silc_tree_enumerate_duplicates
 379  *
 380  * SYNOPSIS
 381  *
 382  *    void *silc_tree_enumerate_duplicates(SilcTree *tree, void *at);
 383  *
 384  * DESCRIPTION
 385  *
 386  *    Enumerates all duplicate values starting at the `at'.  If `at' is the
 387  *    only one of that value in the tree this will return NULL.  Returns same
 388  *    values as `at' until there are no more and will then return NULL.  The
 389  *    `at' must not be NULL.
 390  *
 391  * EXAMPLE
 392  *
 393  * // Find all entries of ID 100
 394  * probe.id = 100;
 395  * entry = silc_tree_find(tree, &probe);
 396  * printf("Entry %p ID %d\n", entry, entry->id);
 397  * while ((entry = silc_tree_enumerate_duplicates(tree, entry)))
 398  *   printf("Entry %p ID %d\n", entry, entry->id);
 399  *
 400  ***/
 401 #define silc_tree_enumerate_duplicates(tree, e) \
 402   __silc_tree_enumerate_dup(&(tree), (e))
 403 static inline
 404 void *__silc_tree_enumerate_dup(SilcTree *tree, void *at)
 405 {
 406   SilcTreeHeader *h = SILC_TREE_GET_HEADER(tree, at);
 407   return h->dup ? SILC_TREE_GET_ENTRY(tree, h->dup) : NULL;
 408 }
 409
 410 #endif /* SILCTREE_H */