source: tools/tracereport/contain.c @ a8f2692

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

Tidy up a bazillion tiny warnings

  • Property mode set to 100644
File size: 4.3 KB
Line 
1/* Updated: 2006-04-07 to deal with duplicate inserts */
2#include <stdio.h>
3#include <inttypes.h>
4#include <lt_inttypes.h>
5#include <stdlib.h>
6#include "contain.h"
7#include <assert.h>
8
9/* a -> b */
10#define implies(a,b) (!(a) || (b))
11
12static 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
29
30splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) {
31
32        if (tree == NULL) {
33                return NULL;
34        }
35
36        assert_tree(tree,cmp);
37
38        for (;;) {
39                int cmpres = cmp(node,tree);
40
41                if (cmpres<0) {
42                        splay *y;
43                        if (tree->left == NULL)
44                                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;
53                        }
54                } else if (cmpres>0) {
55                        splay *y;
56                        if (tree->right == NULL)
57                                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;
66                        }
67                } else {
68                        /* Found it */
69                        break;
70                }
71        }
72
73        assert_tree(tree,cmp);
74
75        return tree;
76}
77
78splay *splay_delete(splay *tree, splay_cmp_t cmp, splay *node) {
79        splay *s;
80
81        if (!tree)
82                return 0;
83
84        tree = splay_search_tree(tree, cmp, node);
85        if (cmp(tree,node)==0) {
86                if (tree->left == NULL) {
87                        s = tree->right;
88                } else {
89                        s = splay_search_tree(tree->left, cmp, node);
90                        s->right = tree->right;
91                }
92                free(tree);
93                return s;
94        }
95        return tree;
96}
97
98void splay_purge(splay *tree) {
99
100        if (!tree)
101                return;
102
103        if (tree->left)
104                splay_purge(tree->left);
105        if (tree->right)
106                splay_purge(tree->right);
107        free(tree);
108}
109       
110splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node) 
111{
112        int cmpres;
113        assert_tree(tree,cmp);
114        if (tree == NULL) {
115                tree = node;
116                node->left = NULL;
117                node->right = NULL;
118                assert_tree(tree,cmp);
119                return tree;
120        }
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);
127        } else {
128                /* Replace the root node with the current node */
129                node->left = tree->left;
130                node->right = tree->right;
131                free(tree);
132                tree=node;
133        }
134
135        assert_tree(tree,cmp);
136        return tree;
137}
138
139void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata)
140{
141        if (!tree) return;
142        if (pre) pre(tree,userdata);
143        splay_visit(tree->left,pre,inorder,post,userdata);
144        if (inorder) inorder(tree,userdata);
145        splay_visit(tree->right,pre,inorder,post,userdata);
146        if (post) post(tree,userdata);
147}
148
149
150#ifdef TEST
151#include <string.h>
152struct foo_t {
153        splay tree;
154        char *key;
155        char *value;
156};
157
158
159void visitor_inorder(const struct foo_t *a)
160{
161        printf("%s: %s\n",a->key,a->value);
162}
163
164int cmp(const struct foo_t *a,const struct foo_t *b)
165{
166        int ret= strcmp(a->key,b->key);
167        printf("cmp(%s,%s)==%i\n",a->key,b->key,ret);
168        return ret;
169}
170
171int main(int argc, char *argv[])
172{
173        struct foo_t *tree = NULL;
174        struct foo_t a = { { NULL, NULL }, "a","apple" };
175        struct foo_t b = { { NULL, NULL }, "b","bear" };
176        struct foo_t q = { { NULL, NULL }, "a", NULL };
177        struct foo_t *node;
178
179        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&a);
180        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
181        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&b);
182        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
183        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
184        printf("%s is for %s\n",q.key,tree->value);
185        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
186        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
187        printf("%s is for %s\n",q.key,tree->value);
188        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
189        q.key="b";
190        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
191        printf("%s is for %s\n",q.key,tree->value);
192        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
193        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
194        printf("%s is for %s\n",q.key,tree->value);
195        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
196
197        return 0;
198}
199
200#endif
Note: See TracBrowser for help on using the repository browser.