source: tools/tracereport/contain.c

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivendag_formatrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file was ee6e802, checked in by Shane Alcock <salcock@…>, 5 years ago

Updated copyright blurb on all source files

In some cases, this meant adding copyright blurbs to files that
had never had them before.

  • Property mode set to 100644
File size: 5.3 KB
RevLine 
[ee6e802]1/*
2 *
3 * Copyright (c) 2007-2016 The University of Waikato, Hamilton, New Zealand.
4 * All rights reserved.
5 *
6 * This file is part of libtrace.
7 *
8 * This code has been developed by the University of Waikato WAND
9 * research group. For further information please see http://www.wand.net.nz/
10 *
11 * libtrace is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU Lesser General Public License as published by
13 * the Free Software Foundation; either version 3 of the License, or
14 * (at your option) any later version.
15 *
16 * libtrace is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19 * GNU Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public License
22 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
23 *
24 *
25 */
26
27
[d320b63]28/* Updated: 2006-04-07 to deal with duplicate inserts */
[49ce177]29#include <stdio.h>
[e3b0188]30#include <inttypes.h>
31#include <lt_inttypes.h>
[49ce177]32#include <stdlib.h>
33#include "contain.h"
[e9ee974]34#include <assert.h>
35
36/* a -> b */
37#define implies(a,b) (!(a) || (b))
38
[a8f2692]39static void assert_tree(splay *tree, splay_cmp_t cmp)
[e9ee974]40{
41#ifndef NDEBUG
42        if (!tree)
43                return;
44
45        assert(implies(tree->left,cmp(tree->left,tree)<0));
46        assert(implies(tree->right,cmp(tree,tree->right)<0));
47        assert(implies(tree->left && tree->right,
48                                cmp(tree->left,tree->right)<0));
49
50        assert_tree(tree->left,cmp);
51        assert_tree(tree->right,cmp);
52#endif
53}
54
55#undef implies
[49ce177]56
57splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node) {
58
[d320b63]59        if (tree == NULL) {
60                return NULL;
[49ce177]61        }
62
[e9ee974]63        assert_tree(tree,cmp);
[49ce177]64
65        for (;;) {
66                int cmpres = cmp(node,tree);
[e9ee974]67
[49ce177]68                if (cmpres<0) {
[e9ee974]69                        splay *y;
[49ce177]70                        if (tree->left == NULL)
71                                break;
[e9ee974]72                        /* Rotate Right */
73                        y = tree->left;
74                        tree->left=y->right;
75                        y->right=tree;
76                        tree=y;
77                        /* Not found? */
78                        if (cmp(node,tree)>0) {
79                                break;
[49ce177]80                        }
81                } else if (cmpres>0) {
[e9ee974]82                        splay *y;
[49ce177]83                        if (tree->right == NULL)
84                                break;
[e9ee974]85                        /* Rotate Left */
86                        y = tree->right;
87                        tree->right=y->left;
88                        y->left=tree;
89                        tree=y;
90                        /* Not found? */
91                        if (cmp(node,tree)<0) {
92                                break;
[49ce177]93                        }
94                } else {
[e9ee974]95                        /* Found it */
[49ce177]96                        break;
97                }
98        }
[e9ee974]99
100        assert_tree(tree,cmp);
101
[49ce177]102        return tree;
103}
104
105splay *splay_delete(splay *tree, splay_cmp_t cmp, splay *node) {
106        splay *s;
107
108        if (!tree)
109                return 0;
110
111        tree = splay_search_tree(tree, cmp, node);
112        if (cmp(tree,node)==0) {
113                if (tree->left == NULL) {
114                        s = tree->right;
115                } else {
116                        s = splay_search_tree(tree->left, cmp, node);
117                        s->right = tree->right;
118                }
119                free(tree);
120                return s;
121        }
122        return tree;
123}
124
125void splay_purge(splay *tree) {
126
127        if (!tree)
128                return;
129
130        if (tree->left)
131                splay_purge(tree->left);
132        if (tree->right)
133                splay_purge(tree->right);
134        free(tree);
135}
136       
137splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node) 
138{
[e9ee974]139        int cmpres;
140        assert_tree(tree,cmp);
[49ce177]141        if (tree == NULL) {
142                tree = node;
[d320b63]143                node->left = NULL;
144                node->right = NULL;
[e9ee974]145                assert_tree(tree,cmp);
[49ce177]146                return tree;
147        }
[e9ee974]148        assert_tree(tree,cmp);
149        cmpres=cmp(node,tree);
150        if (cmpres<0) {
151                tree=splay_insert(tree->left,cmp,node);
152        } else if (cmpres>0) {
153                tree=splay_insert(tree->right,cmp,node);
[49ce177]154        } else {
[d320b63]155                /* Replace the root node with the current node */
156                node->left = tree->left;
157                node->right = tree->right;
158                free(tree);
159                tree=node;
[49ce177]160        }
161
[e9ee974]162        assert_tree(tree,cmp);
[d320b63]163        return tree;
[49ce177]164}
165
166void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata)
167{
168        if (!tree) return;
169        if (pre) pre(tree,userdata);
170        splay_visit(tree->left,pre,inorder,post,userdata);
171        if (inorder) inorder(tree,userdata);
172        splay_visit(tree->right,pre,inorder,post,userdata);
173        if (post) post(tree,userdata);
174}
175
176
177#ifdef TEST
178#include <string.h>
179struct foo_t {
180        splay tree;
181        char *key;
182        char *value;
183};
184
185
186void visitor_inorder(const struct foo_t *a)
187{
188        printf("%s: %s\n",a->key,a->value);
189}
190
191int cmp(const struct foo_t *a,const struct foo_t *b)
192{
193        int ret= strcmp(a->key,b->key);
194        printf("cmp(%s,%s)==%i\n",a->key,b->key,ret);
195        return ret;
196}
197
198int main(int argc, char *argv[])
199{
200        struct foo_t *tree = NULL;
201        struct foo_t a = { { NULL, NULL }, "a","apple" };
202        struct foo_t b = { { NULL, NULL }, "b","bear" };
203        struct foo_t q = { { NULL, NULL }, "a", NULL };
204        struct foo_t *node;
205
206        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&a);
207        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
208        tree=(struct foo_t *)splay_insert((splay*)tree,(splay_cmp_t)cmp,(splay*)&b);
209        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
210        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
211        printf("%s is for %s\n",q.key,tree->value);
212        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
213        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
214        printf("%s is for %s\n",q.key,tree->value);
215        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
216        q.key="b";
217        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
218        printf("%s is for %s\n",q.key,tree->value);
219        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
220        tree=(struct foo_t*)splay_search_tree((splay*)tree,(splay_cmp_t)cmp,(splay *)&q);
221        printf("%s is for %s\n",q.key,tree->value);
222        splay_dump((splay*)tree,visitor_pre,visitor_inorder,visitor_post);
223
224        return 0;
225}
226
227#endif
Note: See TracBrowser for help on using the repository browser.