source: tools/tracereport/contain.c @ bf7018a

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivegetfragoffhelplibtrace4ndag_formatpfringrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since bf7018a was 49ce177, checked in by Perry Lorier <perry@…>, 16 years ago

Added:

  • error reports
  • flow reports
  • per port reports
  • direction report
  • moved everything to use the container library
  • Property mode set to 100644
File size: 3.9 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3#include "contain.h"
4
5splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) {
6        splay N, *l, *r, *y;
7
8        if (tree == 0) {
9                return 0;
10        }
11
12        N.left = N.right = 0;
13        l = r = &N;
14
15        for (;;) {
16                int cmpres = cmp(node,tree);
17                if (cmpres<0) {
18                        if (tree->left == NULL)
19                                break;
20                        if (cmp(node,tree->left)<0) {
21                                y = tree->left;
22                                tree->left = y->right;
23                                y->right = tree;
24                                tree = y;
25                                if (tree->left == NULL)
26                                        break;
27                        }
28                        r->left = tree;
29                        r = tree;
30                        tree = tree->left;
31                } else if (cmpres>0) {
32                        if (tree->right == NULL)
33                                break;
34                        if (cmp(node,tree->right)>0) {
35                                y = tree->right;
36                                tree->right = y->left;
37                                y->left = tree;
38                                tree = y;
39                                if (tree->right == NULL)
40                                        break;
41                        }
42                        l->right = tree;
43                        l = tree;
44                        tree = tree->right;
45                } else {
46                        break;
47                }
48        }
49        l->right = tree->left;
50        r->left = tree->right;
51        tree->left = N.right;
52        tree->right = N.left;
53        return tree;
54}
55
56splay *splay_delete(splay *tree, splay_cmp_t cmp, splay *node) {
57        splay *s;
58
59        if (!tree)
60                return 0;
61
62        tree = splay_search_tree(tree, cmp, node);
63        if (cmp(tree,node)==0) {
64                if (tree->left == NULL) {
65                        s = tree->right;
66                } else {
67                        s = splay_search_tree(tree->left, cmp, node);
68                        s->right = tree->right;
69                }
70                free(tree);
71                return s;
72        }
73        return tree;
74}
75
76void splay_purge(splay *tree) {
77
78        if (!tree)
79                return;
80
81        if (tree->left)
82                splay_purge(tree->left);
83        if (tree->right)
84                splay_purge(tree->right);
85        free(tree);
86}
87       
88
89
90splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node) 
91{
92        if (tree == NULL) {
93                tree = node;
94                return tree;
95        }
96        if (cmp(node,tree)<0) {
97                node->left = tree->left;
98                node->right = tree;
99                tree->left = 0;
100        } else if (cmp(node,tree)>0) {
101                node->right = tree->right;
102                node->left = tree;
103                tree->right = 0;
104        } else {
105                free(node);
106        }
107
108        return node;
109}
110
111void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata)
112{
113        if (!tree) return;
114        if (pre) pre(tree,userdata);
115        splay_visit(tree->left,pre,inorder,post,userdata);
116        if (inorder) inorder(tree,userdata);
117        splay_visit(tree->right,pre,inorder,post,userdata);
118        if (post) post(tree,userdata);
119}
120
121
122#ifdef TEST
123#include <string.h>
124struct foo_t {
125        splay tree;
126        char *key;
127        char *value;
128};
129
130
131void visitor_pre(const struct foo_t *a)
132{
133        printf("{\n");
134}
135void visitor_inorder(const struct foo_t *a)
136{
137        printf("%s: %s\n",a->key,a->value);
138}
139void visitor_post(const struct foo_t *a)
140{
141        printf("}\n");
142}
143
144int cmp(const struct foo_t *a,const struct foo_t *b)
145{
146        int ret= strcmp(a->key,b->key);
147        printf("cmp(%s,%s)==%i\n",a->key,b->key,ret);
148        return ret;
149}
150
151int main(int argc, char *argv[])
152{
153        struct foo_t *tree = NULL;
154        struct foo_t a = { { NULL, NULL }, "a","apple" };
155        struct foo_t b = { { NULL, NULL }, "b","bear" };
156        struct foo_t q = { { NULL, NULL }, "a", NULL };
157        struct foo_t *node;
158
159        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&a);
160        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
161        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&b);
162        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
163        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
164        printf("%s is for %s\n",q.key,tree->value);
165        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
166        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
167        printf("%s is for %s\n",q.key,tree->value);
168        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
169        q.key="b";
170        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
171        printf("%s is for %s\n",q.key,tree->value);
172        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
173        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
174        printf("%s is for %s\n",q.key,tree->value);
175        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
176
177        return 0;
178}
179
180#endif
Note: See TracBrowser for help on using the repository browser.