lib/silcutil/silctree_i.h

   1 /*
   2
   3   silctree_i.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 #ifndef SILCTREE_I_H
  21 #define SILCTREE_I_H
  22
  23 #ifndef SILCTREE_H
  24 #error "Do not include this header directly"
  25 #endif
  26
  27 /* Tree operatins header */
  28 struct SilcTreeOpsStruct {
  29   SilcBool (*add)(SilcTree *tree, void *entry);
  30   SilcBool (*del)(SilcTree *tree, void *entry);
  31   void *(*find)(SilcTree *tree, void *entry, SilcCompare compare,
  32                 void *context);
  33 };
  34
  35 /* Generic tree header, present in each entry in tree */
  36 struct SilcTreeHeaderStruct {
  37   struct SilcTreeHeaderStruct *parent;     /* Parent of this node */
  38   struct SilcTreeHeaderStruct *left;       /* Left leaft */
  39   struct SilcTreeHeaderStruct *right;      /* Right leaft */
  40   struct SilcTreeHeaderStruct *dup;        /* Duplicates, middle leaf, etc. */
  41   SilcInt16 t;
  42   unsigned int duplicate   : 1;
  43 };
  44
  45 /* Tree context */
  46 struct SilcTreeStruct {
  47   const struct SilcTreeOpsStruct *ops;
  48   SilcTreeHeader *root;
  49   SilcCompare compare;
  50   void *context;
  51   SilcUInt32 count;
  52   unsigned int offset      : 31;
  53   unsigned int duplicates  : 1;
  54 };
  55
  56 /* Get tree header from entry */
  57 #define SILC_TREE_GET_HEADER(tree, pos)                 \
  58   ((void *)((unsigned char *)(pos) + tree->offset))
  59
  60 /* Get entry from tree header */
  61 #define SILC_TREE_GET_ENTRY(tree, pos)                  \
  62   ((void *)((unsigned char *)(pos) - tree->offset))
  63
  64 /* Low level undocumented macro API for creating three-leaf binary trees. */
  65
  66 #define silc_tree_set_root(tree, root)          \
  67   (tree).root = SILC_TREE_GET_HEADER(&(tree), (root))
  68 #define silc_tree_set_parent(tree, at, parent)  \
  69   (at)->parent = SILC_TREE_GET_HEADER(&(tree), (parent))
  70 #define silc_tree_set_left(tree, at, left)      \
  71   (at)->left = SILC_TREE_GET_HEADER(&(tree), (left))
  72 #define silc_tree_set_middle(tree, at, middle)  \
  73   (at)->dup = SILC_TREE_GET_HEADER(&(tree), (middle))
  74 #define silc_tree_set_right(tree, at, right)    \
  75   (at)->right = SILC_TREE_GET_HEADER(&(tree), (right))
  76
  77 #define silc_tree_get_root(tree)                \
  78   SILC_TREE_GET_ENTRY(&(tree), (tree).root)
  79 #define silc_tree_get_parent(tree, at)          \
  80   SILC_TREE_GET_ENTRY(&(tree), (at)->parent)
  81 #define silc_tree_get_left(tree, at)            \
  82   SILC_TREE_GET_ENTRY(&(tree), (at)->left)
  83 #define silc_tree_get_middle(tree, at)          \
  84   SILC_TREE_GET_ENTRY(&(tree), (at)->middle)
  85 #define silc_tree_get_right(tree, at)           \
  86   SILC_TREE_GET_ENTRY(&(tree), (at)->right)
  87
  88 #endif /* SILCTREE_I_H */