← Back to branch summary

~ubuntu-branches/ubuntu/quantal/sudo/quantal

« back to all changes in this revision

Viewing changes to plugins/sudoers/redblack.c

  • Committer: Package Import Robot
  • Author(s): Marc Deslauriers
  • Date: 2011-11-20 12:07:45 UTC
  • mfrom: (1.3.17 sid)
  • Revision ID: package-import@ubuntu.com-20111120120745-o3qpklobmygytndc
Tags: 1.8.3p1-1ubuntu1
* Merge from debian/testing, remaining changes:
  - debian/patches/keep_home_by_default.patch:
    + Set HOME in initial_keepenv_table. (rebased for 1.8.3p1)
  - debian/patches/enable_badpass.patch: turn on "mail_badpass" by default:
    + attempting sudo without knowing a login password is as bad as not
      being listed in the sudoers file, especially if getting the password
      wrong means doing the access-check-email-notification never happens
      (rebased for 1.8.3p1)
  - debian/rules:
    + compile with --without-lecture --with-tty-tickets (Ubuntu specific)
    + install man/man8/sudo_root.8 (Ubuntu specific)
    + install apport hooks
    + The ubuntu-sudo-as-admin-successful.patch was taken upstream by
      Debian however it requires a --enable-admin-flag configure flag to
      actually enable it.
  - debian/sudoers: 
    + grant admin group sudo access
  - debian/sudo-ldap.dirs, debian/sudo.dirs: 
    + add usr/share/apport/package-hooks
  - debian/sudo.preinst:
    + avoid conffile prompt by checking for known default /etc/sudoers
      and if found installing the correct default /etc/sudoers file

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugins/sudoers/redblack.c
 
1
/*
 
2
 * Copyright (c) 2004-2005, 2007, 2009-2011
 
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
/*
 
19
 * Adapted from the following code written by Emin Martinian:
 
20
 * http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
 
21
 *
 
22
 * Copyright (c) 2001 Emin Martinian
 
23
 *
 
24
 * Redistribution and use in source and binary forms, with or without
 
25
 * modification, are permitted provided that neither the name of Emin
 
26
 * Martinian nor the names of any contributors are be used to endorse or
 
27
 * promote products derived from this software without specific prior
 
28
 * written permission.
 
29
 *
 
30
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 
31
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 
32
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 
33
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 
34
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 
35
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 
36
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
37
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
38
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
39
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 
40
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
41
 */
 
42
 
 
43
#include <config.h>
 
44
 
 
45
#include <sys/types.h>
 
46
#include <sys/param.h>
 
47
 
 
48
#include <stdio.h>
 
49
#ifdef STDC_HEADERS
 
50
# include <stdlib.h>
 
51
# include <stddef.h>
 
52
#else
 
53
# ifdef HAVE_STDLIB_H
 
54
#  include <stdlib.h>
 
55
# endif
 
56
#endif /* STDC_HEADERS */
 
57
 
 
58
#include "missing.h"
 
59
#include "alloc.h"
 
60
#include "redblack.h"
 
61
 
 
62
static void rbrepair(struct rbtree *, struct rbnode *);
 
63
static void rotate_left(struct rbtree *, struct rbnode *);
 
64
static void rotate_right(struct rbtree *, struct rbnode *);
 
65
static void _rbdestroy(struct rbtree *, struct rbnode *, void (*)(void *));
 
66
 
 
67
/*
 
68
 * Red-Black tree, see http://en.wikipedia.org/wiki/Red-black_tree
 
69
 *
 
70
 * A red-black tree is a binary search tree where each node has a color
 
71
 * attribute, the value of which is either red or black.  Essentially, it
 
72
 * is just a convenient way to express a 2-3-4 binary search tree where
 
73
 * the color indicates whether the node is part of a 3-node or a 4-node.
 
74
 * In addition to the ordinary requirements imposed on binary search
 
75
 * trees, we make the following additional requirements of any valid
 
76
 * red-black tree:
 
77
 *  1) Every node is either red or black.
 
78
 *  2) The root is black.
 
79
 *  3) All leaves are black.
 
80
 *  4) Both children of each red node are black.
 
81
 *  5) The paths from each leaf up to the root each contain the same
 
82
 *     number of black nodes.
 
83
 */
 
84
 
 
85
/*
 
86
 * Create a red black tree struct using the specified compare routine.
 
87
 * Allocates and returns the initialized (empty) tree.
 
88
 */
 
89
struct rbtree *
 
90
rbcreate(int (*compar)(const void *, const void*))
 
91
{
 
92
    struct rbtree *tree;
 
93
 
 
94
    tree = (struct rbtree *) emalloc(sizeof(*tree));
 
95
    tree->compar = compar;
 
96
 
 
97
    /*
 
98
     * We use a self-referencing sentinel node called nil to simplify the
 
99
     * code by avoiding the need to check for NULL pointers.
 
100
     */
 
101
    tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
 
102
    tree->nil.color = black;
 
103
    tree->nil.data = NULL;
 
104
 
 
105
    /*
 
106
     * Similarly, the fake root node keeps us from having to worry
 
107
     * about splitting the root.
 
108
     */
 
109
    tree->root.left = tree->root.right = tree->root.parent = &tree->nil;
 
110
    tree->root.color = black;
 
111
    tree->root.data = NULL;
 
112
 
 
113
    return tree;
 
114
}
 
115
 
 
116
/*
 
117
 * Perform a left rotation starting at node.
 
118
 */
 
119
static void
 
120
rotate_left(struct rbtree *tree, struct rbnode *node)
 
121
{
 
122
    struct rbnode *child;
 
123
 
 
124
    child = node->right;
 
125
    node->right = child->left;
 
126
 
 
127
    if (child->left != rbnil(tree))
 
128
        child->left->parent = node;
 
129
    child->parent = node->parent;
 
130
 
 
131
    if (node == node->parent->left)
 
132
        node->parent->left = child;
 
133
    else
 
134
        node->parent->right = child;
 
135
    child->left = node;
 
136
    node->parent = child;
 
137
}
 
138
 
 
139
/*
 
140
 * Perform a right rotation starting at node.
 
141
 */
 
142
static void
 
143
rotate_right(struct rbtree *tree, struct rbnode *node)
 
144
{
 
145
    struct rbnode *child;
 
146
 
 
147
    child = node->left;
 
148
    node->left = child->right;
 
149
 
 
150
    if (child->right != rbnil(tree))
 
151
        child->right->parent = node;
 
152
    child->parent = node->parent;
 
153
 
 
154
    if (node == node->parent->left)
 
155
        node->parent->left = child;
 
156
    else
 
157
        node->parent->right = child;
 
158
    child->right = node;
 
159
    node->parent = child;
 
160
}
 
161
 
 
162
/*
 
163
 * Insert data pointer into a redblack tree.
 
164
 * Returns a NULL pointer on success.  If a node matching "data"
 
165
 * already exists, a pointer to the existant node is returned.
 
166
 */
 
167
struct rbnode *
 
168
rbinsert(struct rbtree *tree, void *data)
 
169
{
 
170
    struct rbnode *node = rbfirst(tree);
 
171
    struct rbnode *parent = rbroot(tree);
 
172
    int res;
 
173
 
 
174
    /* Find correct insertion point. */
 
175
    while (node != rbnil(tree)) {
 
176
        parent = node;
 
177
        if ((res = tree->compar(data, node->data)) == 0)
 
178
            return node;
 
179
        node = res < 0 ? node->left : node->right;
 
180
    }
 
181
 
 
182
    node = (struct rbnode *) emalloc(sizeof(*node));
 
183
    node->data = data;
 
184
    node->left = node->right = rbnil(tree);
 
185
    node->parent = parent;
 
186
    if (parent == rbroot(tree) || tree->compar(data, parent->data) < 0)
 
187
        parent->left = node;
 
188
    else
 
189
        parent->right = node;
 
190
    node->color = red;
 
191
 
 
192
    /*
 
193
     * If the parent node is black we are all set, if it is red we have
 
194
     * the following possible cases to deal with.  We iterate through
 
195
     * the rest of the tree to make sure none of the required properties
 
196
     * is violated.
 
197
     *
 
198
     *  1) The uncle is red.  We repaint both the parent and uncle black
 
199
     *     and repaint the grandparent node red.
 
200
     *
 
201
     *  2) The uncle is black and the new node is the right child of its
 
202
     *     parent, and the parent in turn is the left child of its parent.
 
203
     *     We do a left rotation to switch the roles of the parent and
 
204
     *     child, relying on further iterations to fixup the old parent.
 
205
     *
 
206
     *  3) The uncle is black and the new node is the left child of its
 
207
     *     parent, and the parent in turn is the left child of its parent.
 
208
     *     We switch the colors of the parent and grandparent and perform
 
209
     *     a right rotation around the grandparent.  This makes the former
 
210
     *     parent the parent of the new node and the former grandparent.
 
211
     *
 
212
     * Note that because we use a sentinel for the root node we never
 
213
     * need to worry about replacing the root.
 
214
     */
 
215
    while (node->parent->color == red) {
 
216
        struct rbnode *uncle;
 
217
        if (node->parent == node->parent->parent->left) {
 
218
            uncle = node->parent->parent->right;
 
219
            if (uncle->color == red) {
 
220
                node->parent->color = black;
 
221
                uncle->color = black;
 
222
                node->parent->parent->color = red;
 
223
                node = node->parent->parent;
 
224
            } else /* if (uncle->color == black) */ {
 
225
                if (node == node->parent->right) {
 
226
                    node = node->parent;
 
227
                    rotate_left(tree, node);
 
228
                }
 
229
                node->parent->color = black;
 
230
                node->parent->parent->color = red;
 
231
                rotate_right(tree, node->parent->parent);
 
232
            }
 
233
        } else { /* if (node->parent == node->parent->parent->right) */
 
234
            uncle = node->parent->parent->left;
 
235
            if (uncle->color == red) {
 
236
                node->parent->color = black;
 
237
                uncle->color = black;
 
238
                node->parent->parent->color = red;
 
239
                node = node->parent->parent;
 
240
            } else /* if (uncle->color == black) */ {
 
241
                if (node == node->parent->left) {
 
242
                    node = node->parent;
 
243
                    rotate_right(tree, node);
 
244
                }
 
245
                node->parent->color = black;
 
246
                node->parent->parent->color = red;
 
247
                rotate_left(tree, node->parent->parent);
 
248
            }
 
249
        }
 
250
    }
 
251
    rbfirst(tree)->color = black;       /* first node is always black */
 
252
    return NULL;
 
253
}
 
254
 
 
255
/*
 
256
 * Look for a node matching key in tree.
 
257
 * Returns a pointer to the node if found, else NULL.
 
258
 */
 
259
struct rbnode *
 
260
rbfind(struct rbtree *tree, void *key)
 
261
{
 
262
    struct rbnode *node = rbfirst(tree);
 
263
    int res;
 
264
 
 
265
    while (node != rbnil(tree)) {
 
266
        if ((res = tree->compar(key, node->data)) == 0)
 
267
            return node;
 
268
        node = res < 0 ? node->left : node->right;
 
269
    }
 
270
    return NULL;
 
271
}
 
272
 
 
273
/*
 
274
 * Call func() for each node, passing it the node data and a cookie;
 
275
 * If func() returns non-zero for a node, the traversal stops and the
 
276
 * error value is returned.  Returns 0 on successful traversal.
 
277
 */
 
278
int
 
279
rbapply_node(struct rbtree *tree, struct rbnode *node,
 
280
    int (*func)(void *, void *), void *cookie, enum rbtraversal order)
 
281
{
 
282
    int error;
 
283
 
 
284
    if (node != rbnil(tree)) {
 
285
        if (order == preorder)
 
286
            if ((error = func(node->data, cookie)) != 0)
 
287
                return error;
 
288
        if ((error = rbapply_node(tree, node->left, func, cookie, order)) != 0)
 
289
            return error;
 
290
        if (order == inorder)
 
291
            if ((error = func(node->data, cookie)) != 0)
 
292
                return error;
 
293
        if ((error = rbapply_node(tree, node->right, func, cookie, order)) != 0)
 
294
            return error;
 
295
        if (order == postorder)
 
296
            if ((error = func(node->data, cookie)) != 0)
 
297
                return error;
 
298
    }
 
299
    return 0;
 
300
}
 
301
 
 
302
/*
 
303
 * Returns the successor of node, or nil if there is none.
 
304
 */
 
305
static struct rbnode *
 
306
rbsuccessor(struct rbtree *tree, struct rbnode *node)
 
307
{
 
308
    struct rbnode *succ;
 
309
 
 
310
    if ((succ = node->right) != rbnil(tree)) {
 
311
        while (succ->left != rbnil(tree))
 
312
            succ = succ->left;
 
313
    } else {
 
314
        /* No right child, move up until we find it or hit the root */
 
315
        for (succ = node->parent; node == succ->right; succ = succ->parent)
 
316
            node = succ;
 
317
        if (succ == rbroot(tree))
 
318
            succ = rbnil(tree);
 
319
    }
 
320
    return succ;
 
321
}
 
322
 
 
323
/*
 
324
 * Recursive portion of rbdestroy().
 
325
 */
 
326
static void
 
327
_rbdestroy(struct rbtree *tree, struct rbnode *node, void (*destroy)(void *))
 
328
{
 
329
    if (node != rbnil(tree)) {
 
330
        _rbdestroy(tree, node->left, destroy);
 
331
        _rbdestroy(tree, node->right, destroy);
 
332
        if (destroy != NULL)
 
333
            destroy(node->data);
 
334
        efree(node);
 
335
    }
 
336
}
 
337
 
 
338
/*
 
339
 * Destroy the specified tree, calling the destructor destroy
 
340
 * for each node and then freeing the tree itself.
 
341
 */
 
342
void
 
343
rbdestroy(struct rbtree *tree, void (*destroy)(void *))
 
344
{
 
345
    _rbdestroy(tree, rbfirst(tree), destroy);
 
346
    efree(tree);
 
347
}
 
348
 
 
349
/*
 
350
 * Delete node 'z' from the tree and return its data pointer.
 
351
 */
 
352
void *rbdelete(struct rbtree *tree, struct rbnode *z)
 
353
{
 
354
    struct rbnode *x, *y;
 
355
    void *data = z->data;
 
356
 
 
357
    if (z->left == rbnil(tree) || z->right == rbnil(tree))
 
358
        y = z;
 
359
    else
 
360
        y = rbsuccessor(tree, z);
 
361
    x = (y->left == rbnil(tree)) ? y->right : y->left;
 
362
 
 
363
    if ((x->parent = y->parent) == rbroot(tree)) {
 
364
        rbfirst(tree) = x;
 
365
    } else {
 
366
        if (y == y->parent->left)
 
367
            y->parent->left = x;
 
368
        else
 
369
            y->parent->right = x;
 
370
    }
 
371
    if (y->color == black)
 
372
        rbrepair(tree, x);
 
373
    if (y != z) {
 
374
        y->left = z->left;
 
375
        y->right = z->right;
 
376
        y->parent = z->parent;
 
377
        y->color = z->color;
 
378
        z->left->parent = z->right->parent = y;
 
379
        if (z == z->parent->left)
 
380
            z->parent->left = y; 
 
381
        else
 
382
            z->parent->right = y;
 
383
    }
 
384
    free(z); 
 
385
    
 
386
    return data;
 
387
}
 
388
 
 
389
/*
 
390
 * Repair the tree after a node has been deleted by rotating and repainting
 
391
 * colors to restore the 4 properties inherent in red-black trees.
 
392
 */
 
393
static void
 
394
rbrepair(struct rbtree *tree, struct rbnode *node)
 
395
{
 
396
    struct rbnode *sibling;
 
397
 
 
398
    while (node->color == black && node != rbroot(tree)) {
 
399
        if (node == node->parent->left) {
 
400
            sibling = node->parent->right;
 
401
            if (sibling->color == red) {
 
402
                sibling->color = black;
 
403
                node->parent->color = red;
 
404
                rotate_left(tree, node->parent);
 
405
                sibling = node->parent->right;
 
406
            }
 
407
            if (sibling->right->color == black && sibling->left->color == black) {
 
408
                sibling->color = red;
 
409
                node = node->parent;
 
410
            } else {
 
411
                if (sibling->right->color == black) {
 
412
                      sibling->left->color = black;
 
413
                      sibling->color = red;
 
414
                      rotate_right(tree, sibling);
 
415
                      sibling = node->parent->right;
 
416
                }
 
417
                sibling->color = node->parent->color;
 
418
                node->parent->color = black;
 
419
                sibling->right->color = black;
 
420
                rotate_left(tree, node->parent);
 
421
                node = rbroot(tree); /* exit loop */
 
422
            }
 
423
        } else { /* if (node == node->parent->right) */
 
424
            sibling = node->parent->left;
 
425
            if (sibling->color == red) {
 
426
                sibling->color = black;
 
427
                node->parent->color = red;
 
428
                rotate_right(tree, node->parent);
 
429
                sibling = node->parent->left;
 
430
            }
 
431
            if (sibling->right->color == black && sibling->left->color == black) {
 
432
                sibling->color = red;
 
433
                node = node->parent;
 
434
            } else {
 
435
                if (sibling->left->color == black) {
 
436
                    sibling->right->color = black;
 
437
                    sibling->color = red;
 
438
                    rotate_left(tree, sibling);
 
439
                    sibling = node->parent->left;
 
440
                }
 
441
                sibling->color = node->parent->color;
 
442
                node->parent->color = black;
 
443
                sibling->left->color = black;
 
444
                rotate_right(tree, node->parent);
 
445
                node = rbroot(tree); /* exit loop */
 
446
            }
 
447
        }
 
448
    }
 
449
    node->color = black;
 
450
}