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  * $Sudo: redblack.h,v 1.4 2008/11/09 14:13:12 millert Exp $
  17  */
  18
  19 #ifndef _SUDO_REDBLACK_H
  20 #define _SUDO_REDBLACK_H
  21
  22 enum rbcolor {
  23     red,
  24     black
  25 };
  26
  27 enum rbtraversal {
  28     preorder,
  29     inorder,
  30     postorder
  31 };
  32
  33 struct rbnode {
  34     struct rbnode *left, *right, *parent;
  35     void *data;
  36     enum rbcolor color;
  37 };
  38
  39 struct rbtree {
  40     int (*compar) __P((const void *, const void *));
  41     struct rbnode root;
  42     struct rbnode nil;
  43 };
  44
  45 #define rbapply(t, f, c, o)     rbapply_node((t), (t)->root.left, (f), (c), (o))
  46 #define rbisempty(t)            ((t)->root.left == &(t)->nil && (t)->root.right == &(t)->nil)
  47 #define rbfirst(t)              ((t)->root.left)
  48 #define rbroot(t)               (&(t)->root)
  49 #define rbnil(t)                (&(t)->nil)
  50
  51 void *rbdelete                  __P((struct rbtree *, struct rbnode *));
  52 int rbapply_node                __P((struct rbtree *, struct rbnode *,
  53                                     int (*)(void *, void *), void *,
  54                                     enum rbtraversal));
  55 struct rbnode *rbfind           __P((struct rbtree *, void *));
  56 struct rbnode *rbinsert         __P((struct rbtree *, void *));
  57 struct rbtree *rbcreate         __P((int (*)(const void *, const void *)));
  58 void rbdestroy                  __P((struct rbtree *, void (*)(void *)));
  59
  60 #endif /* _SUDO_REDBLACK_H */