source: tools/tracereport/tree.c @ d3ff1fb

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

Add trace summary

  • Property mode set to 100644
File size: 3.3 KB
Line 
1#include <stdlib.h>
2#include <stdio.h>
3#include "tree.h"
4
5struct tree_t
6{
7        void *key;
8        void *value;
9        struct tree_t *left;
10        struct tree_t *right;
11};
12
13
14void tree_insert(struct tree_t **tree,void *key,keycmp_t cmp,void *value)
15{
16        int cmpret;
17        if (*tree == NULL) {
18                *tree=malloc(sizeof(struct tree_t));
19                (*tree)->key=key;
20                (*tree)->value=value;
21                (*tree)->left=NULL;
22                (*tree)->right=NULL;
23                return;
24        }
25        cmpret=cmp(key,(*tree)->key);
26        if (cmpret<0) {
27                tree_insert(&(*tree)->left,key,cmp,value);
28        } else {
29                tree_insert(&(*tree)->right,key,cmp,value);
30        }
31        return;
32}
33
34void *tree_replace(struct tree_t **tree,void *key,keycmp_t cmp,void *value)
35{
36        int cmpret;
37        if (*tree == NULL) {
38                *tree=malloc(sizeof(struct tree_t));
39                (*tree)->key=key;
40                (*tree)->value=value;
41                (*tree)->left=NULL;
42                (*tree)->right=NULL;
43                return NULL;
44        }
45        cmpret=cmp(key,(*tree)->key);
46        if (cmpret==0) {
47                void *v = (*tree)->value;
48                (*tree)->value=value;
49                return v;
50        }
51        else if (cmpret<0) {
52                return tree_replace(&(*tree)->left,key,cmp,value);
53        } else {
54                return tree_replace(&(*tree)->right,key,cmp,value);
55        }
56}
57
58void *tree_find(tree_t **tree,void *key,keycmp_t keycmp)
59{
60        int cmpret;
61        if (*tree == NULL) {
62                return NULL;
63        }
64        cmpret=keycmp(key,(*tree)->key);
65        if (cmpret==0) {
66                return (*tree)->value;
67        } else if (cmpret<0) {
68                return tree_find(&(*tree)->left,key,keycmp);
69        }
70        else
71                return tree_find(&(*tree)->right,key,keycmp);
72}
73
74void *tree_delete(tree_t **tree,void *key,keycmp_t keycmp)
75{
76        int cmpret;
77        if (*tree == NULL) {
78                printf("not found\n");
79                return NULL;
80        }
81        cmpret=keycmp(key,(*tree)->key);
82        if (cmpret==0) {
83                void *v=(*tree)->value;
84                tree_t *node_a = (*tree);
85                tree_t *node_b = (*tree)->left;
86                tree_t *node_c = (*tree)->right;
87                tree_t **node_d;
88                tree_t *node_f;
89                if (!node_c) {
90                        (*tree)=node_a->left;
91                        free(node_a);
92                        return v;
93                }
94                for(node_d=&((*tree)->right); (*node_d)->left;
95                                node_d=&((*node_d)->left))
96                        ;
97                node_f=(*node_d)->right;
98                (*tree)=*node_d;
99                (*node_d)->left=node_b;
100                if (*node_d != node_c)
101                        (*node_d)->right=node_c;
102                else
103                        (*node_d)->right=NULL;
104                (*node_d)=node_f;
105                free(node_a);
106                return v;
107        } else if (cmpret<0) {
108                return tree_delete(&(*tree)->left,key,keycmp);
109        }
110        else
111                return tree_delete(&(*tree)->right,key,keycmp);
112}
113
114void tree_inorder(tree_t **tree,visitor_t visitor,void *data)
115{
116        if (*tree) {
117                tree_inorder(&(*tree)->left,visitor,data);
118                visitor((*tree)->key,(*tree)->value,data);
119                tree_inorder(&(*tree)->right,visitor,data);
120        }
121}
122
123#ifdef TEST
124#include <string.h>
125#include <stdio.h>
126
127void dump_tree(tree_t *tree,int level)
128{
129        int i=0;
130        for(i=0;i<level;++i) {
131                printf(" ");
132        }
133        if (!tree) {
134                printf("NULL\n");
135                return;
136        }
137        printf("%s: %s\n",(char*)tree->key,(char*)tree->value);
138        dump_tree(tree->left,level+1);
139        dump_tree(tree->right,level+1);
140}
141
142int main(int argc, char *argv[])
143{
144        tree_t *tree = NULL;
145        tree_insert(&tree,"fish",(keycmp_t)strcmp,"moo");
146        dump_tree(tree,0); printf("\n");
147        tree_insert(&tree,"cows",(keycmp_t)strcmp,"blubb lubb");
148        dump_tree(tree,0); printf("\n");
149        tree_replace(&tree,"cows",(keycmp_t)strcmp,"blubb blubb");
150        dump_tree(tree,0); printf("\n");
151        tree_insert(&tree,"mosquito",(keycmp_t)strcmp,"zzip!");
152        tree_insert(&tree,"narf",(keycmp_t)strcmp,"nargle");
153        tree_insert(&tree,"ghish",(keycmp_t)strcmp,"ghoo");
154        dump_tree(tree,0); printf("\n");
155        tree_delete(&tree,"mosquito",(keycmp_t)strcmp);
156        dump_tree(tree,0); printf("\n");
157        return 0;
158}
159#endif
Note: See TracBrowser for help on using the repository browser.