source: tools/tracereport/tree.c @ 49ce177

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

Added:

  • error reports
  • flow reports
  • per port reports
  • direction report
  • moved everything to use the container library
  • Property mode set to 100644
File size: 3.4 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        struct tree_t *up;
12};
13
14
15void tree_insert(struct tree_t **tree,void *key,keycmp_t cmp,void *value)
16{
17        int cmpret;
18        if (*tree == NULL) {
19                *tree=malloc(sizeof(struct tree_t));
20                (*tree)->key=key;
21                (*tree)->value=value;
22                (*tree)->left=NULL;
23                (*tree)->right=NULL;
24                return;
25        }
26        cmpret=cmp(key,(*tree)->key);
27        if (cmpret<0) {
28                tree_insert(&(*tree)->left,key,cmp,value);
29        } else {
30                tree_insert(&(*tree)->right,key,cmp,value);
31        }
32        return;
33}
34
35void *tree_replace(struct tree_t **tree,void *key,keycmp_t cmp,void *value)
36{
37        int cmpret;
38        if (*tree == NULL) {
39                *tree=malloc(sizeof(struct tree_t));
40                (*tree)->key=key;
41                (*tree)->value=value;
42                (*tree)->left=NULL;
43                (*tree)->right=NULL;
44                return NULL;
45        }
46        cmpret=cmp(key,(*tree)->key);
47        if (cmpret==0) {
48                void *v = (*tree)->value;
49                (*tree)->value=value;
50                return v;
51        }
52        else if (cmpret<0) {
53                return tree_replace(&(*tree)->left,key,cmp,value);
54        } else {
55                return tree_replace(&(*tree)->right,key,cmp,value);
56        }
57}
58
59void *tree_find(tree_t **tree,void *key,keycmp_t keycmp)
60{
61        int cmpret;
62        if (*tree == NULL) {
63                return NULL;
64        }
65        cmpret=keycmp(key,(*tree)->key);
66        if (cmpret==0) {
67                return (*tree)->value;
68        } else if (cmpret<0) {
69                return tree_find(&(*tree)->left,key,keycmp);
70        }
71        else
72                return tree_find(&(*tree)->right,key,keycmp);
73}
74
75void *tree_delete(tree_t **tree,void *key,keycmp_t keycmp)
76{
77        int cmpret;
78        if (*tree == NULL) {
79                printf("not found\n");
80                return NULL;
81        }
82        cmpret=keycmp(key,(*tree)->key);
83        if (cmpret==0) {
84                void *v=(*tree)->value;
85                tree_t *node_a = (*tree);
86                tree_t *node_b = (*tree)->left;
87                tree_t *node_c = (*tree)->right;
88                tree_t **node_d;
89                tree_t *node_f;
90                if (!node_c) {
91                        (*tree)=node_a->left;
92                        free(node_a);
93                        return v;
94                }
95                for(node_d=&((*tree)->right); (*node_d)->left;
96                                node_d=&((*node_d)->left))
97                        ;
98                node_f=(*node_d)->right;
99                (*tree)=*node_d;
100                (*node_d)->left=node_b;
101                if (*node_d != node_c)
102                        (*node_d)->right=node_c;
103                else
104                        (*node_d)->right=NULL;
105                (*node_d)=node_f;
106                free(node_a);
107                return v;
108        } else if (cmpret<0) {
109                return tree_delete(&(*tree)->left,key,keycmp);
110        }
111        else
112                return tree_delete(&(*tree)->right,key,keycmp);
113}
114
115void tree_inorder(tree_t **tree,visitor_t visitor,void *data)
116{
117        if (*tree) {
118                tree_inorder(&(*tree)->left,visitor,data);
119                visitor((*tree)->key,(*tree)->value,data);
120                tree_inorder(&(*tree)->right,visitor,data);
121        }
122}
123
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#ifdef TEST
142
143int main(int argc, char *argv[])
144{
145        tree_t *tree = NULL;
146        tree_insert(&tree,"fish",(keycmp_t)strcmp,"moo");
147        dump_tree(tree,0); printf("\n");
148        tree_insert(&tree,"cows",(keycmp_t)strcmp,"blubb lubb");
149        dump_tree(tree,0); printf("\n");
150        tree_replace(&tree,"cows",(keycmp_t)strcmp,"blubb blubb");
151        dump_tree(tree,0); printf("\n");
152        tree_insert(&tree,"mosquito",(keycmp_t)strcmp,"zzip!");
153        tree_insert(&tree,"narf",(keycmp_t)strcmp,"nargle");
154        tree_insert(&tree,"ghish",(keycmp_t)strcmp,"ghoo");
155        dump_tree(tree,0); printf("\n");
156        tree_delete(&tree,"mosquito",(keycmp_t)strcmp);
157        dump_tree(tree,0); printf("\n");
158        return 0;
159}
160#endif
Note: See TracBrowser for help on using the repository browser.