source: tools/tracereport/contain.h @ 47d4f8c

4.0.1-hotfixescachetimestampsdevelopdpdk-ndagetsilivendag_formatrc-4.0.1rc-4.0.2rc-4.0.3rc-4.0.4ringdecrementfixringperformanceringtimestampfixes
Last change on this file since 47d4f8c was ee6e802, checked in by Shane Alcock <salcock@…>, 6 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.8 KB
Line 
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
28#ifndef _CONTAIN_
29#define _CONTAIN_
30/* Containers */
31
32/* Splay tree backed associative map
33 *
34 * This works by cheating at inheritance in C.  Create the structure you
35 * care about and put the *first* member as being a "splay".  For instance:
36 *
37 * typedef struct {
38 *   splay node;
39 *   char *left;
40 *   char *right;
41 * } foo_t;
42 *
43 * Create the map with:
44 *  foo_t *foomap=NULL;
45 *
46 * You will also need a comparitor.
47 *  int foomapcmp(const foo_t *a, const foo_t *b)
48 *  {
49 *      return strcmp(a->key,b->key);
50 *  }
51 *
52 * Then to insert something into the map:
53 *  foo_t node;
54 *  node.key="a";
55 *  node.value="apple";
56 *  foomap=(foo_t *)splay_insert(
57 *      (splay*)foomap,
58 *      (splay_cmp_t)foomapcmp,
59 *      (splay*)node
60 *      );
61 *
62 * To search for something:
63 *  struct foo_t node;
64 *  node.key="a";
65 *  foomap=(foo_t *)splay_find((splay*)foomap,
66 *      (splay_cmp_t)foomapcmp,
67 *      (splay*)node
68 *      );
69 *  printf("%s is for %s\n",foomap->key,foomap->value);
70 *
71 * Note the annoyingly copious amount of casts, and the fact that the return
72 * from splay_find is the top of the tree, and the result.
73 */
74
75typedef struct splay_node {
76        struct splay_node *left;
77        struct splay_node *right;
78} splay;
79
80typedef int (*splay_cmp_t)(const struct splay_node *, const struct splay_node *); 
81typedef void (*visitor_t)(const splay *tree,void *userdata);
82
83splay *splay_search_tree(splay *tree, splay_cmp_t cmp, splay *node);
84splay *splay_delete(splay *tree, splay_cmp_t cmp, splay *node);
85void   splay_purge(splay *tree);
86splay *splay_insert(splay *tree, splay_cmp_t cmp, splay *node);
87void splay_visit(const splay *tree, visitor_t pre,visitor_t inorder,visitor_t post,void *userdata);
88
89/*
90 * Macros to wrap the splay tree to make it work a bit more like you expect.
91 *
92 * Map:
93 * MAP_CREATE(alphabet,char *,strcmp,char *)
94 * MAP_INSERT(alphabet,"a","apple")
95 * printf("a is for %s",MAP_FIND(alphabet,"a")->value);
96 *
97 * Set:
98 * SET_CREATE(afewofmyfavouritethings,char *,strcmp)
99 * SET_INSERT(afewofmyfavouritethings,"raindrops on roses");
100 * SET_INSERT(afewofmyfavouritethings,"whiskers on kittens");
101 * if (SET_CONTAINS(afewofmyfaovuritethings,"whiskers on kittens")) {
102 *   printf("I like whiskers on kittens\n");
103 * } else {
104 *   printf("Whiskers on kittens suck\n");
105 * }
106 *
107 */
108
109#define MAP_NODE(keytype,valuetype)                                     \
110                struct {                                                \
111                        splay _map_node;                                \
112                        keytype key;                                    \
113                        valuetype value;                                \
114                }
115
116#define MAP(keytype,valuetype)                                          \
117        struct {                                                        \
118                MAP_NODE(keytype,valuetype) *node;                      \
119                splay_cmp_t cmp;                                        \
120        }
121
122#define MAP_INIT(cmp)                                                   \
123        { NULL, (splay_cmp_t)cmp }                                     
124
125#define CMP(name,keytype,exp)                                           \
126        int name(splay *_map_a, splay *_map_b) {                        \
127                struct _map_t {                                         \
128                        splay _map_node;                                \
129                        keytype key;                                    \
130                };                                                      \
131                keytype a = ((struct _map_t*)_map_a)->key;              \
132                keytype b = ((struct _map_t*)_map_b)->key;              \
133                return (exp);                                           \
134        }
135               
136               
137
138#define MAP_INSERT(name,vkey,vvalue)                                    \
139        do {                                                            \
140                typeof((name).node) _node=                              \
141                                malloc(sizeof(typeof(*(name).node)));   \
142                *_node = (typeof(*(name).node)){{0,0},vkey,vvalue};     \
143                (name).node=(typeof((name).node))splay_insert(          \
144                                        (splay *)(name).node,           \
145                                        (name).cmp,                     \
146                                        (splay *)_node                  \
147                                        );                              \
148        } while(0);
149
150#define MAP_FIND(name,vkey)                                             \
151        ({                                                              \
152                typeof(*(name).node) _node;                             \
153                typeof((name).node) _ret;                               \
154                _node.key=vkey;                                         \
155                (name).node=(typeof((name).node))splay_search_tree(     \
156                                        (splay *)(name).node,           \
157                                        (name).cmp,                     \
158                                        (splay *)&_node                 \
159                                        );                              \
160                if ((name).node                                         \
161                    && (name).cmp((splay*)(name).node,(splay*)&_node)==0)\
162                        _ret=(name).node;                               \
163                else                                                    \
164                        _ret=NULL;                                      \
165                _ret;                                                   \
166         })
167
168#define MAP_VISITOR(name,keytype,valuetype)                             \
169        void name(MAP_NODE(keytype,valuetype) *node,void *userdata)
170
171#define MAP_VISIT(name,pre,inorder,post,userdata)                       \
172        splay_visit((splay*)(name).node,                                \
173                        (visitor_t)pre,                                 \
174                        (visitor_t)inorder,                             \
175                        (visitor_t)post,                                \
176                        userdata)
177
178/* Sets ****************************************************************/
179#define SET_CREATE(name,keytype,cmp) \
180        typedef struct { \
181                splay node;                                             \
182                keytype key;                                            \
183        } name ## _t;                                                   \
184        name ## _t *name = NULL;                                        \
185        int name ## _cmp(const splay *a,const splay *b) {               \
186                return cmp(((name ## _t*)a)->key,((name ## _t *)b)->key); \
187        }
188
189#define SET_INSERT(name,vkey) \
190        do {                            \
191                name ## _t *_node=malloc(sizeof(name ## _t)); \
192                _node->key=vkey;                \
193                name=(name ##_t*)splay_insert((splay *)name,            \
194                                        (splay_cmp_t)name ## _cmp,      \
195                                        (splay *)_node                  \
196                                        );                              \
197        } while(0);
198
199#define SET_CONTAINS(name,vkey) \
200        ({                                                              \
201                name ## _t _node;                                       \
202                _node.key=vkey;                                         \
203                name=(name ##_t*)splay_search_tree(                     \
204                                        (splay *)name,                  \
205                                        (splay_cmp_t)name ## _cmp,      \
206                                        (splay *)&_node                 \
207                                        );                              \
208                (name) && name ## _cmp((splay*)(name),(splay *)&_node)==0;\
209         })
210
211#endif /* _CONTAIN_ */
Note: See TracBrowser for help on using the repository browser.