source: tools/tracereport/contain.c @ 3c81b4e

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

Fix bug in container while inserting elements into the tree

  • Property mode set to 100644
File size: 4.2 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
8splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) {
9        splay N, *l, *r, *y;
10
11        if (tree == NULL) {
12                return NULL;
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                node->left = NULL;
98                node->right = NULL;
99                return tree;
100        }
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;
110        } else {
111                /* Replace the root node with the current node */
112                node->left = tree->left;
113                node->right = tree->right;
114                free(tree);
115                tree=node;
116        }
117
118        return tree;
119}
120
121void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata)
122{
123        if (!tree) return;
124        if (pre) pre(tree,userdata);
125        splay_visit(tree->left,pre,inorder,post,userdata);
126        if (inorder) inorder(tree,userdata);
127        splay_visit(tree->right,pre,inorder,post,userdata);
128        if (post) post(tree,userdata);
129}
130
131
132#ifdef TEST
133#include <string.h>
134struct foo_t {
135        splay tree;
136        char *key;
137        char *value;
138};
139
140
141void visitor_pre(const struct foo_t *a)
142{
143        printf("{\n");
144}
145void visitor_inorder(const struct foo_t *a)
146{
147        printf("%s: %s\n",a->key,a->value);
148}
149void visitor_post(const struct foo_t *a)
150{
151        printf("}\n");
152}
153
154int cmp(const struct foo_t *a,const struct foo_t *b)
155{
156        int ret= strcmp(a->key,b->key);
157        printf("cmp(%s,%s)==%i\n",a->key,b->key,ret);
158        return ret;
159}
160
161int main(int argc, char *argv[])
162{
163        struct foo_t *tree = NULL;
164        struct foo_t a = { { NULL, NULL }, "a","apple" };
165        struct foo_t b = { { NULL, NULL }, "b","bear" };
166        struct foo_t q = { { NULL, NULL }, "a", NULL };
167        struct foo_t *node;
168
169        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&a);
170        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
171        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&b);
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        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        q.key="b";
180        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
181        printf("%s is for %s\n",q.key,tree->value);
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
187        return 0;
188}
189
190#endif
Note: See TracBrowser for help on using the repository browser.