git.gag.com Git - debian/sudo/blob - redblack.h

   1 /*
   2  * Copyright (c) 2004, 2007 Todd C. Miller <Todd.Miller@courtesan.com>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #ifndef _SUDO_REDBLACK_H
  18 #define _SUDO_REDBLACK_H
  19
  20 enum rbcolor {
  21     red,
  22     black
  23 };
  24
  25 enum rbtraversal {
  26     preorder,
  27     inorder,
  28     postorder
  29 };
  30
  31 struct rbnode {
  32     struct rbnode *left, *right, *parent;
  33     void *data;
  34     enum rbcolor color;
  35 };
  36
  37 struct rbtree {
  38     int (*compar) __P((const void *, const void *));
  39     struct rbnode root;
  40     struct rbnode nil;
  41 };
  42
  43 #define rbapply(t, f, c, o)     rbapply_node((t), (t)->root.left, (f), (c), (o))
  44 #define rbisempty(t)            ((t)->root.left == &(t)->nil && (t)->root.right == &(t)->nil)
  45 #define rbfirst(t)              ((t)->root.left)
  46 #define rbroot(t)               (&(t)->root)
  47 #define rbnil(t)                (&(t)->nil)
  48
  49 void *rbdelete                  __P((struct rbtree *, struct rbnode *));
  50 int rbapply_node                __P((struct rbtree *, struct rbnode *,
  51                                     int (*)(void *, void *), void *,
  52                                     enum rbtraversal));
  53 struct rbnode *rbfind           __P((struct rbtree *, void *));
  54 struct rbnode *rbinsert         __P((struct rbtree *, void *));
  55 struct rbtree *rbcreate         __P((int (*)(const void *, const void *)));
  56 void rbdestroy                  __P((struct rbtree *, void (*)(void *)));
  57
  58 #endif /* _SUDO_REDBLACK_H */