source: tools/tracereport/contain.h @ 41816bf

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

Update to support libtrace3, also fix (minor) warnings where possible!

  • Property mode set to 100644
File size: 4.8 KB
Line 
1#ifndef _CONTAIN_
2#define _CONTAIN_
3/* Containers */
4
5/* Splay tree backed associative map
6 *
7 * This works by cheating at inheritance in C.  Create the structure you
8 * care about and put the *first* member as being a "splay".  For instance:
9 *
10 * typedef struct {
11 *   splay node;
12 *   char *left;
13 *   char *right;
14 * } foo_t;
15 *
16 * Create the map with:
17 *  foo_t *foomap=NULL;
18 *
19 * You will also need a comparitor.
20 *  int foomapcmp(const foo_t *a, const foo_t *b)
21 *  {
22 *      return strcmp(a->key,b->key);
23 *  }
24 *
25 * Then to insert something into the map:
26 *  foo_t node;
27 *  node.key="a";
28 *  node.value="apple";
29 *  foomap=(foo_t *)splay_insert(
30 *      (splay*)foomap,
31 *      (splay_cmp_t)foomapcmp,
32 *      (splay*)node
33 *      );
34 *
35 * To search for something:
36 *  struct foo_t node;
37 *  node.key="a";
38 *  foomap=(foo_t *)splay_find((splay*)foomap,
39 *      (splay_cmp_t)foomapcmp,
40 *      (splay*)node
41 *      );
42 *  printf("%s is for %s\n",foomap->key,foomap->value);
43 *
44 * Note the annoyingly copious amount of casts, and the fact that the return
45 * from splay_find is the top of the tree, and the result.
46 */
47
48typedef struct splay_node {
49        struct splay_node *left;
50        struct splay_node *right;
51} splay;
52
53typedef int (*splay_cmp_t)(const struct splay_node *, const struct splay_node *); 
54typedef void (*visitor_t)(const splay *tree,void *userdata);
55
56splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node);
57splay *splay_delete(splay *tree, splay_cmp_t cmp, splay *node);
58void   splay_purge(splay *tree);
59splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node);
60void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata);
61
62/*
63 * Macros to wrap the splay tree to make it work a bit more like you expect.
64 *
65 * Map:
66 * MAP_CREATE(alphabet,char *,strcmp,char *)
67 * MAP_INSERT(alphabet,"a","apple")
68 * printf("a is for %s",MAP_FIND(alphabet,"a")->value);
69 *
70 * Set:
71 * SET_CREATE(afewofmyfavouritethings,char *,strcmp)
72 * SET_INSERT(afewofmyfavouritethings,"raindrops on roses");
73 * SET_INSERT(afewofmyfavouritethings,"whiskers on kittens");
74 * if (SET_CONTAINS(afewofmyfaovuritethings,"whiskers on kittens")) {
75 *   printf("I like whiskers on kittens\n");
76 * } else {
77 *   printf("Whiskers on kittens suck\n");
78 * }
79 *
80 */
81
82#define MAP_NODE(keytype,valuetype)                                     \
83                struct {                                                \
84                        splay _map_node;                                \
85                        keytype key;                                    \
86                        valuetype value;                                \
87                }
88
89#define MAP(keytype,valuetype)                                          \
90        struct {                                                        \
91                MAP_NODE(keytype,valuetype) *node;                      \
92                splay_cmp_t cmp;                                        \
93        }
94
95#define MAP_INIT(cmp)                                                   \
96        { NULL, (splay_cmp_t)cmp }                                     
97
98#define CMP(name,keytype,exp)                                           \
99        int name(splay *_map_a, splay *_map_b) {                        \
100                struct _map_t {                                         \
101                        splay _map_node;                                \
102                        keytype key;                                    \
103                };                                                      \
104                keytype a = ((struct _map_t*)_map_a)->key;              \
105                keytype b = ((struct _map_t*)_map_b)->key;              \
106                return (exp);                                           \
107        }
108               
109               
110
111#define MAP_INSERT(name,vkey,vvalue)                                    \
112        do {                                                            \
113                typeof((name).node) _node=                              \
114                                malloc(sizeof(typeof(*(name).node)));   \
115                *_node = (typeof(*(name).node)){{0,0},vkey,vvalue};     \
116                (name).node=(typeof((name).node))splay_insert(          \
117                                        (splay *)(name).node,           \
118                                        (name).cmp,                     \
119                                        (splay *)_node                  \
120                                        );                              \
121        } while(0);
122
123#define MAP_FIND(name,vkey)                                             \
124        ({                                                              \
125                typeof(*(name).node) _node;                             \
126                typeof((name).node) _ret;                               \
127                _node.key=vkey;                                         \
128                (name).node=(typeof((name).node))splay_search_tree(     \
129                                        (splay *)(name).node,           \
130                                        (name).cmp,                     \
131                                        (splay *)&_node                 \
132                                        );                              \
133                if ((name).node                                         \
134                    && (name).cmp((splay*)(name).node,(splay*)&_node)==0)\
135                        _ret=(name).node;                               \
136                else                                                    \
137                        _ret=NULL;                                      \
138                _ret;                                                   \
139         })
140
141#define MAP_VISITOR(name,keytype,valuetype)                             \
142        void name(MAP_NODE(keytype,valuetype) *node,void *userdata)
143
144#define MAP_VISIT(name,pre,inorder,post,userdata)                       \
145        splay_visit((splay*)(name).node,                                \
146                        (visitor_t)pre,                                 \
147                        (visitor_t)inorder,                             \
148                        (visitor_t)post,                                \
149                        userdata)
150
151/* Sets ****************************************************************/
152#define SET_CREATE(name,keytype,cmp) \
153        typedef struct { \
154                splay node;                                             \
155                keytype key;                                            \
156        } name ## _t;                                                   \
157        name ## _t *name = NULL;                                        \
158        int name ## _cmp(const splay *a,const splay *b) {               \
159                return cmp(((name ## _t*)a)->key,((name ## _t *)b)->key); \
160        }
161
162#define SET_INSERT(name,vkey) \
163        do {                            \
164                name ## _t *_node=malloc(sizeof(name ## _t)); \
165                _node->key=vkey;                \
166                name=(name ##_t*)splay_insert((splay *)name,            \
167                                        (splay_cmp_t)name ## _cmp,      \
168                                        (splay *)_node                  \
169                                        );                              \
170        } while(0);
171
172#define SET_CONTAINS(name,vkey) \
173        ({                                                              \
174                name ## _t _node;                                       \
175                _node.key=vkey;                                         \
176                name=(name ##_t*)splay_search_tree(                     \
177                                        (splay *)name,                  \
178                                        (splay_cmp_t)name ## _cmp,      \
179                                        (splay *)&_node                 \
180                                        );                              \
181                (name) && name ## _cmp((splay*)(name),(splay *)&_node)==0;\
182         })
183
184#endif /* _CONTAIN_ */
Note: See TracBrowser for help on using the repository browser.