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

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