Changeset e9ee974 for tools/tracereport
- Timestamp:
- 04/21/06 17:09:12 (16 years ago)
- 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
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
tools/tracereport/contain.c
rd320b63 re9ee974 5 5 #include <stdlib.h> 6 6 #include "contain.h" 7 #include <assert.h> 8 9 /* a -> b */ 10 #define implies(a,b) (!(a) || (b)) 11 12 void 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 7 29 8 30 splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) { 9 splay N, *l, *r, *y;10 31 11 32 if (tree == NULL) { … … 13 34 } 14 35 15 N.left = N.right = 0; 16 l = r = &N; 36 assert_tree(tree,cmp); 17 37 18 38 for (;;) { 19 39 int cmpres = cmp(node,tree); 40 20 41 if (cmpres<0) { 42 splay *y; 21 43 if (tree->left == NULL) 22 44 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; 30 53 } 31 r->left = tree;32 r = tree;33 tree = tree->left;34 54 } else if (cmpres>0) { 55 splay *y; 35 56 if (tree->right == NULL) 36 57 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; 44 66 } 45 l->right = tree;46 l = tree;47 tree = tree->right;48 67 } else { 68 /* Found it */ 49 69 break; 50 70 } 51 71 } 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 56 75 return tree; 57 76 } … … 89 108 } 90 109 91 92 93 110 splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node) 94 111 { 112 int cmpres; 113 assert_tree(tree,cmp); 95 114 if (tree == NULL) { 96 115 tree = node; 97 116 node->left = NULL; 98 117 node->right = NULL; 118 assert_tree(tree,cmp); 99 119 return tree; 100 120 } 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); 110 127 } else { 111 128 /* Replace the root node with the current node */ … … 116 133 } 117 134 135 assert_tree(tree,cmp); 118 136 return tree; 119 137 } … … 139 157 140 158 141 void visitor_pre(const struct foo_t *a)142 {143 printf("{\n");144 }145 159 void visitor_inorder(const struct foo_t *a) 146 160 { 147 161 printf("%s: %s\n",a->key,a->value); 148 }149 void visitor_post(const struct foo_t *a)150 {151 printf("}\n");152 162 } 153 163
Note: See TracChangeset
for help on using the changeset viewer.