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 /****f* silcutil/SilcTreeCompare
  75  *
  76  * SYNOPSIS
  77  *
  78  *    typedef int (*SilcTreeCompare)(void *entry1, void *entry2,
  79  *                                   void *context);
  80  *
  81  * DESCRIPTION
  82  *
  83  *    Callback function of this type is called to compare values in the
  84  *    tree.  If the `entry1' is smaller, equal to or greater than `entry2'
  85  *    this function must return less than, equal to, or greater than zero,
  86  *    respectively.
  87  *
  88  ***/
  89 typedef int (*SilcTreeCompare)(void *entry1, void *entry2, void *context);
  90
  91 /****d* silcutil/SilcTreeType
  92  *
  93  * NAME
  94  *
  95  *    typedef enum { ... } SilcTreeType;
  96  *
  97  * DESCRIPTION
  98  *
  99  *    The supported tree types.
 100  *
 101  * SOURCE
 102  */
 103 typedef enum {
 104   /* AVL Tree.  Automatically balancing binary search tree that provides
 105      excellent performance. */
 106   SILC_TREE_AVL    = 0,
 107 } SilcTreeType;
 108 /***/
 109
 110 #include "silctree_i.h"
 111
 112 /* Tree implementations */
 113 extern DLLAPI const struct SilcTreeOpsStruct silc_tree_avl_ops;
 114
 115 /****f* silcutil/silc_tree_init
 116  *
 117  * SYNOPSIS
 118  *
 119  *    SilcBool silc_tree_init(SilcTree tree, SilcTreeType type,
 120  *                            SilcTreeCompare compare, void *context,
 121  *                            SilcUInt16 offset, SilcBool duplicates);
 122  *
 123  * DESCRIPTION
 124  *
 125  *    Initializes the `tree' as a tree type indicated by `type'.  The
 126  *    `compare' function will be called to compare entries in the tree,
 127  *    for example, when finding entries from the tree.  The `context' is
 128  *    delivered to the callback function.
 129  *
 130  *    The `offset' is the byte offset of the SilcTreeHeader structure field
 131  *    in the entry structure that is going to be added to the tree.  Each
 132  *    structure that is added to the tree must contain SilcTreeHeader
 133  *    structure.  Use silc_offsetof to get the byte offset.
 134  *
 135  *    If the `duplicates' is TRUE the tree will allow the addition of
 136  *    duplicate values.  However, the entry context to be added must not
 137  *    already be in the tree, but its value may be same as some other
 138  *    context's.
 139  *
 140  *    The `tree' need not be uninitialized.  The caller is responsible of
 141  *    freeing the entries it has added to the tree.
 142  *
 143  *    Return FALSE if the `type' is of unknown tree type.  Returns TRUE
 144  *    otherwise.  This function does not allocate any memory.
 145  *
 146  * EXAMPLE
 147  *
 148  * // Structure that is going to be added to tree
 149  * typedef struct {
 150  *   SilcTreeHeader header;
 151  *   char *name;
 152  *   int id;
 153  * } FooEntry;
 154  *
 155  * SilcTree tree;
 156  * silc_tree_init(tree, SILC_TREE_AVL, compare, context,
 157  *                silc_offsetof(FooEntry, header));
 158  *
 159  ***/
 160 #define silc_tree_init(tree, type, compare, context, offset, d) \
 161   __silc_tree_init(&(tree), type, compare, context, offset, d)
 162 static inline
 163 SilcBool __silc_tree_init(SilcTree *tree,
 164                           SilcTreeType type, SilcTreeCompare compare,
 165                           void *context, SilcUInt32 offset,
 166                           SilcBool duplicates)
 167 {
 168   switch (type) {
 169   case SILC_TREE_AVL:
 170     tree->ops = &silc_tree_avl_ops;
 171     break;
 172
 173   default:
 174     return FALSE;
 175     break;
 176   }
 177
 178   tree->root = NULL;
 179   tree->compare = compare;
 180   tree->context = context;
 181   tree->count = 0;
 182   tree->offset = offset;
 183   tree->duplicates = duplicates;
 184
 185   return TRUE;
 186 }
 187
 188 /****f* silcutil/silc_tree_add
 189  *
 190  * SYNOPSIS
 191  *
 192  *    SilcBool silc_tree_add(SilcTree *tree, void *entry);
 193  *
 194  * DESCRIPTION
 195  *
 196  *    Add `entry' to the `tree'.  Returns TRUE after the entry has been
 197  *    added to the tree.  If the `tree' does not allocate duplicate entries
 198  *    this will return FALSE if same value as `entry' is already in the
 199  *    tree.
 200  *
 201  * EXAMPLE
 202  *
 203  * FooEntry *client_entry;
 204  *
 205  * client_entry->id = id;
 206  * client_entry->name = name;
 207  * silc_tree_add(tree, client_entry);
 208  *
 209  ***/
 210 #define silc_tree_add(tree, e) (tree).ops->add(&(tree), (e))
 211
 212 /****f* silcutil/silc_tree_del
 213  *
 214  * SYNOPSIS
 215  *
 216  *    SilcBool silc_tree_del(SilcTree *tree, void *entry);
 217  *
 218  * DESCRIPTION
 219  *
 220  *    Delete entry from the `tree'.  If the `entry' is not the actual entry
 221  *    context that was added to the tree but is merely a temporary context
 222  *    it must be memset'ed to zero (0) initially.  The deletion routine will
 223  *    assume that the given `entry' is the actual added entry context if its
 224  *    SilcTreeHeader structure is not zeroed when deleting the entry.  If it
 225  *    is zeroed the deletion will first try to find the entry from the tree
 226  *    and then delete the found entry.  See example for both cases.
 227  *
 228  *    Return FALSE if the entry does not exist in the tree.  Returns TRUE
 229  *    after successful deletion.
 230  *
 231  * EXAMPLE
 232  *
 233  * // Delete the entry, we have access to the originally added context
 234  * silc_tree_del(tree, client_entry);
 235  *
 236  * // Delete client entry with ID 100
 237  * FooEntry tmp;
 238  * memset(&tmp, 0, sizeof(tmp));
 239  * tmp.id = 100;
 240  * silc_tree_del(tree, &tmp);
 241  *
 242  * // Delete all entries from the tree
 243  * while ((entry = silc_tree_enumerate(tree, NULL)))
 244  *   silc_tree_del(tree, entry);
 245  *
 246  ***/
 247 #define silc_tree_del(tree, e) (tree).ops->del(&(tree), (e))
 248
 249 /****f* silcutil/silc_tree_find
 250  *
 251  * SYNOPSIS
 252  *
 253  *    void *silc_tree_find(SilcTree *tree, void *entry);
 254  *
 255  * DESCRIPTION
 256  *
 257  *    Find entry from the tree.  Returns the found entry or NULL if the
 258  *    entry does not exist in the tree and sets silc_errno.
 259  *
 260  *    If there are duplicate values in the tree this will find the first
 261  *    one.  Rest of the duplicate values can be found by calling
 262  *    silc_tree_enumerate_duplicates.  It will stop the enumeration when
 263  *    the last duplicate entry is returned.
 264  *
 265  * EXAMPLE
 266  *
 267  * FooEntry probe, *client_entry;
 268  *
 269  * // Find entry by ID 100
 270  * probe.id = 100;
 271  * client_entry = silc_tree_find(tree, &probe);
 272  *
 273  ***/
 274 #define silc_tree_find(tree, e) (tree).ops->find(&(tree), (e), NULL, NULL)
 275
 276 /****f* silcutil/silc_tree_find_ext
 277  *
 278  * SYNOPSIS
 279  *
 280  *    void *silc_tree_find_ext(SilcTree *tree, void *entry,
 281  *                             SilcTreeCompare compare, void *context);
 282  *
 283  * DESCRIPTION
 284  *
 285  *    Same as silc_tree_find but takes a separate comparison function as
 286  *    argument.
 287  *
 288  ***/
 289 #define silc_tree_find_ext(tree, e, compare, context) \
 290   (tree).ops->find(&(tree), (e), (compare), (context))
 291
 292 /****f* silcutil/silc_tree_count
 293  *
 294  * SYNOPSIS
 295  *
 296  *    SilcUInt32 silc_tree_count(SilcTree *tree);
 297  *
 298  * DESCRIPTION
 299  *
 300  *    Returns the number of entries in the tree.
 301  *
 302  ***/
 303 #define silc_tree_count(tree) (tree).count
 304
 305 /****f* silcutil/silc_tree_minmax
 306  *
 307  * SYNOPSIS
 308  *
 309  *    void *silc_tree_minmax(SilcTree *tree, SilcBool min);
 310  *
 311  * DESCRIPTION
 312  *
 313  *    Returns either smallest or largest value from the `tree'.  If the `min'
 314  *    is TRUE returns the smallest, otherwise returns the largest.  Returns
 315  *    NULL if the tree is empty.
 316  *
 317  ***/
 318 #define silc_tree_minmax(tree, min) __silc_tree_minmax(&(tree), (min))
 319 static inline
 320 void *__silc_tree_minmax(SilcTree *tree, SilcBool min)
 321 {
 322   SilcTreeHeader *h;
 323
 324   h = tree->root;
 325   if (!h)
 326     return NULL;
 327
 328   if (min)
 329     while (h->left)
 330       h = h->left;
 331   else
 332     while (h->right)
 333       h = h->right;
 334
 335   return SILC_TREE_GET_ENTRY(tree, h);
 336 }
 337
 338 /****f* silcutil/silc_tree_enumerate
 339  *
 340  * SYNOPSIS
 341  *
 342  *    void *silc_tree_enumerate(SilcTree *tree, void *at);
 343  *
 344  * DESCRIPTION
 345  *
 346  *    Enumerates the `tree' starting/continuing at the `at'.  When `at' is
 347  *    NULL this will start enumeration from the root of the tree.  The found
 348  *    entry must be given as `at' for next call to continue the enumeration
 349  *    in order.  The enumeration is done in ascending order starting from the
 350  *    smallest value.  If there are duplicates in the tree, their order is
 351  *    undefined.  Returns NULL at the end of the enumeration.
 352  *
 353  * EXAMPLE
 354  *
 355  * // Start enumerating from beginning in order
 356  * for (entry = silc_tree_enumerate(tree, NULL); entry != NULL;
 357  *      entry = silc_tree_enumerate(tree, entry))
 358  *   printf("Client entry %s\n", entry->name);
 359  *
 360  * // Delete all entries from the tree
 361  * while ((entry = silc_tree_enumerate(tree, NULL)))
 362  *   silc_tree_del(tree, entry);
 363  *
 364  ***/
 365 #define silc_tree_enumerate(tree, e) __silc_tree_enumerate(&(tree), (e))
 366 static inline
 367 void *__silc_tree_enumerate(SilcTree *tree, void *at)
 368 {
 369   SilcTreeHeader *h, *p;
 370
 371   if (at == NULL)
 372     return __silc_tree_minmax(tree, TRUE);
 373
 374   h = SILC_TREE_GET_HEADER(tree, at);
 375
 376   if (h->dup)
 377     return SILC_TREE_GET_ENTRY(tree, h->dup);
 378   else if (h->duplicate)
 379     for (h = h->parent; h->duplicate; h = h->parent) ;
 380
 381   if (h->right) {
 382     for (h = h->right; h->left; h = h->left) ;
 383     return SILC_TREE_GET_ENTRY(tree, h);
 384   }
 385
 386   p = h->parent;
 387   while (p && p->right == h) {
 388     h = p;
 389     p = p->parent;
 390   }
 391
 392   return p ? SILC_TREE_GET_ENTRY(tree, p) : NULL;
 393 }
 394
 395 /****f* silcutil/silc_tree_enumerate_duplicates
 396  *
 397  * SYNOPSIS
 398  *
 399  *    void *silc_tree_enumerate_duplicates(SilcTree *tree, void *at);
 400  *
 401  * DESCRIPTION
 402  *
 403  *    Enumerates all duplicate values starting at the `at'.  If `at' is the
 404  *    only one of that value in the tree this will return NULL.  Returns same
 405  *    values as `at' until there are no more and will then return NULL.  The
 406  *    `at' must not be NULL.
 407  *
 408  * EXAMPLE
 409  *
 410  * // Find all entries of ID 100
 411  * probe.id = 100;
 412  * entry = silc_tree_find(tree, &probe);
 413  * printf("Entry %p ID %d\n", entry, entry->id);
 414  * while ((entry = silc_tree_enumerate_duplicates(tree, entry)))
 415  *   printf("Entry %p ID %d\n", entry, entry->id);
 416  *
 417  ***/
 418 #define silc_tree_enumerate_duplicates(tree, e) \
 419   __silc_tree_enumerate_dup(&(tree), (e))
 420 static inline
 421 void *__silc_tree_enumerate_dup(SilcTree *tree, void *at)
 422 {
 423   SilcTreeHeader *h = SILC_TREE_GET_HEADER(tree, at);
 424   return h->dup ? SILC_TREE_GET_ENTRY(tree, h->dup) : NULL;
 425 }
 426
 427 #endif /* SILCTREE_H */