← Back to branch summary

~ubuntu-branches/ubuntu/trusty/haproxy/trusty-backports

« back to all changes in this revision

Viewing changes to include/common/ebtree.h

  • Committer: Bazaar Package Importer
  • Author(s): Arnaud Cornet
  • Date: 2009-06-26 00:11:01 UTC
  • mfrom: (1.1.6 upstream) (2.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20090626001101-qo261ke2mjh3d8cn
http://bugs.debian.org/534583
* New Upstream Version (Closes: #534583).
* Add contrib directory in docs

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/common/ebtree.h
1
1
/*
2
2
 * Elastic Binary Trees - generic macros and structures.
 
3
 * Version 4.0
3
4
 * (C) 2002-2008 - Willy Tarreau <w@1wt.eu>
4
5
 *
5
6
 * This program is free software; you can redistribute it and/or modify
205
206
       root, it is not possible to see a NULL left branch when walking up a
206
207
       tree. Thus, an empty tree is immediately identified by a NULL left
207
208
       branch at the root. Conversely, the one and only way to identify the
208
 
       root node is to check that it right branch is NULL.
 
209
       root node is to check that it right branch is NULL. Note that the
 
210
       NULL pointer may have a few low-order bits set.
209
211
 
210
212
     - a node connected to its own leaf will have branch[0|1] pointing to
211
213
       itself, and leaf_p pointing to itself.
244
246
       higher to lower keys. It returns duplicates in the opposite order they
245
247
       were inserted. The "eb_last" primitive returns the right-most entry.
246
248
 
 
249
     - a tree which has 1 in the lower bit of its root's right branch is a
 
250
       tree with unique nodes. This means that when a node is inserted with
 
251
       a key which already exists will not be inserted, and the previous
 
252
       entry will be returned.
 
253
 
247
254
 */
248
255
 
249
256
#ifndef _COMMON_EBTREE_H
380
387
#define EB_LEAF     0
381
388
#define EB_NODE     1
382
389
 
 
390
/* Tags to set in root->b[EB_RGHT] :
 
391
 * - EB_NORMAL is a normal tree which stores duplicate keys.
 
392
 * - EB_UNIQUE is a tree which stores unique keys.
 
393
 */
 
394
#define EB_NORMAL   0
 
395
#define EB_UNIQUE   1
 
396
 
383
397
/* This is the same as an eb_node pointer, except that the lower bit embeds
384
398
 * a tag. See eb_dotag()/eb_untag()/eb_gettag(). This tag has two meanings :
385
399
 *  - 0=left, 1=right to designate the parent's branch for leaf_p/node_p
389
403
 
390
404
/* The eb_root connects the node which contains it, to two nodes below it, one
391
405
 * of which may be the same node. At the top of the tree, we use an eb_root
392
 
 * too, which always has its right branch NULL.
 
406
 * too, which always has its right branch NULL (+/1 low-order bits).
393
407
 */
394
408
struct eb_root {
395
409
        eb_troot_t    *b[EB_NODE_BRANCHES]; /* left and right branches */
419
433
                .b = {[0] = NULL, [1] = NULL },         \
420
434
        }
421
435
 
 
436
#define EB_ROOT_UNIQUE                                  \
 
437
        (struct eb_root) {                              \
 
438
                .b = {[0] = NULL, [1] = (void *)1 },    \
 
439
        }
 
440
 
422
441
#define EB_TREE_HEAD(name)                              \
423
442
        struct eb_root name = EB_ROOT
424
443
 
563
582
                /* Walking up from left branch. We must ensure that we never
564
583
                 * walk beyond root.
565
584
                 */
566
 
                if (unlikely((eb_untag(t, EB_LEFT))->b[EB_RGHT] == NULL))
 
585
                if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
567
586
                        return NULL;
568
587
                t = (eb_root_to_node(eb_untag(t, EB_LEFT)))->node_p;
569
588
        }
583
602
 
584
603
        /* Note that <t> cannot be NULL at this stage */
585
604
        t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
 
605
        if (eb_clrtag(t) == NULL)
 
606
                return NULL;
586
607
        return eb_walk_down(t, EB_LEFT);
587
608
}
588
609
 
604
625
                        /* Walking up from left branch. We must ensure that we never
605
626
                         * walk beyond root.
606
627
                         */
607
 
                        if (unlikely((eb_untag(t, EB_LEFT))->b[EB_RGHT] == NULL))
 
628
                        if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
608
629
                                return NULL;
609
630
                        t = (eb_root_to_node(eb_untag(t, EB_LEFT)))->node_p;
610
631
                }
623
644
 
624
645
        while (1) {
625
646
                if (eb_gettag(t) == EB_LEFT) {
626
 
                        if (unlikely((eb_untag(t, EB_LEFT))->b[EB_RGHT] == NULL))
 
647
                        if (unlikely(eb_clrtag((eb_untag(t, EB_LEFT))->b[EB_RGHT]) == NULL))
627
648
                                return NULL;    /* we reached root */
628
649
                        node = eb_root_to_node(eb_untag(t, EB_LEFT));
629
650
                        /* if we're left and not in duplicates, stop here */
639
660
 
640
661
        /* Note that <t> cannot be NULL at this stage */
641
662
        t = (eb_untag(t, EB_LEFT))->b[EB_RGHT];
 
663
        if (eb_clrtag(t) == NULL)
 
664
                return NULL;
642
665
        return eb_walk_down(t, EB_LEFT);
643
666
}
644
667
 
665
688
         * only be attached to the root by its left branch.
666
689
         */
667
690
 
668
 
        if (parent->branches.b[EB_RGHT] == NULL) {
 
691
        if (eb_clrtag(parent->branches.b[EB_RGHT]) == NULL) {
669
692
                /* we're just below the root, it's trivial. */
670
693
                parent->branches.b[EB_LEFT] = NULL;
671
694
                goto delete_unlink;