source: tools/tracereport/contain.c @ 548da5c

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivegetfragoffhelplibtrace4ndag_formatpfringrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since 548da5c was e3b0188, checked in by Daniel Lawson <dlawson@…>, 16 years ago

a lot of changes for cross-compilation support

  • header ordering
  • os-specific headers
  • an lt_inttypes.h which defines PRIu64 etc for platforms that don't have them
  • removed daglegacy.h, merged with dagformat.h
  • Property mode set to 100644
File size: 3.9 KB
Line 
1#include <stdio.h>
2#include <inttypes.h>
3#include <lt_inttypes.h>
4#include <stdlib.h>
5#include "contain.h"
6#include "config.h"
7
8splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) {
9        splay N, *l, *r, *y;
10
11        if (tree == 0) {
12                return 0;
13        }
14
15        N.left = N.right = 0;
16        l = r = &N;
17
18        for (;;) {
19                int cmpres = cmp(node,tree);
20                if (cmpres<0) {
21                        if (tree->left == NULL)
22                                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;
30                        }
31                        r->left = tree;
32                        r = tree;
33                        tree = tree->left;
34                } else if (cmpres>0) {
35                        if (tree->right == NULL)
36                                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;
44                        }
45                        l->right = tree;
46                        l = tree;
47                        tree = tree->right;
48                } else {
49                        break;
50                }
51        }
52        l->right = tree->left;
53        r->left = tree->right;
54        tree->left = N.right;
55        tree->right = N.left;
56        return tree;
57}
58
59splay *splay_delete(splay *tree, splay_cmp_t cmp, splay *node) {
60        splay *s;
61
62        if (!tree)
63                return 0;
64
65        tree = splay_search_tree(tree, cmp, node);
66        if (cmp(tree,node)==0) {
67                if (tree->left == NULL) {
68                        s = tree->right;
69                } else {
70                        s = splay_search_tree(tree->left, cmp, node);
71                        s->right = tree->right;
72                }
73                free(tree);
74                return s;
75        }
76        return tree;
77}
78
79void splay_purge(splay *tree) {
80
81        if (!tree)
82                return;
83
84        if (tree->left)
85                splay_purge(tree->left);
86        if (tree->right)
87                splay_purge(tree->right);
88        free(tree);
89}
90       
91
92
93splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node) 
94{
95        if (tree == NULL) {
96                tree = node;
97                return tree;
98        }
99        if (cmp(node,tree)<0) {
100                node->left = tree->left;
101                node->right = tree;
102                tree->left = 0;
103        } else if (cmp(node,tree)>0) {
104                node->right = tree->right;
105                node->left = tree;
106                tree->right = 0;
107        } else {
108                free(node);
109        }
110
111        return node;
112}
113
114void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata)
115{
116        if (!tree) return;
117        if (pre) pre(tree,userdata);
118        splay_visit(tree->left,pre,inorder,post,userdata);
119        if (inorder) inorder(tree,userdata);
120        splay_visit(tree->right,pre,inorder,post,userdata);
121        if (post) post(tree,userdata);
122}
123
124
125#ifdef TEST
126#include <string.h>
127struct foo_t {
128        splay tree;
129        char *key;
130        char *value;
131};
132
133
134void visitor_pre(const struct foo_t *a)
135{
136        printf("{\n");
137}
138void visitor_inorder(const struct foo_t *a)
139{
140        printf("%s: %s\n",a->key,a->value);
141}
142void visitor_post(const struct foo_t *a)
143{
144        printf("}\n");
145}
146
147int cmp(const struct foo_t *a,const struct foo_t *b)
148{
149        int ret= strcmp(a->key,b->key);
150        printf("cmp(%s,%s)==%i\n",a->key,b->key,ret);
151        return ret;
152}
153
154int main(int argc, char *argv[])
155{
156        struct foo_t *tree = NULL;
157        struct foo_t a = { { NULL, NULL }, "a","apple" };
158        struct foo_t b = { { NULL, NULL }, "b","bear" };
159        struct foo_t q = { { NULL, NULL }, "a", NULL };
160        struct foo_t *node;
161
162        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&a);
163        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
164        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&b);
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        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
170        printf("%s is for %s\n",q.key,tree->value);
171        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
172        q.key="b";
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        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
177        printf("%s is for %s\n",q.key,tree->value);
178        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
179
180        return 0;
181}
182
183#endif
Note: See TracBrowser for help on using the repository browser.