Return to redblack.h CVS log

Up to [local] / src / usr.bin / sudo

Annotation of src/usr.bin/sudo/redblack.h, Revision 1.2

1.1       millert     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 */