Changeset e9ee974 for tools/tracereport


Ignore:
Timestamp:
04/21/06 17:09:12 (16 years ago)
Author:
Perry Lorier <perry@…>
Branches:
4.0.1-hotfixes, cachetimestamps, develop, dpdk-ndag, etsilive, getfragoff, help, libtrace4, master, ndag_format, pfring, rc-4.0.1, rc-4.0.2, rc-4.0.3, rc-4.0.4, ringdecrementfix, ringperformance, ringtimestampfixes
Children:
0c222cc
Parents:
222d8f5
Message:

Rewrote the splay tree code (again!)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • tools/tracereport/contain.c

    rd320b63 re9ee974  
    55#include <stdlib.h>
    66#include "contain.h"
     7#include <assert.h>
     8
     9/* a -> b */
     10#define implies(a,b) (!(a) || (b))
     11
     12void assert_tree(splay *tree, splay_cmp_t cmp)
     13{
     14#ifndef NDEBUG
     15        if (!tree)
     16                return;
     17
     18        assert(implies(tree->left,cmp(tree->left,tree)<0));
     19        assert(implies(tree->right,cmp(tree,tree->right)<0));
     20        assert(implies(tree->left && tree->right,
     21                                cmp(tree->left,tree->right)<0));
     22
     23        assert_tree(tree->left,cmp);
     24        assert_tree(tree->right,cmp);
     25#endif
     26}
     27
     28#undef implies
    729
    830splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) {
    9         splay N, *l, *r, *y;
    1031
    1132        if (tree == NULL) {
    … …  
    1334        }
    1435
    15         N.left = N.right = 0;
    16         l = r = &N;
     36        assert_tree(tree,cmp);
    1737
    1838        for (;;) {
    1939                int cmpres = cmp(node,tree);
     40
    2041                if (cmpres<0) {
     42                        splay *y;
    2143                        if (tree->left == NULL)
    2244                                break;
    23                         if (cmp(node,tree->left)<0) {
    24                                 y = tree->left;
    25                                 tree->left = y->right;
    26                                 y->right = tree;
    27                                 tree = y;
    28                                 if (tree->left == NULL)
    29                                         break;
     45                        /* Rotate Right */
     46                        y = tree->left;
     47                        tree->left=y->right;
     48                        y->right=tree;
     49                        tree=y;
     50                        /* Not found? */
     51                        if (cmp(node,tree)>0) {
     52                                break;
    3053                        }
    31                         r->left = tree;
    32                         r = tree;
    33                         tree = tree->left;
    3454                } else if (cmpres>0) {
     55                        splay *y;
    3556                        if (tree->right == NULL)
    3657                                break;
    37                         if (cmp(node,tree->right)>0) {
    38                                 y = tree->right;
    39                                 tree->right = y->left;
    40                                 y->left = tree;
    41                                 tree = y;
    42                                 if (tree->right == NULL)
    43                                         break;
     58                        /* Rotate Left */
     59                        y = tree->right;
     60                        tree->right=y->left;
     61                        y->left=tree;
     62                        tree=y;
     63                        /* Not found? */
     64                        if (cmp(node,tree)<0) {
     65                                break;
    4466                        }
    45                         l->right = tree;
    46                         l = tree;
    47                         tree = tree->right;
    4867                } else {
     68                        /* Found it */
    4969                        break;
    5070                }
    5171        }
    52         l->right = tree->left;
    53         r->left = tree->right;
    54         tree->left = N.right;
    55         tree->right = N.left;
     72
     73        assert_tree(tree,cmp);
     74
    5675        return tree;
    5776}
    … …  
    89108}
    90109       
    91 
    92 
    93110splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node)
    94111{
     112        int cmpres;
     113        assert_tree(tree,cmp);
    95114        if (tree == NULL) {
    96115                tree = node;
    97116                node->left = NULL;
    98117                node->right = NULL;
     118                assert_tree(tree,cmp);
    99119                return tree;
    100120        }
    101         tree=splay_search_tree(tree,cmp,node);
    102         if (cmp(node,tree)<0) {
    103                 node->left = tree->left;
    104                 node->right = tree;
    105                 tree->left = NULL;
    106         } else if (cmp(node,tree)>0) {
    107                 node->right = tree->right;
    108                 node->left = tree;
    109                 tree->right = NULL;
     121        assert_tree(tree,cmp);
     122        cmpres=cmp(node,tree);
     123        if (cmpres<0) {
     124                tree=splay_insert(tree->left,cmp,node);
     125        } else if (cmpres>0) {
     126                tree=splay_insert(tree->right,cmp,node);
    110127        } else {
    111128                /* Replace the root node with the current node */
    … …  
    116133        }
    117134
     135        assert_tree(tree,cmp);
    118136        return tree;
    119137}
    … …  
    139157
    140158
    141 void visitor_pre(const struct foo_t *a)
    142 {
    143         printf("{\n");
    144 }
    145159void visitor_inorder(const struct foo_t *a)
    146160{
    147161        printf("%s: %s\n",a->key,a->value);
    148 }
    149 void visitor_post(const struct foo_t *a)
    150 {
    151         printf("}\n");
    152162}
    153163
Note: See TracChangeset for help on using the changeset viewer.