Store the frame_data structures in a tree, rather than a linked list.
[obnox/wireshark/wip.git] / cfile.c
1 /* cfile.c
2  * capture_file GUI-independent manipulation
3  * Vassilii Khachaturov <vassilii@tarunz.org>
4  *
5  * $Id$
6  *
7  * Wireshark - Network traffic analyzer
8  * By Gerald Combs <gerald@wireshark.org>
9  * Copyright 1998 Gerald Combs
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program 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 General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software
23  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
24  */
25
26 #ifdef HAVE_CONFIG_H
27 # include "config.h"
28 #endif
29
30 #include <glib.h>
31
32 #include <epan/packet.h>
33
34 #include "cfile.h"
35
36 void
37 cap_file_init(capture_file *cf)
38 {
39   /* Initialize the capture file struct */
40   cf->ptree_root     = NULL;
41   cf->wth            = NULL;
42   cf->filename       = NULL;
43   cf->source         = NULL;
44   cf->user_saved     = FALSE;
45   cf->is_tempfile    = FALSE;
46   cf->rfcode         = NULL;
47   cf->dfilter        = NULL;
48   cf->has_snap       = FALSE;
49   cf->snap           = WTAP_MAX_PACKET_SIZE;
50   cf->count          = 0;
51   cf->redissecting   = FALSE;
52 }
53
54 /*
55  * For a given frame number, calculate the indices into a level 3
56  * node, a level 2 node, a level 1 node, and a leaf node.
57  */
58 #define LEVEL_3_INDEX(framenum) \
59         ((framenum) >> (3*LOG2_NODES_PER_LEVEL))
60 #define LEVEL_2_INDEX(framenum) \
61         (((framenum) >> (2*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
62 #define LEVEL_1_INDEX(framenum) \
63         (((framenum) >> (1*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
64 #define LEAF_INDEX(framenum) \
65         (((framenum) >> (0*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1))
66
67 /*
68  * Add a new frame_data structure to the capture_file's collection.
69  */
70 frame_data *
71 cap_file_add_fdata(capture_file *cf, frame_data *fdata)
72 {
73   frame_data *leaf;
74   frame_data **level1;
75   frame_data ***level2;
76   frame_data ****level3;
77   frame_data *node;
78
79   /*
80    * The current value of cf->count is the index value for the new frame,
81    * because the index value for a frame is the frame number - 1, and
82    * if we currently have cf->count frames, the the frame number of
83    * the last frame in the collection is cf->count, so its index value
84    * is cf->count - 1.
85    */
86   if (cf->count == 0) {
87     /* The tree is empty; allocate the first leaf node, which will be
88        the root node. */
89     leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
90     node = &leaf[0];
91     cf->ptree_root = leaf;
92   } else if (cf->count < NODES_PER_LEVEL) {
93     /* It's a 1-level tree, and is going to stay that way for now. */
94     leaf = cf->ptree_root;
95     node = &leaf[cf->count];
96   } else if (cf->count == NODES_PER_LEVEL) {
97     /* It's a 1-level tree that will turn into a 2-level tree. */
98     level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
99     memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
100     level1[0] = cf->ptree_root;
101     leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
102     level1[1] = leaf;
103     node = &leaf[0];
104     cf->ptree_root = level1;
105   } else if (cf->count < NODES_PER_LEVEL*NODES_PER_LEVEL) {
106     /* It's a 2-level tree, and is going to stay that way for now. */
107     level1 = cf->ptree_root;
108     leaf = level1[cf->count >> LOG2_NODES_PER_LEVEL];
109     if (leaf == NULL) {
110       leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
111       level1[cf->count >> LOG2_NODES_PER_LEVEL] = leaf;
112     }
113     node = &leaf[LEAF_INDEX(cf->count)];
114   } else if (cf->count == NODES_PER_LEVEL*NODES_PER_LEVEL) {
115     /* It's a 2-level tree that will turn into a 3-level tree */
116     level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
117     memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
118     level2[0] = cf->ptree_root;
119     level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
120     memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
121     level2[1] = level1;
122     leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
123     level1[0] = leaf;
124     node = &leaf[0];
125     cf->ptree_root = level2;
126   } else if (cf->count < NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
127     /* It's a 3-level tree, and is going to stay that way for now. */
128     level2 = cf->ptree_root;
129     level1 = level2[cf->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
130     if (level1 == NULL) {
131       level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
132       memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
133       level2[cf->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)] = level1;
134     }
135     leaf = level1[LEVEL_1_INDEX(cf->count)];
136     if (leaf == NULL) {
137       leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
138       level1[LEVEL_1_INDEX(cf->count)] = leaf;
139     }
140     node = &leaf[LEAF_INDEX(cf->count)];
141   } else if (cf->count == NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
142     /* It's a 3-level tree that will turn into a 4-level tree */
143     level3 = g_malloc((sizeof *level3)*NODES_PER_LEVEL);
144     memset(level3, 0, (sizeof *level3)*NODES_PER_LEVEL);
145     level3[0] = cf->ptree_root;
146     level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
147     memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
148     level3[1] = level2;
149     level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
150     memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
151     level2[0] = level1;
152     leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
153     level1[0] = leaf;
154     node = &leaf[0];
155     cf->ptree_root = level3;
156   } else {
157     /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4
158        2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
159        so cf->count is always less < NODES_PER_LEVEL^4.
160
161        XXX - we should fail if cf->count is 2^31-1, or should
162        make the frame numbers 64-bit and just let users run
163        themselves out of address space or swap space. :-) */
164     /* It's a 4-level tree, and is going to stay that way forever. */
165     level3 = cf->ptree_root;
166     level2 = level3[LEVEL_3_INDEX(cf->count)];
167     if (level2 == NULL) {
168       level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL);
169       memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL);
170       level3[LEVEL_3_INDEX(cf->count)] = level2;
171     }
172     level1 = level2[LEVEL_2_INDEX(cf->count)];
173     if (level1 == NULL) {
174       level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL);
175       memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL);
176       level2[LEVEL_2_INDEX(cf->count)] = level1;
177     }
178     leaf = level1[LEVEL_1_INDEX(cf->count)];
179     if (leaf == NULL) {
180       leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL);
181       level1[LEVEL_1_INDEX(cf->count)] = leaf;
182     }
183     node = &leaf[LEAF_INDEX(cf->count)];
184   }
185   *node = *fdata;
186   cf->count++;
187   return node;
188 }
189
190 /*
191  * Find the frame_data for the specified frame number.
192  */
193 frame_data *
194 cap_file_find_fdata(capture_file *cf, guint32 num)
195 {
196   frame_data *leaf;
197   frame_data **level1;
198   frame_data ***level2;
199   frame_data ****level3;
200
201   if (num == 0) {
202     /* There is no frame number 0 */
203     return NULL;
204   }
205
206   /* Convert it into an index number. */
207   num--;
208   if (num >= cf->count) {
209     /* There aren't that many frames. */
210     return NULL;
211   }
212
213   if (cf->count <= NODES_PER_LEVEL) {
214     /* It's a 1-level tree. */
215     leaf = cf->ptree_root;
216     return &leaf[num];
217   }
218   if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
219     /* It's a 2-level tree. */
220     level1 = cf->ptree_root;
221     leaf = level1[num >> LOG2_NODES_PER_LEVEL];
222     return &leaf[LEAF_INDEX(num)];
223   }
224   if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
225     /* It's a 3-level tree. */
226     level2 = cf->ptree_root;
227     level1 = level2[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
228     leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
229     return &leaf[LEAF_INDEX(num)];
230   }
231   /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4
232      2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
233      so cf->count is always less < NODES_PER_LEVEL^4. */
234   /* It's a 4-level tree, and is going to stay that way forever. */
235   level3 = cf->ptree_root;
236   level2 = level3[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)];
237   level1 = level2[(num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)];
238   leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)];
239   return &leaf[LEAF_INDEX(num)];
240 }
241
242 /*
243  * Free up all the frame information for a capture file.
244  */
245 void
246 cap_file_free_frames(capture_file *cf)
247 {
248   frame_data **level1;
249   frame_data ***level2;
250   frame_data ****level3;
251   guint i, j, k;
252
253   if (cf->count == 0) {
254     /* Nothing to free. */
255     return;
256   }
257   if (cf->count <= NODES_PER_LEVEL) {
258     /* It's a 1-level tree. */
259     g_free(cf->ptree_root);
260   } else if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) {
261     /* It's a 2-level tree. */
262     level1 = cf->ptree_root;
263     for (i = 0; i < NODES_PER_LEVEL && level1[i] != NULL; i++)
264       g_free(level1[i]);
265     g_free(level1);
266   } else if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) {
267     /* It's a 3-level tree. */
268     level2 = cf->ptree_root;
269     for (i = 0; i < NODES_PER_LEVEL && level2[i] != NULL; i++) {
270       level1 = level2[i];
271       for (j = 0; j < NODES_PER_LEVEL && level1[i] != NULL; j++)
272         g_free(level1[j]);
273       g_free(level1);
274     }
275     g_free(level2);
276     return;
277   } else {
278     /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4
279        2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10,
280        so cf->count is always less < NODES_PER_LEVEL^4. */
281     /* It's a 4-level tree, and is going to stay that way forever. */
282     level3 = cf->ptree_root;
283     for (i = 0; i < NODES_PER_LEVEL && level3[i] != NULL; i++) {
284       level2 = level3[i];
285       for (j = 0; j < NODES_PER_LEVEL && level2[i] != NULL; j++) {
286         level1 = level2[j];
287         for (k = 0; k < NODES_PER_LEVEL && level1[k] != NULL; k++)
288           g_free(level1[k]);
289       }
290       g_free(level2);
291     }
292     g_free(level3);
293   }
294   cf->ptree_root = NULL;
295   cf->count = 0;
296 }